《操作系统》进程与线程

难点和常考点

• 进程与程序的区别和联系
  • 进程是动态的，程序是静态的
  • 进程 = 程序+数据+PCB
  • 程序 = 一组有序的指令集合
  • 进程是动态创建消失的，程序是永久存在的，可长期保存
  • 进程= 程序的一次执行过程
  • 程序 = 一组代码的集合
  • 进程可以执行一个或几个程序，程序也可以构成多个进程
  • 进程可以创建进程，程序不可以创建程序
• 死锁与饥饿
  • 定义
    • 死锁 = 两个或多个进程无限地等待一个事件，而该事件只能由这些等待进程之一来产生
    • 饥饿/无限期阻塞 = 进程在信号量内无穷等待的情况
  • 差别
    • 饥饿并不代表系统一定会死锁，但至少有一个进程的执行被无限期推迟
    • 进入饥饿的状态进程可以只有一个，但进入死锁状态的进程鼻血大于等于2个
    • 处于饥饿状态的基础可以是一个就绪进程，但是死锁状态的进程必定时阻塞进程
• 同步与互斥的区别和联系
  • 同步：进程之间竞争使用临界资源，只能让他们逐个使用
  • 互斥：进程之间协同完成任务，在关键点上等待另一个进程发来的消息，以便协同一致

线程

常考知识点

• 交换数据
  • 进程之间不能直接交换数据，但可以利用OS提供的共享文件（管道），信息传递系统，共享存储区来进行通信
  • 全局变量是针对一个进程而言的，不同的进程拥有不同的代码和数据段，不能通过全局变量来交换进程间数据
  • 临界资源一次只能为一个进程所用
• 进程的特性
  • 进程失去封闭性（进程执行的结果之只取决于进程本身）后，不同速度下的执行结果不同
  • 进程被建立后，随着进程运行的正常或不正常而撤销
  • 进程不是一个完整的程序
    • 进程是动态的，程序是静态的
    • 进程是暂时的，程序是永久的
    • 进程至少由代码、数据、PCB组成，程序仅需要代码和数据
  • 一个进程是程序在一个数据集上的一次运行过程；运行于不同的数据集，会形成不同的进程
• 进程与进程的关系
  • 进程与进程之间完全隔离，线程与线程之间没有隔离
    • 一个进程的状态变化可能引起另一个进程的状态变化
    • 如打印机进程结束后可能改变另一个等待打印机的进程
• 各种状态
  • 死锁的进程位于阻塞态，不可能所有进程都处于就绪态，但可以所有的进程都处于阻塞态（死锁的时候）
  • 就绪队列进程的多少与处理器的效率无关，只有当就绪队列为空时，CPU进入等待态，CPU效率下降
• 进程里的各种信息
  • 正文段
    • 存放二进制代码，常量
      • 全局赋值变量，常量值123
  • 数据堆段
    • 动态分配的存储区
      • malloc动态分配的存储区
  • 数据栈段
    • 临时使用变量
      • 未赋值的局部变量，函数调用实参传递值

进程概念与特征

• 进程
  • 定义
    • 进程是程序的一次执行过程
    • 进程是一个程序及其数据在处理机上顺序执行时所发生的活动
    • 进程是具有独立功能的程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位
  • 特征
    • 动态性
    • 并发性
    • 独立性
    • 异步性
  • 引入进程原因
    • 使多道程序并发执行，提高资源利用率和系统吞吐量
  • 其他考点
    • 进程实体/进程映像 = PCB+程序段+相关数据段
    • 进程映像是静态的，进程是动态的，程序是静态的
    • 进程控制块（PCB）是进程的唯一标志
    • 系统资源 = 处理机，存储器和其他设备服务于某个进程的时间【系统资源类似于处理机的时间片】

进程的状态与切换

• 五种状态
  • 运行态Running 该进程占用CPU
  • 就绪态Ready 进程获得了除处理机外的一切所需资源，一旦得到处理机就可以立即运行
  • 阻塞态Blocked 该进程正在等待某一事件发生而暂停运行，即使给他CPU控制权，它也无法运行
  • 创建态 New 进程正在被创建时的状态
  • 结束态Exit 进程正在从系统中消失时的状态
