操作系统复习 （二）进程管理

1.进程基本概念

顺序执行

• 特征：
  顺序性：下一操作要等待前一操作结束
  封闭性：执行独占资源，不受外界影响
  可再现性：重复执行将获得相同结果
• 程序顺序执行：
  当前操作执行完后才能执行后继操作
• 语句顺序执行：
  当前语句执行完后才能执行后继语句

前趋图

• 简介：
  前趋图描述进程之间执行的前后关系，结点描述一个程序段、进程或语句，有向边表示偏序或者前趋关系。

• 特征：
  有向无环图。

  
  
• 描述：
  Pi→Pj，Pi是Pj的直接前趋，Pj是Pi的直接后继；
  初始结点：没有前趋的结点；
  终止结点：没有后继的结点；
  Weight：表示程序量或者执行时间；
  图的前趋关系：P1→P2，P2→P3。

并发执行

• 描述：
  In+1 和 Cn 是并发的（它们都需要In），In+2 和 Cn+1 和 Pn 是并发的（In+2需要In+1，Cn+1需要Cn，Pn需要Cn）

  
  
• 特征：（破坏了顺序执行）
  • 间断性
  • 失去封闭性
  • 不可再现性
• 体现特性的例子：
  思考：程序A每次执行N+1，程序B每次执行Print(N)，再设N=0。A、B不同速度执行。

• 题目：
  根据式子画前趋图（基于并发）
  S1: a:=x+2
  S2: b:=y+4
  S3: c:=a+b
  S4: d:=c+b

  
  

进程的基本概念

1. 引入原因：
   为了解决程序并发的时候出现的问题，引入了进程。
2. 进程的结构：

• 程序：描述进程要完成的功能，代码段
• 数据：进程执行时所需要的数据区，数据段
• 进程控制块PCB：一种数据结构，用于标识进程的存在，记录进程执行过程各个时刻的状态特征

3. 进程四个特性
   动态性：生命周期 创建执行消亡
   并发行：多个进程共存于内存，同时执行
   独立性：资源独立，互不干扰
   异步性：速度不可预知
