Jerry

外观

操作系统漫游（二）进程

1882字约6分钟

操作系统

2018-03-17

程序的顺序执行和并发执行

顺序执行

一个程序，通常由多个程序段组成。当前程序段执行结束之后，才运行后一程序段，这样的执行方式称为顺序执行。例如，输入 - 计算 - 输出，就是一个顺序执行的例子。

顺序执行的程序具有三个特征：顺序性，封闭性，可再现性。

并发执行

假设有三个设备，分别要进行 输入 - 计算 - 请求IO - 计算 - 输出。当 A 设备请求IO的时候，CPU 可以为 B 设备进行计算。这样的执行方式称为并发执行。

并发执行的程序具有三个特征：间断性、失去封闭性、不可再现性。

并发带来的程序不可再现性，是我们不希望出现的，因此我们要采取并发的控制。

进程的概念

进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

为了使并发执行的多个程序能独立地运行，操作系统提供了一个专门的数据结构，称为进程控制块（Process Control Bolck, PCB）。因此，进程实体（或者称进程映像）包括 PCB、程序段 和 数据段 三个部分。

值得注意的是，PCB是由OS进行管理的，进程本身无法操作其对应的PCB。

一般来说，操作系统分配资源以进程为基本单位。但是在操作系统内核支持线程的情况下，调度是以线程为单位的。

进程的特征

进程的特征有：动态性、并发行、独立性、异步性。

进程的基本状态

  • 就绪（Ready）状态：万事俱备，只等CPU

  • 执行（Running）状态：获得CPU，正在执行

  • 阻塞（Block）状态： 发生某事件（例如IO请求）从而无法继续执行

有时候，用户或者操作系统会将暂时不用的进程执行挂起（suspend）操作，这时候进程会进入挂起状态，表示该进程暂不接受调度。直至被重新激活（active）。

process_status

除此之外，进程还有创建状态和终止状态。

当计算机系统没有用户进程执行时，处理机没有停止工作，而是执行 IDLE 程序。

进程控制

进程控制主要包括创建新进程、终止已完成的进程、阻塞异常进程、转换进程状态等。

为了防止OS本身以及PCB等关键数据被应用程序破坏，处理机的执行状态分为系统态（管态）和用户态（目态）。系统态有较高的特权，能执行一切指令。用户态则只能访问特定寄存器和存储区。

OS的进程控制中，主要有三种支撑功能：中断处理、时钟管理、原语操作。

所谓原语（Primitive），是由若干条指令组成的用于完成一定功能的一个过程。它是一种原子操作，不允许被中断。进程的原语操作有： CREATE、TERMINATION、BLOCK、WAKEUP、SUSPEND 和 ACTIVE。

进程同步

前面提到，并发执行带来的程序不可再现性，是我们不希望出现的，因此我们要采取并发的控制。我们用进程同步来解决这一问题。

进程同步规则

  • 空闲让进：临界资源闲时，进程进入
  • 忙则等待：临界资源忙时，进程需等待
  • 有限等待：超时机制，避免死等
  • 让权等待：对不能进入临界区的进程，应立即释放处理机

基于这4个规则设计的进程同步机制，不会导致进程无限等待。

临界资源的概念

临界资源（Critical Resource）指的是一段时间内只允许一个进程访问的资源，只能够互斥访问。进程中访问互斥资源的那段代码称为临界区。

信号量（Semaphores）机制

信号量机制是1965年荷兰学者 Dijkstra 提出的一种进程同步工具。信号量可用于进程同步、进程互斥、控制进程的前驱关系。目前广泛用在单处理机、多处理机和计算机网络中。

在信号量机制中，分为 P操作 wait(S)（申请资源） 和 V操作 signal(S)（释放资源）。这是两个原子操作，在执行时是不可中断的。

整形信号量

整形信号量原型如下：

wait(S){
  while (S<=0); //do no-op
  S--
}

signal(S){
  S++;
}

即资源为0或者小于0时，进行等待。

但是这样会导致忙等，没有遵循让权等待的原则。于是又出现了记录型信号量。

记录型信号量

记录型信号量即是建立一个链表，让申请资源的进程进行排队。

原型如下：

typedef struct {
  int value;
  struct Process_control_block *list;
}semaphore;

wait(semaphore *S){
  S->value--;
  if(S->value < 0) block(S->list);
}

signal(semaphore *S){
  S->value++;
  if(S->value <=0) wakeup(S->list);
}

S->value的初始值表示系统中某类资源数目。

AND型信号量

假设 共享数据D 和 共享数据E 是可以被 进程A 和 进程B 访问的数据。

无论哪个进程，需要同时获得数据D和E后，方能进行操作。

那么，考虑以下情况：

process A: wait(Dmutex)； // Dmutex = 0
process B: wait(Emutex)； // Dmutex = 0
process A: wait(Emutex)； // Dmutex = -1 阻塞
process B: wait(Dmutex)； // Dmutex = -1 阻塞

也就是说，A获取了D资源， B获取了E资源， A想要再取得E资源才能进行操作，可是E资源在B那里，于是A进行阻塞等待。B想要再取得D资源才能进行操作，可是D资源在A那里，于是B也进行阻塞等待。

这样就造成了僵持状态，也就是死锁。

为了避免这种情况，我们可以用AND同步机制。其核心思想是：将进程在运行中需要的所有资源，一次性分配给该进程。

也就是说，要么一次性把 D资源和E资源 都分配给进程A，要么就都不分配。

信号量的应用

  • 实现进程同步
  • 实现进程互斥
  • 实现前驱关系

经典进程同步问题

生产者-消费者问题

定义变量

var mutex, empty, full = 1, n, 0
buffer:array[0...n-1] of item
in,out :Integer = 0, 0
  • mutex 用来加锁，某进程持有锁的时候其他进程不可进入
  • empty 表示缓存区可用空间，生产=往缓冲区放置，empty-1， 消费=从缓冲区读取，empty+1
  • full 表示可用产品，为0时消费者不可继续消费

生产者进程

//process p
begin
    while(true):
        do begin
        produce nextp
        wait(empty)
        wait(mutex)

        buffer[in] = nextp
        in = (in + 1) mod n

        signal(mutex)
        signal(full)
    end
end

消费者进程

begin
    while(true):
        do begin
        wait(full)
        wait(mutex)

        nextp = buffer[out]
        out = (out + 1) mod n

        signal(mutex)
        signal(empty)

    end
end

读者-写者问题

定义变量

var rmutex, wmutex: Semaphores = 1, 1
    ReadCount: Integer = 0
  • rmutex表示读锁
  • wmutex表示写锁

读者进程

begin
    while(true):
        wait(rmutex)    
        if ReadCount == 0 then wait(wmutex)

        ReadCount++

        signal(rmutex)
        // 读文件操作
        wait(rmutex)

        ReadCount--

        if ReadCount == 0 then signal(wmutex)
        signal(rmutex)
    end
end

写者进程

begin
    while(true):
        wait(wmutex)
        //写文件操作
        signal(wmutex)
    end
end