操作系统作业3应用题详解与实战技巧助你高效掌握进程调度与内存管理核心概念

引言

操作系统是计算机科学的核心课程，而进程调度和内存管理是操作系统中最为关键的两个概念。作业3通常会涉及这两个领域的实际应用题，帮助学生从理论走向实践。本文将详细解析进程调度和内存管理的常见应用题，并提供实战技巧，帮助你高效掌握这些核心概念。

进程调度应用题详解

1. 进程调度的基本概念

进程调度是操作系统决定哪个进程在何时获得CPU使用权的过程。常见的调度算法包括先来先服务（FCFS）、短作业优先（SJF）、优先级调度、轮转法（RR）等。

示例题目：

假设有以下四个进程，到达时间和执行时间如下：

进程	到达时间	执行时间
P1	0	7
P2	2	4
P3	4	1
P4	5	4

分别使用FCFS、SJF（非抢占式和抢占式）、RR（时间片=2）算法计算平均等待时间和平均周转时间。

2. FCFS（先来先服务）算法

FCFS是最简单的调度算法，按照进程到达的顺序分配CPU。

计算过程：

• 进程顺序：P1 → P2 → P3 → P4
• P1：等待时间=0，周转时间=7
• P2：等待时间=7-2=5，周转时间=5+4=9
• P3：等待时间=9-4=5，周转时间=5+1=6
• P4：等待时间=6-5=1，周转时间=1+4=5

平均等待时间 = (0+5+5+1)/4 = 2.75
平均周转时间 = (7+9+6+5)/4 = 6.75

3. SJF（短作业优先）算法

非抢占式SJF：

• 在每个进程完成时，从就绪队列中选择执行时间最短的进程。

计算过程：

• 初始就绪队列：P1（到达时间0）
• P1执行7单位时间，完成时间=7
• 此时已到达进程：P2（2）、P3（4）、P4（5）
• 选择执行时间最短的P3（1），完成时间=8
• 剩余进程：P2（4）、P4（4），选择P2，完成时间=12
• 最后P4，完成时间=16

等待时间：

• P1：0
• P2：7-2=5
• P3：8-4=4
• P4：12-5=7

平均等待时间 = (0+5+4+7)/4 = 4
平均周转时间 = (7+9+5+11)/4 = 8

抢占式SJF（最短剩余时间优先SRTF）：

• 每当有新进程到达时，比较剩余时间，选择最短的执行。

计算过程：

• 时间0：P1（剩余7）
• 时间2：P2到达（剩余4），P1剩余5，选择P2
• 时间4：P3到达（剩余1），P2剩余2，选择P3
• 时间5：P4到达（剩余4），P3剩余0，选择P2（剩余2）
• 时间6：P2完成，选择P1（剩余5）
• 时间11：P1完成，选择P4（剩余4）
• 时间15：P4完成

等待时间：

• P1：(2-0)+(11-6)=2+5=7
• P2：(4-2)+(6-4)=2+2=4
• P3：0
• P4：15-5=10

平均等待时间 = (7+4+0+10)/4 = 5.25
平均周转时间 = (12+6+1+10)/4 = 7.25

4. RR（轮转法）算法

RR算法使用时间片轮转的方式分配CPU，时间片=2。

计算过程：

• 队列初始状态：[P1]
• 时间0-2：P1执行2，剩余5，队列变为[P2, P1]
• 时间2-4：P2执行2，剩余2，队列变为[P1, P3, P2]
• 时间4-5：P1执行1，剩余4，P3到达，队列变为[P3, P2, P1]
• 时间5-6：P3执行1，完成，队列变为[P2, P1, P4]
• 时间6-8：P2执行2，完成，队列变为[P1, P4]
• 时间8-10：P1执行2，剩余2，队列变为[P4, P1]
• 时间10-12：P4执行2，剩余2，队列变为[P1, P4]
• 时间12-14：P1执行2，完成，队列变为[P4]
• 时间14-16：P4执行2，完成

等待时间：

• P1：(2-0)+(5-4)+(8-6)+(12-10)=2+1+2+2=7
• P2：(4-2)+(6-5)=2+1=3
• P3：0
• P4：(10-5)+(12-10)+(14-12)=5+2+2=9

