mos-进程管理

进程

进程的状态

  1. 运行态(占用CPU)
  2. 就绪态(等待调度程序调度)
  3. 阻塞态(等待阻塞原因解决)

进程表

寄存器、程序计数器、程序状态字、堆栈指针、进程状态、优先级、调度参数、进程ID、父进程、进程组、信号、进程开始时间、使用的CPU时间、子进程的CPU时间、下次报警时间

维持顺序进程

  1. 中断产生
  2. 中断硬件将程序计数器、程序状态字、寄存器等压入堆栈
  3. 中断硬件从中断向量处装入新的程序计数器
  4. 汇编语言过程保存寄存器、设置新的堆栈,并删除中断硬件保存的信息
  5. 运行中断处理程序
  6. 调度程序
  7. 汇编语言过程设置寄存器,内存映射,启动被调度的程序

线程

与进程的区别

  1. 同一个进程下面的线程分享同一个地址空间,是一种轻量级进程
  2. 进程拥有一个执行的线程,线程包含程序计数器、寄存器、堆栈
  3. 进程用于把资源集中到一起,线程是在CPU上被调度的实体

服务器的三种模型

  1. 多线程:并行性、阻塞系统调用
  2. 单线程进程:无并行性、阻塞系统调用
  3. 有限状态机:并行性、非阻塞系统调用、中断

多线程的实现

  1. 在用户空间实现:

    线程表保存在用户空间、由运行时系统管理

    优点:不需要操作系统支持、比陷入内核快得多、允许自定义调度算法

    缺点:

    1. 需要实现单个线程进行系统调用而不阻塞进程里的其他线程

      目前的解决方案是使用某个系统调用(例如select)通知预期的系统的系统调用(例如read)是否会阻塞,根据情况判断是否进行该系统调用

    2. 页面故障(页错误)导致内核阻塞整个进程

    3. 缺乏强硬机制挂起某个正在运行而耗光资源线程

  2. 在内核中实现:

    线程表保存在内核中,创建删除均需要系统调用

    优点:阻塞线程的系统调用发生后,调度程序能够作用

    缺点:创建删除线程开销大,目前的解决方案是使用线程池

  3. 混合实现:

    内核调度内核级线程,内核级线程被多个用户级线程多路复用

    调度程序的激活机制(模拟内核线程的功能):

    违反了n层不能调用n+1层的规定

    1. 内核发现某内核级线程阻塞,通知该线程的运行时系统,这个机制称为上行调用
    2. 运行时系统重新调度线程:阻塞当前线程,从就绪表取出另一个线程,设置寄存器后再启动
    3. 内核发现线程可重新运行,又一次上行调用,运行时系统自行处理该信号

进程间通信

互斥实现

  1. 屏蔽中断(单核适用)

  2. 锁变量

  3. 严格轮换法

    临界区外的进程可能阻塞要进入临界区的进程

  4. Peterson算法(忙等待)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #define False 0
    #define True 1
    int turn;
    int interested[2];
    void enter_critical_region(int process){
    int other = 1 - process;
    interested[process] = True;
    turn = process;
    while(turn == process && interested[other] == True);
    }
    void leave_critical_region(int process){
    interested[process] = False;
    }
  5. TSL指令(忙等待)

    TSL RX, LOCK

    当LOCK变量为0,任何进程都能用TSL将其设置为1,并锁住内存总线,读写操作完成后,进程使用MOVE指令将LOCK的值重新设置为0

    1
    2
    3
    4
    5
    6
    7
    8
    enter_critical_region:
    TSL REGISTER, LOCK
    CMP REGISTER, 0
    JNE enter_critical_region
    RET
    leave_critical_region:
    MOVE LOCK, 0
    RET
  6. XCHG指令(忙等待)

    原子性交换指令

    1
    2
    3
    4
    5
    6
    7
    8
    9
    enter_critical_region:
    MOVE REGISTER, 1
    XCHG REGISTER, LOCK
    CMP REGISTER, 0
    JNE enter_critical_region
    RET
    leave_critical_region:
    MOVE LOCK, 0
    RET

信号量

两种作用:互斥、同步

设置变量的两种操作down和up,作为系统调用实现,操作时屏蔽中断,通过TSL或XCHG保证同一时刻只有一个CPU操作信号量(测试或更新信号量或使某进程睡眠时间很短)。

down:进程检查信号量是否大于0,如果大于0,则将其值减1,并且继续运行;否则,因为信号量尚未减1,down操作并未完成,进程睡眠。检查、修改、睡眠均为原子操作

up:信号量加1,由操作系统决定完成一个睡眠进程的down操作,即唤醒该进程,而信号量总体值不变

