第二章 进程管理

进程与线程

概念

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

系统为参与并发执行的程序配置一个专门的数据结构，称为进程控制块（PCB）用于控制管理进程，程序段、相关数据段和PCB三部分构成了进程映像。

进程映像是静态的，进程是动态的。

PCB是进程存在的唯一标志！

特征

• 动态性：进程是程序的一次执行，具有生命周期，动态性是其基本特征
• 并发性：多个晋城市提同时存于内存中，能在一段时间内同时运行
• 独立性：是能独立运行、获得资源和独立接受调度的基本单位。
• 异步性：进程按各自独立的、不可预知的速度向前推进
• 结构性：程序段、数据段、进程控制块

状态和转换

• 运行态：进程正在处理机上运行，单处理机，每个时刻最多只有一个进程在运行态

• 就绪态：处于就绪的进程可能有多个，通常排成一个队列，即就绪队列 。仅缺少处理机

• 阻塞态：又称等待态，进程正在等待某一事件而暂停运行，即使处理机空闲，进程也不能运行

• 创建态：进程正在被创建，还未转到就绪态。

  • 申请一个空白PCB，向其中填写控制和管理进程的信息
  • 系统为该进程分配运行时所必须的资源
  • 该进程转入就绪态

• 结束态：进程需结束运行时，首先要置该进程为结束态，然后进一步处理资源释放和回收等工作

• 就绪态到运行态

• 运行态到就绪态：处于运行态的进程时间片用完后，让出处理机，转为就绪态

• 运行态到阻塞态：进程请求某一资源的使用或等待某一事件的发生

• 阻塞态到就绪态

进程由运行态变为阻塞态是主动行为，由阻塞态变为就绪态是被动行为

控制

进程控制具有创建新进程、撤销已有进程、实现进程状态转换等功能。一般进程控制用的程序段称为原语

• 进程创建

  • 分配进程标识号，申请空白PCB
  • 为进程分配资源 若分配失败，处于阻塞态，等待内存资源
  • 初始化PCB
  • 将新进程插入就绪队列

• 进程终止

  • 根据终止进程标识符，检索PCB
  • 若进程处于执行状态，终止执行
  • 终止其子孙进程
  • 归还资源
  • 删除PCB

• 进程阻塞和唤醒

  只有处于运行态的进程才可能将其转换为阻塞态

  阻塞原语

  • 找到标识号对应的PCB
  • 若进程为运行态，保护现场，转为阻塞态，停止运行
  • 把该PCB插入相应事件的等待队列，处理机调度给其他进程

  唤醒原语

  • 在等待队列中找到对应PCB
  • 移出，转为就绪态
  • 插入就绪队列，等待处理机调度

• 进程切换

  1. 保护处理机上下文
  2. 更新PCB
  3. 把进程的PCB移入相应序列
  4. 选择另一个进程执行，更新其PCB
  5. 更新内存管理的数据结构
  6. 恢复处理机上下文

  调度是分配行为，切换是执行行为

组织

操作系统通过PCB来对进程进行控制

程序可被多个进程共享，即多个进程可以执行同一个程序

通信

PV操作是低级通信方式，高级通信方式三类

共享存储

操作系统提供可共享使用的存储空间和同步互斥工具

要想让两个用户进程共享空间，必须通过特殊的系统调用实现

消息传递

• 直接通信：发送进程直接把消息发送给接收进程，并把消息挂在接收进程的消息缓冲队列上，接收进程从缓冲队列取得消息
• 间接通信：发送进程把消息发送到某个中间实体，接收进程从中间实体取得消息，又称为信箱通信方式

管道通信*

共享存储中的共享空间变为了缓冲区，只允许一边写入，另一边读出

属于半双工通信

线程多线程

线程是轻量级进程，自己不拥有系统资源。引入线程后，进程只作为除CPU以外系统资源的分配单元，而线程作为处理机的分配单元

• 线程与进程的比较

  • 调度 引入线程后，线程是调度的基本单位，进程是拥有资源的基本单位
  • 拥有资源 线程不拥有系统资源
  • 并发性 进程 线程都可以并发执行 提高了并发性和系统吞吐量
  • 系统开销 线程开销远小于进程
  • 地址空间和其他资源 进程的地址空间之间相互独立，同一进程的各线程共享进程资源
  • 通信 进程需要进程同步和互斥手段的辅助，以保证数据一致性。线程可直接读/写进程数据段来通信