• 进程转换
  • 就绪态$\to$运行态
    • 进程被调度，获得处理机资源（分派处理机时间片）
  • 运行态$\to$就绪态
    • 时间片用完后，不得不让出处理机
    • 可剥夺的OS中，当有更高优先级的进程就绪时，调度程序将正在执行的进程转换为就绪态
  • 运行态$\to$阻塞态
    • 进程请求某一资源（外设）的使用和分配时
    • 等待某一事件的发生时（I/O操作的完成）
      • 进程以系统调用的方式请求OS提供服务，这个过程系统从用户态转换为核心态
      • 该过程为主动行为
  • 阻塞态$\to$就绪态
    • I/O操作结束或中断结束时
    • 该过程为被动行为，需要其他相关进程的协助

进程的控制结构/数据结构

• PCB
  • 进程存在的唯一标识
  • 一个进程的存在，必然会有一个PCB，如果进程消失了，PCB也会随之消失
• PCB包含信息
  • 进程描述信息
    • 进程标识符PID：标识各个进程，每个进程都有一个并且唯一的标识符
    • 用户标识符UID：进程归属的用户，用户标识符主要为共享和保护服务
  • 进程控制和管理信息
    • 进程当前状态：如new、ready、running、waiting、blocked等
    • 进程优先级：进程抢占CPU时的优先级
  • 资源分配清单
    • 有关内存地址空间或虚拟地址空间的信息
    • 所打开文件的列表和所使用的I/O设备信息
  • CPU相关信息
    • CPU中各个寄存器的值
    • 进程被切换时，CPU的状态信息都会被保存在相应的PCB中以便进程重新执行时，从断点处继续执行
• 组织PCB
  • 链接方式
    • 把统一状态的PCB链成一个队列，不同状态对应不同队列
    • 把处于阻塞态的进程的PCB，根据阻塞原因，排成多个阻塞队列
  • 索引方式
    • 把统一状态的进程组织在一个索引表中
    • 如就绪索引表，阻塞索引表
• 程序段
  • 能被进程调度程序调度到CPU执行的程序代码段
  • 程序可以被多个进程共享，即多个进程可以运行同一个程序
• 数据段
  • 可以是进程对应的程序加工处理的原始数据
  • 可以是程序执行时产生的中间或最终结果

进程控制

• 创建
  • 定义和过程
    • 允许一个进程创建另一个进程
    • 允许子进程继承父进程所拥有的资源
    • 创建进程的过程：
      • 申请一个空白的PCB，并向PCB中填写一些控制和管理进程的信息，比如进程的唯一标识等
      • 为该进程分配运行时所必需的资源，如内存资源
      • 将PCB插入到就绪队列，等待被调度运行
  • 对应事件
    • 中断登陆系统，作业调度
    • 系统提供服务
    • 用户程序的应用
      • 设备分配不需要创建进程
• 终止
  • 定义和过程
    • 有3种终止方式：正常结束，异常结束以及外界干预
    • 当子进程被终止时，其在父进程处继承的资源应当还给父进程
    • 当父进程被终止时，该父进程的子进程就变为孤儿进程
    • 终止进程的过程
      • 查找需要终止的进程的PCB
      • 如果处于执行状态，则立即终止该进程的执行，然后将CPU资源分配给其他进程
      • 如果还有其他子进程，则将该进程的子进程交给1号进程接管
      • 将该进程所拥有的全部资源都归还给操作系统
      • 将其从PCB所在队列中删除
  • 对应事件
    • 正常结束
    • 异常结束
    • 外界干预
• 阻塞
  • 定义和过程
    • 当进程需要等待某一事件完成时，它可以调用阻塞语句把自己阻塞等待
    • 一旦被阻塞等待，只能由另一个进程唤醒
      • 阻塞进程的过程
        • 找到将要被阻塞进程标识号对应的PCB
        • 如果该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行
        • 将该PCB插入到阻塞队列中去
  • 对应事件
    • 请求系统资源失败
    • 等待某种操作的完成
    • 新数据尚未到达或无新任务可做
• 唤醒
  • 定义和过程
    • 进程由运行转变为阻塞状态是由于进程必须等待某一事件的完成
    • 处于阻塞状态的进程是绝对不可能自我唤醒
    • 如果某进程正在等待I/O事件，需由别的进程发消息给它
    • 只有当该进程所期待的事件出现时，才由发现者进程用唤醒语句叫醒它
    • 唤醒进程的过程
      • 在该事件的阻塞队列中找到相应进程的PCB
      • 将其从阻塞队列中移出，重置状态为就绪状态
      • 把该PCB插入到就绪队列中，等待调度程序调度；
  • 对应事件
    • 释放I/O设备的进程
    • 提供数据的进程

