综合练习题

调度过程（时间片=10ms）：

• 0-10ms: P1（剩余10ms）
• 10-20ms: P2（剩余5ms）
• 20-30ms: P3（剩余20ms）
• 30-40ms: P4（完成，周转时间=40ms）
• 40-50ms: P1（完成，周转时间=50ms）
• 50-55ms: P2（完成，周转时间=55ms）
• 55-65ms: P3（剩余10ms）
• 65-75ms: P3（完成，周转时间=75ms）

各进程周转时间：

• P1: 50ms
• P2: 55ms
• P3: 75ms
• P4: 40ms

平均周转时间 = (50+55+75+40)/4 = 220/4 = 55ms

答案：P1=50ms，P2=55ms，P3=75ms，P4=40ms，平均周转时间=55ms。

(1) Need = Max - Allocation：

• P0: (7,5,3)-(0,1,0) = (7,4,3)
• P1: (3,2,2)-(2,0,0) = (1,2,2)
• P2: (9,0,2)-(3,0,2) = (6,0,0)
• P3: (2,2,2)-(2,1,1) = (0,1,1)
• P4: (4,3,3)-(0,0,2) = (4,3,1)

Available = 总资源 - 已分配总和 已分配总和 = (0+2+3+2+0, 1+0+0+1+0, 0+0+2+1+2) = (7,2,5) Available = (10,5,7)-(7,2,5) = (3,3,2)

(2) 安全性检查：

• Available=(3,3,2)
• P1 Need=(1,2,2) ≤ (3,3,2)，执行P1，释放后Available=(3,3,2)+(2,0,0)=(5,3,2)
• P3 Need=(0,1,1) ≤ (5,3,2)，执行P3，释放后Available=(5,3,2)+(2,1,1)=(7,4,3)
• P0 Need=(7,4,3) ≤ (7,4,3)，执行P0，释放后Available=(7,4,3)+(0,1,0)=(7,5,3)
• P2 Need=(6,0,0) ≤ (7,5,3)，执行P2，释放后Available=(7,5,3)+(3,0,2)=(10,5,5)
• P4 Need=(4,3,1) ≤ (10,5,5)，执行P4

安全序列：P1 → P3 → P0 → P2 → P4

答案：(1) Need矩阵如上，Available=(3,3,2)；(2) 安全状态，安全序列P1→P3→P0→P2→P4。

设信号量：

• mutex = 1（互斥访问缓冲区）
• empty = n（空缓冲区数量）
• full = 0（满缓冲区数量）

生产者进程：

while (true) {
    生产产品;
    P(empty);      // 等待空缓冲区
    P(mutex);      // 进入临界区
    将产品放入缓冲区;
    V(mutex);      // 退出临界区
    V(full);       // 增加满缓冲区
}

消费者进程：

while (true) {
    P(full);       // 等待满缓冲区
    P(mutex);      // 进入临界区
    从缓冲区取出产品;
    V(mutex);      // 退出临界区
    V(empty);      // 增加空缓冲区
    消费产品;
}

注意：P操作的顺序很重要，必须先P(empty/full)再P(mutex)，否则可能死锁。V操作的顺序无关。

答案：如上伪代码，使用mutex、empty、full三个信号量。

1. 页面大小 4KB = 2^12，页内偏移 12 位
2. 逻辑地址 0x00003004：
   • 页号 = 0x00003004 >> 12 = 0x3 = 3
   • 页内偏移 = 0x00003004 & 0xFFF = 0x004 = 4
3. 查页表：页号3 → 页框号2
4. 物理地址 = 页框号 × 页面大小 + 页内偏移 = 2 × 4096 + 4 = 8192 + 4 = 8196 = 0x2004

答案：物理地址为 0x2004（8196）。

引用串：1,2,3,4,1,2,5,1,2,3,4,5（共12次引用），物理块数=3

FIFO算法：

• 1(缺), 2(缺), 3(缺), 4(缺,淘汰1), 1(缺,淘汰2), 2(缺,淘汰3), 5(缺,淘汰4), 1(命中), 2(命中), 3(缺,淘汰5), 4(缺,淘汰1), 5(缺,淘汰2)
• 缺页次数：9次
• 缺页率：9/12 = 75%

LRU算法：

• 1(缺), 2(缺), 3(缺), 4(缺,淘汰1), 1(缺,淘汰2), 2(缺,淘汰3), 5(缺,淘汰4), 1(命中), 2(命中), 3(缺,淘汰5), 4(缺,淘汰1), 5(缺,淘汰2)
• 缺页次数：10次
• 缺页率：10/12 ≈ 83.3%

OPT算法：

