进程描述与控制

进程的描述与控制

进程管理

前驱图(DAG)：有向无循环图

1. 进程的特征

   • 结构特征：PCB进程控制块（与进程共存亡）、程序段、相关数据段总称为进程映像（进程实体）
   • 动态性：进程的基本特征，进程有一定生命周期，而程序则只是一组有序指令集合
   • 并发性
   • 异步性：进程按各自独立的、不可预测的速度向前推进
   • 独立性:独占性是个假象，多人主机，独立性是指一个独立运行的个体

   进程是进程实体的运行过程，是系统进行资源分配和调度的基本单位，作业 !=进程，作业可能包含很多进程，操作系统内部只存在进程

2. 进程的三种基本状态

   • 就绪状态：缺CPU

   • 执行状态

   • 阻塞状态：除了CPU还缺IO资源

   就绪 —进程调度–》执行—时间片用完–》就绪
   就绪 —进程调度–》执行–I/O请求–》阻塞–I/O完成–》就绪

   

   挂起状态：挂起时：程序段、数据段放在外存，PCB放在内存

   一个进程在挂起状态，其状态仍可能改变

   创建状态、终止状态：都只存在一次，创建状态用于分配资源然后来到就绪态，终止状态回收资源，修改状态，取消内存

   

3. 进程控制块：进程存在的唯一标志

   1. 信息
      • 进程标识符：内部标识符、外部标识符(用户可见)
      • 处理机状态：三态状态字，寄存器、计数器、栈指针
   2. 组织方式：
   • 线性
   • 链接（最常用）
   • 索引

进程控制

进程控制一般由OS的内核中原语实现的

原语：由若干条（特权指令+硬件）指令组成的，用于完成一定功能的一个不可分割的过程，是原子操作

操作系统内核不并发

1. 操作系统内核

   支撑功能：

   • 中断处理
   • 时钟管理
   • 原语操作

2. 进程的创建

   1. 进程的层次结构

      子进程可以继承父进程所拥有的资源，当子进程被撤销时，应将其从父进程那里获得的资源归还给父进程

      撤销父进程时，同时必须撤销子进程

   2. 进程的创建

      1. 申请空白PCB
      2. 为新进程分配其运行所需的资源
      3. 初始化PCB
      4. 如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列

3. 进程的终止

   1. 引起终止的实践
      • 正常结束
      • 异常结束
   2. 终止的过程
      1. 根据标识符，读出进程状态
      2. 若处于执行状态，终止执行
      3. 终止子孙进程
      4. 将资源归还系统
      5. 将PCB移除队列

4. 进程的阻塞与唤醒

   1. 进程阻塞过程

      block原语，主动的由执行-》阻塞

   2. 进程唤醒过程

      signal原语，被动的由阻塞-》就绪

5. 进程的挂起与激活（主体是操作系统）

进程同步

1. 基本概念

   1. 两种形式的制约关系

      • 间接相互制约关系（互斥共享）：多个进程对之只能互斥的访问，如共享单车
      • 直接相互制约关系（依赖关系）：源于进程之间的相互合作，如接力赛

   2. 临界资源（操作系统所有）：必须使用互斥共享的资源、一段时间只允许一个进程访问

   3. 临界区：访问临界资源的代码段为临界区

      while(Ture) {
      	进入区 //对临界资源进行检查，如果未被访问，设置访问状态，否则则阻塞该进程
      	临界区 //访问临界资源的代码段
      	退出区 //设置未访问状态
      	剩余区
      }
      

   4. 同步机制规则

      • 空闲让进
      • 忙则等待
      • 有限等待
      • 让权等待

2. 信号量机制

   P操作wait(S), V操作signal(S)

   1. 整型信号量(S代表资源数目)

      wait(S) {
      	while (S <= 0); //违反让权等待
      	S--;
      }
      
      signal(S) {
      	S++
      }
      

   2. 记录型信号量

      typedef struct {
      	int value;
      	struct process_control_block *list;
      }semaphore;
      
      wait(semaphore *S) {
      	S->value--;
      	if (S->value < 0) block(S->list);
      }
      
      sigal(semaphore *S) {
      	S->value++;
      	if (S->value <= 0) wakeup(S->list); // 信号量链表中仍有被阻塞资源，应该唤醒
      }
      
      /**
      S.value < 0 : 因竞争失败而被阻塞挂起的进程数
      S.value == 0 :没有进程被阻塞且临界资源为空
      S.value > 0 : 有空闲临界资源
      */
      