进程的通信

• 定义
  • 进程通信是指进程之间的信息交换
• 低级通信方法
  • PV操作
• 高级通信方法
  • 共享存储，如共享内存，共享文件系统
  • 信息传递，需要发送消息和接受消息两个原语
  • 管道通信
    • 需要满足的能力 = 互斥+同步+确定对方的存在
    • 缓冲区只允许一边写入，另一边读出，所以管道只能采用半双工通信
    • 管道是一种文件，所以两个进程可以通过文件系统交换数据
  • 共享存储：进程$\leftrightarrows$共享空间$\leftrightarrows$进程
  • 信息传递：进程$\leftrightarrows$进程
  • 管道通信：进程$\leftarrow$缓冲区$\leftarrow$进程$\rightarrow$缓冲区$\rightarrow$进程

进程的上下文切换

• 上下文
  • 上下文是指某一时刻CPU寄存器和PC的内容
• 进程上下文切换
  • 上下文切换时指一个进程切换到另一个进程的过程
• 上下文切换的实质
  • 上下文切换实质是处理机从一个进程的运行转到另一个进程上运行，这个过程中，进程的运行环境产生了实质性的变化
• 上下文切换的消耗
  • 有些处理器提供多个寄存器组，上下文切换指需要简单改变当前寄存器组的指针
• 上下文切换的场景
  • 某个进程时间片耗尽时
  • 进程在系统资源不足时，要等到资源满足后才可以运行
  • 进程通过sleep将自己挂起
  • 由优先级更高的基础运行时
  • 发送硬件中断时
• 上下文切换的流程
  • 挂起一个进程，保存CPU上下文，包括PC和其他寄存器
  • 更新PCB信息
  • 把进程的PCB移到相应的队列
  • 加载另一个进程执行，更新其PCB
  • 跳转到新进程PCB中的PC所指向的位置执行
  • 恢复处理机上下文
• 调度和切换的区别
  • 先有资源的调度，才有进程的切换
    • 调度：决定资源分配给哪个进程的行为，是一种决策行为
    • 切换：实际分配的行为，是一种执行行为

线程

常考知识点

• 关于线程的特征
  • 线程是处理机调度的基本单位，可以独立执行程序
  • 没有相同的进程，但是调用在不同进程中的线程可以相同
• 关于线程可共享的东西
  • 线程没有自己独立的地址空间，每个线程只拥有自己的独立的栈空间
  • 线程之间可以共享进程的资源（如代码段，堆空间，数据段，打开的文件）
  • 线程之间不能共享虚拟地址空间，线程之间不能共享栈指针
• 线程的并行与并发
  • 同一进程或不同进程内的线程都可以并发执行
  • 进程之间可以并发但不可以并行，同一进程之间的线程可以并行
• 其他
  • 键盘驱动程序不能体现多线程系统的特点，因为计算机一般只有一个键盘

进程与线程的比较

线程的概念与特征

• 定义
  • 线程是进程当中的一条执行流程
  • 线程之间可以并发运行且共享相同的地址空间
  • 线程自己不拥有系统资源，但可与同属一个进程的程序共享进程所有的资源
  • 线程同样具有三种基本状态：运行态+阻塞态+就绪态
• 为什么引入线程
  • 减少程序在并发执行过程中所付出的时空开销，提高操作系统的并发能力
• 引入线程提高系统并发性原因
  • 线程可以导致平均每次切换所需开销变少，使更多线程参与并发

线程组成和控制

• 每个线程配置一个线程控制块TCP
  • 功能
    • 记录控制和管理线程的信息
  • 组成
    • 线程标识符
    • 一组寄存器
    • 线程运行状态
    • 优先级
    • 线程专有存储区
    • 堆栈指针
  • 控制线程
    • 创建线程
    • 终止线程

线程的分类

多线程模型

• 多对一模型
  • 定义
    • 多个ULT映射到一个KLT
  • 优点
    • 线程管理在用户空间进行，效率高
  • 缺点
    • 如果一个线程阻塞，其他进程都会被阻塞
    • 任何时刻，只有一个线程能访问内核
    • 多个线程不能同时在多个处理机上运行
• 一对一模型
  • 定义
    • 每个ULT映射到一个KLT
  • 优点
    • 一个线程被阻塞，运行调度另一个线程运行，并发能力强
  • 缺点
    • 每创建一个用户线程，就要创建一个对应的内核线程，开销大
