OS_第二章进程管理

OS OS

Created At : 2024-02-27 21:52

Count:5.3k Views 👀 :

Comment:

第二章-进程管理

第二章-进程管理

进程的描述
- 程序执行
  - 顺序执行
    - 顺序性
    - 封闭性
    - 可再现性
  - 并发执行
    - 间断性
    - 非封闭性
    - 不可再现性
- 进程的定义
  - 进程是具有独立功能的程序在一个数据集合上运行的过程，它是 系统进行资源分配和调度的独立单位
  - 进程由 程序段、相关数据段以及PCB（进程控制块） 三部分组成
  - 进程与程序的区别：进程是 运行的程序 ，是系统 资源分配调度的基本单位 ， 进程是动态的概念 ，而程序是静态的概念
- 进程的特征
  - 结构特征：程序段、数据段、PCB
  - 动态性： 最基本的特性 ，进程实体具有一定的生命周期，而程序只是一组有序指令的集合
  - 并发性：多个进程共存在内存中，且能在一段时间内同时运行
  - 独立性：指的是进程可以独立运行、独立获得资源、独立接受调度的基本单位， 未建立PCB的程序都不能作为一个独立的单位参与运行
  - 异步性：指的是进程运行过程相互独立，推进速度不可预知，进程走走停停
- 进程的状态转换
  - 三种基本状态转换
    - 就绪状态：进程已分配到除了CPU以外的所有必要资源
    - 执行状态：进程已获得CPU，其程序正在执行的状态
    - 阻塞状态：指的是正在执行的进程由于发生某件事 （IO请求、申请缓冲区失败等） ，无法继续执行的状态
  - 五种基本状态转换
    - 创建状态： 创建进程时因所需的资源尚不能得到满足 ，比如系统尚无足够的内存使进程装入其中，此时创建工作尚未完成，进程不能被调度运行，于是把此时进程所处的状态称为创建状态，当其获取了所需的资源以及对其PCB初始化工作完成后，创建状态转为就绪状态
    - 终止状态：当一个 进程到达了自然结束点 ， 或是出现了无法克服的错误 ， 或是被操作系统终结 ， 或是被其他有终止权的进程终结 ， 它将进入终止状态 。 进入终止态的进程不能再执行 ，但在操作系统中依然保留一个记录，其中保存状态码和一些计时统计数据供其他进程收集，完成上述操作后，OS删除该进程， 将其PCB清零，并将空白PCB归还OS
  - 引入挂起、激活操作的状态转换
    - 挂起（Suspend操作）的引入
      - 终端用户的需要：debug
      - 父进程请求：有时父进程希望挂起自己的某个子进程，以便考察和修改该子进程或协调各子进程间的活动
      - 负荷调节的需要：实时系统中工作负荷较重，已可能影响到对实时任务的控制时，系统把一些不重要的进程挂起，以保证系统能正常运行
      - OS的需要:OS有时需要挂起某些进程，以便检查运行中的资源使用情况或进行记账
- 进程控制块PCB
  - OS用于管理控制的数据结构
    - 内存表
    - 设备表
    - 文件表
    - 进程表 ( PCB )： PCB作为进程实体的一部分，拥有描述进程情况及控制进程运行所需的全部信息的记录性数据结构
  - PCB的作用
    - 作为独立运行基本单位的标志
    - 能实现间断性运行方式
    - 提供进程管理所需要的信息
    - 提供进程调度所需要的信息
    - 实现与其他进程的同步与通信
  - PCB的信息内容
    - 进程标识符： 唯一地标识一个进程
      - 外部标识符：为了 方便用户（进程） 对进程的访问，为每个进程设置一个外部标识符，由创建者提供
      - 内部标识符：为了 方便OS对进程的使用 ，在OS中为进程设置了唯一的内部标识符，通常是进程的序号
    - 处理机状态：通用、PC、PSW、用户栈指针寄存器
    - 进程调度信息：进程状态、进程优先级、事件及其他
    - 进程控制信息：程序和数据地址、进程同步通信机制、资源清单、链接指针
  - PCB的组织方式
    - 线性方式
    - 链接方式
    - 索引方式
