计算题:
生产消费者问题
为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用
S1
表示，初值为有界缓冲区的大小 N，另一个说明已用缓冲区的数目，用 S2表示，初值 为0。 由于在此问题中有 M个生产者和N个消费者，它们在执行生产活动和消费活动中要对 有界缓冲区进行操作。由于有界缓冲区是一个临界资源， 需要设置一个互斥信号量 mutex，其初值为1。
必须互斥使用，所以，另外还
P: i = 0; while (1) { 生产产品； P(S”； P(mutex); 往Buffer [i]放产 品； i = (i+1) % n; V(mutex); V(S2); }; 二、 地址转换 Q : j = 0； while (1) { P(S2); P(mutex); 从Buffer。］取产品； j = (j+1) % n; V(mutex); V(S1); 消费产品； }; 例1:若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为 试将逻辑地址 1011, 2148, 3000 , 4000, 5012转化为相应的物理地址。
1024字节,
页号
0 1 2 3
解：本题中，为了描述方便，设页号为 则
p=i nt(A/L)
w=A mod L
对于逻辑地址1011
块号
2 3 1 6
P,页内位移为 W，逻辑地址为A，页面大小为L,
：
p=i nt(1011/1024)=0
w=1011 mod 1024=1011
查页表第0页在第二块，所以物理地址为 对于逻辑地址 2148
3059。
p=i nt(2148/1024)=2 w=2148 mod 1024=100
查页表第2页在第1块，所以物理地址为 1124。 对于逻辑地址3000 p=i nt(3000/1024)=2 w=3000 mod 1024=928 查页表第2页在第1块，所以物理地址为1796。
对于逻辑地址4000
p=i nt(4000/1024)=3 w=4000mod 1024=928
查页表第3页在第6块，所以物理地址为 7072。 对于逻辑地址5012 p=i nt(5012/1024)=4
w=5012mod1024=916
因页号超过页表长度，该逻辑地址非法。 例2 :
在一分页存储管理系统中，逻辑地址长度为
16位，页面大小为4096字节，现有一逻辑地址为
2F6AH,且第0, 1, 2页依次存放在物理块 5, 10 ,11中，问相应的物理地址为多少 ?
解:由题目所给给条件可知，本页式系统的逻辑地址结构为 ：
页号P
贡内位移W 逻辑地址2F6AH的二进制表示如下
0010 111101101010
由此可知逻辑地址 2F6AH的页号为2,该页存放在第11号物理块中，用十六进制表示志 号为B,所以物理地址为BF6AH. 三、 求文件最大长度
例：设文件索引节点中有 7个地址项，其中4个地 址项为直接地址索引，2个地址项是一级间接地址索 弓I, 1个地址项是二级间接地址索引，每个地址项大 小为4字节，若磁盘索引块和盘块大小均为 256字 节，则可表示的单个文件的最大长度是多少？
解答：本题的文件结构属混合索引分配方式。每个地址项大小为 4字节，索引块和盘 块大小为256字节，每个索引块中的项目数 =256B/4B=64个。4个地址项为直接地址索 弓I,对应的文件大小为 4X256B=1KB。2个地址项是一级间接地址索引，对应的文件大 小是2X64X256B=32KB，一个地址项是二级间接地址索引，对应的文件大小为 1X64 X 64 X256B=1024KB。所以单个文件的最大长度=1KB+32KB+1024KB=1057KB 四、 磁盘调度算法：
〔从1O0爭厳道开始、 披访冋的下
55 58 39 1S 90 。
移勒距周 45 3 19 21 72 70 1O 112 146
150 &8 1￡4 1.先来先服务FCFS
（从100号磁逍开始） 被访问的下 一个磁道号 移动距离 （磁道数） 90 10 58 32 55 3 39 16 38 1 18 20 150 132 160 10 184 24 2.最短寻道时间优先
平均寻道悅度’ 27,5 （从】0尸磁道开始.向磁道号增加方向 访问） 被访问的下 移动距离 一个磁道号 （磁道数） 150 50 160 10 184 24 90 94 58 32 55 3 3& 16 3B 1 18 20 3. SCAN算法
平均寻道快度匸27.8
械苗冋的下 150 50 160 1O 1& 3 & 1 55 10. SB 3 90 32 4. 平均寻Fit怔庚r 27. 5 循环扫描（CSCAN）算 例: 假设一个活动头磁盘有法 200道,编号从0-199.当前磁头正在143道上服务 刚刚完成了 125道的请求.现有如下访盘请求序列（磁道号）: 86, 147, 91, 177, 94, 150, 102, 175, 130 并且 试给出采用下列算法后磁头移动的顺序和移动总量 （1） （2） .先来先服务（FCFS）磁盘调度算法. .最短寻道时间优先（SSTF）磁盘调度算法. （总磁道数）. （3）.扫描法（SCAN）磁盘调度算法.（假设沿磁头移动方向不再有访问请求时 反方向移动.） 答案：三、（1）86, 147, 91，177, 94, 150，102，175，130 （2）当前磁头在143道上： 147， 150， 130， 102， 94， 91， 86， 175， 177 （3）当前磁头在143道上，并且刚刚完成 125道的请求 147，150，175，177，130，102，94，91，86 ，磁头沿相 五、 调度算法（求周转时间，加权周转时间） 1. 先来先服务调度算法 FCFS:该算法按照进程进入就绪队列的先后顺序选择最先 进入该队列的进程，把处理机分配给它，使之投入运行。 例 在单道环境下，某批处理軽然有四道作业，己対I他们的 进入系统的时刻\估计运算时间如下* 到达时剣 A B C D 0 1 服务时何 1 100 1 100 0 1 101 102 丸成时细 1 101 102 202 1 周转时同 搐权周转 1 100 100 1**9 1 丄 1.99 2 3 短作的带权周转时问高达讪叽 长作业?的带权周转时问仅 2. 数。 单 易行，系统开销小，但不够精确，很可能出现优先权低的作业（进程）长期不被调 度的情况。所以，只在要求不太高的系统中，才使用静态优先数（权） 动态优先权：在创建进程时所赋予的优先权, 更好的调度性能 ） 以便获得 可以随进程的推进而改变， 优先级调度算法：总是选择具有 最分为： （简 高优先级的进程首先使用处理机。在这种算法 中，首先考虑的问题是如何确定进程的优先 静态优先权：在创建讲程的时候便确定的，且在讲程的运行期间保持不变。 例2 有5个进程P2. P3x P4X P5, 它们同时依次进入就绪队列，它们的 彳尤先数希口需要的处理机时间女口下: 进程 P1 P2 P3 P4 ■ P5 处理机时间 10 1 2 1 5 优先数 3 1 3 4 2 忽略进程调度所花的时间，要求： (1)分别写出采用先来先服务调度算法和静态优 先级调度算法中进 程的执行次序： (2 )分别计算各进程在就绪队列中的等待吋间和 平均等待时间° ■解；(1)采用先来先服务调度算法时各进程的执 行次序为：Pl— P2—P3 —P4—P5a ■采用静态优先级调度算法时各进程的执行次序为’ P4— P 4 — P3 — P5— F2。 (2) FCFS中，平土匀等待日寸间= (0 + 10+1 1 +13+14) /5 = 9. 6； 静态优先级法中，平均等待时间= (1 + 18+1 1+0+13) /5 = 8, 6 进程 处5HML时M FCFS^^It 寸冋 静态优加纽江曾待I时网 P1 P2 P3 P4 P5 10 1 2 1 5 0 10 1 1 13 14 1 18 11 0 13 3. 最短作业/进程优先法(SJF/SPF): SJF:从后备队列中选择估计运行时间最短的作业， 先调入内存运行。 SPF:从就绪队列中选择估计运行时间最短的进程，先将处理机分配给它，使它立即执 行。 4. 最高响应比作业优先算法(HRN)：是对FCFS方式和SJF方式的一种综合平衡响应 比。R =(作业等待时间+需运行时间 \需运行时间 =1 +已等待时间/需运行时间 =1 + W/T
操作系统计算题