平均等待时间 = (7+3+0+9)/4 = 4.75
平均周转时间 = (14+6+1+11)/4 = 8

5. 进程调度实战技巧

1. 制作时间线图表：在纸上画出时间线，标记每个进程的执行区间，直观展示调度过程。
2. 注意进程到达时间：不同算法对新到达进程的处理方式不同（抢占式与非抢占式）。
3. 计算周转时间：周转时间=完成时间-到达时间，等待时间=周转时间-执行时间。
4. 处理同时到达：如果多个进程同时到达，通常按进程ID顺序或执行时间顺序处理。
5. 时间片轮转细节：注意时间片用完和进程阻塞的区别，RR中时间片用完会重新放入队尾。

内存管理应用题详解

1. 内存管理的基本概念

内存管理负责分配和回收内存空间，常见的管理方式包括连续分配（固定分区、可变分区）、分页、分段、段页式等。

示例题目：

假设内存容量为1024MB，采用分页存储管理，页面大小为1KB。某进程有8页，分别装入内存块2、4、5、7、8、10、12、14。计算逻辑地址0x000004A7和0x000008F3对应的物理地址。

2. 分页存储管理

分页存储将逻辑地址分为页号和页内偏移两部分。

计算过程：

• 页面大小1KB=1024字节，页内偏移占10位（2^10=1024）
• 逻辑地址结构：页号（高22位）+页内偏移（低10位）

逻辑地址0x000004A7：

• 0x4A7 = 0000 0000 0000 0000 0000 0100 1010 0111
• 页内偏移：低10位 = 0x0A7 = 167
• 页号：高22位 = 0x1 = 1
• 查页表：页号1对应物理块5
• 物理地址 = 块号×块大小 + 偏移 = 5×1024 + 167 = 5120 + 167 = 5287（0x14A7）

逻辑地址0x000008F3：

• 0x8F3 = 0000 0000 0000 0000 0000 1000 1111 0011
• 页内偏移：低10位 = 0x0F3 = 243
• 页号：高22位 = 0x2 = 2
• 查页表：页号2对应物理块7
• 物理地址 = 7×1024 + 243 = 7168 + 243 = 7411（0x1CF3）

3. 可变分区分配算法

可变分区分配包括首次适应（FF）、最佳适应（BF）、最坏适应（WF）等算法。

示例题目：

内存初始有100KB空闲区，按地址从小到大排列。进程请求顺序：P1(30KB)、P2(20KB)、P3(15KB)、P4(10KB)。使用FF、BF、WF算法分配，然后P2释放，再请求P5(25KB)。画出内存变化图。

FF算法：

• 初始：[100KB]
• P1(30)：分配30，剩余70（地址0-30已用，30-100空闲）
• P2(20)：分配20，剩余50（地址30-50已用，50-100空闲）
• P3(15)：分配15，剩余35（地址50-65已用，65-100空闲）
• P4(10)：分配10，剩余25（地址65-75已用，75-100空闲）
• P2释放：合并后空闲区为[30-50]和[75-100]，但FF按地址顺序合并为[30-100]（70KB）
• P5(25)：分配25，剩余45（地址30-55已用，55-100空闲）

BF算法：

• 初始：[100KB]
• P1(30)：分配30，剩余70
• P2(20)：分配20，剩余50
• P3(15)：分配15，剩余35
• P4(10)：分配10，剩余25
• P2释放：空闲区[30-50]（20KB）和[75-100]（25KB）
• P5(25)：选择25KB分区（BF选择最小的能满足的），分配后剩余0

WF算法：

• 初始：[100KB]
• P1(30)：分配30，剩余70
• P2(20)：分配20，剩余50
• P3(15)：分配15，剩余35
• P4(10)：分配10，剩余25
• P2释放：空闲区[30-50]（20KB）和[75-100]（25KB）
• P5(25)：选择25KB分区（WF选择最大的能满足的），分配后剩余0

4. 页面置换算法

常见的页面置换算法包括OPT、FIFO、LRU等。

示例题目：

页面访问序列：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1。使用FIFO和LRU算法计算缺页次数（假设内存有3个页框）。

FIFO（先进先出）：

