实验报告
学院（系）名称：计算机与通信工程学院
姓名 班级
卢洪利 2014级4班 课程名称
学号 实验项目
操作系统
20116年12月 8 日 第3、4节 20116年12月12日 第7、8节 20116年12月15日 第3、4节 20116年12月19日 第7、8节
20146049
专业
计算机科学与技术
实验三：磁盘调度算法的实现
课程代码
0668036 软件实验室7-220 软件实验室7-220 软件实验室7-220
实验时间 实验地点
批改意见
成绩
教师签字：
实验环境：
●操作系统：Fedora 25 with Linux 4.8.13-300.fc25.x86_64 ●编程语言：Python 3.5.2
●开发环境：PyCharm 2016.3.1
实验内容：
1．本实验是模拟操作系统的磁盘寻道方式，运用磁盘访问顺序的不同来设计磁盘的调度算法。 2．实现的磁盘调度算法有FCFS，SSTF，SCAN，CSCAN和 NStepSCAN算法。
3．设定开始磁道号寻道范围，依据起始扫描磁道号和最大磁道号数，随机产生要进行寻道的磁道号序
列。
4．选择磁盘调度算法，显示该算法的磁道访问顺序，计算出移动的磁道总数和平均寻道总数。 5．按算法的寻道效率进行排序，并对各算法的性能进行分析比较。
实验要求：
1．详细描述实验设计思想、程序结构及各模块设计思路； 2．详细描述程序所用数据结构及算法； 3．明确给出测试用例和实验结果；
4．为增加程序可读性，在程序中进行适当注释说明；
5．认真进行实验总结，包括：设计中遇到的问题、解决方法与收获等； 6．实验报告撰写要求结构清晰、描述准确逻辑性强；
7．实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。
设计思想：
设计一个类模拟磁头，给它分配运行方向，当前位置，程序的请求序列等属性，并附有各种寻道算法可以被公开调用，模拟的各种算法在执行时，会产生运行轨迹等数据，这些数据算做磁头的数据属性，随时使用随时清空。
FCFS算法按照请求序列依次满足程序的请求。 SSTF算法选择与当前位置最近的请求进行响应。
SCAN算法优先保证磁头的方向不发生改变的前提下，选择最近的请求进行响应。 CSCAN算法在SCAN算法的基础上，固定了磁头的移动方向。
NStepSCAN算法将请求分为多个队列，每个队列使用SCAN算法。一般将请求分成大于2的队列。 算法实现时，对于SCAN和CSCAN算法，先实现CSCAM算法，在其基础上，当磁头到达最接近边界的一个请求时，将磁头方向反转（代码中的reverse()函数实现这个功能）即可。
执行结果及测试用例：
进程的读磁盘请求： [129, 47, 31, 94, 153, 131, 106, 11, 182]（所有算法使用同样的测试用例） ====================================================== FCFS算法 初始位置： 28
访问顺序： [129, 47, 31, 94, 153, 131, 106, 11, 182] 移动距离： [101, 82, 16, 63, 59, 22, 25, 95, 171] 移动总数： 634 平均寻道： 70.44
====================================================== SSTF算法
初始位置： 28
访问顺序： [31, 47, 11, 94, 106, 129, 131, 153, 182] 移动距离： [3, 16, 36, 83, 12, 23, 2, 22, 29] 移动总数： 226 平均寻道： 25.11
====================================================== SCAN算法 初始位置： 28
初始移动方向：由里向外
访问顺序： [31, 47, 94, 106, 129, 131, 153, 182, 11] 移动总数： 325 平均寻道： 36.11
====================================================== CSCAN算法 初始位置： 28
移动方向：由里向外
访问顺序： [31, 47, 94, 106, 129, 131, 153, 182, 11] 移动总数： 164 平均寻道： 18.22
程序源代码：
# coding=utf-8 import random
class HEAD: """
magnetic head """
__location = -1 __next = -1 __request = []
# 大于0为由里向外，小于0 为由外向里 __direction = 0
# SCAN算法的磁道访问顺序 __scan_trace = []
# SSTF算法的磁道访问顺序 __sstf_trace = []
# FCFS算法的磁道访问顺序 __fcfs_trace = []
# 每次寻道的移动距离 __move_length = [] # 寻道的移动总距离 __sum_length = 0
def __init__(self):
self.__location = 1 self.__direction = 1
def __init__(self, location): self.__location = location if location > 100:
self.__direction = -1 elif location
self.__direction = 1
def __clear(self):
self.__sum_length = 0
self.__move_length.clear()
self.__sstf_trace.clear() self.__fcfs_trace.clear() self.__scan_trace.clear()
def get_location(self): return self.__location
def reverse(self):
if self.__direction == 1: self.__direction = -1 elif self.__direction == -1: self.__direction = 1
def request(self, rec):
self.__request.append(rec)
def show_request_list(self): print(self.__request)
def get_sstf_trace(self): return self.__sstf_trace
def get_fcfs_trace(self): return self.__fcfs_trace
def get_scan_trace(self): return self.__scan_trace
def get_move_length(self): return self.__move_length
def get_sum_length(self): return self.__sum_length
def get_direction(self): return self.__direction
def fcfs(self): self.__clear()
temp = self.__location
for rec in self.__request:
self.__move_length.append(abs(self.__location-rec)) self.__sum_length += abs(self.__location-rec) self.__location = rec
self.__fcfs_trace.append(self.__location) # 为了方便与其他算法做对比，将磁头复位 self.__location = temp
def sstf(self): self.__clear()
temp_loc = self.__location temp = self.__request.copy() while len(self.__request) != 0: min_length = 200 min_no = 0
for i in range(0, len(self.__request)): req = self.__request[i]
if abs(req - self.__location)
self.__location = self.__request[min_no] self.__sstf_trace.append(self.__location) del self.__request[min_no] self.__request = temp
# 为了方便与其他算法做对比，将磁头复位 self.__location = temp_loc
def cscan(self): self.__clear()
temp_request = self.__request.copy() temp_loc = self.__location
temp_direction = self.__direction while len(self.__request) != 0: min_length = 200 min_no = -1
if self.__direction == 1:
for i in range(0, len(self.__request)): req = self.__request[i]
if abs(req - self.__location) self.__location:
min_length = abs(req - self.__location) min_no = i if min_no == -1:
self.__location = 1 continue
elif self.__direction == -1:
for i in range(0, len(self.__request)): req = self.__request[i]
if abs(req - self.__location)
min_length = abs(req - self.__location) min_no = i if min_no == -1:
self.__location = 200 continue self.__move_length.append(abs(self.__location - self.__request[min_no])) self.__sum_length += abs(self.__location - self.__request[min_no])
self.__location = self.__request[min_no] self.__scan_trace.append(self.__location) del self.__request[min_no]
self.__request = temp_request self.__location = temp_loc
self.__direction = temp_direction
def scan(self): self.__clear()
temp_direction = self.__direction temp_request = self.__request.copy() temp_loc = self.__location
while len(self.__request) != 0: min_length = 200 min_no = -1
if self.__direction == 1:
for i in range(0, len(self.__request)): req = self.__request[i]
if req - self.__location self.__location:
min_length = abs(req - self.__location) min_no = i if min_no == -1: self.reverse() continue
elif self.__direction == -1:
for i in range(0, len(self.__request)): req = self.__request[i]
if self.__location - req
min_length = abs(req - self.__location) min_no = i if min_no == -1: self.reverse() continue self.__move_length.append(abs(self.__location self.__request[min_no])) self.__sum_length += abs(self.__location self.__request[min_no])
self.__location = self.__request[min_no] self.__scan_trace.append(self.__location) del self.__request[min_no]
self.__request = temp_request self.__location = temp_loc
self.__direction = temp_direction
def run_fcfs(head):
print("======================================================") print("FCFS算法")
print("初始位置： " + str(head.get_location())) head.fcfs()
print("访问顺序：", head.get_fcfs_trace()) print("移动距离：", head.get_move_length()) print("移动总数：", head.get_sum_length()) print("平均寻道：", round(head.get_sum_length() len(head.get_move_length()), 2))
def run_sstf(head):
print("======================================================") print("SSTF算法")
print("初始位置： " + str(head.get_location())) head.sstf()
print("访问顺序：", head.get_sstf_trace()) print("移动距离：", head.get_move_length()) print("移动总数：", head.get_sum_length()) print("平均寻道：", round(head.get_sum_length() len(head.get_move_length()), 2))
def run_cscan(head):
print("======================================================")
- -
/
/
print("CSCAN算法")
print("初始位置： " + str(head.get_location())) if head.get_direction() == 1: print("移动方向：由里向外")
elif head.get_direction() == -1: print("移动方向：由外向里") head.cscan()
print("访问顺序：", head.get_scan_trace()) # print("移动距离：", head.get_move_length()) print("移动总数：", head.get_sum_length()) print("平均寻道：", round(head.get_sum_length() len(head.get_move_length()), 2))
def run_scan(head):
print("======================================================") print("SCAN算法")
print("初始位置： " + str(head.get_location())) if head.get_direction() == 1: print("初始移动方向：由里向外") elif head.get_direction() == -1: print("初始移动方向：由外向里") head.scan()
print("访问顺序：", head.get_scan_trace()) # print("移动距离：", head.get_move_length()) print("移动总数：", head.get_sum_length()) print("平均寻道：", round(head.get_sum_length() len(head.get_move_length()), 2))
if __name__ == "__main__":
head = HEAD(random.randint(1, 200)) for i in range(0, 9):
head.request(random.randint(1, 200)) print("进程的读磁盘请求：", end=" ") head.show_request_list() run_fcfs(head) run_sstf(head) run_scan(head) run_cscan(head)
/
/
心得体会：
1.Python是一种动态语言，对数据类型不严格，使用时必需注意数据类型的控制。
2.这个实验中不同的算法可以实现互相调用以提高代码的重用率，比如NStepSCAN可以调用SCAN
算法进行小队列的处理。前提是算法和数据的设计足够清晰，容易分离。如上面我自己写的例子中，因为写前面的算法时没有考虑后续的可能要求，导致代码重用率很低，已经不方便对前几个算法进行修改。
【实验过程记录（源程序、测试用例、测试结果及心得体会等）】
实验报告
学院（系）名称：计算机与通信工程学院
姓名 班级
卢洪利 2014级4班 课程名称
学号 实验项目
操作系统
20116年12月 8 日 第3、4节 20116年12月12日 第7、8节 20116年12月15日 第3、4节 20116年12月19日 第7、8节
20146049
专业
计算机科学与技术
实验三：磁盘调度算法的实现
课程代码
0668036 软件实验室7-220 软件实验室7-220 软件实验室7-220
实验时间 实验地点
批改意见
成绩
教师签字：
实验环境：
●操作系统：Fedora 25 with Linux 4.8.13-300.fc25.x86_64 ●编程语言：Python 3.5.2
●开发环境：PyCharm 2016.3.1
实验内容：
1．本实验是模拟操作系统的磁盘寻道方式，运用磁盘访问顺序的不同来设计磁盘的调度算法。 2．实现的磁盘调度算法有FCFS，SSTF，SCAN，CSCAN和 NStepSCAN算法。
3．设定开始磁道号寻道范围，依据起始扫描磁道号和最大磁道号数，随机产生要进行寻道的磁道号序
列。
4．选择磁盘调度算法，显示该算法的磁道访问顺序，计算出移动的磁道总数和平均寻道总数。 5．按算法的寻道效率进行排序，并对各算法的性能进行分析比较。
实验要求：
1．详细描述实验设计思想、程序结构及各模块设计思路； 2．详细描述程序所用数据结构及算法； 3．明确给出测试用例和实验结果；
4．为增加程序可读性，在程序中进行适当注释说明；
5．认真进行实验总结，包括：设计中遇到的问题、解决方法与收获等； 6．实验报告撰写要求结构清晰、描述准确逻辑性强；
7．实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。
设计思想：
设计一个类模拟磁头，给它分配运行方向，当前位置，程序的请求序列等属性，并附有各种寻道算法可以被公开调用，模拟的各种算法在执行时，会产生运行轨迹等数据，这些数据算做磁头的数据属性，随时使用随时清空。
FCFS算法按照请求序列依次满足程序的请求。 SSTF算法选择与当前位置最近的请求进行响应。
SCAN算法优先保证磁头的方向不发生改变的前提下，选择最近的请求进行响应。 CSCAN算法在SCAN算法的基础上，固定了磁头的移动方向。
NStepSCAN算法将请求分为多个队列，每个队列使用SCAN算法。一般将请求分成大于2的队列。 算法实现时，对于SCAN和CSCAN算法，先实现CSCAM算法，在其基础上，当磁头到达最接近边界的一个请求时，将磁头方向反转（代码中的reverse()函数实现这个功能）即可。
执行结果及测试用例：
进程的读磁盘请求： [129, 47, 31, 94, 153, 131, 106, 11, 182]（所有算法使用同样的测试用例） ====================================================== FCFS算法 初始位置： 28
访问顺序： [129, 47, 31, 94, 153, 131, 106, 11, 182] 移动距离： [101, 82, 16, 63, 59, 22, 25, 95, 171] 移动总数： 634 平均寻道： 70.44
====================================================== SSTF算法
初始位置： 28
访问顺序： [31, 47, 11, 94, 106, 129, 131, 153, 182] 移动距离： [3, 16, 36, 83, 12, 23, 2, 22, 29] 移动总数： 226 平均寻道： 25.11
====================================================== SCAN算法 初始位置： 28
初始移动方向：由里向外
访问顺序： [31, 47, 94, 106, 129, 131, 153, 182, 11] 移动总数： 325 平均寻道： 36.11
====================================================== CSCAN算法 初始位置： 28
移动方向：由里向外
访问顺序： [31, 47, 94, 106, 129, 131, 153, 182, 11] 移动总数： 164 平均寻道： 18.22
程序源代码：
# coding=utf-8 import random
class HEAD: """
magnetic head """
__location = -1 __next = -1 __request = []
# 大于0为由里向外，小于0 为由外向里 __direction = 0
# SCAN算法的磁道访问顺序 __scan_trace = []
# SSTF算法的磁道访问顺序 __sstf_trace = []
# FCFS算法的磁道访问顺序 __fcfs_trace = []
# 每次寻道的移动距离 __move_length = [] # 寻道的移动总距离 __sum_length = 0
def __init__(self):
self.__location = 1 self.__direction = 1
def __init__(self, location): self.__location = location if location > 100:
self.__direction = -1 elif location
self.__direction = 1
def __clear(self):
self.__sum_length = 0
self.__move_length.clear()
self.__sstf_trace.clear() self.__fcfs_trace.clear() self.__scan_trace.clear()
def get_location(self): return self.__location
def reverse(self):
if self.__direction == 1: self.__direction = -1 elif self.__direction == -1: self.__direction = 1
def request(self, rec):
self.__request.append(rec)
def show_request_list(self): print(self.__request)
def get_sstf_trace(self): return self.__sstf_trace
def get_fcfs_trace(self): return self.__fcfs_trace
def get_scan_trace(self): return self.__scan_trace
def get_move_length(self): return self.__move_length
def get_sum_length(self): return self.__sum_length
def get_direction(self): return self.__direction
def fcfs(self): self.__clear()
temp = self.__location
for rec in self.__request:
self.__move_length.append(abs(self.__location-rec)) self.__sum_length += abs(self.__location-rec) self.__location = rec
self.__fcfs_trace.append(self.__location) # 为了方便与其他算法做对比，将磁头复位 self.__location = temp
def sstf(self): self.__clear()
temp_loc = self.__location temp = self.__request.copy() while len(self.__request) != 0: min_length = 200 min_no = 0
for i in range(0, len(self.__request)): req = self.__request[i]
if abs(req - self.__location)
self.__location = self.__request[min_no] self.__sstf_trace.append(self.__location) del self.__request[min_no] self.__request = temp
# 为了方便与其他算法做对比，将磁头复位 self.__location = temp_loc
def cscan(self): self.__clear()
temp_request = self.__request.copy() temp_loc = self.__location
temp_direction = self.__direction while len(self.__request) != 0: min_length = 200 min_no = -1
if self.__direction == 1:
for i in range(0, len(self.__request)): req = self.__request[i]
if abs(req - self.__location) self.__location:
min_length = abs(req - self.__location) min_no = i if min_no == -1:
self.__location = 1 continue
elif self.__direction == -1:
for i in range(0, len(self.__request)): req = self.__request[i]
if abs(req - self.__location)
min_length = abs(req - self.__location) min_no = i if min_no == -1:
self.__location = 200 continue self.__move_length.append(abs(self.__location - self.__request[min_no])) self.__sum_length += abs(self.__location - self.__request[min_no])
self.__location = self.__request[min_no] self.__scan_trace.append(self.__location) del self.__request[min_no]
self.__request = temp_request self.__location = temp_loc
self.__direction = temp_direction
def scan(self): self.__clear()
temp_direction = self.__direction temp_request = self.__request.copy() temp_loc = self.__location
while len(self.__request) != 0: min_length = 200 min_no = -1
if self.__direction == 1:
for i in range(0, len(self.__request)): req = self.__request[i]
if req - self.__location self.__location:
min_length = abs(req - self.__location) min_no = i if min_no == -1: self.reverse() continue
elif self.__direction == -1:
for i in range(0, len(self.__request)): req = self.__request[i]
if self.__location - req
min_length = abs(req - self.__location) min_no = i if min_no == -1: self.reverse() continue self.__move_length.append(abs(self.__location self.__request[min_no])) self.__sum_length += abs(self.__location self.__request[min_no])
self.__location = self.__request[min_no] self.__scan_trace.append(self.__location) del self.__request[min_no]
self.__request = temp_request self.__location = temp_loc
self.__direction = temp_direction
def run_fcfs(head):
print("======================================================") print("FCFS算法")
print("初始位置： " + str(head.get_location())) head.fcfs()
print("访问顺序：", head.get_fcfs_trace()) print("移动距离：", head.get_move_length()) print("移动总数：", head.get_sum_length()) print("平均寻道：", round(head.get_sum_length() len(head.get_move_length()), 2))
def run_sstf(head):
print("======================================================") print("SSTF算法")
print("初始位置： " + str(head.get_location())) head.sstf()
print("访问顺序：", head.get_sstf_trace()) print("移动距离：", head.get_move_length()) print("移动总数：", head.get_sum_length()) print("平均寻道：", round(head.get_sum_length() len(head.get_move_length()), 2))
def run_cscan(head):
print("======================================================")
- -
/
/
print("CSCAN算法")
print("初始位置： " + str(head.get_location())) if head.get_direction() == 1: print("移动方向：由里向外")
elif head.get_direction() == -1: print("移动方向：由外向里") head.cscan()
print("访问顺序：", head.get_scan_trace()) # print("移动距离：", head.get_move_length()) print("移动总数：", head.get_sum_length()) print("平均寻道：", round(head.get_sum_length() len(head.get_move_length()), 2))
def run_scan(head):
print("======================================================") print("SCAN算法")
print("初始位置： " + str(head.get_location())) if head.get_direction() == 1: print("初始移动方向：由里向外") elif head.get_direction() == -1: print("初始移动方向：由外向里") head.scan()
print("访问顺序：", head.get_scan_trace()) # print("移动距离：", head.get_move_length()) print("移动总数：", head.get_sum_length()) print("平均寻道：", round(head.get_sum_length() len(head.get_move_length()), 2))
if __name__ == "__main__":
head = HEAD(random.randint(1, 200)) for i in range(0, 9):
head.request(random.randint(1, 200)) print("进程的读磁盘请求：", end=" ") head.show_request_list() run_fcfs(head) run_sstf(head) run_scan(head) run_cscan(head)
/
/
心得体会：
1.Python是一种动态语言，对数据类型不严格，使用时必需注意数据类型的控制。
2.这个实验中不同的算法可以实现互相调用以提高代码的重用率，比如NStepSCAN可以调用SCAN
算法进行小队列的处理。前提是算法和数据的设计足够清晰，容易分离。如上面我自己写的例子中，因为写前面的算法时没有考虑后续的可能要求，导致代码重用率很低，已经不方便对前几个算法进行修改。
【实验过程记录（源程序、测试用例、测试结果及心得体会等）】