《操作系统》实验教学指导书..docx

《操作系统》实验教学指导书.

———————————————————————————————— 作者：
———————————————————————————————— 日期：

20

天津理工大学华信软件学院
《操作系统》实验教学指导书2.2
课程代码： 1460350
课程名称： 操作系统 / Operating System
开课院（系）、实验室：华信软件学院C408机房
适用专业： 软件工程专业
实验指导书名称： 《操作系统实验教程（Linux版）》第八章
指导教师： 张一鸣

实验二 进程的建立与调度（2.2 进程的调度）
1. 实验目的
(1) 理解并比较处理机调度的常用策略。
(2) 重点掌握优先权调度和时间片轮转两种调度算法的设计与实现。
(3) 按优先权调度算法设计并实现一个处理机调度的程序。
2. 实验内容
本实验中，根据进程状态的转换图模拟多个进程在一个处理机上进行调度。本实验有两个题目，可任选其一。
(1) 设计一个按动态优先权调度算法实现处理机调度的程序。
(2) 设计一个按时间片轮转调度算法实现处理机调度的程序。
3. 准备知识
(1) 理解操作系统中处理机调度的概念和调度算法。
(2) 学习Linux下进程控制以及进程间通信的知识。
4. 实验原理
时间片轮转调度算法和优先权调度算法本质上是一直的，只是在调度时选择的策略不一样而已，故程序流程图是一致的，所以在本教程中仅给出一个流程图即可。具体算法流程图如1所示。

4.1. 时间片轮转调度算法
当系统按时间片轮转算法调度进程时，将所有的就绪进程按照一定的原则（如先来先服务原则）排列，形成一个就绪队列。每次调度为队首进程分配CPU资源，令其执行一个时间片，该时间片的大小从几ms到几百ms。当时间片用完时，由计时器发出中断信号，通知系统剥夺当前运行进程的CPU使用权，并将此进程送入就绪队列的末尾，等待下一次执行；然后，把处理机分配给就绪队列中新的队首进程，执行重复操作。在进程运行过程中，如果时间片未用完而等待时间发生，则该进程进入等待队列，系统将CPU重新分配给就绪队列的队首进程，一旦时间发生后，等待队列的队首进程进入就绪队列末尾。这样就可以保证就绪队列中的所有进程，在可接受的等待时间内，均能获得处理机并调度执行。
时间片轮转调度算法的进程状态转换图，如图2所示。

4.2. 优先权调度算法
优先权调度算法的进程状态转换图，如图3所示。
1）优先权调度算法的类型
（1）非抢占式优先权调度算法。在非抢占式优先权算法中，处理机一旦被分配给就绪队列中优先权最高的进程，则该进程会一直执行到完成，不会被抢占；只有当发生某一事件使该进程放弃处理机时，处理机才会被分配给就绪队列中优先权最高的另一进城。一般在批处理系统中会使用该调度算法，某些对实时性要求不严的实时系统也可以使用该调度算法。
（2）抢占式优先权调度算法。在抢占式调度算法中，处理机一开始也会被分配给就绪队列中优先权最高的进程，使之执行。但如果出现了一个优先权更高的进程时，进程调度程序就会剥夺原最高优先权进程的处理机使用权，而分配给新出的优先权更高的进程。
2）优先权的类型
对于优先权调度算法，其关键是看采用的是静态优先权，还是动态优先权。
（1）静态优先权时在进程创建的时候确定的，而且优先权在进程的运行期间保持不变。一般是用某一范围内的一个整数来表示优先权大小。确定进程优先权的依据是：
①进程类型；
②进程对资源的需求；
③进程的估计执行时间及内存占用量；
④用户的需求
（2）动态优先权是指在创建进程时会被赋予一个优先权，但该优先权可以在进程的等待过程中，随某些条件的变化而改变，以便获得更好的调度性能。
例如，在就绪队列中的进程，随着其等待时间的增长，优先权可以以某一速率提高。假设所有的进程在一开始都具有相同的优先权，则应将最先进入就绪队列的进程（其等待时间最长）赋予最高优先权，从而优先获得处理机，这就是FCFS算法。
优先权的变化规律可描述为：
优先权=（等待时间+要求服务时间）/要求服务时间
而等待时间与要求服务时间之和就是系统对该作业的响应时间，故该优先权又相当于响应比。
5. 实验步骤
1.设计一个按动态优先权调度算法实现处理机调度的程序
（1）假定系统有4个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的结构如表8-1所示。