• 初始：[]
• 7: 7
• 0: 7,0
• 1: 7,0,1
• 2: 0,1,2
• 0: 0,1,2
• 3: 1,2,3
• 0: 2,3,0
• 4: 3,0,4
• 2: 0,4,2
• 3: 4,2,3
• 3: 4,2,3
• 0: 2,3,0
• 3: 2,3,0
• 2: 2,3,0
• 1: 3,0,1
• 2: 0,1,2
• 0: 0,1,2
• 1: 0,1,2
• 7: 1,2,7
• 0: 2,7,0

缺页次数：15

LRU（最近最少使用）：

• 初始：[]
• 7: 7
• 0: 7,0
• 1: 7,0,1
• 2: 0,1,2
• 0: 0,1,2
• 3: 1,2,3
• 0: 2,3,0
• 4: 3,0,4
• 2: 0,4,2
• 3: 4,2,3
• 0: 2,3,0
• 3: 2,3,0
• 2: 2,3,0
• 1: 3,0,1
• 2: 0,1,2
• 0: 0,1,2
• 1: 0,1,2
• 7: 1,2,7
• 0: 2,7,0

缺页次数：15

5. 内存管理实战技巧

1. 地址转换技巧：对于分页系统，先计算页号和页内偏移，再查页表。
2. 分区分配算法比较：
   • FF：简单，但可能产生外部碎片
   • BF：尽量使用小分区，减少碎片
   • WF：尽量使用大分区，减少碎片但可能浪费大空间
3. 页面置换算法选择：
   • OPT：理想算法，无法实现，用于比较
   • FIFO：简单但可能出现Belady现象
   • LRU：接近OPT，但实现复杂
4. 缺页率计算：缺页次数/总访问次数，注意内存大小和页面大小的影响
5. 碎片处理：外部碎片（可变分区）和内部碎片（固定分区、分页）的区别

综合应用题

示例题目：

一个系统采用分页存储管理，页面大小为4KB，逻辑地址空间为256页，物理内存128MB。计算：

1. 逻辑地址结构
2. 页表项大小（假设支持64位物理地址）
3. 若采用两级页表，每页可存放256个页表项，计算页目录号和页号位数

解答：

1. 逻辑地址结构：

   • 页面大小4KB=2^12，页内偏移占12位
   • 逻辑地址空间256页=2^8，页号占8位
   • 逻辑地址 = 页号（8位）+页内偏移（12位）= 20位

2. 页表项大小：

   • 物理内存128MB=2^27，块号需27位
   • 支持64位物理地址，块号需64位
   • 页表项还需状态位、访问位、修改位等，假设共需8字节（64位）

3. 两级页表：

   • 页目录号位数：总页号8位，每页256项=2^8，页目录号=8-8=0位？不对
   • 正确计算：一级页表256项，页目录号8位；剩余页号0位？不对
   • 实际：总页号8位，一级页表256项（8位），所以页目录号8位，页号0位？不合理
   • 重新理解：两级页表是将页号分为两部分，假设页目录号m位，页号n位，m+n=8
   • 每页可存256项=2^8，所以页目录号m=8-n
   • 通常均分，m=4，n=4，页目录号4位，页号4位

实战技巧总结

进程调度：

1. 制作时间线：画出时间轴，标记进程执行区间
2. 注意抢占时机：抢占式算法在新进程到达或时间片用完时可能抢占
3. 计算公式：
   • 周转时间 = 完成时间 - 到达时间
   • 等待时间 = 周转时间 - 执行时间
4. 处理同时到达：按进程ID顺序或执行时间顺序处理
5. RR时间片：注意时间片用完后进程重新入队

内存管理：

1. 地址转换：先分离页号和页内偏移，再查页表
2. 分区算法：FF、BF、WF的选择和碎片分析
3. 页面置换：理解各种算法的置换策略和缺页率
4. 两级页表：合理分配页目录号和页号位数
5. 碎片分析：外部碎片（可变分区）和内部碎片（分页）的区别

结语

通过本文的详细解析和实战技巧，相信你对进程调度和内存管理的核心概念有了更深入的理解。在实际操作中，多做练习题，制作时间线图表，注意细节处理，你将能够高效掌握这些关键知识点。继续努力，操作系统学习将不再困难！# 操作系统作业3应用题详解与实战技巧助你高效掌握进程调度与内存管理核心概念

