操作系统实验一：处理器调度算法的实现

操作系统实验一：处理器管理

实验报告

一、实验目的

（1）加深对处理机调度的作用和工作原理的理解。

（2）进一步认识并发执行的实质。

 

二、实验要求：

本实验要求用高级语言，模拟在单处理器情况下，采用多个调度算法，对N个进程进行进程调度。语言自选。

并完成实验报告。

  

三、实验内容：

在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。

当就绪状态进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占用处理器。

1. 进程及进程队列的表示。
2. 处理器调度算法：FCFS，SJF，RR
3. 跟踪进程状态的转化
4. 输出：系统中进程的调度次序，计算CPU利用率，平均周转时间和平均带权周转时间

四、实验过程与结果

1. 算法思想与设计
2. 算法实现代码
3. 运行结果

 

1. FCFS：

1.1算法思想:先到达系统的作业拥有优先执行的权利，无论此作业的执行时间长短，执行完成后输出它的相关信息。

1.2算法设计：

 

2.算法实现代码

import psutil
import os
#先来先服务
 
class  Process:
    def __init__(self,name,arrive_time,serve_time):
        self.name=name
        self.arrive_time=arrive_time
        self.serve_time=serve_time
        self.left_serve_time=serve_time
        self.finish_time=0
        self.cycling_time=0
        self.w_cycling_time=0
        
process_list=[]
processA=Process('A',0,4)
processB=Process('B',2,4)
processC=Process('C',5,4)
processD=Process('D',9,4)
process_list.append(processA)
process_list.append(processB)
process_list.append(processC)
process_list.append(processD)
for p in process_list:
    print(p.name,p.arrive_time,p.serve_time)
    
process_list.sort(key=lambda x:x.arrive_time)
for p in process_list:
    print(p.name,p.arrive_time,p.serve_time,p.left_serve_time,\
         p.finish_time,p.cycling_time,p.w_cycling_time)
 
index = int(0)
running_time=int(0)
pf =[]
while len(process_list)>0:
    p = process_list[index]
    if p.arrive_time>running_time:
        running_time=p.arrive_time
        running_time +=p.serve_time
        
    else:
        print(p.name,p.left_serve_time)
        running_time +=p.left_serve_time
        p.left_serve_time=0
        p.finish_time=running_time
        p.cycling_time=p.finish_time-p.arrive_time
        p.w_cycling_time=p.cycling_time/p.serve_time
        print('--',p.name,p.arrive_time,p.serve_time,p.left_serve_time,\
             p.finish_time,p.cycling_time,p.w_cycling_time)
        pf.append(p)
        process_list.remove(p)
        index-=1
    index+=1
    if index>=len(process_list):
        index=0

3.运行结果

 

2.JSF:

1. 算法思想与设计 1.1算法思想：当作业的到达时间大于或者等于系统的运行时间时，比较出所需执行时间最短的作业，优先执行它；当只有一个作业到达系统时，其他作业还未来到，则不管此作业的长短都先执行它。

1. 1.2算法设计：

2.算法实现代码

 

3.运行结果

 

3.RR：

1.算法思想及设计：

    1.1算法思想：

• CPU时间划分为时间片，例如100ms
• 时间片调度：调度程序每次把CPU分配给就绪队列首进程使用一个时间片，就绪队列中的每个进程轮流地运行一个时间片。当这个时间片结束时，强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度

     1.2算法设计：

Ø进程排序

Ø队列不为空时循环：

Ø到达？

Ø剩余服务时间>时间片

Ø运行时间

Ø剩余服务时间

Ø剩余服务时间<=时间片

Ø运行时间

Ø剩余服务时间、完成时间、周转时间、加权周转时间

Ø保存

Ø从队列删除进程

 

2.算法实现代码：

import psutil
import os
#RR
class  Process:
    def __init__(self,name,arrive_time,serve_time):
        self.name=name
        self.arrive_time=arrive_time
        self.serve_time=serve_time
        self.left_serve_time=serve_time
        self.finish_time=0
        self.cycling_time=0
        self.w_cycling_time=0
        
process_list=[]
processA=Process('A',0,4)
processB=Process('B',2,4)
processC=Process('C',5,4)
processD=Process('D',9,4)
process_list.append(processA)
process_list.append(processB)
process_list.append(processC)
process_list.append(processD)
for p in process_list:
    print(p.name,p.arrive_time,p.serve_time)
    
process_list.sort(key=lambda x:x.arrive_time)
for p in process_list:
    print(p.name,p.arrive_time,p.serve_time,p.left_serve_time,\
         p.finish_time,p.cycling_time,p.w_cycling_time)
 