• 多对多模型
  • n个ULT映射到m个KLT，n$geq$m
• 优点
  • 克服了多对一模型的并发度不高的缺点
  • 克服了一对一模型的一个用户进程占用太多内核线程而开销打的缺点

处理机调度

常考知识点

• 作业是用户提交的，以用户任务为单位
• 进程是系统自动生成的，以操作系统控制为单位

基本概念

• 调度是处理机进行分配，即从就绪队列中按一定算法（公平，高效的原则）选择一个进程并将处理机分配给他运行，以实现进程并发地执行
• 调度是多道程序OS的基础：调度是OS设计的核心问题
• 层次分类模型图

• 高级调度、作业调度
  • 是内存与辅存的调度，从后备队列中调度作业
  • 每个作业只调入调出一次
  • 通常存在于多道批处理系统中
• 中级调度、内存调度
  • 提高内存利用率和系统吞吐量
  • 将暂时不能运行的进程调度到外存等待，设为挂起态，最后修改状态为就绪态，挂在就绪队列上
  • 是存储器管理中的对换功能
• 低级调度、进程调度
  • 从就绪队列中选取一个进程，调度频率很高
  • 各种OS都必须配置这种调度
• 三种调度的联系
  • 作业调度为进程活动做准备，进程调度使进程正常活动
  • 中级调度将暂时不能运行的进程挂起，中级调度处于另外两个调度之间
  • 调用频率：作业调度<内存调度<进程调度
  • 进程调度使最基本的，不可或缺

调度的实现

• 调度程序结构图

• 调度器的组成
  • 用于调度和分派CPU的组件
  • 排队器
    • 按策略给就绪进程排出一个或多个队列
  • 分派器
    • 从就绪队列中取出进程，并分配CPU
  • 上下文切换器
    • 在对处理机进行切换时，会发生两对上下文的切换操作
• 调度的时机
  • 先调度再切换
  • 进程从一个状态到另一个状态变化时，就会触发一次调度
  • 调度时机举例
    • 运行的进程运行完毕
    • 运行的进程时间片用完
    • 运行的进程所需资源未准备好
    • 运行的进程自我阻塞
    • 运行的进程出现错误
• 进程的切换
  • 不能进行调度与切换的情况
    • 在处理中断的过程中
    • 进程在OS内核临界区中
    • 其他需要完全屏蔽中断的原子操作过程中
  • 可以进行调度与切换的情况
    • 发生引起调度条件且当前进程无法继续进行下去时（非剥夺调度）
    • 中断处理结束或自陷处理结束后，被置上请求调度标志（剥夺方式的调度）
    • 在进程结束时能进行处理机调度
    • 创建新进程后能进行处理机调度
    • 在系统调用完成并返回用户态时能进行处理机调度
    • 进程处于临界区时，只要不破坏临界资源的使用规则，就不影响处理机的调度
  • 切换的过程
    • 将原进程的信息推入当前进程的内核堆栈中，并更新堆栈指针
    • 内核从新进程的内核栈中装入新进程的信息
    • 内核更新当前运行的进程空间指针，重设PC寄存器后开始运行新的进程
  • 调度方式
    • 非抢占式调度
      • 优点
        • 实现简单，系统开销小，适合批处理系统
      • 缺点
        • 不适合分时和大多数的实时系统
    • 抢占式调度
      • 优点
        • 有利于提高系统吞吐率和响应效率
      • 缺点
        • 必须遵循一定的准则（如优先级，短进程优先，时间片原则）

调度相关指标

• 调度最终考虑的元素：特定用户的要求 + 系统整体效率 + 调度算法的开销
• 常用指标
  • CPU利用率：$\frac{CPU有效工作时间}{CPU有效工作时间 + CPU空闲等待时间}$
  • 等待时间：等待CPU的时间
  • $周转时间（t_i）= 作业完成时间 - 作业提交时间$
  • $带权周转时间（w_i） = \frac{周转时间}{作业实际运行时间}$
  • $平均周转时间 = \frac{t_1+t_2+\cdots+t_i}{i}$
  • $平均带权周转时间 = \frac{w_1+w_2+\cdots+w_i}{i}$

调度算法

• FCFS先来先服务
  • 平均等待时间 = 1.575
  • 平均周转T = 2.5
  • 平均带权周转时间 = 5.625