引言

操作系统是计算机科学的核心课程，而进程调度和内存管理是操作系统中最为关键的两个概念。作业3通常会涉及这两个领域的实际应用题，帮助学生从理论走向实践。本文将详细解析进程调度和内存管理的常见应用题，并提供实战技巧，帮助你高效掌握这些核心概念。

进程调度应用题详解

1. 进程调度的基本概念

进程调度是操作系统决定哪个进程在何时获得CPU使用权的过程。常见的调度算法包括先来先服务（FCFS）、短作业优先（SJF）、优先级调度、轮转法（RR）等。

示例题目：

假设有以下四个进程，到达时间和执行时间如下：

进程	到达时间	执行时间
P1	0	7
P2	2	4
P3	4	1
P4	5	4

分别使用FCFS、SJF（非抢占式和抢占式）、RR（时间片=2）算法计算平均等待时间和平均周转时间。

2. FCFS（先来先服务）算法

FCFS是最简单的调度算法，按照进程到达的顺序分配CPU。

计算过程：

• 进程顺序：P1 → P2 → P3 → P4
• P1：等待时间=0，周转时间=7
• P2：等待时间=7-2=5，周转时间=5+4=9
• P3：等待时间=9-4=5，周转时间=5+1=6
• P4：等待时间=6-5=1，周转时间=1+4=5

平均等待时间 = (0+5+5+1)/4 = 2.75
平均周转时间 = (7+9+6+5)/4 = 6.75

3. SJF（短作业优先）算法

非抢占式SJF：

• 在每个进程完成时，从就绪队列中选择执行时间最短的进程。

计算过程：

• 初始就绪队列：P1（到达时间0）
• P1执行7单位时间，完成时间=7
• 此时已到达进程：P2（2）、P3（4）、P4（5）
• 选择执行时间最短的P3（1），完成时间=8
• 剩余进程：P2（4）、P4（4），选择P2，完成时间=12
• 最后P4，完成时间=16

等待时间：

• P1：0
• P2：7-2=5
• P3：8-4=4
• P4：12-5=7

平均等待时间 = (0+5+4+7)/4 = 4
平均周转时间 = (7+9+5+11)/4 = 8

抢占式SJF（最短剩余时间优先SRTF）：

• 每当有新进程到达时，比较剩余时间，选择最短的执行。

计算过程：

• 时间0：P1（剩余7）
• 时间2：P2到达（剩余4），P1剩余5，选择P2
• 时间4：P3到达（剩余1），P2剩余2，选择P3
• 时间5：P4到达（剩余4），P3剩余0，选择P2（剩余2）
• 时间6：P2完成，选择P1（剩余5）
• 时间11：P1完成，选择P4（剩余4）
• 时间15：P4完成

等待时间：

• P1：(2-0)+(11-6)=2+5=7
• P2：(4-2)+(6-4)=2+2=4
• P3：0
• P4：15-5=10

平均等待时间 = (7+4+0+10)/4 = 5.25
平均周转时间 = (12+6+1+10)/4 = 7.25

4. RR（轮转法）算法

RR算法使用时间片轮转的方式分配CPU，时间片=2。

计算过程：

• 队列初始状态：[P1]
• 时间0-2：P1执行2，剩余5，队列变为[P2, P1]
• 时间2-4：P2执行2，剩余2，队列变为[P1, P3, P2]
• 时间4-5：P1执行1，剩余4，P3到达，队列变为[P3, P2, P1]
• 时间5-6：P3执行1，完成，队列变为[P2, P1, P4]
• 时间6-8：P2执行2，完成，队列变为[P1, P4]
• 时间8-10：P1执行2，剩余2，队列变为[P4, P1]
• 时间10-12：P4执行2，剩余2，队列变为[P1, P4]
• 时间12-14：P1执行2，完成，队列变为[P4]
• 时间14-16：P4执行2，完成

等待时间：

• P1：(2-0)+(5-4)+(8-6)+(12-10)=2+1+2+2=7
• P2：(4-2)+(6-5)=2+1=3
• P3：0
• P4：(10-5)+(12-10)+(14-12)=5+2+2=9

