2020 操作系统复习 -第二、三章 处理机管理

2020 操作系统 -第二、三章 处理机管理

第二章 进程的描述与控制

进程是资源分配和独立运行的基本单位
2.1 前驱图和程序执行
2.1.1 前驱图
前趋图：有向无循环图（DAG），用于描述进程之间执行的先后顺序
? 前趋图中的每个结点：可以表示一条语句、一个程序段或一个进程
? 结点间的有向边：表示两个结点之间存在的偏序关系或前趋关系“→ ”
2.1.2 程序顺序执行
程序顺序执行：必须按照某种先后次序逐个执行。
程序顺序执行时有如下特征：
? 顺序性：一个程序各个部分的执行，严格地按照某种先后次序执行。
? 封闭性：程序在封闭的环境下运行，即程序运行时独占全部系统资源。
? 可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，都将获得相同的结果。
程序顺序执行的特性为程序员检测和校正程序的错误带来很大方便。 2.1.3 程序的并发执行
程序的并发执行：指一组在逻辑上互相独立的程序或程序段在执行时间上客观上互相重叠，即一个程序或程序段的执行尚未结束，另一个程序（段）的执行已经开始的方式。 程序并发执行时的特征：
? 间断性（异步性）：互斥、同步
? 失去封闭性：共享资源 → 失去封闭性
? 不可再现性：失去封闭性 → 失去可再现性
程序并发执行时的不可再现性是绝对不允许的；因此应采取措施使并发程序保持其可再现性：引入进程，对并发执行的程序加以描述和控制。
程序并发执行条件（Bernstein 条件）：

第三章 处理机调度与死锁

3.1 处理机调度的层次和调度算法的目标
3.1.1 处理机调度的层次
一个作业从提交开始，往往要经历三级调度：高级调度、中级调度、低级调度。
? 高级调度（长程/作业/宏观调度）
从外存后备队列中选择作业进入内存就绪队列。
在批处理系统中，大多配有作业调度。
作业调度执行频率较低，时间尺度是分钟、小时或天。
? 中级调度（交换调度）
在内存和外存对换区之间按照给定的策略选择进程对换。
解决内存紧张问题，提高内存的利用率和系统吞吐量。
? 低级调度（短程/CPU/进程/微观调度）
任务是从就绪队列中选择一个进程来执行并由分派程序（Dispatcher）分配处理机。
是 OS 中最基本的调度。
时间尺度通常是毫秒级的，由于低级调度算法的频繁使用，要求在实现时做到高效。
常采用非抢占（非剥夺）方式和抢占（剥夺）方式两种。
3.1.2 处理机调度算法的目标
处理机调度算法的共同目标：
? 资源利用率