index = int(0)
running_time=int(0)
q =2
pf =[]
while len(process_list)>0:
    p = process_list[index]
    if p.arrive_time>running_time:
        running_time=p.arrive_time
    if p.left_serve_time>q:
        print(p.name,q)
        running_time +=q
        p.left_serve_time-=q
    else:
        print(p.name,p.left_serve_time)
        running_time +=p.left_serve_time
        p.left_serve_time=0
        p.finish_time=running_time
        p.cycling_time=p.finish_time-p.arrive_time
        p.w_cycling_time=p.cycling_time/p.serve_time
        print('--',p.name,p.arrive_time,p.serve_time,p.left_serve_time,\
             p.finish_time,p.cycling_time,p.w_cycling_time)
        pf.append(p)
        process_list.remove(p)
        index-=1
    index+=1
    if index>=len(process_list):
        index=0

　　3.运行结果：

 

4.MLFQ

 class Process:
    def __init__(self, name, arrive_time, serve_time):
        self.name = name  # 进程名
        self.arrive_time = arrive_time  # 到达时间
        self.serve_time = serve_time  # 需要服务时间
        self.left_serve_time = serve_time  # 剩余需要服务时间
        self.finish_time = 0  # 完成时间
        self.cycling_time = 0  # 周转时间
        self.w_cycling_time = 0  # 带权周转时间
 
 
class RR:
    def __init__(self, process_list, q):
        self.process_list = process_list
        self.q = q
 
    def scheduling(self):
        process_list = self.process_list
        process_list.sort(key=lambda x: x.arrive_time)
 
        pf = []
        q = self.q
        index = int(0)
        running_time = int(0)
 
        while len(process_list) > 0:
            p = process_list[index]
            if p.arrive_time > running_time:
                running_time = p.arrive_time
            if p.left_serve_time > q:
                print(p.name, q)
                running_time += q
                p.left_serve_time -= q
            else:
                print(p.name, p.left_serve_time)
                running_time += p.left_serve_time
                p.left_serve_time = 0
                p.finish_time = running_time
                p.cycling_time = p.finish_time - p.arrive_time
                p.w_cycling_time = p.cycling_time / p.serve_time
                print('--', p.name, p.arrive_time, p.serve_time, p.left_serve_time, p.finish_time, p.cycling_time,
                      p.w_cycling_time)
                pf.append(p)
                process_list.remove(p)
                index -= 1
            index += 1
            if index >= len(process_list):
                index = 0
        return pf
 
 
# 定义队列类
class Queue:
    def __init__(self, level, process_list, q):
        self.level = level
        self.process_list = process_list
        self.q = q
 
    def size(self):
        return len(self.process_list)
 
    def get(self, index):
        return self.process_list[index]
 
    def add(self, process):
        self.process_list.append(process)
 
    def delete(self, index):
        self.process_list.remove(self.process_list[index])
 
 
class MulitlevedFeesbackQueue():
    def __init__(self, queue_list):
        self.queue_list=queue_list
 
    def scheduling(self):
        q_list = self.queue_list
 
        for i in range(len(q_list)):
            if i==len(q_list)-1:
                print("=======对最后一个队列执行RR算法=====")
            #最后一个队列重新设置到达时间
                for t in range(len(q_list[i].process_list)):
                    q_list[i].process_list[t].arrive_time = t
                rr_last_queue = RR(q_list[i].process_list, q_list[i].q)
                rr_last_queue.scheduling()
            else:
                currentQueue = q_list[i]
 
                index=int(0)
                while(True):
                    if currentQueue.get(index).left_serve_time>q_list[i].q:
                        currentQueue.get(index).left_serve_time-=q_list[i].q
                        print("第%d队列时间片：%d"%(i,q_list[i].q))
                        print("进程没有执行完毕，需要添加至下一队列末尾：进程名称：%s" % (currentQueue.get(index).name))
 
                        q_list[i+1].add(currentQueue.get(index))
                        index+=1
                    else:
                        print('服务时间并弹出：',currentQueue.get(index).name)
                        currentQueue.get(index).left_serve_time=0
                        currentQueue.delete(index)
 
                    if index==currentQueue.size():
                        break
 
processA=Process('A',0,16)
processB=Process('B',1,3)
processC=Process('C',2,4)
processD=Process('D',3,2)
processE=Process('E',4,4)
process_list0,process_list1,process_list2=[],[],[]
process_list0.append(processA)
process_list0.append(processB)
process_list1.append(processC)
process_list1.append(processD)
process_list2.append(processE)
 
queue0=Queue(0,process_list0,2)
queue1=Queue(1,process_list1,4)
queue2=Queue(2,process_list2,8)
 
queue_list=[]
queue_list.append(queue0)
queue_list.append(queue1)
queue_list.append(queue2)
 
for i in range(3):
    print(queue_list[i].level,queue_list[i].process_list,queue_list[i].q)
 
mlfq=MulitlevedFeesbackQueue(queue_list)
mlfq.scheduling()