• 短作业优先算法

  • 平均等待时间 = 1.175
  • 平均周转时间 = 2.1
  • 平均带权周转时间 = 3.525

• 高响应比优先调度算法

  • 响应比$R_p = \frac{等待时间+要求服务时间}{要求服务时间}$（值越大，调用优先级越高）

• 其余算法

  • 优先级调度算法
    • I/O繁忙型作业优于计算繁忙作业【因为I/O操作要及时完成，无法长时间保存数据】
    • 系统进程优于用户进程
  • 时间片轮转算法
    • 若时间片过大，退化为FCFS
    • 若时间片过小，切换频繁，处理机开销增大
  • 多级反馈队列算法
    • 综合考虑
      • 优先级数量，优先级之间的转换规则
      • 就绪队列数量，就绪队列的调度算法
      • 进程在就绪队列间的迁移条件

调度算法对比

同步与互斥

常见考点

• 可重入代码/纯代码：一种允许多个进程同时访问的代码，如进程映像中的共享程序段
• PV操作实现的同步的S的初值由用户确定，如果期望的信息还没发送，则对应的初值为-，若信息已存在，则初值为非0的正数，PV操作实现的互斥的S的初值为1
• 执行P操作的进程处于运行态；若P操作后S<0，则表示没有可用资源，该进程进入阻塞状态
• 判断代码中的语句是否要互斥执行
  • 不同范围的变量不需要互斥
  • 对变量赋值前，都有声明语句的话，不需要互斥
• 信箱通信是一种间接通信

基本概念

• 引入同步互斥原因
  • 因为并发进程是异步的，为了协调进程之间的相互制约关系，所以引入同步互斥
• 进程异步性
  • 由于系统的资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进
• 并发过程执行产生的两种相互制约关系
  • 同步：进程A应在进程B之前执行
  • 互斥：进程A和进程B不能再同一时刻执行
• 临界资源
  • 一次仅允许一个进程使用的资源（如物理设备，共享变量，共享数据，共享缓冲区，公用队列）
• 共享资源
  • 可被多个进程同时使用的资源；如可重入代码/纯代码、共享程序段、磁盘、非共享数据
• 临界区
  • 访问临界资源的那段代码
  • 如果n个进程涉及到了同一个变量A，则A的相关临界区 = 访问临界资源A的那段代码 = n个代码段
• 同步机制遵循的准则
  • 空闲让进：临界区空闲，允许一个进程进入【运行进程访问空闲的临界资源】
  • 忙则等待：有进程进入临界区时，其他进程需要等待【两个进程不能同时进入临界资源】
  • 有限等待：请求访问的进程应保证在有限时间内进入临界区【进程等待进入临界区的时间是有限的】
  • 让权等待：进程不能进入临界区时，应该立即释放处理器，防止进程忙等待【不能进入临界区的执行态进程立即放弃CPU】

进程同步与互斥机制：硬件和软件方法

• 硬件方法【此方法实现同步时不能实现让权等待】
  • 中断屏蔽法
    • 硬件指令方法
      • swap指令
      • TestAndSet指令
• 软件方法
  • 单标志法
  • 双标志法
  • Peterson's Algorithm【满足有限等待但不满足让权等待】
  • 记录型信号量引入阻塞机制，可以让权等待

进程同步与互斥机制：管程

• 定义
  • 管程定义了共享数据结构和各种进程在该数据结构上的全部操作
  • 结构类似于Class，把对共享资源的操作封装起来
  • 管程支持进程互斥；任何时候只有一个进程在管程中执行
  • 管程不仅能实现进程间互斥。还能实现进程间同步
  • java采用管程机制
  • Java中管程相关代码:sunchronized关键字,wait(),notify(),notifyAll()
• 组成
  • 管程的名字
  • 局部于管程内部的共享数据结构或者共享变量说明
  • 对管程内的数据结构进行操作的一组过程
  • 对局部于管程内部的共享数据设置初始值的语句
  • 管程的组成都是基于管程内部的
• 管程中设置的条件变量
  • 定义
    • 阻塞原因定义为条件变量condition
  • 操作
    • x.wait：阻塞进程，将其插入到阻塞队列中
    • x.signal：唤醒进程，将其插入到就绪队列中
  • 与信号量相似点
    • wait/signal类似于信号量的P/V操作，实现进程的阻塞/唤醒，但不能说和PV操作相同
  • 与信号量不同点
    • 条件变量没有值，仅实现排队等待功能
    • 信号量有值，这个值反映了剩余资源数

