王道操作系统-进程管理

王道操作系统之进程管理笔记，包括进程调度算法、后背队列、调度算法细节、死锁、进程与线程、临界资源和临界区等内容。

汤子瀛操作系统-进程管理

• 细节
  • 时间片轮转
  • 最小松弛度算法
    • 若某一时间两个松弛度一样，则按照排队顺序来
  • 银行家算法答题模板（习题教材P78 例13）
• 教材
  • 子主题
  • 子主题
  • 同一个程序的一次执行可产生多个进程（fork子进程）
  • 进程创建的主要事件
    • 用户登录
    • 作业调度
    • 提供服务
    • 应用请求
  • 子主题
  • 整形信号量不满足让权等待原则
  • 进程是资源分配的基本单位
  • 线程是CPU调度和分配的基本单位
  • 用户级线程CPU调度对象：进程
  • 内核支持的线程
    • CPU调度对象：线程
  • 状态转变
    • 某进程所要求的一次打印输出结束
      • 该进程被 唤醒
      • 由阻塞态到就绪态
    • 绝不可能发生的是就绪态到阻塞态
      • 一般不会发生的是阻塞态到执行态（没得选才选这个）
    • 活动就绪变成静止就绪
      • suspend原语
    • 时间片用完
      • 执行态->活动就绪
    • 静止阻塞，当进程等待的事件出现，变成 静止就绪
    • 因终端的请求需要停下来查看其运行情况
      • 执行态->静止就绪
      • 阻塞态->静止阻塞
    • 用户态切换到系统状态
      • 访管指令
      • 中断
    • 王道
      • 进程撤销
        • 正常完成
        • 出现内存错误
      • 就绪队列的数目与CPU的效率无关
        • 跟响应时间有关
      • 对进程的控制和管理使用原语 P41 t29
  • 调用进程时候才分配CPU，创建进程不分配CPU，只分配进程资源
  • 创建进程
    • 分时系统
      • 典型事件：用户登录
    • 批处理系统
      • 作业调度
    • 由系统为应用进程创建新进程的事件
      • 提供服务
    • 设备分配不算
  • 各类型系统与之进程调度算法
    • 分时系统无作业调度
    • • https://www.douban.com/note/311010077/
        • 短进程优先调度算法不适用于分时系统（可能产生饿死）
    • FCFS和SJF无法保证及时处理,达不到实时系统的要求
      • 优先级符合实时系统
    • HRRN,RR,多级反馈队列符合分时
  • 临界区资源可以被中断
  • 判断：
    • 用户进程可以从Pcb中读出与本身运行状态相关的信息。（X）
      • 解析：用户进程不能读，得是系统级别的
    • 当进程由执行状态变为就绪状态时,CPU 现场信息必须被保存在PCB。（√）
      • 是在PCB而不是在系统栈
    • 信号量初值不能为负数（√）
    • wait，signal操作可以解决一切互斥问题（√）
  • 三种调度
    • 高级调度（作业调度）
      • 从外存的批处理后备作业队列中选取作业调度到内存
      • 批处理系统中
      • 时间片轮转不适合该调度
    • 中级调度（内存调度）
      • 应用在 分时系统 和虚拟存储的系统中
      • 从内存中将部分进程挪到外存中
      • 提高内存利用率和系统吞吐量
    • 低级调度（进程调度）
      • 分配给就绪队列的进程
      • 我们学的算法
  • 后备队列
    • 操作系统首先从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。
    • • 习题教材P75 例7
  • 调度算法细节
    • 必须采用抢占
      • RR
    • 必须采用非抢占
      • FCFS
    • 短作业优先算法的平均周转时间,平均等待时间最短
    • 能实现人机交互作用
      • 时间片轮转算法
        • 时间片的大小一般选择为【略大于一次典型的交换所需时间】
        • 影响因素
          • 系统响应时间
          • 就绪队列的数目
          • 系统的处理能力
    • 兼顾短作业和长作业
      • HRRN
    • 抢占式静态优先权算法 最容易引起进程长期等待
    • 进程刚完成I/O操作
      • ：表示刚从外存调度到内存，还没执行
    • 降低进程优先级最合理的时机
      • 当进程的时间片用完，调度程序需要调度其他程序进入处理机执行
    • 优先级：I/O型优先，系统进程优先，短作业优先，资源要求少的优先，动态优先权执行时间越长则优先级越低 交互型大于非交互型
    • EDF算法：选择调度截止时间最早算法
    • HRRN克服了饥饿
    • 同时到达的进程,要使得平均周转时间最小,按照从小到大的运行时间调度即可
      • 即HRRN
    • FCFS不利于I/O繁忙型的作业,利于CPU繁忙(长作业)的作业 P59 T3
      • 排队买奶茶例子
  • 死锁
    • 死锁的四个必要条件中，一般情况下，无法破坏的是【互斥使用资源】
    • 【一次性分配策略】破坏了请求与保持条件，【资源有序分配策略】破坏了循环等待条件
    • 死锁预防：资源有限分配
      • 一次性分配所有的资源
    • 死锁避免：银行家算法
    • 死锁检测：资源分配图
      • 一个状态为死锁状态的充分条件是 当且仅当该状态的资源分配图是【不可完全简化】时
    • 死锁解除
      • 【撤销进程】和【剥夺资源】是解除死锁的两个常用方法
  • 系统开销比率
  • 实时OS的优先级倒置是指：【高优先级进程被低优先级进程延迟或阻塞】
  • 在多道程序的环境中，不会因竞争【可抢占资源】而产生死锁