其中：
进程id：进程的标识。
进程名称：假设若干个进程的进程名称分别为P1,P2,P3,P4…。
进程状态：进程状态转换的标识（1-运行态、2-就绪态、3-等待态、0-完成态）。
进程类型：进程是系统进程还是用户进程（0-系统进程，1-用户进程）。
请求资源的时刻：请求资源的时刻。
总共需要CPU的时间：假设进程需要运行的时间数。
运行时间：当前进程已运行时间。
优先数：赋予进程的优先数，调度时总是选取优先数小（既优先级高的）的进程先执行。
指向下一个进程的指针：用指针指出下一个进程的进程控制块的首地址，最后一个进程中的指针为NULL。
（2）在每次运行所涉及的处理器调度程序之前，为每个进程确定“进程名称”和“总共需要CPU的时间”。
（3）在调度过程中，设计4个队列：完成态队列，运行态队列，就绪态队列，等待态队列。
（4）根据“总共需要CPU的时间”确定请求资源的时刻，资源的数据结构可以如表8-2所示。

（5）处理器调度总是选就绪队列的首进程运行。采用动态改变优先数的方法，进程每运行一次优先数就减“1”，就绪队列中的进程加“2”。在运行过程中，改变进程的优先级，要求运行时间减“1”来模拟进程的一次运行。
（6）当运行进程的运行时间到达请求资源的时刻时，去占用资源，若资源现处于被占用状态就进入等待状态，若资源空闲，进入就绪状态。
2.设计一个按时间片轮转调度算法实现处理机调度的程序
（1）假定系统中有4个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的元素如表8-3所示。