进程控制 (OS内核：系统态和用户态的概念补充)
进程同步
- 进程同步的概念
  - 同步操作： 同步操作是指在执行一个操作时，当前线程或进程会一直等待操作完成，然后再继续执行后续的操作。 在同步操作中，执行顺序是严格按照代码的编写顺序来进行的，每个操作都会阻塞当前线程或进程，直到操作完成为止。
  - 异步操作： 异步操作是指在执行一个操作时，当前线程或进程不会等待操作完成，而是继续执行后续的操作。 在异步操作中，不会阻塞当前线程或进程，而是通过回调函数、事件或轮询等方式来处理操作完成后的结果。这使得可以在等待耗时操作的同时，继续执行其他任务，提高了效率。
  - 进程同步： 进程同步 是指在 多进程或多线程的并发执行环境中 ，为了 保证数据的一致性和正确性 ，对进程或线程之间的 执行顺序进行协调和控制 的一种机制。进程同步中的"同步"更多地指的是协调和控制多个进程或线程之间的执行顺序，以确保数据的一致性和正确性。 这种同步并不仅仅是顺序执行，而是要求在多个进程或线程之间建立一种合理的协调机制，以防止竞态条件、死锁等问题的发生。
  - 两种形式的制约关系
    - 间接相互制约关系（ 进程互斥 ）例如：多个进程并发执行时，因 互斥地访问共享系统资源 而产生的相互制约关系
    - 直接相互制约关系（ 进程同步 ）例如：为完成某任务而建立多个进程，这些 进程因相互合作而形成的制约关系，输入进程A和计算进程B之间因共享一个缓冲区而形成的制约关系
    - 进程互斥是实现进程同步的一个重要手段
- 进程同步的操作
  - 临界资源： 一段时间内仅允许一个进程使用的资源 叫临界资源
    - 打印机
    - CPU
    - 磁带机
  - 临界区： 进程中访问临界资源的那段代码 称为临界区(critical section)， 进程互斥地进入自己的临界区 --> 可实现 进程对临界资源的互斥访问
  - 进程同步机制准则
    - 空闲让进：当无进程处于某临界区时，可允许一个请求进入“对等”临界区的进程立即进入自己的临界区
    - 忙则等待：当已有进程进入自己的临界区时，所有企图进入“对等”临界区的进程必须等待
    - 有限等待：对要求访问临界资源的进程，应保证该进程能在 有限时间内进入 自己的临界区
    - 让权等待：当进程不能进入（ 临界资源被其他进程占用 ）自己的临界区时，应 释放处理机
- 解决进程互斥的软硬件方法
  - 软件方法：虽然可以解决进程互斥进入临界区的问题，但有一定难度，且存在很大的局限性，现在已很少采用
  - 硬件方法
    - 关中断：进入锁测试之前关闭中断，这样进程在临界区执行期间 计算机系统不响应中断，从而不会引发调度 ，保证了对锁的测试和关锁操作的连续性和完整性，保证了互斥（ 进入临界区关中断，离开临界区开中断 ）
      - 缺点：滥用关中断权力可能 导致严重后果
      - 关中断时间过长会 影响系统效率 ，限制处理器交叉执行程序的能力
      - 关中断方法也 不适用于多CPU系统 ，因为不能防止进程在其它CPU上执行
    - Test-and-Set指令： 原子操作指令，不可中断
      - 为每个临界资源设置一把锁lock，空闲为false，占用为true， 可以看到，当某个临界资源被占用，其他进程不断地循环测试，占用CPU资源，不符合让权等待的原则
    - Swap指令：对换指令，也称为XCHG指令
      - 为每个临界资源设置一个 全局变量lock ，为每个进程中再利用一个 局部变量key
    - 硬件指令可以实现进程互斥，但不符合让权等待的原则
