在学习和掌握操作系统知识的过程中，计算题是检验我们理解程度的重要手段。王道操作系统作为一本经典的教材，其中的计算题尤其考验我们对操作系统的深入理解。本文将详细解析王道操作系统中的几个典型计算题，帮助读者轻松掌握核心技能，告别学习难题。
一、进程调度算法的计算题
1. FCFS（先来先服务）调度算法
问题描述：假设有5个进程，它们的到达时间和服务时间如下表所示，使用FCFS调度算法计算平均周转时间和平均带权周转时间。
| 进程ID | 到达时间 | 服务时间 |
|---|---|---|
| P1 | 0 | 3 |
| P2 | 1 | 6 |
| P3 | 2 | 4 |
| P4 | 3 | 5 |
| P5 | 4 | 2 |
解题步骤：
- 按照进程到达时间排序，得到调度顺序：P1, P2, P3, P4, P5。
- 计算每个进程的完成时间、等待时间和周转时间。
- 计算平均周转时间和平均带权周转时间。
代码示例：
processes = [
{"id": 1, "arrival_time": 0, "service_time": 3},
{"id": 2, "arrival_time": 1, "service_time": 6},
{"id": 3, "arrival_time": 2, "service_time": 4},
{"id": 4, "arrival_time": 3, "service_time": 5},
{"id": 5, "arrival_time": 4, "service_time": 2}
]
def fcfs(processes):
# 按照到达时间排序
processes.sort(key=lambda x: x["arrival_time"])
# 初始化变量
completion_time = 0
waiting_time = 0
turnaround_time = 0
weighted_turnaround_time = 0
# 遍历进程
for process in processes:
completion_time += process["service_time"]
waiting_time = completion_time - process["arrival_time"]
turnaround_time = waiting_time + process["service_time"]
weighted_turnaround_time += (turnaround_time / process["service_time"])
# 计算平均周转时间和平均带权周转时间
average_turnaround_time = turnaround_time / len(processes)
average_weighted_turnaround_time = weighted_turnaround_time / len(processes)
return average_turnaround_time, average_weighted_turnaround_time
average_turnaround_time, average_weighted_turnaround_time = fcfs(processes)
print("平均周转时间：", average_turnaround_time)
print("平均带权周转时间：", average_weighted_turnaround_time)
2. SJF（最短作业优先）调度算法
问题描述：假设有5个进程，它们的到达时间和服务时间如下表所示，使用SJF调度算法计算平均周转时间和平均带权周转时间。
| 进程ID | 到达时间 | 服务时间 |
|---|---|---|
| P1 | 0 | 3 |
| P2 | 1 | 6 |
| P3 | 2 | 4 |
| P4 | 3 | 5 |
| P5 | 4 | 2 |
解题步骤：
- 按照进程到达时间排序，得到调度顺序：P1, P2, P3, P4, P5。
- 从到达时间最早的进程开始，选择服务时间最短的进程执行。
- 计算每个进程的完成时间、等待时间和周转时间。
- 计算平均周转时间和平均带权周转时间。
代码示例：
def sjf(processes):
# 按照到达时间排序
processes.sort(key=lambda x: x["arrival_time"])
# 初始化变量
completion_time = 0
waiting_time = 0
turnaround_time = 0
weighted_turnaround_time = 0
# 遍历进程
for process in processes:
if process["arrival_time"] > completion_time:
completion_time = process["arrival_time"]
service_time = min([p["service_time"] for p in processes if p["arrival_time"] <= completion_time])
for p in processes:
if p["service_time"] == service_time and p["arrival_time"] <= completion_time:
completion_time += service_time
waiting_time = completion_time - p["arrival_time"]
turnaround_time = waiting_time + service_time
weighted_turnaround_time += (turnaround_time / service_time)
# 计算平均周转时间和平均带权周转时间
average_turnaround_time = turnaround_time / len(processes)
average_weighted_turnaround_time = weighted_turnaround_time / len(processes)
return average_turnaround_time, average_weighted_turnaround_time
average_turnaround_time, average_weighted_turnaround_time = sjf(processes)
print("平均周转时间：", average_turnaround_time)
print("平均带权周转时间：", average_weighted_turnaround_time)
二、内存管理计算题
1. 分区分配策略的计算题
问题描述：假设内存大小为100MB，进程P1、P2、P3、P4、P5的内存需求分别为20MB、30MB、10MB、50MB、40MB，使用固定分区分配策略进行内存分配，计算内存碎片情况。
解题步骤：
- 按照进程内存需求大小进行排序。
- 将内存划分为与进程内存需求相等的分区。
- 将进程分配到对应的分区。
- 计算内存碎片。
代码示例：
processes = [
{"id": 1, "memory_requirement": 20},
{"id": 2, "memory_requirement": 30},
{"id": 3, "memory_requirement": 10},
{"id": 4, "memory_requirement": 50},
{"id": 5, "memory_requirement": 40}
]
def fixed_partition(processes, memory_size):
# 按照内存需求大小排序
processes.sort(key=lambda x: x["memory_requirement"])
# 初始化内存分区
partitions = []
# 遍历进程
for process in processes:
if len(partitions) == 0 or partitions[-1]["size"] >= process["memory_requirement"]:
partition = {"id": process["id"], "size": process["memory_requirement"]}
partitions.append(partition)
else:
partition = partitions[-1]
partition["size"] += process["memory_requirement"]
# 计算内存碎片
memory_fragmentation = memory_size - sum([p["size"] for p in partitions])
return partitions, memory_fragmentation
partitions, memory_fragmentation = fixed_partition(processes, 100)
print("内存分区：", partitions)
print("内存碎片：", memory_fragmentation)
通过以上解析，相信读者已经能够轻松掌握王道操作系统计算题的核心技能。在学习和练习过程中，多加思考和实践，才能更好地理解和应用操作系统知识。