其中：
进程id：进程的标识
进程名称：假设若干个进程的进程名称分别为P1,P2,P3,P4…。
进程状态：进程状态转换的标识（1-运行态、2-就绪态、3-等待态、0-完成态）。
进程类型：进程是系统进程还是用户进程（0-系统进程，1-用户进程）。
请求资源的时刻：请求资源的时刻。
总共需要CPU的时间：假设进程需要运行的时间数。
运行时间：当前进程已运行时间。
优先数：赋予进程的优先数，调度时总是选取优先数小（既优先级高的）的进程先执行。
指向下一个进程的指针：用指针指出下一个进程的进程控制块的首地址，最后一个进程中的指针为NULL。
（2）在每次运行所涉及的处理器调度程序之前，为每个进程确定“进程名称”和“总共需要CPU的时间”。
（3）在调度过程中，设计4个队列：完成态队列，运行态队列，就绪态队列，等待态队列。
（4）根据“总共需要CPU的时间”确定请求资源的时刻，资源的数据结构可以如表8-2所示。
（5）处理器调度总是选就绪队列的首进程运行。采用时间片轮转的办法，进程没运行一个时间片当前运行进程进入就绪态，就绪队列中的首个进程进入运行态来模拟进程的一次运行。
（6）当运行进程的运行时间到达请求资源的时刻时，去占用资源，若资源现处于被占用状态就进入等待状态，若资源空闲，进入就绪状态。
6. 参考代码
1.按动态优先权调度算法实现处理器调度的程序
[源程序]
#include<stdip.h>
#include<stdlib.h>
#include<string.h>
#include<unistd.h>
#include<signal.h>
#include<time.h>
#include<sys/time.h>
typedef struct pcbStruct
{
int pid;
char name[10];
int status;
int type;
int res;
int totalTime;
int runTime;
int count;
int prio;
struct pcbStruct *next;
}PCB;
typedef struct resStruct
{
int pid;
int free;
}Resource;
Resource resource;
PCB *finish,*ready,*tail,*run,*wait,*head;
int N;
int timeSlice=2;
int hodeUpTime=5;
int changePrio=0;
void sort();
void changeRunPrio();
void changeReadyPrio();
int randomPrio(double from ,double to)
{
return 1+(int)((to)*rand()/(RAND_MAX+from));
}
runIn()
{
run=ready;
run->status=1;
} ready=ready->next;
readyIn()
{
wait->status=2;
tail->next=wait;
wait=wait->next;
}
void print1()
{
printf("-------------------------------------------\n");
printf("pid name status type prio res tatalTime count runTime\n");
}
void printf2(PCB *q)
{
printf("%d|%-4s|%-4d|%-6d|%-4d|%-4d|%-8d|%-5d|%-d\n",q->pid,q->name,q->status,q->type,q->prio,q->res,q->totalTime,q->count,q->runTime);
}
void print()
{
PCB *p;
if(ready!=NULL)
sort();
if(run!=NULL)
{
printf("Running..........\n");
print2(run);
}
p=ready;
if(p!=NULL)
printf("Ready..........\n");
while(p!=NULL)
{
print2(p);
p=p->next;
}
p=wait;
if(p!NULL)
printf("Waiting..........\n");
while(p!=NULL)
{
print2(p);
p=p->next;
}
p=finish;
if(p!=NULL)
printf("Finished..........\n");
while(p!=NULL)
{
print2(p);
p=p->next;
}
print1();
}
insertReady(PCB *p2)
{
tail->next=p2;
tail=p2;
p2->next=NULL;
}
insertWait(PCB *p2)
{
head->next=p2;
head=p2;
p2->next=NULL;
}
void creat()
{
PCB *p;
int i,time;
char na[10];
ready=NULL;
finish=NULL;
run=NULL;
wait=NULL;
printf("Enter name and run time of each process:(eg.pid1[press ENTER]100)\n");
for(i=1;i<=N;i++)
{
p=malloc(sizeof(PCB));
p->pid=1000+i;
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->status=2;
if(i%2==0)
{
p->type=0;
p->prio=randomPrio(1.0,9.0);
}
else
{
p->type=1;
p->prio=randomPrio(11.0,19.0);
}
p->res=time/2;
p->totalTime=time;
p->count=0;
p->runTime=0;
if(ready!=NULL)
insertReady(p);
else
{
p->next=ready;
ready=p;
tail=p;
}
}
printf("**********调度开始**********");
print1();
print();
run=ready;
ready=ready->next;
run->status=1;
}
prioChangerun()
{
while(run!=NULL)
{
if(run->res==run->runTime)
{
if(resource.free==1)
{
resource.pid=run->pid;
resource.free=0;
}
else
{
run->count=0;
run->status=3;
PCB *p=run;
if(wait!=NULL)
insertWait(p);
else
{
p->next=wait;
wait=p;
head=p;
}
runIn();
}
}
run->runTime=run->funTime+1;
run->count=run->count+1;
sleep(1);
changePrio++;
if(changePrio%2==0)
{
changeRunPrio();
changeReadyPrio();
}
if((run->runTime-run->res)>=hodeUpTime)
resource.free=1;
if(run->runTime>=run->totalTime)
{
if(run->pid==resource.pid)
resource.free=1;
run->next=finish;
finish=run;
run->status=0;
run=NULL;
if(ready!=NULL)
runIn();
}
else if(run->count==timeSlice)
{
run->count=0;
if(ready!=NULL)
{
run->status=2;
insertReady(run);
runIn();
}
}
if(ready!=NULL)
{
if(run->prio>ready->prio)
{
run->count=0;
if(ready!=NULL)
{
run->status=2;
insertReady(run);
runIn();
}
}
}
if(resource.free==1)
{
if(wait!=NULL)
{
wait->status=2;
insertReady(wait);
wait=wait->next;
}
}
print();
}
}
void changeRunPrio()
{
if(run->prio<20)
run->prio+=1;
}
void changeReadyPrio()
{
PCB *p;
p=ready;
if(p!=NULL)
{
do
{
if(p->type==0)
{
if(p->prio>-20)
p->prio-=2;
}
else
{
if(p->prio>0)
p->prio-=2;
}
}while(p!=NULL);
}
}
void sort()
{
PCB *p,*min;
min=ready;
p=ready;
while(p->next!=NULL)
{
if(min->prio>p->next->prio)
{
min=p->next;
p->next=p->next->next;
min->next=ready;
ready=min;
}
else
{
if(p->next!=NULL)
p=p->next;
}
}
p=ready;
while(p->next!=NULL)
{
p=p->next;
}
tail=p;
}
int main()
{
}
2.时间片轮转调度算法实现处理器调度的程序
[源程序]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<unistd.h>
#include<signal.h>
#include<time.h>
#include<sys/time.h>