3. 信号量应用

   1. 实现互斥：设置一个互斥信号量mutex
   2. 实现前驱关系

4. 经典进程同步问题

   1. 生产者-消费者问题

      int in, out = 0;
      item buffer[n];
      semaphore mutex = 1, empty = n, full = 0
      void producer() {
          do {
              produce an item nextp;
              ...
              wait(empty)
              wait(mutex)
              //如果wait(empty)，wait(mutex)换位置，可能出现死锁，先wait(mutex)的话，如果full = n，empty = 0此时无法获得empty锁，且消费者由于无法得到mutex也无法从中取走数据
              buffer[in] = nextp;
              in = (in + 1) % n
              signal(mutex)
              signal(full) //如果缺少signal(full)，消费者会陷入死锁
          } while(TRUE)
      }
      void consumer() {
          do {
              wait(full)
              wait(mutex)
              //如果wait(full)，wait(mutex)换位置，可能出现死锁，先wait(mutex)的话，如果full = 0，empty = n此时无法获得full锁，且生产者由于无法得到mutex也无法向其中加入数据
              nextc = buffer[out];
              out = (out + 1) % n
              signal(mutex)
              signal(empty)//如果缺少signal(empty)，生产者会陷入死锁
          } while(TRUE)
      }
      
      void main() {
      	cobegin
      		producer();
      		consumer()
      	coend
      }
      

   2. 哲学家进餐问题：可能引起死锁

   3. 读者-写者问题

      semaphore rmutex = 1, wmutex = 1;
      int readcount = 0
      void reader() {
          do {
              wait(rmutex); //给readcount上锁
              if (readcount == 0) wait(wmutex); //只要有一个Reader进程在读，便不允许Writer去写
              readcount++;
              signal(rmutex);
              ...
              perform read operation;
              ...
              wait(rmutex);
              read--;
              if (readcount == 0) signal(wmutex)
              signal(rmutex)
          } while(TRUE)
      }
      void Writer() {
      	do {
      		wait(wmutex);
      		perform write operation;
      		signal(wmutex;)
      	}while (TRUE)
      }
      void main() {
      	cobegin
      		Reader();Writer();
      	coend
      }
      

5. 进程通信

   1. 类型
      • 共享存储器系统：共享数据结构（少量数据）、共享存储区
        • 效率最高
      • 管道通信系统
      • 消息传递系统：应用最广
      • 客户机-服务器系统
   2. 进程同步方式
      1. 发送进程阻塞，接收进程阻塞，用于进程之间紧密同步，进程直接无缓冲（汇合）
      2. 发送进程不阻塞，接收进程阻塞
      3. 发送进程和接收进程均不阻塞（异步）

6. 线程的基本概念

   早期进程类似个体户，一个人完成所有任务（分配资源并完成任务）

   现在的进程：类似公司，只参与计算机资源分配，由线程（共享进程资源）完成任务

   现代程序执行空间都是在线程空间

   线程也有自己的私有资源

   1. 线程和进程的比较
      • 在引入线程的OS中，已把线程作为调度和分派的基本单位
      • 并发性
      • 拥有资源：TCB
      • 独立性：比进程低
      • 系统开销
      • 支持多处理机系统
   2. 线程状态和线程控制块
      1. 线程状态（无挂起，线程本身就没有什么资源）
         • 执行
         • 就绪
         • 阻塞
      2. TCB类似于PCB
      3. 多线程OS中的进程
         1. 进程是一个可拥有资源的基本单位
         2. 多个线程可并发执行
         3. 进程已不是可执行实体
   3. 线程的实现
      1. 内核支持线程KST：缺点：对于用户线程切换，效率太低
      2. 用户级线程ULT：缺点：线程执行到系统调用的时候，不仅线程被阻塞，进程内的所有线程也会被阻塞
         控制块
      3. 线程状态（无挂起，线程本身就没有什么资源）
         • 执行
         • 就绪
         • 阻塞
      4. TCB类似于PCB
      5. 多线程OS中的进程
         1. 进程是一个可拥有资源的基本单位
         2. 多个线程可并发执行
         3. 进程已不是可执行实体
   4. 线程的实现
      1. 内核支持线程KST：缺点：对于用户线程切换，效率太低
      2. 用户级线程ULT：缺点：线程执行到系统调用的时候，不仅线程被阻塞，进程内的所有线程也会被阻塞
      3. 组合方式KST/ULT