• 王道2.1.8 P39
  • 进程与线程
    • T15
      • 多对一模型中的线程切换在线程库中完成
        • 不需要使用系统调用函数
        • 不需要在内核级切换进程,即不需要内核的支持
      • 引入线程后,进程仍然是资源分配的单位
        • 引入线程前,进程是资源调度和并发的基本单位
      • 线程本身不具有资源
    • T3
      • 每个进程只能访问自己的地址空间,访问别人的会发生指针越界错误
    • T2: 线程可以独立执行程序
      • 但不能脱离进程运行 T32
    • 不同进程内的线程也能并发,只是开销高一点 T33
    • 进程中的某线程的栈指针不能被别人访问
    • T47
      • 进程可以创建进程和线程
      • 线程可以创建线程
      • 线程不能创建进程
    • T54
      • 父子进程不共享虚拟地址空间
      • 父子进程有不同的PCB
        • 进程复制的时候复制了PCB、文件结构体，不止拷贝了文件描述符
    • T53
      • 操作系统为每一个 内核级线程 建立一个线程控制块
        • 只有在一对一模型中 操作系统为每个用户级线程建立线程控制块
      • 用户级线程可以在不支持内核级线程的操作系统上实现'
  • T20
    • 数据栈段
      • 未初始化的全局变量和静态变量在数据段的BSS段
      • 未赋值的局部变量
      • 临时使用的变量
    • 数据堆
      • malloc,new
    • 正文段
      • 代码和赋值数据段
      • 赋值的全局变量
  • T46
    • 进程间的通信
      • 共享文件(如:管道)
      • 消息传递
      • 共享内存
      • 文件映射
      • 套接字
  • 设备分配不需要创建进程
  • T49管道
    • 不能实现双向传输
      • 半双工不属于双向
    • 存在与内存当中
    • 无名管道:容量大小通常为内存中的一页
    • 管道空:读操作阻塞
    • 管道满:写操作阻塞
    • 只能有一个读进程
      • 有可能有多个写进程
• 王道 2.2.7 P58
  • T27
    • • 中断向量地址不是中断服务例行程序的入口地址 中断向量才是
    • 中断发生的时候由硬件保护和更新PC
      • 因为无法用软件完成(软件无法事先知道JMP的位置)
  • T28
    • • 进程在 内核程序临界区 才说不能进行处理机调度
  • 好题积累:T32,T31
• 王道2.3.7 P91
  • T5
    • • 访问临界区过程io被其他进程占领CPU,则其他进程不能访问被锁住的临界区部分,但可以访问没有被锁住的部分
  • T7:临界资源和临界区
    • 临界区:PV操作,加减锁
    • T10
      • 临界资源
        • 磁盘不是临界资源,是共享资源 多个资源可同时访问
      • 可重入的程序代码 (不允许任何修改的代码, 即不会修改数据的代码) 又叫 "纯代码"T20
        • 并发执行顺序不影响结果,如print("Hello!")
      • 公用队列是临界资源
    • T27
  • T11
    • 进程可以在无限的时间内完成
      • 比如可以一直打开微信不关
    • 进程是有结构的:PCB,数据段,程序段
      • 该结构与代码运行顺序没有关系 因此一刷时误选该选项
    • 并发进程进行同步的原因是并发进程是异步的
  • T13:原语
    • PV操作是 低级进程通信原语
      • 不是系统调用命令,因为用户不能进行PV
    • 原语
    • 机器指令
      • 关中断
      • 开中断
    • T15:不能运行在用户态
      • 是操作系统内核的一部分,不是操纵系统内核
  • 管程
    • T16:定义共享数据结构和各种进程在该数据结构的全部操作
      • 相当于类封装函数
        • 编译器负责每个进程互斥进入管程
    • 类:定义不共享数据结构和各种进程在该数据结构的全部操作
      • 没有类程的说法
    • T29:管程的signal与信号量机制的V操作不同
      • 管程的条件变量不会加减
    • 管程是语法范围,无法创建和撤销,是静态的
    • • 可解决同步和互斥问题
  • T19 进程同步的初始值由用户决定
    • 比如empty=n
  • T21
    • 共享程序段必须是可重入代码
  • T40:TSL
    • TSL中要么处于就绪态要么处于运行态
    • 不会放弃CPU操作
    • while语句不在关中断中执行
  • T48
    • Peteson
    • Swap指令
    • TestAndSet
    • 忙等
  • T49
    • 让权等待
      • 应用
        • 管程
        • PV操作(信号量机制)
      • 不能进入临界区的执行态进程立即放弃CPU