typedef struct pcbStruct
{
int pid;
char name[10];
int status;
int type;
int res;
int totalTime;
int runTime;
int count;
int prio;
struct pcbStruct *next;
}PCB;

typedef struct resStruct
{
int pid;
int free;
}Resource;

Resource resource;
PCB *finish,*ready,*tail,*run,*wait,*head;

int N;
int timeSlice=2;
int hodeUpTime=3;
int randomPrio(double from,double to)
{
return 1+(int)((to)*rand()/(RAND_MAX+from));
}

runIn()
{
run=ready;
run->status=1;
ready=ready->next;
}

void print1()
{
printf("---------------------\n");
printf("pid name status type prio res totalTime count runTime\n");
}

void print2(PCB *q)
{
printf("%d|&-4s|%-4d|%-6d|%-4d|%-4d|%-8d|%-5d|%-d\n",q->pid,q->name,q->status,q->type,q->prio,q->res,q->totalTime,q->count,q->runTime);
}

void print()
{
PCB *p;
if(run!=NULL)
{
printf("Running...............\n");
print2(run);
}
p=ready;
if(p!=NULL)printf("Ready............\n");
while(p!=NULL)
{
print2(p);
p=p->next;
}
p=wait;
if(p!=NULL)printf("Waiting.........................\n");
while(p!=NULL)
{
print2(p);
p=p->next;
}
p=finish;
if(p!=NULL)printf("Finished.............\n");
while(p!=NULL)
{
print2(p);
p=p->next;
}
print1();
}

insertReady(PCB *p2)
{
tail->next=p2;
tail=p2;
p2->next=NULL;
}

insertWait(PCB *p2)
{
head->next=p2;
head=p2;
p2->next=NULL;
}

void creat()
{
PCB *p;
int i,time;
char na[10];
ready=NULL;
finish=NULL;
run=NULL;
wait=NULL;
printf("enter name and run time of each process:(eg.pidl[press enter]100):\n");
for(i=1;i<N;i++)
{
p=malloc(sizeof(PCB));
p->pid=1000+i;
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->status=2;
if(i%2==0)
{
p->type=0;
p->prio=randomPrio(1.0,9.0);
}
else
{
p->type=1;
p->prio=randomPrio(11.0,19.0);
}
p->res=time/2;
p->totalTime=time;
p->count=0;
p->runTime=0;
if(ready!=NULL)
insertReady(p);
else
{
p->next=ready;
ready=p;
tail=p;
}
}
printf("*******调度开始*********\n");
print1();
print();
run=ready;
ready=ready->next;
run->status=1;
}

timeRoundRun()
{
while(run!=NULL)
{
if(run->res==run->runTime)
{
if(resource.free==1)
{
resource.pid=run->pid;
resource.free=0;
}
else
{
run->count=0;
run->status=3;
PCB *p=run;
if(wait!=NULL)
insertWait(p);
else
{
p->next=wait;
wait=p;
head=p;
}
runIn();
}
}
run->runTime=run->runTime+1;
run->count=run->count+1;
sleep(1);
if((run->runTime-run->res)>=hodeUpTime)
{
resource.free=1;
if(wait!=NULL)
{
PCB *p=wait;
wait=wait->next;
p->status=2;
insertReady(p);
}
}
if(run->runTime>=run->totalTime)
{
if(run->pid==resource.pid)
{
resource.free=1;
if(wait!=NULL)
{
PCB *p=wait;
wait=wait->next;
p->status=2;
insertReady(p);
}
}
run->next=finish;
finish=run;
run->status=0;
run=NULL;
if(ready!=NULL)
runIn();
}
else if(run->count==timeSlice)
{
run->count=0;
if(resource.free==1)
{
if(wait!=NULL)
{
PCB *p=wait;
wait=wait->next;
p->status=2;
insertReady(p);
}
}
if(ready!=NULL)
{
run->status=2;
insertReady(run);
runIn();
}
}
print();
}
}

int main()