平均等待时间 = (7+3+0+9)/4 = 4.75
平均周转时间 = (14+6+1+11)/4 = 8

5. 进程调度实战技巧

1. 制作时间线图表：在纸上画出时间线，标记每个进程的执行区间，直观展示调度过程。
2. 注意进程到达时间：不同算法对新到达进程的处理方式不同（抢占式与非抢占式）。
3. 计算周转时间：周转时间=完成时间-到达时间，等待时间=周转时间-执行时间。
4. 处理同时到达：如果多个进程同时到达，通常按进程ID顺序或执行时间顺序处理。
5. 时间片轮转细节：注意时间片用完和进程阻塞的区别，RR中时间片用完会重新放入队尾。

内存管理应用题详解

1. 内存管理的基本概念

内存管理负责分配和回收内存空间，常见的管理方式包括连续分配（固定分区、可变分区）、分页、分段、段页式等。

示例题目：

假设内存容量为1024MB，采用分页存储管理，页面大小为1KB。某进程有8页，分别装入内存块2、4、5、7、8、10、12、14。计算逻辑地址0x000004A7和0x000008F3对应的物理地址。

2. 分页存储管理

分页存储将逻辑地址分为页号和页内偏移两部分。

计算过程：

• 页面大小1KB=1024字节，页内偏移占10位（2^10=1024）
• 逻辑地址结构：页号（高22位）+页内偏移（低10位）

逻辑地址0x000004A7：

• 0x4A7 = 0000 0000 0000 0000 0000 0100 1010 0111
• 页内偏移：低10位 = 0x0A7 = 167
• 页号：高22位 = 0x1 = 1
• 查页表：页号1对应物理块5
• 物理地址 = 块号×块大小 + 偏移 = 5×1024 + 167 = 5120 + 167 = 5287（0x14A7）

逻辑地址0x000008F3：

• 0x8F3 = 0000 0000 0000 0000 0000 1000 1111 0011
• 页内偏移：低10位 = 0x0F3 = 243
• 页号：高22位 = 0x2 = 2
• 查页表：页号2对应物理块7
• 物理地址 = 7×1024 + 243 = 7168 + 243 = 7411（0x1CF3）

3. 可变分区分配算法

可变分区分配包括首次适应（FF）、最佳适应（BF）、最坏适应（WF）等算法。

示例题目：

内存初始有100KB空闲区，按地址从小到大排列。进程请求顺序：P1(30KB)、P2(20KB)、P3(15KB)、P4(10KB)。使用FF、BF、WF算法分配，然后P2释放，再请求P5(25KB)。画出内存变化图。

FF算法：

• 初始：[100KB]
• P1(30)：分配30，剩余70（地址0-30已用，30-100空闲）
• P2(20)：分配20，剩余50（地址30-50已用，50-100空闲）
• P3(15)：分配15，剩余35（地址50-65已用，65-100空闲）
• P4(10)：分配10，剩余25（地址65-75已用，75-100空闲）
• P2释放：合并后空闲区为[30-50]和[75-100]，但FF按地址顺序合并为[30-100]（70KB）
• P5(25)：分配25，剩余45（地址30-55已用，55-100空闲）

BF算法：

• 初始：[100KB]
• P1(30)：分配30，剩余70
• P2(20)：分配20，剩余50
• P3(15)：分配15，剩余35
• P4(10)：分配10，剩余25
• P2释放：空闲区[30-50]（20KB）和[75-100]（25KB）
• P5(25)：选择25KB分区（BF选择最小的能满足的），分配后剩余0

WF算法：

• 初始：[100KB]
• P1(30)：分配30，剩余70
• P2(20)：分配20，剩余50
• P3(15)：分配15，剩余35
• P4(10)：分配10，剩余25
• P2释放：空闲区[30-50]（20KB）和[75-100]（25KB）
• P5(25)：选择25KB分区（WF选择最大的能满足的），分配后剩余0

4. 页面置换算法

常见的页面置换算法包括OPT、FIFO、LRU等。

示例题目：

页面访问序列：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1。使用FIFO和LRU算法计算缺页次数（假设内存有3个页框）。

FIFO（先进先出）：

