操作系统备忘录-进程管理

1. 基本概念

2. 程序基本概念

程序

指令或语句序列

程序的执行方式

  • 顺序执行

    程序各部分（程序段或指令）依次顺序执行。当前操作完成 后才能执行其后继操作

    • 前驱图

  • 并发执行

    一组逻辑相互独立的程序或者程序段在执行过程中，其执行时间在客观上互相重叠

3. 顺序执行

前驱图

  • 有向无循环图，DAG(Directed Acyclic Graph)
  • 用于描述进程之间执行的前后关系
  • 可写成Pi→Pj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继

4. 并发执行

目的

  • 提高资源利用率

并行与并发

  • 并行（parallel）

  • 并发（concurrency）

    如果某个系统支持两个或者多个动作（Action）同时存在，那么这个系统就是一个并发系统。如果某个系统支持两个或者多个动作同时执行，那么这个系统就是一个并行系统。并发系统与并行系统这两个定义之间的关键差异在于“存在”这个词。

    在并发程序中可以同时拥有两个或者多个线程。这意味着，如果程序在单核处理器上运行，那么这两个线程将交替地换入或者换出内存。这些线程是同时“存在”的——每个线程都处于执行过程中的某个状态。

    并行”概念是“并发”概念的一个子集。

前驱图

  • I3，C2，P1可并发执行

区别顺序执行

  • 间断性

    • 缺乏共享资源，可能要等

  • 失去封闭性

    • 共享系统中的各种资源

  • 失去可再现性

    可再现性

    序运行结果与程序执行速度无关，只要初始状态相同，结果应相同

进程的引入

  • 刻画系统的动态性
  • 解决共享性

5. 进程基本概念

6. 概念

定义

行为的一个规则叫做程序，程序在处理器上执行时所发生的活动称为进程－Dijkstra

异步性

各进程按各自独立的不可预知的速度推进

7. 进程状态(生命周期)

分类

  • 运行态（Running）

    • 占有CPU，并在CPU上运行

  • 就绪态（Ready）

    • 已经具备运行条件，但由于无CPU暂时不能运行 的状态（当调度给其CPU时，立即可以运行）

  • 等待态(Wait) /阻塞(Blocked)/睡眠(sleep)

    • 因等待某种事件的发生而暂时不能运行的状态（即使CPU空闲，该进程也不可运行）

  • 创建状态(new)

    • 创建PCB，填写必要信息,申请必要资源，将进程转入就绪 状态并插入就绪队列,完成创建

  • 终止状态(exit)

    • 进程已结束运行，回收除PCB之外的其他资源，并让其他进程从PCB中收集有关信息

  • 挂起（动作）

    挂起进程在操作系统中可以定义为暂时被淘汰出内存的进程，机器的资源是有限的，在资源不足的情况下，操作系统对在内存中的程序进行合理的安排，其中有的进程被暂时调离出内存，当条件允许的时候，会被操作系统再次调回内存，重新进入等待被执行的状态即就绪态，系统在超过一定的时间没有任何动作。

    • 活跃就绪：是指进程在主存并且可被调度的状态
    • 静止就绪（挂起就绪）：是指进程被对换到辅存时的就绪状态，是不能被直接调度的状态，只有当主存中没有活跃就绪态进程，或者是挂起就绪态进程具有更高的优先级，系统将把挂起就绪态进程调回主存并转换为活跃就绪
    • 活跃阻塞：是指进程已在主存，一旦等待的事件产生便进入活跃就绪状态
    • 静止阻塞：是指进程对换到辅存时的阻塞状态，一旦等待的事件产生便进入静止就绪状态
    • 活跃：内存；静止：外存

状态转化

7.1. 挂起

引入原因

  • 终端用户的请求：调试需要
    • 在调试时，挂起被调试进程，从而对其地址空间 进行读写
  • 父进程请求
  • 负荷调节的需要
    • 挂起不重要进程，保证实时任务的运行
  • 操作系统的需要
    • 系统挂起进程以检查系统资源使用情况

状态转化

  • 活动就绪 －> （挂起） －>静止就绪
    • 当有高优先级就绪进程和低优先级就绪进程竞争时，系统可能会选择挂起低优先级就绪进程
  • 运行－>静止就绪(挂起就绪)：从内存调到外存
    • 高优先级抢占CPU，且内存不足
    • 自我挂起

8. PCB

定义

进程控制块（英语：Process Control Block，PCB）是操作系统核心中一种数据结构，主要表示行程状态。

内容

  • 进程标志符
    • 内部标识符(process ID)，唯一，通常是一个整数
    • 外部标志符，进程名，创建者提供
    • 父进程标志、子进程标志，用户标志等，说明进程家族关系
  • 处理机状态
    • 寄存器信息
  • 进程调度信息
    • 进程当前状态，优先级等
  • 进程控制信息
    • 程序和数据的地址等

PCB表

系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表

进程队列

  • 同一状态的所有进程控制块链接在一起构成进程队列

9. 进程控制

定义

  • 创建、撤消进程以及完成进程各状态之间的转换

方式

  • 原语(primitive)

    所谓原语，一般是指由若干条指令组成的程序段，用来实现某个特定功能，在执行过程中不可被中断

进程创建

  • 创建原语

    • 申请PCB,赋予一个统一进程标识符
    • 分配资源, 如内存
    • 初始化进程控制块

    从技术上来说，只有一种创建进程的方法， 即在一个已经存在的进程（用户进程或系统 进程）当中，通过系统调用来创建一个新的进程。

    • Windows：CreateProcess函数

