mos-进程管理

Posted on Edited on

进程

进程的状态

  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. 公平分享调度

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

实时系统

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

策略与机制

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

线程调度

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

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