01 音频课

02 Interim 创业要保重自己的身体

03 操作系统概述

04 进程管理

三态模型和五态模型



PV操作是低级通信原语。原语 Primitive。

(1) P操作如下定义，其中 semaphore 为信号量的意思。

Procedure P(Var S:Semaphore);
    Begin
        S:=S-1; // 执行 P 操作的进程插入等待队列
        If S<0 then w(S)
    End;

(2) V操作定义如下。

Procedure V(Var s:Semaphore);
    Begin
        S:=S+1;
        If s≤0 then R(S) // 从阻塞队列中唤醒一个进程
    End;

(3) 利用 PV 操作实现互斥。

P(mutex)
    临界区
V(mutex)

利用 PV 操作实现进程的同步

进程的同步，是由于进程间 合作引起的相互制约 的问题，要实现进程的同步可用一个信号量与消息联系起来，当信号量的值为 0 时表示等待的消息未产生，当信号量的值为非 0 时表示等待的消息已经存在。假定用信号量 S 表示某条消息，进程可以通过调用 P 操作测试消息是否到达，调用 V 操作通知消息已准备好。最典型的同步问题是单缓冲区的生产者和消费者的同步问题。

[例4.2] 生产者进程P不断地生产产品送入缓冲区，消费者进程P,不断地从缓冲区中取产品进行消费。请给出实现进程同步的模型图。

分析:为了实现 P与 P,进程间的同步问题，需要设置两个信号量 S和 S，但信号量初值不同可有如下两种实现方案。

方案 1: 信号量 S的初值为 1，表示缓冲区空，可以将产品送入缓冲区:信号量 S,的初值为 0，表示缓冲区有产品。其同步过程如图 4-6 所示。

方案 2: 信号量 S,的初值为 0，信号量 S,的初值为 0，此时同步过程如图 4-7 所示。



[例4.3] 一个生产者和一个消费者，缓冲区中可存放 n 件产品，生产者不断地生产产品消费者不断地消费产品，如何用 PV 操作实现生产者和消费者的同步。可以通过设置 3 个信号量 S、S,和 S2，其中，S 是一个互斥信号量，初值为 1，因为缓冲区是一个互斥资源，所以要进行互斥控制；S1 表示是否可以将产品放入缓冲区，初值为 n；S2 表示缓冲区是否存有产品初值为 0。其同步过程如图 4-8 所示。


n 个缓冲区同步举例

[例4.4] 进程推进顺序不当引起的死锁。设系统中有一台读卡机 A 和一台打印机 B 资源,这些资源被进程 P和P共享，当 P和 P并发执行时，按如下顺序请求和释放资源。


死锁示例

其中，P1表示执行 Request(A)，P2表示执行 Request(B)，……。如果系统按照 P1 P2 P1 P2 的顺序执行，则系统会发生死锁。因为进程 P1时，由于读卡机未被占用，所以请求可以得到满足:进程 P2时，由于打印机未被占用，所以请求也可以得到满足。接着进程 P1时，由于打印机被占用，所以请求得不到满足，P1 等待;进程 P2时，由于读卡机被占用，所以请求得不到满足，P2也等待，导致互相在请求对方已占有的资源，系统发生死锁。

[例4.6] PV 操作使用不当引起的死锁。对于图 4-9，当信号量 S1=S2=0 时将发生死锁。


PV 引起死锁

[例4.7] 假设系统中有三类互斥资源 R1、R2 和 R3，可用资源数分别为 8、7 和4。在 T0 时刻系统中有 P1、P2、P3、P4 和 P5 这 5 个进程，这些进程对资源的最大需求量和已分配资源数如图 4-11 所示。若有如下 （1）- （4） 个执行序列，那么进程按什么序列执行，系统状态是安全的。

（1）P1 -> P2 -> P4 -> P5 -> P3
（2）P2 -> P1 -> P4 -> P5 -> P3
（3）P4 -> P2 -> P1 -> P5 -> P3
（4）P4 -> P2 -> P5 -> P1 -> P3






[例 4.13] 某计算机系统输入/输出采用双缓冲工作方式，其工作过程如图 4-25 所示，假设磁盘块与缓冲区大小相同，每个盘块读入缓冲区的时间T为 10us，缓冲区送用户区的时间 M为 6us，系统对每个磁盘块数据的处理时间 C 为2s。若用户需要将大小为 10 个磁盘块的 Docl文件逐块从磁盘读入缓冲区，并送用户区进行处理，那么采用双缓冲需要花费的时间为______(1)ns，比使用单缓冲节约了______(2) us 时间。

(1) A.100     B.108     C.162     D.180
(2) A.0     B.8     C.54     D.62



[例 4.14] 数据存储在磁盘上的排列方式会影响 I/O 服务的总时间。假设每个磁道划分成10个物理块，每块存放 1个逻辑记录。逻辑记录 R,R,,Ro存放在同一个磁道上，记录的顺序如下表所示。

