操作系统漫游（二）进程
程序的顺序执行和并发执行
顺序执行
一个程序，通常由多个程序段组成。当前程序段执行结束之后，才运行后一程序段，这样的执行方式称为顺序执行。例如，输入 - 计算 - 输出，就是一个顺序执行的例子。
顺序执行的程序具有三个特征：顺序性，封闭性，可再现性。
并发执行
假设有三个设备，分别要进行 输入 - 计算 - 请求IO - 计算 - 输出。当 A 设备请求IO的时候，CPU 可以为 B 设备进行计算。这样的执行方式称为并发执行。
并发执行的程序具有三个特征：间断性、失去封闭性、不可再现性。
并发带来的程序不可再现性，是我们不希望出现的，因此我们要采取并发的控制。
进程的概念
进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。
为了使并发执行的多个程序能独立地运行，操作系统提供了一个专门的数据结构，称为进程控制块（Process Control Bolck, PCB）。因此，进程实体（或者称进程映像）包括 PCB、程序段 和 数据段 三个部分。
值得注意的是，PCB是由OS进行管理的，进程本身无法操作其对应的PCB。
一般来说，操作系统分配资源以进程为基本单位。但是在操作系统内核支持线程的情况下，调度是以线程为单位的。
进程的特征
进程的特征有：动态性、并发行、独立性、异步性。
进程的基本状态
就绪（Ready）状态：万事俱备，只等CPU
执行（Running）状态：获得CPU，正在执行
阻塞（Block）状态： 发生某事件（例如IO请求）从而无法继续执行
有时候，用户或者操作系统会将暂时不用的进程执行挂起（suspend）操作，这时候进程会进入挂起状态，表示该进程暂不接受调度。直至被重新激活（active）。
除此之外，进程还有创建状态和终止状态。
当计算机系统没有用户进程执行时，处理机没有停止工作，而是执行 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