高等学校操作系统课程庐山研讨班北京大学信息学院陈向群

高等学校操作系统课程庐山研讨班北京大学信息学院陈向群内容摘要：

占用的空间与间隙占用的空间之比是多少。 （ 2）此时，磁带空间的利用率是多少。 （ 3）采用以 10个逻辑记录为一组的成组操作时，磁带空间的利用率是多少。 （ 4）为了使磁带空间的利用率大于 50％，采用记录成组时其块因子至少为多少。 文件系统的一致性 磁盘块 → 内存 → 写回磁盘块 若在写回之前，系统崩溃，则文件系统出现不一致 * 设计一个实用程序，当系统再次启动时，运行该程序，检查磁盘块和目录系统 1文件系统的可靠性 1 UNIX一致性检查工作过程： 两张表，每块对应一个表中的计数器，初值为 0 表一：记录了每块在文件中出现的次数 表二：记录了每块在空闲块表中出现的次数 文件系统的可靠性 2 文件系统的可靠性 3 文件系统的可靠性 4 文件系统的可靠性 5 文件系统的可靠性 6 1 磁头移动量的计算 1 假设一个活动头磁盘有 200道，编号从 0199。 当前磁头正在 143道上服务，并且刚刚完成了 125道的请求。 现有如下访盘请求序列 (磁道号 )： 86， 147， 91， 177， 94， 150， 102， 175， 130 试给出采用下列算法后磁头移动的顺序和移动总量 (总磁道数 )。 （ 1）最短寻道时间优先（ SSTF）磁盘调度算法。 （ 2）扫描法（ SCAN）磁盘调度算法（假设沿磁头移动方向不再有访问请求时 , 磁头沿相反方向移动。 ） 答案： （ 1）最短寻道时间优先： 磁盘移动： 147， 150， 130， 102， 94， 91， 86，175， 177 移动总量： 4＋ 3＋ 20＋ 28＋ 8＋ 3＋ 5＋ 89＋ 2＝ 162 （ 2）扫描磁盘调度算法： 147， 150， 175， 177， 130，102， 94， 91， 86。 总量： 4＋ 3＋ 25＋ 47＋ 28＋ 8＋ 3＋ 5＝ 125 磁头移动量的计算 2 旋转调度：根据延迟时间来决定执行次序的调度 分析：  若干等待访问者请求访问同一磁道上的不同扇区  若干等待访问者请求访问不同磁道上的不同编号的扇区  若干等待访问者请求访问不同磁道上具有相同的扇区 1旋转调度 1 解决方案： • 对于前两种情况：总是让首先到达读写磁头位置下的扇区先进行传送操作 • 对于第三种情况：这些扇区同时到达读写磁头位置下，可任意选择一个读写磁头进行传送操作 旋转调度 2 请求顺序 柱面号 磁头号 扇区号 ① 5 4 1 ② 5 1 5 ③ 5 4 5 ④ 5 2 8 旋转调度 3 记录在磁道上的排列方式也会影响输入输出操作的时间 例子：处理程序要求顺序处理 8个记录；磁盘旋转一周为 20毫秒 /周；花 5毫秒对记录进行处理 1 2 8 7 3 4 5 6 1 4 6 3 7 2 5 8 1信息的优化分布 1 请求顺序 柱面号 磁头号 扇区号 ① 9 6 3 ② 7 5 6 ③ 15 20 6 ④ 9 4 4 ⑤ 20 9 5 ⑥ 7 15 2 1磁盘调度综合练习 假设磁头在 8柱面，求最省时间的响应次序 1串行异步通信速率和效率的计算 串行异步通信端口在现代计算机中主要用于将终端（键盘和监视器）或打印机与计算机相连。 典型的信号协议用 1或 2个开始位和 1个结束位打包每个字节。 发送者向接收者发送开始位以通知它将要开始传输一个字节。 然后传送字节的 8个位，后面跟 1个结束位。 用这种协议在 9， 600波特率的串行线上每秒能传送多少个字节。 用于传送控制字节的时间所占百分比是多少。 答案： 假设开始位为 1位，那么 9600波特率的串行线上每秒能传送9600/10=960个字节。 用于传送控制字节的时间为 2/10=20%。 1关于死锁条件的计算 一个计算机系统有某种资源 6个，供 n个进程使用，每个进程至少需要 2个资源。 当 n为何值时，系统不会发生死锁。 答案： N为 5时，系统不会发生死锁 银行家资源分配算法的计算 1 某系统当前有同类资源 10个，进程 P， Q， R所需资源总数分别为 8， 4， 9。 它们向系统申请资源的次序和数量如图所示。 （ 1）系统采用银行家算法分配资源，请给出系统完成第 6次请求后各进程的状态及所占资源量。 （ 2）在以后各次的申请中，哪次的申请要求可先得到满足。 次序 进程 申请量 次序 进程 申请量 1 R 2 6 Q 2 2 P 4 7 R 3 3 Q 2 8 P 2 4 P 2 9 R 3 5 R 1 答案： （ 1）第六次请求后各进程的状态和所占资源量 银行家资源分配算法的计算 2 进程 目前占有量 最大需求量 尚需要量 P 4 8 4 Q 4 4 0 R 2 9 7 （ 2）第 4次请求可先得到满足 2银行家算法应用 1 已分配的资源 最大需求量 A B C A B C P1 0 1 0 7 5 3 P2 2 0 0 3 2 2 P3 3 0 2 9 0 2 P4 2 1 1 2 2 2 P5 0 0 2 4 3 3 剩余资源 A B C 3 3 2 银行家算法应用 2 问题 :此状态是否为安全状态，如果 是 , 则找出安全序列 在此基础上 （ 1） P2 申请（ 1， 0， 2）能否分配。 为什么。 （ 2） P5 申请（ 3， 3， 0）能否分配。 为什么。 （ 3） P1 申请（ 0， 2， 0）能否分配。 为什么。 有关 OS的 PV操作习题 题型分类 第一类：生产者 消费者问题 （共享缓冲区，一方放，一方取，同步、互斥） 第二类：读者 写者问题 （有不同优先级，主要解决互斥问题） 第三类：理发师问题、吸烟者问题 第四类：资源分配问题（阅览室问题、超市问题、银行服务问题） 第五类：纯同步问题 第六类：其他同步互斥问题 第一类：生产者 消费者问题 1 设有一台计算机，有两条 I/O通道，分别接一台卡片输入机和一台打印机。 卡片机把一叠卡片逐一输入到缓冲区 B1中，加工处理后再搬到缓冲区 B2中，并在打印机上印出。 问： （ 1）系统要设几个进程来完成这个任务。 各自的工作是什么。 （ 2）这些进程间有什么样的相互制约关系。 （ 3）用 PV操作写出这些进程的同步算法； （ 4）设系统中只有上述几个进程，用图表示出各自状态变迁情况及原因。 第一类：生产者 消费者问题 2 get copy put f s t g 进程 A A …… 、 An1通过 m个缓冲区向进城 B B ……Bn2 不断发送消息，发送和接收工作遵循如下规则： （ 1）每个发送进程每次发送一个消息，写入一个缓冲区，缓冲区大小与消息长度一样； （ 2）对每一个消息， B B …… 、 Bn2都需要各接收一次，读到各自的数据区内； （ 3） m个缓冲区都满时，发送进程等待；没有可读的消息时，接收进程等待； 试用 P、 V操作组织正确的发送和接收操作。 第一类：生产者 消费者问题 3 第一类：生产者 消费者问题 4 有四个进程 A、 B、 C、 D (1) 进程 A通过一个缓冲区不断地向进程 B、C、 D发送信息， A 每向缓冲区送入一个信息后，必须等进程 B、 C、 D都取走后才可以发送下一个信息 , B、 C、 D对 A 送入的每一信息各取一次，试用 P、 V操作实现它们之间的正确通讯。 (2) 试用最少个数的信号量实现进程 A、 B、C、 D间的正确通讯。 某商店有两种食品 A和 B， 最大数量各为 m个。 该商店将 A,B两种。