• 初始：[]
• 7: 7
• 0: 7,0
• 1: 7,0,1
• 2: 0,1,2
• 0: 0,1,2
• 3: 1,2,3
• 0: 2,3,0
• 4: 3,0,4
• 2: 0,4,2
• 3: 4,2,3
• 3: 4,2,3
• 0: 2,3,0
• 3: 2,3,0
• 2: 2,3,0
• 1: 3,0,1
• 2: 0,1,2
• 0: 0,1,2
• 1: 0,1,2
• 7: 1,2,7
• 0: 2,7,0

缺页次数：15

LRU（最近最少使用）：

• 初始：[]
• 7: 7
• 0: 7,0
• 1: 7,0,1
• 2: 0,1,2
• 0: 0,1,2
• 3: 1,2,3
• 0: 2,3,0
• 4: 3,0,4
• 2: 0,4,2
• 3: 4,2,3
• 0: 2,3,0
• 3: 2,3,0
• 2: 2,3,0
• 1: 3,0,1
• 2: 0,1,2
• 0: 0,1,2
• 1: 0,1,2
• 7: 1,2,7
• 0: 2,7,0

缺页次数：15

5. 内存管理实战技巧

1. 地址转换技巧：对于分页系统，先计算页号和页内偏移，再查页表。
2. 分区分配算法比较：
   • FF：简单，但可能产生外部碎片
   • BF：尽量使用小分区，减少碎片
   • WF：尽量使用大分区，减少碎片但可能浪费大空间
3. 页面置换算法选择：
   • OPT：理想算法，无法实现，用于比较
   • FIFO：简单但可能出现Belady现象
   • LRU：接近OPT，但实现复杂
4. 缺页率计算：缺页次数/总访问次数，注意内存大小和页面大小的影响
5. 碎片处理：外部碎片（可变分区）和内部碎片（固定分区、分页）的区别

综合应用题

示例题目：

一个系统采用分页存储管理，页面大小为4KB，逻辑地址空间为256页，物理内存128MB。计算：

1. 逻辑地址结构
2. 页表项大小（假设支持64位物理地址）
3. 若采用两级页表，每页可存放256个页表项，计算页目录号和页号位数

解答：

1. 逻辑地址结构：

   • 页面大小4KB=2^12，页内偏移占12位
   • 逻辑地址空间256页=2^8，页号占8位
   • 逻辑地址 = 页号（8位）+页内偏移（12位）= 20位

2. 页表项大小：

   • 物理内存128MB=2^27，块号需27位
   • 支持64位物理地址，块号需64位
   • 页表项还需状态位、访问位、修改位等，假设共需8字节（64位）

3. 两级页表：

   • 页目录号位数：总页号8位，每页256项=2^8，页目录号=8-8=0位？不对
   • 正确计算：一级页表256项，页目录号8位；剩余页号0位？不对
   • 实际：总页号8位，一级页表256项（2^8），所以页目录号8位，页号0位？不合理
   • 重新理解：两级页表是将页号分为两部分，假设页目录号m位，页号n位，m+n=8
   • 每页可存256项=2^8，所以页目录号m=8-n
   • 通常均分，m=4，n=4，页目录号4位，页号4位

实战技巧总结

进程调度：

1. 制作时间线：画出时间轴，标记进程执行区间
2. 注意抢占时机：抢占式算法在新进程到达或时间片用完时可能抢占
3. 计算公式：
   • 周转时间 = 完成时间 - 到达时间
   • 等待时间 = 周转时间 - 执行时间
4. 处理同时到达：按进程ID顺序或执行时间顺序处理
5. RR时间片：注意时间片用完后进程重新入队

内存管理：

1. 地址转换：先分离页号和页内偏移，再查页表
2. 分区算法：FF、BF、WF的选择和碎片分析
3. 页面置换：理解各种算法的置换策略和缺页率
4. 两级页表：合理分配页目录号和页号位数
5. 碎片分析：外部碎片（可变分区）和内部碎片（分页）的区别

结语

通过本文的详细解析和实战技巧，相信你对进程调度和内存管理的核心概念有了更深入的理解。在实际操作中，多做练习题，制作时间线图表，注意细节处理，你将能够高效掌握这些关键知识点。继续努力，操作系统学习将不再困难！