• 王道2.4.7 P130
  • 解除死锁不采用的方法
    • 从非死锁处抢夺资源
  • T13：无中断，不并发
  • T19
    • 破坏“请求与保持”不会发生死锁，更不谈回退
      • 可能会发生“饥饿”
  • T22
    • 读者-写者问题（读者优先法）不会产生死锁，但会产生“饥饿”
  • 死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁
    • 用来检测死锁
  • T32 银行家算法没有限制用户申请资源的顺序
    • 其中的安全序列顺序只是在判断是否安全的时候的一个顺序，安全之后可以按随意顺序申请资源
• 二刷选择题
  • 线程
    • 线程没有自己独立的地址空间
    • 线程包含CPU现场，可以独立执行程序
      • 但不能脱离进程独立运行
    • 不管是否引入线程，进程都是资源分配的单位
    • 引入线程后
      • 线程是调度和分派的单位
      • 提高并发执行程度
    • 用户级线程中，其切换由应用程序完成，与内核无关
    • 多线程的应用 （键盘输入没必要用多线程，因为很慢）
      • 进行矩阵乘法
      • 请求http资源
  • 封闭性
    • 执行结果只取决于程序本身
    • 失去封闭性：并发的过程会使得结果不同
  • 进程调度
    • 当运行进程出错的时候，进程不可继续运行
      • 此时释放处理机
        • 必然发生进程调度
    • 进程切换
      • • 线程切换则不会
      • 代价比线程切换高
  • 对进程的管理和控制通过原语来实现
  • 进程通信
    • 全局变量是针对一个进程而言的，因此不能作为进程间通信的渠道
      • 进程间通信要求速度高
        • 数据库在外存，虽然也可以交换数据，但速度不满足进程间通信
  • 进程优先级切换
    • 进行完IO进入就绪队列的进程，应当提高优先级，让其尽快处理IO结果，因为其没办法长期保存输入/输出数据
      • 因此优先级中，IO繁忙的先做，CPU繁忙后做
    • 降低优先级应该在时间片用完之后
  • 父子进程不共享虚拟地址空间
  • 关于并发
    • IO和CPU可以并行操作
      • 同时如果题目说输入设备和输出设备各一个，则IO里面的输入输出也可以再并发
  • 执行的前驱关系实际上是同步
    • 需要信号量的参与
  • 临界资源
    • 公用队列是临界资源
      • 一次只能一个进程用
    • 属于临界资源的硬件有打印机、磁带机等,软件有消息缓冲队列、变量、数组、缓冲区
    • 磁盘是共享资源
  • 进程的并发不需要信号量
    • 只需要并发
  • PV操作是两个过程，每个过程包括关中断，执行，开中断
  • 管程
  • 阻塞队列最多有n个进程
    • 死锁的时候
  • TSL中
    • 退出临界区的进程唤醒的是就绪态的进程而不是阻塞态的
    • 等待进入临界区的进程不会主动放弃CPU
      • 一直在while循环中
• 二刷大题
  • 两道作业批处理
    • 内存里面最多两道作业
    • 每次调度一个
    • 两道中的一道处理完之后，从外存调度一道进来
  • PV操作
    • 取号机默认是互斥资源
    • 叫号问题里面：有empty必然有full
    • 读者-写者问题中，互斥资源不用再被保护
    • semaphore的empty可以直接用if语句判断
    • 读者写者问题每个资源一个互斥锁
    • 信箱要互斥访问
    • 看上交学长的哲学家
      • 奇数偶数法
      • 数目控制法
    • A，B线程读x，C写x
      • 互斥锁要为AB各分配一个
        • 因为AB可以同时读x
        • C进程要写x，要P(mutex x2);P(mutex x1)
    • 9.13：最难的是理发师问题，之后要多看！
  • 死锁
    • 并发性排序
    • 永远不要回答 “会发生死锁”，应该回答“可能发生死锁”
    • Work Need Allocation Work+Allocation
      • 四列
        • 第二行的Work=第一行的Work+Allocation
    • 资源分配图的分析中，执行了一次申请边，则资源指向进程
• 王道思维导图
  • 读者写者问题
    • 读者优先
    • 写者优先
  • 在生产者消费者问题中,若缓冲区资源大于1,则需要设置互斥信号量来防止其互斥访问
  • 实现互斥的P操作(mutex)一定要在实现同步的P操作之后,不然会发生死锁 (原因是位于临界值的时候一个人抢了mutex资源而等待另一个人,但另一个人因为没有mutex所以也无法释放第一个人所需要的资源,造成相互等待,其中两个人所需要的资源:一个需要mutex,另一个需要真的资源)
  • 子主题