进程同步与互斥机制：互斥锁

• 定义
  • 解决临界区最简单的工具
• 特点
  • 通常采用硬件机制实现
  • 常用于多处理器系统
• 缺点
  • 忙等待
• 代码
  • accquire() 获取锁
  • release() 释放锁

进程同步与互斥机制：信号量和PC操作

• PV操作定义
  • P操作
    • 将信号量值S减一，表示申请占用一个资源
    • 如果S<0，表示已经没有可用资源，执行P操作的进程被阻塞
    • 如果S$\leq$0，表示现有资源足够使用，执行P操作的进程继续执行
    • 举例：当信号量的值为2时，表示有2个资源可以使用，当信号量的值为-2时，表示有两个进程正在等待使用这个资源
  • V操作
    • 将信号量S加1，表示释放一个资源，即使用完资源后归还资源
    • 如果S$\leq$0，表示有某些进程正在等待该资源
    • 由于我们已经释放出一个资源了，因此需要唤醒一个等待使用该资源的进程，使之运行下去
• 常见问题
  • S>0表示有临界资源可使用，这时候为什么不需要唤醒进程
    • 所谓唤醒进程是从就绪队列中唤醒进程，信号量的值大于0表示有临界资源可供使用
    • 即此时没有进程被阻塞在这个资源上，因而不需要唤醒，正常运行即可
  • S=0表示没有临界资源可供使用，为什么要唤醒进程
    • V操作时先执行S+1,也就是把信号量的值加1后才变成了0
    • 在之前信号量的值为-1，即有一个进程正在等待这个临界资源
  • 其他概念
    • 原子操作就是要么全部执行，要么都不执行，不能出现执行到一半的中间状态的操作
    • PV操作时低级进程通信语言
  • 信号量分类
    • 整型信号量
      • 该信号量被定义为一个用于表示资源数目的整型量S
      • 该机制不遵循让权等待的准则
    • 记录型信号量
      • 一种不存在忙等现象的进程同步机制
      • 需要一个用于代表资源数目的变量Value
      • 需要一个进程链表L，用于链接所有等待该资源的进程
      • wait操作 = P操作 = 请求一个资源
      • signal操作 = V操作 = 释放一个资源
  • 信号量应用
    • 信号量实现同步
      • 用资源P操作，释放资源V操作，此时信号量表示资源量
      • 同步信号量初始值不确定，可以设置
      • 信号量最大值 = 最多可以请求的资源数
      • 信号量最小值 = 最大值/初始值-最大请求值
    • 信号量实现互斥
      • PV操作夹着互斥资源，此时信号量表示互斥量
      • 互斥信号量初始值 = 1，表示临界区只运行一个进程进入，从而实现互斥
      • 互斥信号量 = 0，表示临界区已经有一个进程进入，临界区外还没有进程等待
      • 互斥信号量<0，表示临界区中有一个进程
      • 互斥信号量：表示临界区外等待进入的进程数
      • 利用信号量实现前驱关系

信号量和PV操作的代码定义

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

//信号量定义
typedef struct semaphore{
  int value;
  struct pcb * list;

}

//P操作
void P(semaphore s){
  s.value --;
  if(s.value < 0)
    asleep(s.list);
}

//V操作
void V(semaphore s){
  s.value ++;
  if(s.value <=0)
    wakeup(s.list);
}

同步与互斥的代码实现

• 进程同步
  • 定义一个同步信号量，并初始话为当前可用资源的数量
  • 在优先级较高的操作后面执行V操作，释放资源
  • 在优先级较低的操作的前面执行P操作，申请占用资源

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

semaphore S =0;//初始化同步信号量，表示当前可用资源为0

P1(){
  代码 1;
  代码 2;
  V(S);//代码2运行完后，释放资源
  代码 3;
}

P2(){
  P(S);//代码4运行前先申请占用资源，保证代码4一定在代码2之后运行
  代码4;
  代码5;
  代码6;
}

• 进程互斥
  • 定义一个互斥信号量，并初始化为1
  • 把对于临界资源的访问置于P操作和V操作之间
  • P操作和V操作必须成对出现
  • 缺少P操作就不能保证对临界资源的互斥访问
  • 缺少V操作就会导致临界资源永远得不到释放，处于等待态的进程永远得不到唤醒

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