初始值为1的信号量称作二元信号量,保证同时只有一个进程可以进入临界区,每个进程进入临界区之前执行一个down操作,刚刚退出时执行一个up操作,实现互斥。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#define N 100
typedef int semaphore;//信号量
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;
void producer()
{
int item;
while(1)
{
item = produce_item();
down(&empty);//空槽减1
down(&mutex);//进入临界区
insert_item(item);
up(&mutex);//离开临界区
up(&full);//满槽加1
}
}
void consumer()
{
int item;
while(1)
{
down(&full);//满槽减1
down(&mutex);//进入临界区
item = remove_item();
up(&mutex);//离开临界区
up(&empty);//空槽加1
consumer_item(item);
}
}

信号量mutex用来实现互斥,保证两个进程不会同时读写数据;信号量full和empty用来实现同步,保证某种事件的顺利进行,发生或不发生,这里保证缓冲区满时生成者停止运行(empty)和缓冲区 空时消费者停止运行(full)

互斥量

简化的信号量,是一种加强的二元信号量,必须是同一个进程加锁解锁,通过类似yield的调用主动放弃CPU,避免忙等待,等待线程下次运行时,重新测试锁的状态

管程

一个由过程、变量、数据结构组成的一个集合,进程可以调用管程的过程,但不能在管程之外的过程访问管程的数据结构,并且任一时刻管程中只能有一个活跃进程。

屏障

当一个进程到达屏障时,他就被屏障拦截,直到所有进程都达到该屏障为止

调度

需要调度的情形:

  1. 创建一个新进程之后
  2. 一个进程退出之后
  3. 进程阻塞
  4. 硬件中断

调度算法的目标;

  1. 公平,给每个进程公平的CPU份额
  2. 策略强制执行,保证所宣布的策略执行
  3. 平衡,保持系统的所有部分繁忙
  4. (批处理系统)吞吐量,每小时的最大作业数
  5. (批处理系统)周转时间,从提交到终止间的最小时间
  6. (批处理系统)CPU利用率,保持CPU始终忙碌
  7. (交互系统)响应时间,快速响应请求
  8. (交互系统)均衡性,满足用户期望
  9. (实时系统)满足截止时间,避免丢失数据
  10. (实时系统)可预测性,在多媒体系统中避免品质降低

批处理系统

  1. 先来先服务(非抢占)
  2. 最短作业优先(非抢占)
  3. 最短剩余时间优先(抢占)

交互式系统

  1. 轮转调度

    依赖时间片管理进程运行时间,时间片设置太短会导致过多的进程切换,降低了CPU的效率,设置太长会又可能引起对短的交互请求的响应时间变长

  2. 优先级调度

    为了避免高优先级进程无休止的运行,可以利用最大时间片机制,当进程的时间片用完,下一个次高优先级的进程获得机会运行

    优先级可以静态或动态赋予,IO密集型进程应该赋予较高的优先级,同时运行较短的时间,CPU密集型相反

  3. 多级队列

    设立优先级类,属于最高优先级类的进程运行一个时间片,属于次高级类的进程运行两个时间片,再次一级运行四个时间片,以此类推,当一个进程的时间片用完后,被移到下一类

  4. 最短进程优先

    通过首先运行最短的作业来使响应时间最短,假设某进程的估计运行时间为$$T_0$$ ,下一次测量的运行时间为$$T_1$$,可以用两个值的加权和来改进估计时间,即$$aT_0+(1-a)T_1$$,通过选择$$a$$的值,可以决定是尽快忘掉老的运行时间,还是在一段长的时间内记住他们

  5. 保证调度

    保证每个进程获得的CPU时间相等,系统必须跟踪每个进程自从创建以来的CPU运行时间

  6. 彩票调度

    给进程分发彩票,给更重要的进程分发额外的彩票,CPU调度通过抽奖的方式选择进程,进程之间可以交换彩票

  7. 公平分享调度

    考虑进程的拥有者,给拥有者分配公平的资源份额

实时系统

调度系统的任务就是满足所有进程的截止时间

策略与机制

为了解决主进程对子进程的调度控制问题,将调度机制与调度策略分离,即将调度算法以某种形式参数化,由用户进程填写该参数。调度机制位于内核,调度策略由用户进程决定

线程调度

用户级线程:调度程序决定进程运行顺序,运行时系统决定线程运行顺序,缺少时钟强制挂起运行时间过长的线程

内核级线程:像调度进程一样调度线程,比用户级线程效率低的多,需要完整的上下文切换,修改内存映像,使高速缓存失效,带来的好处是,线程阻塞没必要挂起整个进程