• 线程有利于提高系统并发性，减少了每次切换所需的开销

• 多线程模型

  • 多对一
  • 一对一
  • 多对多

处理机调度

调度的概念

处理机调度是多道程序操作系统的基础，是操作系统设计的核心问题

• 调度的层次
  • 作业调度（高级调度）
  • 中级调度（内存调度）
  • 进程调度（低级调度）

调度的时机、切换与过程

时机

• 需要进程调度

  • 当前运行进程主动放弃处理机
  • 被迫放弃处理机

• 不能进程调度

  • 处理中断过程中
  • 该进程在系统内核程序临界区中
  • 在原子操作过程中

切换与过程

• 切换过程

  • 对原来运行进程各种数据的保存
  • 对新的进程各种数据的恢复

• 进程调度、切换是有代价的，并不是调度越频繁并发度越高

方式

• 非抢占
• 抢占

评价指标

• CPU利用率=忙碌时间/总时间

• 系统吞吐量=单位时间内完成作业的数量

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

  • 带权周转时间=作业周转时间/作业实际运行的时间

• 等待时间 指进程/作业等待处理机状态时间之和

  • 对作业来说，包括建立进程后的等待时间和作业在外存后备队列中等待的时间

• 响应时间 从用户提交到首次产生响应所用的时间

调度算法

• 先来先服务算法 选择最先进入队列的

  

• 短作业优先 选择完成时间最短的

  

• 优先级调度 选择优先级别最高的

  

• 高响应比优先调度 选择响应比最高的

  

• 时间片轮转调度 总是选择就绪队列中第一个进程，但仅能运行一个时间片

• 

• 多级反馈队列调度 时间片轮转调度算法和优先级调度算法的综合和发展

  

进程同步

进程同步基本概念

一个时间段内只允许一个进程使用的资源称为临界资源

//对临界资源的互斥访问
do{
    entry section;		//进入区	上锁
    critical section;	//临界区	实际访问资源的代码
    exit section;		//退出区	解锁
    remainder section;	//剩余区
}while（true）

互斥访问需要遵循的原则

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

实现临界区互斥的基本方法

单标志法

违背空闲让进原则

双标志先检查法

先检查后上锁，但两操作无法一气呵成

由于进程是并发的，可能两个进程同时访问临界区，违反了忙则等待的原则

双标志后检查法

先上锁后检查

违反了空闲让进和有限等待的原则，可能会产生饥饿

Peterson算法

//两个标志
flag[n];
turn=;

在进入区中先主动争取，再谦让，最后检查。没有遵守让权等待的原则

中断屏蔽方法

在某进程开始访问到结束访问都不允许被中断。

优点：简单高效

缺点：不适用于多处理机，只适用于操作系统内核进程，不适用于用户进程

TestAndSet指令

是用硬件实现的，执行过程不允许被中断，适用于多处理机环境

检查、上锁一气呵成

不满足让权等待

Swap指令

跟TSL逻辑一样

所有方案都无法实现让权等待的功能

信号量

信号量是一个变量（可以是一个整数，也可以是更复杂的记录型变量）

对信号量的操作只有3种：初始化，P操作，V操作

• 整型信号量

  检查、上锁一气呵成，避免了并发、异步导致的问题。不满足让权等待，会发生忙等

• 记录型信号量 （超高频考点）

  • 可以用记录型信号量实现进程互斥、进程同步

  •   typedef strcut{
          int value;
          strcut process *L;
      }semphore;
      
      void wait(semphore S){
          S.value--;
          if(S.value<0){
              block(S.L);
          }
      }
      
      void signal(semphore S){
          S.value++;
          if(S.value<=0){
              wakeup(S.L);
          }
      }
    

• 信号量机制实现互斥

  • 设置互斥信号量，初值为1
  • 临界区之前进行P操作
  • 临界区之后进行V操作

• 信号量机制实现同步

  • 设置同步信号量
  • 前操作之后执行V操作
  • 后操作之前执行P操作

• 信号量机制实现前驱关系

  • 为每一对前驱关系各设置一个同步变量
  • 在前操作后执行对应V操作
  • 在后操作之前执行对应P操作

生产者消费者问题

死锁

死锁概念

死锁预防

操作系统

原文：https://www.cnblogs.com/1012wenquan66/p/14054887.html