进程管理部分主要包括进程与线程、进程调度算法、同步与互斥、死锁。

进程与线程

进程

进程映像（进程实体） = 程序段 + 数据段 + PCB

其中PCB是进程存在的唯一标志。

操作系统是根据进程控制块(PCB)来对并发执行的进程进行控制和管理的。

二进制代码和常量存放在正文，动态分配(malloc)的变量在数据堆段，临时使用的变量在数据栈段。

  • 栈是由操作系统自动分配和释放，速度快
  • 堆是由程序员分配和释放，速度慢

进程的特点

动态性是进程最基本的特征，程序是静态的。（进程与程序的区别）

进程具有异步性，会导致执行结果有不可再现性，为此在操作系统中必须配置相应的进程同步机制。

进程通信

  1. 共享文件
  2. 消息传递
  3. 共享存储区
  4. 管道，采用半双工通信，某一时刻只能单向传输。

进程控制

终端用户登陆系统、作业调度、系统提供服务、用户程序的应用请求都会创建进程。

进程创建后进入就绪态，也就是进入了就绪队列。

进程控制用的程序段：原语。

进程状态

就绪态进程管理 - 图1运行态：经过处理机调度，就绪进程得到处理机资源

运行态进程管理 - 图2就绪态：时间片用完或在可剥夺系统中有更高优先级进程进入

运行态进程管理 - 图3阻塞态：进程需要的某一资源还没准备好

阻塞态进程管理 - 图4就绪态：进程所需资源已经准备好，进程被唤醒

线程

线程最直接的理解就是“轻量级进程”（或者说是，特殊的进程）。

在引入线程的操作系统中，线程是独立调度的基本单位，进程是拥有资源的基本单位。

从一个进程内的线程切换到另一个进程中的线程，会引起进程切换。

用户级线程与内核级线程

多线程模型

  1. 多对一模型：一个线程在使用内核服务时被阻塞，整个进程都会被阻塞。
  2. 一对一模型
  3. 多对多模型

进程调度算法与计算

调度准则

周转时间

周转时间 = 作业完成时间 - 作业提交时间

平均周转时间

平均周转时间 = (作业1的周转时间 + 进程管理 - 图5 +作业n的周转时间) / n

等待时间

进程处于等待处理机状态的时间之和。

调度算法

进程与作业

进程是从操作系统角度出发，作业是从用户角度出发。

先来先服务(FCFS)算法

对长作业有利，对短作业不利。

有利于COP繁忙型作业，不利于I/O繁忙型作业。

短作业优先(SJF)算法

有饥饿现象。

平均等待时间、平均周转时间最少。

优先级调度算法

优先级原则

  1. 系统进程 > 用户进程
  2. I/O进程 > 计算型进程

I/O型进程的优先级设置高，就能让I/O设备尽早工作，提升系统整体性能。

高响应比调度算法

用于作业调度。

满足短作业优先但不会发生饥饿现象。

进程管理 - 图6

时间片轮转调度算法

也是一种剥夺式调度算法。

同步与互斥

临界区与临界资源

临界资源：一次仅允许一个进程使用的资源称为临界资源。

临界区：访问临界资源的那段代码称为临界区。

可重入代码：允许多个进程同时访问的代码，不允许任何修改的代码。

例题

若一个系统中有5个并发进程涉及某个相同的变量A，则变量A的相关临界区是由( )个临界区构成的。

临界区是代码部分，因此答案是5个。

临界区互斥访问

软件方法

  1. 单标志法，违背“空闲让进”
  2. 双标志法先检查，违背“忙则等待”
  3. 双标志法后检查，违背“有限等待”，陷入了“饥饿”
  4. Peterson算法，解决了互斥访问临界区问题，但是违背“让权等待”

硬件方法

  1. TestAndSet指令
  2. Swap指令

硬件方法不能实现“让权等待”

信号量

P操作和V操作是一种低级进程原语，不是系统调用。

原语(Atomic Action)是指完成某种功能且不能分割、不被中断执行的操作序列。

管程

组成

  1. 局部与管程的共享结构说明。
  2. 对该数据结构进行操作的一组过程。
  3. 对局部于管程的共享数据设置初始值的语句。

管程不仅能实现进程间的互斥，而且能实现进程间的同步。

在同一时刻，管程中只能有一个进程在执行。

条件变量

条件变量是没有值的，只有signal和wait两个操作。

管程的signal操作与信号量机制中的V操作不同（有相似之处），signal操作是针对某个条件变量的，若不存在因该条件而阻塞的进程，则signal不会产生任何影响。

看下述代码可以方便理解，（不恰当的说，signal操作前进行了条件判断，而V操作中包含条件判断。）

  1. monitor Demo {
  2.     共享数据结构 S;
  3.     condition x;
  4.     init_code() {
  5.         ...
  6.     }
  7.     take_away() {
  8.         if(S <= 0) x.wait();
  9.         ...分配资源
  10.     }
  11.     give_back() {
  12.         ... 归还资源
  13.         if(有进程在等待) x.signal();
  14.     }
  15. }

死锁

死锁与饥饿

死锁产生原因：非剥夺资源的竞争、进程的不恰当推进顺序

系统资源不足只会导致进程“饥饿”，让进程一直等待。

死锁一定要有两个或两个以上的进程才会导致，而饥饿可能由一个进程导致。

死锁预防

关键在“预”——破坏死锁发生的四个必要条件。

破坏互斥条件

不可行，无法破坏互斥访问条件

破坏不剥夺条件

破坏请求和保持条件

预先静态分配，会导致“饥饿”

破坏循环等待条件

顺序资源分配法

死锁避免

在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。

死锁检测

进程在分配资源时不采取任何措施，应该提供死锁检测和解除的手段。

资源分配图

圆圈：代表一个进程

矩形框：代表一类资源

请求边：进程进程管理 - 图7资源

分配边：资源进程管理 - 图8进程

死锁定理

死锁的条件：当且仅当资源分配图时不可化简的。

死锁解除

资源剥夺法

撤销进程法

进程回退法