进程终止

  • 终止原语
    • 根据被终止进程的标识符，从PCB集合中检索出该
      进程的PCB，从中读出该进程的状态
    • 若被终止进程正处于执行状态，应立即终止该进程
      的执行，并置调度标志为真，用于指示该进程被终止后应 重新进行调度
    • 终止子孙进程
    • 归还进程资源
    • 移出进程队列

进程阻塞

  • 停止执行
  • 修改PCB状态；插入阻塞队列
  • 调度程序重新调度；切换处理机

进程唤醒

  • 移出阻塞队列；修改PCB状态；插入就绪队列

10. 进程同步

基本概念

  • 略

同步机制应遵循的规则

  • 空闲让进
    • 当无进程在临界区时，任何有权使用临界区的进程可以进入
  • 忙则等待
    • 不允许两个以上的进程同时进入临界区
  • 有限等待
    • 进程在临界区内仅逗留有限的时间
  • 让权等待
    • 进程不能进入自己的临界区时，释放处理机，不允许“忙等”

实现

  • 硬件：基于关闭中断的互斥实现
    • 当一个进程进入临界区后，关闭所有的中断；当它退出临界区时，再打开中断
  • 软件：信号量

信号量的应用

  • 实现互斥

  • 实现前驱关系

    • 若希望执行语句S1后再执行语句S2

      1
      2
      进程P1: S1; signal(s);
      进程P2: wait(s); S2;

11. 进程同步问题

生产者－消费者问题

  • 记录型信号量

    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
    producer()
    {
        do
        {
            producer an item nextp;
            wait(empty);
            wait(mutex);
            //Swait(empty, mutex); AND
            buffer(in) = nextp;
            in = (in + 1) mod n;
            signal(mutex);
            signal(full);
        } while (true);
    }
    consumer()
    {
        do
        {
            wait(full);
            wait(mutex);
            nextc = buffer(out);
            out = (out + 1) mod n;
            signal(mutex);
            signal(empty);
            consumer the item in nextc;
        } while (true);
    }

哲学家进餐问题

有五个哲学家围坐在一 圆桌旁，桌子中央有一盘通心面，每人面前有一只空盘子，每两人之 间放一把叉子。每个哲学家思考、饥饿、吃通心面。

欲吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子。

1
2
3
4
5
6
7
8
9
10
semaphore chopstick[5] = {1, 1, 1, 1, 1};
do
{
    wait(chopstick［i］); //P
    wait(chopstick［(i + 1) % 5］); //P
    eat;
    signal(chopstick［i］); //V
    signal(chopstick［(i + 1) % 5］); //V
    think;
} while (true);

读者－写者问题

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
Void reader()
{
    do
    {
        wait(rmutex);
        if (readcount = 0)
            wait(wmutex);
        readcount++;
        signal(rmutex);
        perform read operation;
        wait(rmutex);
        readcount--;
        if (readcount = 0)
            signal(wmutex);
        signal(rmutex);
        while (true)
            ;
    }
}
void writer()
{
    do
    {
        wait(wmutex);
        perform write operation;
        signal(wmutex);
        while (true)
            ;
    }
}

  • 信号量集机制——最多允许N个读者同时读

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    #define N
    88 semaphore L = N, mx = 1;
    void reader() do
    {
        swait(L, 1, 1);  //控制读者数目
        swait(mx, 1, 0); //无写进程可读
        perform read operation;
        ssignal(L, 1);
    }
    while (true);
    }

    void writer()
    {
        do
        {
            swait(mx, 1, 1; L, N, 0); 
            //无写进程， 
            //无读进程，即L＝N； 
            perform write operation; ssignal(mx,1);
        } while (true)
    }

12. 进程通信

分类

  • 共享存储器系统
    • 向系统申请共享存储区的一个分区，对此分区读写等
  • 消息传递系统
    • 程序员直接利用系统提供的一组通信命令(原语)进行通信等
  • 管道通信
    • 读写进程通过称为管道的共享文件进行通信等

实现

  • 直接通信方式
    • 发送进程利用OS所提供的发送命令，直接把消息发送给目标进程等
  • 间接通信方式
    • 通信双方需要通过共享数据结构暂存消息－邮箱
    • 发送进程发消息到邮箱，接受进程从信箱取消息

13. 线程

引入

  • 创建进程 －－ 撤销进程 －－ 进程切换过程中涉及到资源的管理和分配
    • 处理机调度时系统时间空间开销大，并发度有限

线程与进程的比较

  • 调度
    • 线程作为调度单位；进程资源拥有单位
    • 减少了切换开销，提高了切换速度
  • 并发性
    • 不同进程的线程之间可以并发
  • 拥有资源
    • 线程拥有少量资源（用于保证自身运行，线程本身并不具有系统资源），访问所属进程的资源，进程的资源对其所属线程是共享的
  • 系统开销
    • 线程切换仅涉及一些寄存器，不涉及存储器
  • 独立性
    • 线程有相同地址空间，同步通信较容易

状态

  • 同进程

线程控制块

  • 线程标识符
  • 寄存器状态
    • 包括程序计数器PC和堆栈指针中的内容
  • 堆栈指针
    • 在堆栈中通常保存有局部变量和返回地址
  • 线程运行状态
  • 优先级
  • 线程专有存储器
  • 信号屏蔽

实现

参考