• 1(缺), 2(缺), 3(缺), 4(缺,淘汰3), 1(命中), 2(命中), 5(缺,淘汰4), 1(命中), 2(命中), 3(缺,淘汰5), 4(缺,淘汰1), 5(缺,淘汰2)
• 缺页次数：7次
• 缺页率：7/12 ≈ 58.3%

答案：FIFO缺页9次(75%)，LRU缺页10次(83.3%)，OPT缺页7次(58.3%)。

1. 每个磁盘块可存放的指针数 = 4KB / 4B = 1024 个

2. 直接块：12 × 4KB = 48KB

3. 一级间接：1 × 1024 × 4KB = 4MB

4. 二级间接：1 × 1024 × 1024 × 4KB = 4GB

5. 三级间接：1 × 1024 × 1024 × 1024 × 4KB = 4TB

6. 最大文件大小 = 48KB + 4MB + 4GB + 4TB

答案：最大文件大小约为 4TB + 4GB + 4MB + 48KB（约4.004TB）。

请求队列：98, 183, 37, 122, 14, 124, 65, 67 当前磁道：53，方向：磁道号增加

SCAN算法（电梯算法）： 先向增加方向处理，到达最远端后反向。

• 53 → 65 (12) → 67 (2) → 98 (31) → 122 (24) → 124 (2) → 183 (59) → 37 (146) → 14 (23)
• 总磁道数 = 12+2+31+24+2+59+146+23 = 299

C-SCAN算法（循环扫描）： 向增加方向处理到最远端，然后直接跳转到最远端（反向），继续向增加方向处理。

• 53 → 65 (12) → 67 (2) → 98 (31) → 122 (24) → 124 (2) → 183 (59) → 14 (169,跳转) → 37 (23)
• 总磁道数 = 12+2+31+24+2+59+169+23 = 322

（注：C-SCAN中从183跳转到14的移动是否计入取决于具体实现，通常计入。若不计入跳转，则为153。）

答案：SCAN总磁道数=299，C-SCAN总磁道数=322（含跳转）。

1. 设备数据传输率 = 2 MB/s = 2 × 1024 × 1024 B/s ≈ 2,097,152 B/s
2. 每次中断传输 4 字节
3. 每秒中断次数 = 2,097,152 / 4 = 524,288 次/秒
4. 每次中断 CPU 开销 = 2 μs
5. 每秒 CPU 用于该设备的时间 = 524,288 × 2 μs = 1,048,576 μs = 1.048576 s
6. CPU 时间占比 = 1.048576 / 1 = 104.86%

这超过了100%，说明中断方式无法满足该设备的传输需求，需要采用DMA方式。

答案：CPU时间占比约为104.9%，超过100%，说明中断方式无法满足需求，应采用DMA。

Spooling过程：作业先写入磁盘（输入井），再从磁盘读出打印。

1. 输入时间（写入磁盘）：

   • 总数据量 = 100 + 200 + 50 = 350 KB
   • 磁盘写入时间 = 350 KB / 10 MB/s = 350 / 10240 s ≈ 0.0342 s = 34.2 ms

2. 打印时间（从磁盘读出并打印）：

   • 打印是瓶颈，速度为 50 KB/s
   • 总打印时间 = 350 KB / 50 KB/s = 7 s

3. Spooling可以使输入和打印并行，但打印是瓶颈。

   • 第一个作业输入完成后即可开始打印
   • 总时间 ≈ 输入时间 + 打印时间（输入很快，打印是主要时间）
   • 更精确：第一个作业输入时间 = 100KB/10MB/s ≈ 9.8ms，然后开始打印
   • 打印总时间7s，输入在打印开始后很快完成（34.2ms）
   • 总时间 ≈ 9.8ms + 7s ≈ 7.01s

答案：总时间约为 7.01 秒（打印是瓶颈，输入可与打印并行）。

1. 缺页率 = (1000 - 700) / 1000 = 30% = 0.3

2. 命中率 = 70% = 0.7

3. 平均缺页处理时间：

   • 有空闲页框(20%)：1 μs = 1000 ns
   • 置换未修改(50%)：10 μs = 10000 ns
   • 置换已修改(30%)：20 μs = 20000 ns
   • 平均缺页时间 = 0.2×1000 + 0.5×10000 + 0.3×20000 = 200 + 5000 + 6000 = 11200 ns

4. 有效访问时间 EAT： EAT = 命中率 × 内存访问时间 + 缺页率 × (缺页处理时间 + 内存访问时间) = 0.7 × 100 + 0.3 × (11200 + 100) = 70 + 0.3 × 11300 = 70 + 3390 = 3460 ns = 3.46 μs

答案：有效访问时间为 3460 ns（3.46 μs）。