semaphore mutex = 1;//初始化互斥信号量，初始化为1

//进程P1
P1(){
  ···
  P(mutex);//申请占用资源
  临界区
  V(mutex);//释放资源
}
//进程P2
P2(){
  ···
  P(mutex);//申请占用资源
  临界区
  V(mutex);//释放资源
}

经典同步问题

生产者-消费者问题

• 问题描述

  • 系统中有一组生产者进程和一组消费者进程
  • 生产者进程每次生产一个产品放入缓冲区
  • 消费者进程每次从缓冲区中取出一个产品并使用
  • 任何时刻，只能有一个生产者或消费者可以访问缓冲区

• 同步与互斥关系和设置的信号量

  • 题目的同步互斥关系
    • 缓冲区：生产者、消费者共享一个初始为空，大小为n的缓冲区
    • 同步关系1：只有缓冲区没满时，（优先级高），生产者才能把产品放入缓冲区（优先级低），否则必须等待
    • 同步关系2：只有缓冲区不空时（优先级高），消费者才能从中取出产品（优先级低），否则必须等待
    • 互斥关系：缓冲区是临界资源，各进程必须互斥地访问
  • 设置的信号量
    • empty
      • 同步信号量（对应同步关系1）
      • 表示生产者还能生成多少，即还能放入缓冲区多少产品
      • 该数量小于等于0，则生产者不能生产
      • 初始化为n
    • full
      • 同步信号量（对应同步关系2）
      • 表示消费者还能从缓冲区取出多少，即当前缓冲区已有产品的数量
      • 该数量小于等于0，则消费者不能进行读取
      • 初始化为0
    • mutex
      • 互斥信号量
      • 实现对缓冲区的互斥访问
      • 初始化为1

• 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

semaphore empty = n;//同步信号量
semaphore full = 0;//同步信号量
semaphore mutex = 1;//互斥信号量

//生产者

producer(){
  while(1){
    P(empty);//申请一个生产者可用数量
    p(mutex);//互斥使用缓冲区
    把产品放入缓冲区
    V(mutex);//释放缓冲区占用
    V(full);//增加一个消费者可用数量
  }
}

//消费者
consumer(){
  P(full);//申请一个消费者可用数量，若该信号量小于等于0，则阻塞，不进行消费
  p(mutex);//互斥使用缓冲区
  从缓冲区中取出一个产品
  V(mutex);//释放缓冲区占用
  V(mutex);//增加一个缓冲区/生产则可用数量
}

读者-写者问题

• 问题描述
  • 一些进程只读数据，称“读者”
  • 另一些会对数据进行修改，称“写者”
  • 写者与写者互斥，写者与读者互斥
  • 读者之间不互斥
• 同步互斥关系与信号量
  • 写进程
    • 互斥访问，保证写者和读者互斥，写者和写者互斥
  • 读进程
    • 若为第一个读者，实现与写者的互斥，若为后继读者，则不需要
    • 若为最后一个读者，需要考虑唤醒阻塞的写者，以便能够让写者有机会进入临界区
• 设置信号量
  • writemutex:控制写者互斥的访问共享数据，初值为1；
  • readCount:读者计数器，记录当前读者数，初值为0；
  • readmutex:控制读者互斥访问readcount，初值为1；
• 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

//写进程
do{
  wait(writemutex);
  //写者完成编写
  signal(writemutex);
}while(true);

//读进程

do{
  wait(readmutex);
  readcount ++;
  if(readcount == 1)
  wait(writemutex);
  signal(readmutex)

  //执行读

  wait(readmutex);
  readcount --;
  if(readcount ==0)
  signal(writemutex);
  signal(readmutex);

}while(true);

哲学家进餐问题

• 问题描述
  • 5个哲学家围绕一张圆桌而坐，桌上放着5根筷子，哲学家进餐时需要同时拿起左边和右边的筷子
  • 思路一
    • 对于每一个哲学家，先等待左边的筷子可用，然后等待右边的筷子可用
    • 吃饭
    • 放下两根筷子
  • 问题
    • 极端情况下，5个哲学家同时拿起左边的筷子，势必会造成每个人都只有左筷子而没有右筷子，造成死锁现象
  • 解决方法
    • 同时最多允许四个哲学家围坐在桌子周围
    • 只有哲学家两侧的筷子都可用时才允许他捡起筷子
  • 代码

1
2
3
4
5
6
7