- 信号量机制
  - 整型信号量：与一般整型变量不同，整型信号量只能通过 原子操作,Wait(S)和Signal（S）访问，一般称为P、V操作 ，注意到 Wait操作时，只要是信号量S<=0，就会不断地测试，忙等，不符合《让权等待》的原则
  - 记录型信号量：记录型信号量机制是 一种不存在忙等现象的进程同步机制，但在采取了《让权等待》的原则后，出现了多个进程等待访问同一临界资源的情况， 为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表指针list，用于链接上述的所有等待进程
  - AND型信号量：为了 避免死锁，将进程需要的所有资源一次性全部分配给进程，待使用完后再一起释放 （死锁发生的例子：假设有两个进程A，B都需要资源G、H，A先申请完资源G，B申请完资源H，然后A去申请资源H，B申请资源G，两进程就此僵持，发生死锁）
  - 信号量集：引出原因：其一：记录型信号量一次需要多个单位时，需要进行多次P、V操作，低效且增加死锁的概率；其二：为确保系统的安全性，当所申请的资源数量低于某一下限值时，必须进行管制，不予以分配，因此，当进程申请某类临界资源时，在每次分配前，必须测试资源的数量，判断是否大于可分配的下限。
    - 信号量集的几种特殊情况：
    - Swait(S, d, d） ：信号量集中 只有一个信号量S，但允许每次申请d个资源，当现有资源少于d时不予分配
    - Swait(S, 1, 1） ：信号量已 退化为一般的记录型信号量 （ S>1时 ），或 互斥信号量（S=1时）
    - Swait(S, 1, 0） ：一种很特殊很有用的信号量操作。 当S>=1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。它相当于一个可控开关
- 信号量的应用基础
  - 利用信号量实现进程互斥
    - 设mutex为互斥信号量，初值为1，取值范围为{-1，0，1}
  - 利用信号量实现前驱关系
经典进程同步问题
- 同步问题程序设计要领
  - 每个并发子程序关于 互斥信号量的wait与signal操作必须在同一子程序中成对出现
  - 资源信号量的wait与signal操作 同样需成对出现，但 可以分别处于不同的并发子程序中
  - 并发子程序中的多个wait操作的顺序不能颠倒 ，即 资源信号量wait操作执行在前而互斥信号量wait操作执行在后 ，否则可能引起死锁
  - 每个并发子程序中的多个 signal 操作的执行顺序无关紧要
  - 非临界资源访问操作无需放到临界区中
- 生产者——消费者问题：一群生产者进程生产产品，将产品提供给消费者进程，为使二者可以 并发执行 ，设置一个具有长度为n的 循环缓冲区； 异步运行方式 ：生产者、消费者进程都以异步方式运行 ；必须保持同步 ：不允许消费者进程去空缓冲区取，不允许生产者进程往满缓冲区放。
  - 记录型信号量解决方案
    - 1. mutex实现循环缓冲区的互斥访问
    - 2. empty、full为资源信号量
  - AND信号量解决方案
  - 优化方案：在记录型信号量解决方案中，设置一个mutex用于实现生产者——生产者、生产者——消费者、消费者——消费者对循环缓冲区的互斥访问，这其中，生产者——消费者对循环缓冲区的互斥访问是没有必要的，所以分别为输入指针与输出指针设置互斥信号量，仅有生产者——生产者、消费者——消费者之间的互斥访问，提高了并发度
  - 管程解决方案
- 哲学家进餐问题：5个哲学家环坐在五张椅子上，并全部奉行交替地进行思考和进餐的生活方式，桌子上仅有五支筷子，均匀排放在哲学家之间，哲学家饥饿时便试图去取用圆桌上最靠近他左右两端的两支筷子，且只有在同时拿到两支筷子时方可进餐，进餐完毕则把筷子放回原处，并继续进行思考。
  - 问题剖析 ：五支筷子作为临界资源，初值为1， 利用记录型信号量解决时，会出现死锁的情况：当五位哲学家同时饥饿并且各自拿起左边的筷子
  - 死锁产生的四个必要条件：故破坏其必要条件是解决死锁问题的关键
    - 互斥访问
    - 占有和等待：已经得到某个资源还要申请其他资源
    - 不可抢占
    - 环路等待
  - 避免死锁的三种方法: ①：双筷并举②：奇偶有别 ③进餐限数
    - 双筷并举（破坏条件2）
    - 奇偶有别：奇数号哲学家先拿左筷后拿右筷；而偶数号哲学家则相反（破坏条件4）
    - 进餐限数字（破坏条件4）
- 读者——写者问题：读者写者问题是指保证任何 写者进程 必须与其他进程互斥地访问共享数据对象的同步问题
  - 读者优先的解决方案：设置wmutex=1，用于实现写进程与其他进程的互斥访问；同时设置读者进程计数变量readercount=0，用于记录读者进程的数量，在实现读者进程与写进程互斥访问的时候，读者进程有“前人栽树，后人乘凉”的特点，故是读者进程优先与写进程：
  - 读写公平解决方案：设置公平互斥锁 S = 1，保证新来的读者进程与队伍前的写进程存在前驱关系
    - 写进程
    - 读进程
  - 写者优先的解决方案：在读写公平的基础上，仿照读者优先，为写者进程增加一个写等待队列，由领头羊为每一个写者进程争抢，设置变量writercount=0，用于描述写者进程数，实现领头羊功能，并增加互斥锁 W=1，用于实现对变量writercount的互斥访问
    - 读者进程：与读写公平的读者进程没有区别
    - 写者进程：在读写公平方案的基础上，套了一层P/V（W）
  - 读者数限定（读者优先）：只需要设置一个资源信号量rmax=N即可
管程
进程通信（进程之间的信息交换）
- 进程通信的类型
  - 共享存储器系统：相互通信的进程 共享某些数据结构或共享存储区
    - 基于共享数据结构的通信方式（ 效率低下，低级通信 ）
      - 进程公用某些数据结构 （例如生产者-消费者问题中的缓冲区）实现进程间的信息交换。操作系统仅提供共享存储器，由程序员负责对公用数据结构的设置和进程间同步的处理， 适用于相对少量的数据，效率低下，低级通信
    - 基于共享存储区的通信方式（ 高级通信 ）
      - 进程共享某些数据结构和存储区 ，需要通信的 进程在通信前先向系统申请一块共享存储区的分区并将其附加到自己的地址空间中 ， 用完后将其归还给共享存储区 ，例如 linux中的shmget()、shmat()、shmdt()、shmctl() Windows中的内存映射文件
  - 管道通信系统：管道指的是 用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件（高级通信）
    - 写进程 以 字节流 形式将数据 送入管道 ； 读进程 从管道中 接收(读)数据
    - 对pipe的访问要互斥
    - 读写进程要保证 同步的合作关系
  - 消息传递系统 ： 进程不必借助任何共享存储区或数据结构 ，而是 以格式化的消息（Message）为单位 ，将 通信的数据封装在消息 中，并利用操作系统提供的 通信原语 ，在 进程间进行消息传递，完成进程间的数据交换 。（ 高级通信 ）
    - 直接通信方式：发送进程通过OS提供的原语，直接把message发送给目标进程
      - 直接通信原语
      - 消息的格式：由 消息头 与正文部分构成，分为 定长/变长 两种
      - 进程的同步方式：不论是发送进程还是接收进程，在完成消息的发送或接收后，都存在两种可能性，即进程或者继续发送(或接收)或者阻塞
        
        发送进程和接收进程 均阻塞 ：进程之间 紧密同步 ， 进程间无缓冲
        
        发送进程不阻塞、接收进程阻塞 ： 应用最广 的进程同步方式。平时 发送进程不阻塞 ，可以 尽快地把一个或多个消息发送给多个目标 ； 接收进程 平时阻塞， 直到发送进程发来消息时才被唤醒
        
        发送进程和接收进程 均不阻塞 ： 较常见 的同步形式。平时，发送进程和接收进程都忙于自己的事情， 仅当发生某事件无法继续运行时 才自己阻塞起来等待
      - 通信链路：（1）由发送进程在通信之前用显式的“建立连接”命令(原语)请求系统为之建立一条通信链路，使用完后拆除（2）通信方式：单向/双向
    - 间接通信方式：进程的通信通过中间实体（如共享数据结构等，信箱）来完成
      - 信箱的结构（一种数据结构）：由 信箱头 和 信箱体 （若干个存放信息的信息格）构成， 信箱头 ：存放有关 信箱的描述信息 ； 信箱体 ：存放 消息/消息头
      - 信箱通信原语
      - 信箱的类型
        
        私用邮箱： 用户进程为自己建立一个新邮箱，并作为该进程的一部分。邮箱的拥有者有权从邮箱中读取消息，其他用户则只能将自己构成的消息发送到该邮箱中 。这种私用邮箱可采用 单向通信链路 的邮箱来实现。拥有 该邮箱的进程结束时，邮箱也随之消失
        
        公用邮箱： 操作系统创建并提供给系统中的所有核准进程使用 。核准进程既可把消息发送到该邮箱，也可以从邮箱中读取发送给自己的消息。显然，公用邮箱应采用 双向通信链路 的邮箱来实现。 公用邮箱在系统运行期间始终存在
        
        共享邮箱： 由某进程创建 。创建时或创建后指明它是可共享的，同时需指出共享进程（用户）的名字。 邮箱的拥有者和共享者都有权从邮箱中取走发送给自己的消息
    - 直接通信方式实例，应用消息缓冲队列通信机制
      - 消息缓冲队列通信机制中的数据结构
      - 发送原语
      - 接收原语
  - 客户机——服务器系统（ 高级通信 ）
    - 套接字Socket
    - 远程过程调用RPC
线程：在OS中引入线程，为了 减少程序在并发执行时所付出的时空开销 ，使OS具有 更好的并发性

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2542608082@qq.com