第一章 引论
1、操作系统定义（P1）
操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。
是一组控制和管理计算机硬件和软件资源、合理地对各类作业进行调度以及方便用户使用的程序的集合。
2、操作系统的作用（P2）
1. OS作为用户与计算机硬件系统之间的接口 2. OS作为计算机系统资源的管理者 3. OS实现了对计算机资源的抽象
3、推动操作系统发展的主要动力（P4）
1. 不断提高计算机资源的利用率 2. 方便用户
3. 器件的不断更新迭代 4. 计算机体系结构的不断发展
4、多道批处理系统的特征及优缺点（P8）
特征：多道性、无序性、调度性 优点：
1. 资源利用率高 2. 系统吞吐量大 缺点：
1. 平均周转时间长
2. 无交互能力（单道、多道都是）
5、分时系统和实时系统特征的比较（P12）
1. 多路性（实时系统的多路性主要表现在系统周期性地对多路信息的采集、以及对多个对象或多个执行机制进行控制。 分时系统中的多路性则
和用户有关，时多时少。）
2. 独立性
3. 及时性:（实时系统对及时性的要求更严格,
实时控制系统以控制对象要求的开始截止时间或
完成截止时间来确定。 ）
4. 交互性:实时系统的交互性仅限于访问某些专用服务程序。
5. 可靠性:实时系统对可靠性的要求更高,否则经济损失及后果无法预料。
6、操作系统的基本特征（P14）
（并发、共享、虚拟和异步 其中并发特征是操作系统最重要的特征是其他特征的前提）
1. 并发性
2. 共享性（互斥共享方式、同时访问方式） 3. 虚拟性（时分复用技术（虚拟处理机技术、虚拟设备技术）、空分复用技术（虚拟磁盘技术、虚拟存储器技术））
4. 异步性（进程的异步性：进程是以人们不可预知的速度向前推进的）
7、操作系统的主要功能（P18）
1. 处理机管理功能（进程控制（1、进程互斥方式：进程或者线程在对临界资源进行访问时，应采取互斥方式；2、进程同步方式：相互合作去完成共同任务的诸进程货线程）、进程通信、调度（作业调度、进程调度））
2. 存储器管理功能 （内存分配、内存保护、地址映射、内存扩充）
3. 设备管理功能（缓冲管理、设备分配、设备处理）
4. 文件管理功能（文件存储空间的管理、目录管理、文件的读/写管理和保护）
5. 用户接口（命令接口（联机用户接口、脱机用户接口）、程序接口、图形接口）
第二章 进程管理
1、程序顺序执行时的特征（P34）
1. 顺序性：严格按照程序所规定的次序执行。
2. 封闭性：程序在封闭环境下运行，系统中
所有资源的状态只有本程序才能改变它。
3. 可再现性：只要初始条件相同，无论怎样
执行，其结果都是相同的。
2、程序并发执行时的特征（提高了系统吞吐量）（P36）
1. 间断性：并发执行的实体之间相互制约，造成程序的执行出现间断，而不连续。
2. 非封闭性：多个程序共享系统资源，因而其状态有多个程序改变，从而失去封闭性。
3. 不可再现性：封闭性的失去必然导致不可再现性。
3、进程及其特征（P37）
进程是进程实体的运行过程，是系统进行资源
分配和调度的一个独立单位。
进程是程序的一次执行
进程实体：由程序段、相关的数据段和PCB构成
特征： 结构特征
动态性（进程最基本的特征）
并发性（引人进程的目的：为了使其进程实体能和其他的进程实体并发执行；而程序（没有建立PCB）不能并发执行）
独立性 异步性
4、进程的基本状态及其转换图（P38）
1. 就绪(Ready)状态 2. 执行状态
3. 阻塞状态 （典型事例：请求I/O、申请缓冲空间等）
就绪时间片完I/O完成进程调度阻塞I/O请求执行
5、引入挂起状态的原因（P39）
1. 终端用户的请求 2. 父进程请求 3. 负荷调节的需要 4. 操作系统的需要
6、具有挂起状态的进程状态及其转换图
执行O挂/起请求I激活活动静止就绪挂起就绪释放激活活动静止释放阻塞挂起阻塞
7、进程控制块及其作用（P41）
PCB是一种数据结构，是进程实体的一部分，
记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。
作用：
1. 使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。
2. PCB是进程存在与否的唯一标志,随着进程
的建立而建立,随着进程的撤消而撤消。创建进程就是创建PCB。。。
8、进程之间的两种制约关系（P48）
1. 间接制约——竞争资源——进程互斥
2. 直接制约——相互合作——进程同步
9、临界资源（P48）
OS中把一次只能被一个进程使用的资源成为临界资源。
10、临界区（P50）
进程中访问临界资源的那段代码称为临界区。
11、同步机构应遵循的规则（P50）
空闲让进、忙则等待、有限等待、让权等待
12、利用信号量实现前驱关系算法
P( 54 ) —— P( 55 )
13、经典同步算法（生产者－消费者问题, 哲学家就餐问题和读者－写者问题）
略
14、进程通信的类型（P65）
低级：信号量
进程通信 共享存储器系统（基于共享数
据结构或存储区的通信方式）
高级 消息传递系统（直接、间接）
管道通信系统（必须提供的协
调能力：互斥、同步、确定对方是否存在）
15、线程的定义（P72）
现代OS引入的比进程更小的可以独立运行、调度的基本单位，是轻型实体，不拥有资源。
16、线程和进程比较
线程又称为轻型进程，通常一个进程都拥有若干个线程，至少也有一个（多线程OS中的进程不是一个可执行的实体）
1、调度：传统OS中，进程是拥有资源的基本单位，独立调度、分派的基本单位。引入线程后，则把线程作为调度和分派的基本单位，而进程作为拥有资源的基本单位
2、并发性：引入线程的OS中，进程之间可以并发执行，在一个进程中的多个线程之间也可以；这样使得OS具有更好的并发性，从而能更加有效的提高系统资源的利用率和吞吐量
3、拥有资源：线程不能拥有资源
4、系统开销：就切换代价而言，进程远高于
线程
17、线程的属性（P73）
1. 轻型实体
2. 独立调度和分派的基本单位 3. 可并发执行 4. 共享进程资源
第三章 处理机调度与死锁
1、高级调度（P84）
又称为作业调度。即从外存的后备队列中选择一个作业，为它创建进程，分配必要的资源，并将新进程插入主存的就绪队列上。注意：分时系统和实时系统无作业调度。
JCB（作业控制块）；是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息
2、低级调度（P86）
又称进程调度或短程调度，即从就绪队列中选择一个进程进入运行状态（非抢占方式、可抢占方式）。调度的对象是进程（多批道处理、分时、实时三种类型的OS中都有）
3、中级调度（P87）中程调度
为了提高内存利用率和系统吞吐量（引入目的），为此，应使那些暂时不能运行的进程不再占用内存资源，而将它们调至外存。适当时机再将其调回内存。这种调度称为中级调度。
4、进程调度的两种方式（P86）
1、非抢占方式（一旦给进程分配处理机，一直让他运行下去，直到完成再把处理机分配给其他进程）
2、抢占方式（允许调度程序根据某些原则去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一个进程）
5、抢占的原则（P87）
1. 优先权原则
2. 短作业（进程）优先原则 3. 时间片原则
中的进程。
算法采用抢占式调度策略。
执行的进程在规定的时间片内为执行完毕，则进入下一级队列的队尾，新进程则进入第一级队列的队尾。
性能：（较好的性能，能满足各种类型的用户）
6、操作系统选择调度方式和调度算法的若干准则（P90）
1、终端型作业用户 2、短批处理作业用户 1. 面向用户的准则（周转时间短、响应时间快、 截止时间的保证、优先权准则）
2. 面向系统的准则（系统吞吐量高、处理机利用率好、各类资源的平衡利用）
7、周转时间（P92）
周转时间：是指从作业被提交给系统开始，到作业完成为止的这段时间间隔
周转时间 = 完成时间 - 到达时间 待权周转时间 = 周转时间 / 服务时间
8、针对各种调度算法（先来先服务，短进程优先，优先权），计算周转时间、带权周转时间, 平均周转时间、平均带权周转时间 9、吞吐量
指在单位时间内系统所完成的作业数
10、多级反馈队列调度算法的原理、性能
该算法用于进程调度，主要是为解决前面各种进程调度算法存在的各种不同问题而设计的一种考虑综合因素的调度算法。其思想如下：
1、设置多个就绪队列，不同队列具有不同优先级，第一个队列优先级最高，以后次之。
给不同队列分配不同大小的时间片，第一个队列最小，以后次之（皆为前者的二倍）。有的系统也将最后一级队列不划分时间片。
2、当有一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS（先来先服务）原则排队等待调度。当轮到该进程执行时，如果它能在该时间片内完成，便可准备撤离系统；若不能则将它放在第二列的队尾。。。。。。
3、仅当前一级队列为空时才调度下一级队列
3、长批处理作业用户
11、死锁、产生死锁原因、必要条件（P103）
死锁是指两个或多个进程由于资源竞争而造
成的一种僵局，若无外力作用，这些进程将永远无法向前推进。
产生死锁的原因：
1. 竞争资源（可剥夺和非剥夺性资源、竞争非剥夺性资源、竞争临时性资源）
2. 进程推进顺序非法（请求和释放资源的顺序不当）
必要条件：
1. 互斥条件：进程间必须互斥使用某些资源
才可能产生死锁。
2. 请求保持条件：进程已经占有至少一个资源，但又提出了新的资源请求。
3. 不剥夺条件：进程已经获得的资源不能被剥夺。
4. 环路等待条件：在发生死锁时，必然存在一个进程——资源环形链。
12、处理死锁的基本方法（P105）
1. 预防死锁：通过设置某些限制条件，破坏四个必要条件中的一个或几个。该方法比较简单，但由于限制条件过于严格，往往导致系统资源利用率和吞吐量低。
2. 避免死锁：不需事先预防，但在资源的动态分配时，用某种方法防止系统进入不安全状态，从而避免死锁。该方法比较难于实现，但往往可获得较高资源利用率和系统吞吐量。
3. 死锁的检测与解除：允许系统产生死锁，但能及时检测出来，并通过某些措施解除。该方法实现难度最大，但往往可获得较好的资源利用率和系统吞吐量。
13、预防死锁的方法（P106）
预防死锁的方法是使四个必要条件中的第2、3、4个条件不能成立，来避免发生死锁。至于必要条件1，因为他是由设备固有性能决定的，不仅不能改变，还应加以保证。（互斥条件破坏不了）
1. 摒弃“请求和保持”条件：资源静态分配 2. 摒弃“不剥夺”条件：资源的动态分配 3. 摒弃“环路等待”条件：资源有序分配
14、安全状态（P107）
所谓安全状态，是指系统能按某种进程顺序(P1, P2, …，Pn)(称〈P1, P2, …, Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
15、银行家算法
P( 109 )
16、死锁定理（P113）
S状态是死锁的充分条件是，当且仅当S状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理
第四章 存储器管理
1、程序装入的方式（P119）
1. 绝对装入方式：完全按照目标程序中所给定的地址装入内存，即目标程序中使用的是绝对地址。该绝对地址既可在编译或汇编是给出，也可由程序员直接赋予。
2. 可重定位装入方式：通常是把在装入时对目标程序中指令和数据的修改过程称为重定位 。又因为地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位
3. 动态运行时装入方式：在这种方式下动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此， 装入内存后的所有地址都仍是相对地址。 显然为使指令的执行不受影响，进行这种地址的动态转换，就必须有专门的硬件机构解决
2、重定位、静态重定位、动态重定位（P119）
重定位：我们把装入时对目标程序中的指令地址和数据地址的修改过程称为重定位。
静态重定位：如果重定位是在装入时由装入程序一次性完成的，则称为静态重定位。
动态重定位：在这种方式下动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。
3、内存的连续分配方式有哪些？（P121）
1. 单一连续分配（单道） 2. 固定分区分配
3. 动态（可变式）分区分配 4. 可重定位分区分配
4、动态分区分配算法（P123）
1. 首次适应算法 2. 循环首次适应算法 3. 最佳适应算法 4. 最坏适应算法 5. 快速适应算法
5、对换技术（P129）
对换技术，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需的程序和数据调入内存的方法。
6、紧凑或拼接技术（P127）
紧凑技术，是指通过移动内存中作业的位置，把原先分散的小分区拼接成一个大分区的方法。在每次拼接后，都必须对移动了的程序或数据进行重定位
7、基本分页管理原理、地址变换过程
P( 130)
8、分段系统的基本原理、地址变换过程
P( 136 )
9、分页与分段的主要区别（P138）
1. 页是信息的物理单位，分页是为了实现离散分配方式，以消减内存的外零头，提高内存利用率，分页是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，分段的目的是为了能
更好地满足用户的需要。
2. 页的大小固定且由系统决定；而段的长度
却不固定， 取决于用户所编写的程序。
3. 分页的作业地址空间是一维的，即单一的线性地址空间； 而分段的作业地址空间则是二维的。
10、虚拟存储器的定义、特征（P143）
定义：虚拟存储器就是仅把作业的一部分装入内存便可运行的存储器系统，具体说就是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。
特性：
1. 离散性：即非连续性，这是实现虚拟存储器管理技术的前提；
2. 多次性：一个作业被分成多次调入内存； 3. 对换性：允许在作业运行过程中换入、换出；
4. 虚拟性：能够从逻辑上扩充内存容量。
11、页面置换算法：计算缺页次数、置换次数、缺页率、置换率
P( 150 )
第五章 设备管理
1、设备管理的对象：
设备、设备控制器、通道
2、I/O控制方式及发展宗旨（P167）
I/O系统是用于实现数据的输入，输出及数据存储的系统
I/O控制方式：
1. 程序I/O方式（忙等待方式） 2. 中断驱动I/O方式
3. 直接存储器访问DMA控制方式 4. I/O通道控制方式 发展宗旨：
尽量较少主机对I/O控制的干预，把主机从繁
杂的I/O控制事务中解脱出来，以便更多的去完成
数据处理任务。
3、缓冲引入的原因（P172）
1. 缓和CPU与I/O设备间速度不匹配的矛盾。2. 减少对CPU的中断频率， 放宽对CPU中断响应时间的限制。
3. 提高CPU和I/O设备之间的并行性。
4、设备独立性
应用程序独立于具体使用的物理设备叫设备独立性，也称为设备无关性。
5、SPOOLING原理、组成、特点、共享打印机原理（P190）
SPOOLING原理：在联机情况下实现的外围操作与CPU对数据的处理同时进行，称为假脱机操作，又叫Spooling。
Spooling系统的组成： 1. 输入井和输出井
2. 输入缓冲区和输出缓冲区（为了缓和CPU与磁盘之间速度不匹配的矛盾）
3. 输入进程和输出进程 4. 请求打印队列 SPOOLing系统的特点： 1. 提高了I/O的速度。
2. 将独占设备改造为共享设备。 3. 实现了虚拟设备功能。 共享打印机原理：
共享打印机技术已被广泛地用于多用户系统和局域网络中。 当用户进程请求打印输出时， SPOOLing系统同意为它打印输出， 但并不真正立即把打印机分配给该用户进程， 而只为它做两件事：
1. 由输出进程在输出井中为之申请一个空闲
磁盘块区， 并将要打印的数据送入其中；
2. 输出进程再为用户进程申请一张空白的用
户请求打印表，并将用户的打印要求填入其中， 再
将该表挂到请求打印队列上。
6、磁盘访问时间包括什么？（P193）
1. 寻道时间Ts 2. 旋转延迟时间Tτ 3. 传输时间Tt
7、磁盘调度算法：计算平均寻道长度
P ( 194 )
第六章 文件管理
1、文件
文件是指由创建者所定义的、 具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种。在有结构的文件中，文件由若干个相关记录组成；而无结构文件则被看成是一个字符流。文件在文件系统中是一个最大的数据单位，它描述了一个对象集。
2、文件的逻辑结构及分类（P208）
文件的逻辑结构分为两大类：
1. 有结构文件：即记录式文件；记录的长度分为定长记录和变长记录
2. 无结构文件：即流式文件（被看成字符流）。
3、文件的物理结构及分类（P213）
文件的物理结构直接与外存分配方式有关。可分为：
1. 连续分配方式时的顺序式文件结构。 2. 链接分配方式时的链接式文件结构。 3. 索引分配方式时的索引式文件结构。
4、文件外存分配方式（P213）
1. 连续分配。 2. 链接分配。 3. 索引分配。
5、文件目录，目录查询方式
文件目录是一种数据结构，用于标识系统中的
文件及其物理地址，供检索时使用，是文件数据块
的有序集合。
目录查询方式：
1. 线性检索法
2. Hash方法
6、目录管理的要求
1. 实现“按名存取”。 2. 提高对目录的检索速度。
3. 文件共享。 4. 允许文件重名。
7、文件控制块
为了能对一个文件进行正确的存取，必须为文件设置用于描述和控制的数据结构，称之为文件控制块（包含三大信息：基本信息、存取控制信息、使用信息）
8、索引节点概念，为什么引入索引节点？
索引节点：采用将文件名与文件描述信息分开的办法，将文件描述信息单独形成一个数据结构叫索引节点简称i节点。
引入原因：由于检索目录文件只用到文件名，即用不到该文件的描述信息，且在检索目录时索引节点不用调入内存，从而大大节省了系统开销。
9、文件存储空间的管理方法
1. 空闲表法 2. 空闲链表法 3. 位示图法
4. 成组链接法 （空闲表法和空闲链表法都不适合大型文件系统）
10、成组链接法的空闲盘块组织、分配回收过
第七章 操作系统接口
程
10010099空闲盘块号4000栈3997999…3017901S.free100030012993004007900……982024993997899799999201……………20130178017901
(1) 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。
(2) 将所找到的一个或一组二进制位， 转换成与之相应的盘块号。假定找到的其值为“0”的二进制位，位于位示图的第i行、第j列，则其相应的盘块号应按下式计算： b=n(i-1)+j
式中， n代表每行的位数。
(3) 修改位示图，令map［i,j］=1。 空闲盘块的分配与回收：当系统要为用户分配文件所需的盘块时，首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。
若该盘块号已是栈底， 即S.free(0)，这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此， 须调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去。
在系统回收空闲盘块时，将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作。当栈中空闲盘块号数目已达100时， 表示栈已满，便将现有栈中的100个盘块号， 记入新回收的盘块中，再将其盘块号作为新栈底。
1、操作系统接口
分为用户接口和程序接口（概念）。用户接口包括命令接口、图形接口等。
2、程序接口
程序接口是由一组系统调用组成。系统调用是
在OS核心设置的一组实现系统功能的子程序（过程）。
第八章 网络操作系统
1、网络操作系统的功能
数据通信，网络资源共享，应用互操作，网络管理
应用互操作包括：信息互通性和信息互用性。在Internet下，主要利用TCP/IP协议实现信息的互通性。
2、网络操作系统提供的服务：
域名服务，目录服务，Web服务
3、目录管理记录了网络中的三大资源
物理设备，网络服务和用户的名字，属性和位置。
1、进程同步互斥问题
* 信号量类型:整型(忙等待)、记录型、AND型、一般信号量集 解决的问题：
1、描述前趋关系：根据前趋图，各边分别设置信号量，初值为0；
若某边从某节点出发，在此节点操作后，对该边对应信号量作signal操作；
若某边指向某节点，在此节点操作前，对该边对应信号量作wait错作；
Var
a,b,c,d,e,f,g,h,i,j:
semaphore:=0,0,0,0,0,0,0,0;
begin parbegin
begin S1; signal(a); signal(b); end; begin wait(a); S2; signal(c); signal(d); end;
begin
wait(b);
S3;
signal(e);signal(f); end;
begin wait(c); S4;signal(g); end; begin wait(d); S5;signal(h); end; begin wait(e); S6; signal(i); end;
begin wait(f); S7; signal(j); end;
begin wait(g); wait(h); wait(i); wait(j); S8; end;
parend end
2、进程互斥问题（资源共享）
* 根据临界资源的种类设置信号量
的个数，初值为各临界资源的可用数量；
* 在访问临界资源前，对对应信号量作wait操作；在访问结束后作signal操作，即将临界区放在wait和signal之间。 3、进程同步（相互合作）
* 为同步双方设置各自的信号量，初值为其初始状态可用的资源数(故该信号量称为资源信号量或私有信号量)；
* 同步双方任一进程在进入临界区之前，应先对自己的信号量执行wait(<己方信号量>)操作，以测试是否有自己可用的资源。若有资源可用，则进入临界区，否则阻塞；
同步双方任一进程离开临界区后，应对合作
方 (对方)的信号量执行signal(<对方信号量>)操作，以通知(若对方处于阻塞状态，则唤醒它)对方已有资源可用(对方已可进入临界区)。
* 有一个阅览室，共有100个座位，读者进入时必须先在一张登记表上登记，该表为每一个座位列一表目，包括座号和读者姓名等，读者离开时要消掉登记的信息，试用wait,signal原语描述各个进程之间的同步互斥关系。
Var s,mutax: semaphore:=100,1; Reader： Begin Repeat Wait(s); Wait(mutex); 登记；
Signal(mutex); 阅览图书； Wait(mutex); 取消登记；
Signal(mutex); Signal(s);
Until fasle end
桌上有一个盘子，每次只能放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放橘子，儿子专等吃盘里的桔子，女儿专等吃盘里的苹果。只要盘子空，爸爸妈妈可向盘中放水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出，请给出他们四人之间的同步关系程序。
VAR s,so,sa:semaphore :=1,0,0;//s表示盘空，so表示橘子，sa表示苹果。
parbegin
Father:begin repeat
wait(s); put apple(); signal(sa); until false end Mother:begin repeat
wait(s); put orange(); signal(so); until false end Son:
begin repaet
wait(so); eat orange(); signal(s); until false end daughter: begin repeat
wait(sa); eat apple(); signal(s); until false end parend
2．设公共汽车上有一位司机和一位售票员，它们的活动如下：
司机：启动车辆，行车，到站停车， 售票员：售票；到站开门，关门
请分析司机与售票员之间的同步关系，如何用PV操作实现。
答：为了安全起见，显然要求：关车门后才能启动车辆；到站停车后才能开车门。所以司机和售票员在到站、开门、关门、启动车辆这几个活动之间存在着同步关系。用两个信号量S1、S2分别表示可以开车和可以开门，S1的初值为1，S2的初值为0。用PV操作实现司机进程和售票员进程同步的算法描述如下：
司机： P（S1） ； 启动车辆 ； 正常行车 ； 到站停车； V（S2）； 售票员：
售票； P（S2） ； 开车门； 关车门；
V（S1）； 生产者消费者问题
三个进程两个缓冲区俩俩合作（下页）； 设自行车生产车间有两个货架，货架A可以存放8个车架，货架B可以存放20个车轮；又设有4个工人，他们的活动是重复劳动，分别为：工人1 加工一个车架放入货架A中；工人2、3分别加工车轮放入货架B中（每人每次放入1个车轮）；工人4从货架A中取一个车架，再从货架B中取两个车轮，组装成一辆自行车。试用PV操作实现四个工人的合作
1、系统中有是三个进程GET，PRO和PUT，共用两个缓冲区BUF1和BUF2。假设BUF1中最多可放8个信息，BUF2中最多可放5个信息。GET进程负责不断地将信息送入BUF1中，PRO进程负责从BUF1中取出信息进行处理，并将处理结果送到BUF2中，PUT进程负责从BUF2中读取结果并输出。试用wait、signal原语（P、V操作）实现GET，PRO，PUT进程之间的同步算法。
1、 var：mutex1，mutex2，empty1，empty2，full11，full2：=1，1，8，5，0，0；
GET:begin（ repeat
wait(empty1); wait(mutex1); 送入BUF1；; signal(mutex1); signal(full); until false end PRO:begin repeat wait(full1);
wait(mutex1); 从BUF1中取信息加工; signal(mutex1); signal(empty1); wait(empty2); wait(mutex2);
将加工后的信息放入BUF2; signal(mutex2); signal(full2); until false end PUT:begin repeat wait(full2); wait(mutex2); 从BUF2中取信息输出; signal(mutex2); signal(empty2); until false end
【分析】设置资源信号量和互斥信号量如下：★
信号量Aempty表示货架A的
空位数，其初值为8；
★
信号量Afull表示货架A上存
放的车架数，其初值为0；
★
信号量Bempty表示货架B的
空位数，其初值为20；
★
信号量Bfull表示货架B上存
放的车轮数，其初值为0；
★ 信号量mutex用于互斥（初值
为1）。
Var
Aempty,Afull,Bempty,Bfull,mutex:semaphore;
Aempty.value:=8; Afull.value:=0;
Bempty.value:=20;Bfull.value:=0;
mutext.value:=1; wheelcount:integer:=0; Begin parbegin worker1:begin repeat
生产一个车架； wait(Aempty);//看看货架A上是否有空位置
车架放到货架A上； signal(Afull);//货架A上的车架数增1，并通知工人4 until false; end
Worker2，3:begin repeat
生产一个车轮；
wait(Bempty);//看看货架B上是否有空位置
wait(mutex); 将车轮放到货架B上； signal(mutex);
signal(Bfull);//货架B上的车轮数增1，并通知工人4
until false; end Worker4:begin repeat
wait(Afull);wait(Bfull);wait(Bfull);
取一个车架和两个车轮；
signal(Aempty);signal(Bempty);signal(Bempty);
组装一辆自行车；
until false end parend end
哲学家就餐问题（非死锁算法）
① 至多允许4个哲学家同时取左边的筷子，
这样能至少保证一个哲学家能就餐，并在用毕后释放他用过的两只筷子，从而使更多的哲学家能够进餐。（请学生考虑算法的描述）
② 仅当哲学家左右两只筷子均可用时，才允
许他拿起筷子进餐。（用AND信号量机制）③ 规定奇数号哲学家先拿左边筷子，然后再
拿右边筷子；而偶数号哲学家先拿右边筷子，然后再拿左边筷子。
（1） var chopstick:array[0,…,4] of semaphore := 1,1,1,1,1;
Sm:semaphore := 4; begin repeat wait(Sm);
wait(chopstick[i]);
wait(chopstick[(i+1) mod 5]); eat;
signal(chopstick[i]); signal(chopstick[(i+1) mod 5); signal(Sm); think; until false
End （2） var
chopstick:array[0,…,4]
of
semaphore := 1,1,1,1,1;
begin repeat
swait(chopstick[i]，chopstick[(i+1) mod 5]);
eat;
ssignal(chopstick[i]，chopstick[(i+1) mod 5);
think; until false end
（3）var chopstick:array[0,…,4] of semaphore := 1,1,1,1,1;
begin repeat
if i mod 2=0 then begin
wait(chopstick[i]);
wait(chopstick[(i+1) mod 5]); end; else begin
wait(chopstick[(i+1) mod 5]); wait(chopstick[i]); end; eat;
signal(chopstick[i]); signal(chopstick[(i+1) mod 5); think; until false End
读者写者问题及变形---独木桥问题
假定有如下独木桥问题：过桥时，同一方向的行人可连续过桥，当某一方有人过桥时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。试用信号量机制解决。
答案： (1) 将独木桥的两个方向分别标记为A和B。用整型变量countA和countB分别 表示A、B方向上已在独木桥上的行人数。初值为0。需要设置三个初值都为1的互斥信号量：SA用来实现对countA的互斥访问，SB用来实现对countB的互斥访问，mutex用来实现对独木桥的互斥使用。
(2)
A方向行人过桥： Begin P(SA); countA=countA+1; if (countA= =1) P(mutex); V(SA); 过桥； (SA);
countA=countA-1; if(countA= =0) V(mutex); V(SA); End
B方向行人过桥：
Begin P(SB); countB=countB+1; if (countB= =1) P(mutex); V(SB); 过桥； P(SB);
countB=countB-1; if(countB= =0) V(mutex);
V(SB); End
处理机调度算法： 1. 先来先服务调度算法
该算法既可用于作业调度又可用于进程调度，用于前者时，每次调度都是从外存后备队列中选择一个或多个作业，将它们调入内存，为它们分配资源、创建进程，然后将新建进程放入就绪队列。用于后者时，每次调度时从就绪队列中选择一个最先进入该队列的进程，把处理机分配给它，使其运行。
FCFS算法的特点如下：
? 利于长作业（进程），而不利于短作业（进程）
? 利于CPU繁忙型作业（进程），而不利于I／O型繁忙作业（进程）
? 作业平均等待时间长 ? 系统吞吐量不高
2. 短作业(进程)优先调度算法
短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法，
是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃
处
理
机
时
，
再
重
新
调
度
该算法的特点如下：
? 能有效降低作业平均等待时间 ? 能提高系统吞吐量 ? 对长作业不利
? 未考虑作业的紧迫程度，因而不能保证紧迫型作业或进程得到及时处理。 由于作业或进程的长短是根据用户所提供的估计执行时间而定，因而不免存在差异。 3.高优先权优先调度算法
1) 非抢占式优先权算法 2) 抢占式优先权算法
【例3-3】设有一个最多可有两道作业同时装入内存执行的批处理系统，作业调度采用最短作业优先调度算法，进程调度采用抢占式静态优先权调度算法，今有如下纯计算型作业序列（表中所列进程优先数中，数值越小优先权越高）：
(1)列出所有作业进入内存时间及结束时间。 (2)计算平均周转时间。
平均周转时间=(50+30+55+55)/4=47.5(分钟)
3). 高响应比优先调度算法(只使用作业调度)
优先权=（等待时间+要求服务时间）/要求服务时间=响应时间/要求服务时间=Rp 算法特点：
(1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。(2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。(3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机。
【例3-4】设有一个最多可有两道作业同时装入内存执行的批处理系统，作业调度采用高响应比优先
调度算法，进程调度采用抢占式静态优先权调度算法，今有如下纯计算型作业序列（假设表中所列进程优先数中，数值越小优先权越高）：
(1)列出所有作业进入内存时间及结束时间。 (2)计算平均周转时间。
平均周转时间=(75+30+45+55)/4=51.25(分钟)
3 基于时间片的轮转调度算法 1. 时间片轮转法
利用银行家算法避免死锁 1. 银行家算法中的数据结构
(1) 可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。
(2) 最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。
(3) 分配矩阵Allocation。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。
(4) 需求矩阵Need。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。
Need［i,j］=Max［i,j］-Allocation［i,j］ 2. 银行家算法
设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：
(1) 如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
(2) 如果Requesti［j］≤Available［j］，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。
(3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
Available［j］∶=Available［j］-Requesti
［j］;
Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;
Need［i,j］∶=Need［i,j］-Requesti［j］; (4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本
次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
3. 安全性算法
(1) 设置两个向量：① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available; ② Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false; 当有足够资源分配给进程时， 再令Finish［i］∶=true。
2) 从进程集合中找到一个能满足下述条件的进程： ① Finish［i］=false; ② Need［i,j］≤Work［j］； 若找到,执行步骤(3);否则，执行步骤(4)。
(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
Work［j］∶=Work［j］+Allocation［i,j］; Finish［i］∶=true;go to step 2; (4) 如果所有进程的Finish［i］=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。
4. 银行家算法之例
假定系统中有五个进程｛P0, P1, P2, P3, P4｝和三类资源｛A, B, C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 3-15 所示。
图 3-15 T0时刻的资源分配表 (1) T0时刻的安全性：
图 3-16 T0时刻的安全序列
(2) P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查：
① Request1(1, 0, 2)≤Need1(1, 2, 2) ② Request1(1, 0, 2)≤Available1(3, 3, 2)
③ 系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成的资源变化情况如图 3-15 中的圆括号所示。
④ 再利用安全性算法检查此时系统是否安全。
图 3-18 为P0分配资源后的有关资源数据
图 3-17 P1申请资源时的安全性检查 (3) P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查：
① Request4(3, 3, 0)≤Need4(4, 3, 1); ② Request4(3, 3, 0) < Available(2, 3, 0)，让P4等待；
(4) P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查：
① Request0(0, 2, 0)≤Need0(7, 4, 3); ② Request0(0, 2, 0)≤Available(2, 3, 0);
③ 系统暂时先假定可为P0分配资源，并修改有关数据，如图 3-18 所示。
存储器管理地址装换问题 基本分页存储管理方式
页表
用户程序页表内存0 页页号块号1 页0202 页1313 页2624 页3835 页494…556n 页……78910
地址变换机构
越界中断页表寄存器逻辑地址L页表始址页表长度＞页号(3)页内地址＋页号块号01123b物理地址页表
2．在采用页式存储管理的系统中，某作业的逻辑地址空间为4页（每页4096字节），且已知该作业的页表如下表。试求出逻辑地址14688所对应的物理地址 页表： 页 号 内存块号 0 2 1 4 2 7 3 9
页号P=INT(14688/4096)=3
页内偏移d=14688@96=2400(960H) 物理地址=9×4096+2400=39264(9960H)
两级和多级页表
1. 两级页表(Two-Level Page Table)
两
级页
表结
构
第0页页表010111011078014122623……4102356第1页页表701141115…n1742外部页表…1141023115第n页页表01468121468……1023内存空间具有两级页表的地址变换机构
外部页号外部页内地址页内地址逻辑地址P1P2d外部页表寄存器＋＋bd……物理地址外部页表页表
基本分段存储管理方式
分段
利用段表实现地址映射
作业空间(MAIN)＝0内存空间00段表30K段号段长基址40K0(X)＝1(MAIN)＝0030K40K30K20K120K80K(X)＝180K0(D)＝2215K120K20K120K15K0(S)＝3310K150K(D)＝215K(S)＝3150K10K10K
分段系统的地址变换过程
控制寄存器越界段号S位移量W段表始址段表长度＞2100有效地址＋段号段长基址01 K6 K＋16004 K25008 K320092008292物理地址8K82928692主存
页面置换算法
1. 最佳(Optimal)置换算法
假定系统为某进程分配了三个物理块,并考虑有以下的页面号引用串：
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
进程运行时,先将7，0，1三个页面装入内存。以后， 当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。
引用率70120304230321201701777222227000040001133311页框(物理块）
2. 先进先出(FIFO)页面置换算法
引用率701203042303212011701777222444000777000333222111001110003332221页框
3.最近最久未使用(LRU)置换算法
选择最近一段时间内，最久未被访问的页面予以淘汰。即试图通过过去来预测未来。实现时在每个页面上设置一个一个访问字段，用来记录该页面自上次访问至今所经历的时间。
引用率70120304230321201701777224440111000000333001133222227页框
2、在一个请求页式存储管理系统中，进程P共有5页，页号为0至4。若对该进程页面的访问序列为3，2，1，0，3，2，4，3，2，1，0，4，试用LRU置换算法和FIFO置换算法，计算当分配给该进程的物理块数为3时，访问过程中发生的缺页次数和缺页率。
磁盘调度问题
磁盘的类型：1) 固定头磁盘 2) 移动头
磁盘
磁盘访问时间：1) 寻道时间Ts 2) 旋转延迟时间Tτ 3) 传输时间Tt
1. 先来先服务FCFS
一种既公平又简单的磁盘调度算法，即按进程提出访问的先后次序予以服务。但在对磁盘访
问频繁的系统中，平均寻道距离大，因而平均访问时间长
2. 最短寻道时间优先SSTF
每次从等待队列中选择要访问的目标磁道距当前的磁头最近的进程予以服务。该方法使磁头的移动距离最近，以使每次的寻道时间最
短，虽可由于FCFS，但不能保证平均寻道时间最短，而且有可能使某些进程发生“饥饿”现象
2、 假设一个磁盘的每个盘面上有200个磁道，现有多个进程要求对存储在该盘面上的数据进行访问，按照这些请求到达的先后次序，它们的访问位置分别处于54、57、39、18、90、162、154、38、180号磁道上。假定当前磁头在100号磁道上。请给出按“先来服务（FCFS）”、“最短寻道时间优先(SSTF)”和“扫描（SCAN）”算法进行磁盘调度时各自实际的访问次序，并计算它们的平均寻道长度。(注：当采用扫描算法时，规定当前磁头正在向磁道号增加的方向上移动)
、FCFS算法访问次序:54、57、39、18、90、162、154、38、180（2分） 平均寻道长度：55.3
SSTF算法访问次序:90、57、54、39、38、18、154、162、180（2分） 平均寻道长度：27.1
SCAN算法访问次序:154、162、180、90、57、54、39、38、18（3分） 平均寻道长度：26.8
3. 扫描(SCAN)算法
规定磁头的移动方向总是从内及外，然后从外及内，循环往复，每次只服务于那些在磁头前进方向上且离当前磁头位置最近提出访问的进程，又称电梯调度算法。注意：此处的内外磁道并不是指实际物理上的最内最外磁道，而是指本次进程访问的最内最外磁道。
操作系统重点知识总结