do{
  Swait(chopstick[(i+1)%5],chopstick[i]);
  //eat
  Ssignal(chopstick[(i+1)%5,chopstick[i]]);
  //think
}while(true);

死锁

常考点

• 每个进程都分得一个资源，而且还有多余的资源可让任意一个进程使用，则不出现死锁
• 多道程序技术要求进程间能够实现并发，需要实现进程调度保证CPU的工作效率，而并发性的实现需要中断功能的支持
• 系统资源不足不是系统产生死锁的原因，资源不足只会对进程造成饥饿
• 设进程有X个，每个进程最多请求使用3个A资源，系统有11个A资源，则不会出现死锁的最大X为
  • 2*X + 1 =11，解得X = 5（极端情况时，每个进程分配2个A资源，只要有一个资源就不会出现死锁）

死锁概念

• 死锁是多个进程因为竞争资源而造成的一种互相等待
• 死锁的充分条件：资源分配图中每个资源只有一个，又出现了环路

死锁产生原因

• 系统资源的竞争【空间上】
  • 系统中不可剥夺资源不足以满足多个进程
  • 只有对不可剥夺资源的竞争才可能产生死锁
• 进程推进顺序非法【时间上】
  • 进程运行时，请求和释放资源的顺序不当
  • 系统对独占资源分配不当

产生死锁的必要条件

• 需要同时满足以下四个条件
  • 互斥条件：多个线程不能同时使用同一个资源
  • 不剥夺条件：进程A已经拥有资源1，在自己使用完之前不能被其他进程获取
  • 请求并保持条件：进程A已经有资源1，想申请资源2，但是资源2被进程B持有，进程A处于等待状态，但是进程A不释放资源1
  • 循环等待条件：两个线程获取资源的顺序构成了环形链

如何解决死锁

• 死锁预防
  • 破坏互斥条件
    • 缺点：打印机等临界资源只能互斥使用
    • 举例
      • 方法不可行
  • 破坏不剥夺条件
    • 常用于状态易于保存和恢复的资源（CPU的寄存器和内存资源）
    • 举例
      • 剥夺资源法
  • 破坏请求并保持条件
    • 可能会导致饥饿现象
      • 举例
        • 一次性分配策略
  • 破坏循环等待条件
    • 可采用顺序资源分配法，但是编号必须相对稳定，限制了新类型设备的增加
      • 举例
        • 资源有序分配策略
• 死锁避免
  • 安全性算法
  • 银行家算法
  • 死锁包含在不安全状态之中【系统处于安全状态时，一定无死锁；系统处于不安全状态时，不一定出现死锁】
  • 死锁避免时不会限制用户申请资源的顺序，需要进程运行所需资源的总量信息，不会给可能导致死锁的进程分配资源
• 死锁检测
  • 资源分配图
    • 资源分配图是一个有向图，用于表示某时刻系统资源与进程之间的状态
    • 圆圈表示进程，框表示一类资源，从进程到资源的边叫做请求边，从资源到进程的边叫做分配边
  • 死锁定理
    • S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的
• 死锁解除
  • 资源剥夺法
    • 资源剥夺法：挂起某些死锁进程，并抢占它的资源
    • 撤销进程法：强制撤销部分甚至全部死锁进程并剥夺这些进程的资源
    • 进程回退法：让一个或多个进程回退到足以回避死锁的地步
• 各策略比较
  • 死锁预防
    • 资源分配策略
      • 保守，宁可资源闲置
    • 各种可能模式
      • 一次请求所有资源，资源剥夺，资源按序分配
    • 主要优点
      • 适用于突发式处理的进程，不必进行剥夺
    • 主要缺点
      • 效率低，进程初始化时间延长，剥夺次数过多，不便灵活申请新资源
  • 死锁避免
    • 资源分配策略
      • 是预防和检测的折中（运行时判断是否可能死锁）
    • 各种可能模式
      • 寻找可能得安全允许顺序
    • 主要优点
      • 不必进行剥夺
    • 主要缺点
      • 必须知道将来的资源需求，进程不能被长时间阻塞
  • 死锁检测
    • 资源分配策略
      • 宽松，只要允许就分配资源
    • 各种可能模式
      • 定期检查死锁是否已经发生
    • 主要优点
      • 不延长进程初始化时间，允许对死锁进行现场处理
    • 主要缺点
      • 通过剥夺解除死锁，造成损失

安全性算法和银行家算法例题举例

安全性算法解法

银行家算法解法