4. 进程定义：
   → 进程是程序的一次执行
   → 进程是一个程序及其数据在处理机上顺序执行时发生的活动
   → 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位
   进程是进程实体的运行过程，它系统进行资源分配和调度的一个独立单位。(最终定义）
5. 进程与程序的区别

• 进程是动态的执行实体，程序是静态的数据与指令的集合
• 一个程序可以包含多个进程
• 进程用于并发执行与接受调度，程序用于存储数据和接受系统启动
• 进程执行需要CPU，程序存储需要存储器
• 进程是有生命周期的，程序是永存的

6. 进程分类

• 系统进程：（管态下运行、初始资源最高优先使用、直接IO、执行一切指令和访问保护的寄存器和存储区）
• 用户进程：（目态下运行、通过服务请求作竞争、不能直接IO、执行特定指令访问指定的寄存器和存储区）

7. 进程三种基本状态

• 就绪状态：获得CPU以外资源，处于就绪队列
• 执行状态：获得CPU，处于执行过程
• 阻塞状态：发生某种事件暂时无法进行(IO)，放弃CPU处于暂停状态，处于阻塞队列。

状态轮回

8. 挂起状态

   
   五种状态轮回

• 一种静止状态，不能马上投入运行。
• 这个状态导致增加了两种状态：静止就绪和静止阻塞。
• 原因：终端用户请求 - 父进程请求 - 负荷调节请求 - 操作系统请求

9. 创建状态和终止状态
   创建状态：进程初始化时，拥有PCB但没有资源，未进入调度队列，OS根据资源情况可以推迟进程创建
   终止状态：进程结束时，资源释放回收状态。永远不得CPU，释放CPU等所有资源，自然退出或者外力终止它。

10. 总结状态：
    就绪：没CPU，有资源，
    执行：有CPU，有资源，
    阻塞：没CPU，没IO资源，
    挂起：没内存

2. 进程的控制

进程控制块 (PCB Process Control Block)

1. 作用
   使一个多道程序环境下不能独立运行的程序成为一个能独立运行的基本单位，一个能和其他程序并发执行的进程。
   OS根据PCB对并发执行的进程进行控制和管理。
2. 考试作用：

• 进程存在的唯一标志
• 记录进程的外部特征
• 描述进程变化的过程
• 记录进程和其他进程的联系
• OS通过PCB控制和管理进程

3. PCB中的信息

• 进程标识符
• 处理机状态：各寄存器内容
• 进程调度信息
• 进程控制信息

4. 组织方式
   链接方式 执行指针->PCB1->PCB4...（链表）
   索引方式 表中指针指向PCB

进程的创建

1. 父子进程
   父子进程关系：

• 进程控制：子进程由父进程创建或撤销，子进程不能控制父进程
• 资源继承：子进程可以全部或部分共享父进程的资源
• 运行方式：可同时进行，可以控制先后
• PCB：在PCB中设置家族关系表项，标明自己的父进程和子进程

2. 原语操作 - 原子操作，要么全做，要么全不做
3. 进程创建过程

• 申请空白PCB
• 分配资源：用户请求，自身创建，交互型
• 初始化PCB：标识、处理机状态、控制信息
• 新进程插入就绪队列

4. 进程的终止

• 类型：
  正常结束：halt
  异常结束：Error
  外界干预：操作员、操作系统、父进程
• 终止过程：
  （1）根据PCB读取进程状态
  （2）如果正在执行->停止执行；设调度位为真，避免被再次调度
  （3）终止子孙进程
  （4）回收资源
  （5）释放PCB

5. 进程的阻塞 block

• 引起事件
  请求系统、启动某操作、新数据未到达、无新工作
• 正执行过程中，当发现引发阻塞的事件，无法继续执行，进程调用阻塞原语block把自己阻塞
• 阻塞是进程自身的一种主动行为
• 阻塞过程：
  （1）停止执行
  （2）修改状态为阻塞
  （3）PCB插入相应阻塞队列
  （4）重新调度分配CPU
  （5）CPU环境切换，保存该进程CPU状态到PCB、恢复新进程PCB的CPU状态设置到CPU中。

6. 进程的唤醒 wakeup
   （1）从阻塞队列移除
   （2）PCB从阻塞改就绪
   （3）PCB插回就绪队列 //静止就绪or活动就绪
7. 进程挂起 suspend
   （1）活动就绪改为静止就绪；活动阻塞改为静止阻塞
   （2）复制PCB到指定内存
   （3）数据复制到外存，释放内存
8. 进程激活 active
   （1）进程从外存调入内存
   （2）静止就绪改为活动就绪；静止阻塞改为活动阻塞
   （3）若是进入就绪队列，则重新调度

3. 进程同步

基本概念

1. 进程同步的任务：是使并发进行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性
2. 两种形式的制约关系
   间接相互制约关系：申请I/O、CPU
   直接相互制约关系：输入与运算
3. 临界资源：互斥共享
4. 生产者-消费者问题
   in = (in+1) mod n
   out = (out+1) mod n
5. 同步机制遵循：
   空闲让进
   忙则等待
   有限等待
   让权等待
6. 整型信号量
   只有一个整数变量记录可用资源数量
   有限等待，但不满足让权等待的规则。（s<=0 while循环会浪费CPU哦）
7. 记录型信号量
   一个结构体的信号量
   采取让权等待。 （s<=0 直接进阻塞队列 不浪费CPU）

type semaphore=record
value:integer;   (下文传说中的S)
L: list of process;(排队使用的进程要待的阻塞队列)
end;

procedure P(var s:semaphore);
begin
s.value:=s.value-1;(将信号量值减1)
if s.value<0 then block(s.L);（若信号量值小于0，则调用阻塞原语阻塞自己，插入到阻塞队列中去）
end;

procedure V(var s:semaphore);
begin
s.value:=s.value+1;(将信号量值加1)
if s.value<=0 then wakeup(s.L);（若信号量值小于等于0，则调用唤醒原语从阻塞队列中唤醒一个进程）

8. 银行取款信号量

wait(mutex)        wait(mutex)
count+=m           count-=n
signal(mutex)      signal(mutex)

9. AND型信号量 避免死锁
   多个信号量,资源要么全部分配，要么一个都不分配
   Ssignal(s1,s2,s3,...)
   Swait(s1,s2,s3,...)

10. 信号量集
    请求n种资源，每种数量n个
    Swait(S, d, d)：此时在信号量集中只有一个信号量S， 但允许它每次申请d个资源，当现有资源数少于d时，不予分配。
    Swait(S, 1, 1)：信号量集蜕化为一般的记录型信号量(S＞1时)或互斥信号量(S=1时)。
    Swait(S, 1, 0)：这是一种很特殊且很有用的信号量操作。当S≥1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。它相当于一个可控开关。。

四、同步问题

1. 信号量机制的特性
   wait(S)和signal(S)必须成对出现，但可以不在同一个进程中
   缺少wait(S)不能保证资源互斥
   缺少signal(S)可能使资源永远不能释放
   不存在“忙等”问题
2. 信号量完成前趋图
   箭头从哪里出发，哪里signal()，从哪里结束，哪里先wait()
3. 信号量的不足
   临界区在不同进程，不方便管理。
   临界区操作类似，浪费代码。
   wait，signal，可读性差。
   错误时，因为阻塞不方便调试。
   wait，signal错误，难以预测易死锁。
4. 管程

• 定义：
  （1）一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据
  （2）管程实际上是一种能实现进程同步的特殊的子程序（函数、过程）的集合
• 作用
  （1）使用临界资源的进程进行调用时非常简单
  （2）进程结构清晰
  （3）易于查错

5. 进程通信的类型
   （1）共享存储器系统（无格式）：进程间以共享存储器方式进行数据通信
   （2）消息传递系统（有格式）：
   进程间的数据交换以消息（message）为单位
   操作系统直接提供一组命令（原语）实现通信
   （3）管道通信系统（相当于文件）：
6. 线程是调度和执行的基本单位，进程是分配的基本单位
7. 线程与进程的关系
   （1）线程是进程中的运行实体
   （2）一个进程可包含多个线程
   （3）一个进程中至少包含一个线程，称主线程
   （4）进程相当于线程的载体

五、各种问题收集

1. 生产者、消费者问题

   
   信号量版本
   AND信号量版本
   原语同步

2. 公交车问题

S1 = 0；S2 = 0；
driver() {
  while(1) {
    wait(S1)
    启动车辆
    运行
    到站
    signal(S2)
}

busman() {
  while(1) {
    上下乘客
    关门
    signal(S1)
    售票
    wait(S2)
    开门
    上下乘客
  }
}

3. 仓库问题

mutex = 1；shelf = 50；item = 0;
in() {
  wait(shelf)
  wait(mutex)
  登记
  存货物
  signal(mutex)
  signal(item)
}

out() {
  wait(item)
  wait(mutex)
  登记
  取货物
  signal(mutex)
  signal(shelf)
}

4. 哲学家问题

left = i
right = (i+1)%5
// A 只有4位哲学家能开始就餐，其他3人只能拿一边
r = 4
philosopher (){
  while(1) {
    think()
    hugry()
    wait(r)
    wait(left)
    wait(right)
    eat()
    signal(left)
    signal(r)
    signal(right)
  }
}

// B and信号量
philosopher (){
  while(1) {
    think()
    hugry()
    Swait(left,right)
    eat()
    Ssignal(left,right)
  }
}

// C 奇数拿右边 偶数拿左边
philosopher (){
  while(1) {
    think()
    hugry()
    if(i%2==0)
      wait(right)
      wait(left)
      eat()
      signal(left)
      signal(right)
    else
      wait(left)
      wait(right)
      eat()
      signal(right)
      signal(left)
  }
}

5. 读者 写者问题

Var  wmutex, rmutex :semaphore :=1, 1;
        Readcount :integer :=0;
begin
    parbegin
        Reader : begin
             repeat
                wait(rmutex);
                if Readcount=0 then wait(wmutex);
                Readcount :=Readcount +1;
                signal(rmutex);
                   …
                   读;
                   …
                wait(rmutex);
                Readcount :=Readcount -1;
                if Readcount=0 then signal(wmutex);
                signal(rmutex);
            until  false;
       end
     parend
end 

Writer : begin
     repeat
         wait(wmutex);
         写;
         signal(wmutex);
     until  false;
end 

//L: 控制读进程的数目≤RN
//Mx: 实现读、写互斥；写、写互斥

Var  RN  integer;
        L, mx: semaphore :=RN, 1;
begin
    parbegin
        reader : begin
            repeat
               Swait(L, 1, 1); //控制Rn个读进程可以读，前Rn个读者都可以进去
               Swait(mx, 1, 0);// 打开，读者都可以进来读
               …
               读;
               …
              Ssignal(L, 1);
          until  false;
      end
   parend
end


writer : begin
    repeat
       Swait(mx, 1, 1; L, RN, 0);// 将读进程关闭，且没有读进程，写进程才能写操作
       写;
       Ssignal(mx, 1); // 读进程都可以读了
   until  false;
end