假定磁盘的旋转速度为每周 20ms，磁头当前处在 R1 的开始处。若系统顺序处理这些记录使用单缓冲区，每个记录处理时间为 4ms，则处理这 10 个记录的最长时间为____(1)；对信息存储进行优化分布后，处理 10 个记录的最少时间为____(2) 。

(1) A.180ms     B.200ms     C.204ms     D.220ms
(2) A.40ms     B.60ms     C.100ms     D.160ms

05 存储管理

线程


主存


页面管理


进程通信


程序局部性原理

分页存储管理

页表

图 4-14

两级页表制


段式存储管理


段页式存储管理

内外存交互：缺页中断

分析:

从例题的图中可以看到，程序的 COPY 指令跨两个页面，且源地址 A 和目标地址B所涉及的区域也跨两个页面页内地址,这时,如果 2、3、4 和 5 号页面不在内存,系统执行“COPYA TO B”指令时，取地址为 A 的操作数。由于该操作数不在内存且跨两个页面2、3，需要将 2、3 页面装入内存，所以产生两次缺页中断。同理，取地址为 B 的操作数，由于该操作数不在存且跨两个页面 4 和 5，需要将 4 和 5 页面装入内存，所以产生两次缺页中断，共产生 4 次缺页中断。故例题空(1)的正确答案为 C。

同理，如果 1、2、3 号页面不在内存，系统执行“COPY A TO B”指令时，由于程序的COPY 指令跨两个页面，当取出指令分析是多字节的，那么系统将产生一次缺页中断取指令的后半部分;当取地址为 A 的操作数，由于该操作数不在内存，且跨两个页面2和3，需要将 2和 3 页面装入内存，所以产生两次缺页中断，共产生 3 次缺页中断。故例题空(2) 的正确答案为 B。

内存算法

页面置换算法

Optimal
[例 4.10] 假定系统为进程 P1 分配了 3 个物理块，该进程访问页面的顺序为“0，7，6, 5，7，4，7，3，5，4，7，4，5，6，5，7，6，0，7，6”，利用最佳置换算法的结果如图 4-20所示，图中X表示产生缺页中断。求缺页中断次数、页面置换次数和缺页率。



FIFO
[例4.11] 假定系统中某进程访问页面的顺序为“0，7，6，5，7，4，7，3，5，4，7, 4 ,5，6，5，7，6，0，7，6”，利用 FIFO算法对上例进行页面置换的结果如图 4-21 所示。



LRU
[例4.12] 假定系统中某进程访问页面的顺序为“0，7，6，5，7，4，7，3，5，4，7，4，5，6，5，7，6，0，7，6” 利用 LRU 算法对上例进行页面置换的结果如图 4-22 所示。

外存

[例 4.13] 某计算机系统输入/输出采用双缓冲工作方式，其工作过程如图 4-25 所示，假设磁盘块与缓冲区大小相同，每个盘块读入缓冲区的时间T为 10us，缓冲区送用户区的时间 M为 6us，系统对每个磁盘块数据的处理时间 C 为2s。若用户需要将大小为 10 个磁盘块的 Docl文件逐块从磁盘读入缓冲区，并送用户区进行处理，那么采用双缓冲需要花费的时间为______(1)ns，比使用单缓冲节约了______(2) us 时间。

(1) A.100     B.108     C.162     D.180
(2) A.0     B.8     C.54     D.62





[例 4.14] 数据存储在磁盘上的排列方式会影响 I/O 服务的总时间。假设每个磁道划分成10个物理块，每块存放 1个逻辑记录。逻辑记录 R,R,,Ro存放在同一个磁道上，记录的顺序如下表所示。

假定磁盘的旋转速度为每周 20ms，磁头当前处在 R1 的开始处。若系统顺序处理这些记录使用单缓冲区，每个记录处理时间为 4ms，则处理这 10 个记录的最长时间为____(1)；对信息存储进行优化分布后，处理 10 个记录的最少时间为____(2) 。

(1) A.180ms     B.200ms     C.204ms     D.220ms
(2) A.40ms     B.60ms     C.100ms     D.160ms

06 设备管理

Spooling 技术

07 文件管理

文件的共享和保护




位图
[例4.17] 某文件管理系统在磁盘上建立了位示图 (bitmap)，记录磁盘的使用情况。若系统的字长为 32 位，磁盘上的物理块依次编号为 0, 1, 2, …, 那么 4096 号物理块的使用情况在位示图中的第____(1)个字中描述; 若磁盘的容量为 200GB，物理块的大小为 1MB，那么位示图的大小为____(2)个字。

A.129     B.257     C.513     D.1025
A.600     B.1200     C.3200     D.6400

08 作业管理

作业控制块


[例4.18] 作业 J1、J2、J3 的提交时间和所需运行时间如下表所示。若采用响应比高者优先调度算法，则作业调度次序为 _____ （1）。

A.J1 -> J2 -> J3
B.J1 -> J3 -> J2
C.J2 -> J1 -> J3
D.J2 -> J3 -> J1




用户界面