进程调度算法操作系统课程设计.doc

操作系统课程设计

计算机科学与应用系

操作系统原理

课程设计报告

题目： 进程调度算法
班级： 0510074
姓名： lee hye
专业： 计算机科学与技术
指导老师： hhh

进程调度算法

一、实验目的
通过优先权法与轮转调度算法的模拟加深对进程概念和进程调度过程的理解，掌握进程状态之间的切换，同时掌握进程调度算法的实现方法和技巧。
二、实验内容
1、用C语言或C++语言来实现对N个进程采用优先算法以及轮转算法的进程调度。
2、每个用来标示进程的进程控制块PCB用结果来描述，包括以下字段
（1）进程标识ID，其中0为闲逛进程，用户进程的标识数为1、2、3、、、、、、、。
（2）进程优先级Priority，闲逛进程（idle）的优先级为0，用户有进程的优先级大于0，且随机产生，标识数越大，优先级越高。
（3）进程占用的CPU时间CPUtime，进程每运一次，累积等于4.
（4）进程总共需要运行时间Alltime，利用随机函数产生。
（5）进程状态，0—就绪态，1—运行态，2—阻塞态。
（6）队列指针next，用来将多个进程控制块PCB链接为队列。
3、优先数改变的原则
（1）进程在就绪队列中每呆一个时间片，优先数增加1.
（2）进程每运行一个时间片，优先数增加1.
4、在调度前，系统中拥有的进程数PCB_number有键盘输入，进初始化后，所有的进程控制块PCB连接成就绪队列。
5、为了清楚的观察诸进程的调度过程，程序应将每个时间片内的进程的情况显示出来。
三、实验步骤
1、进程管理程序调式好后，运行进程管理程序

输入开始进程数n

创建n个PCB并加入ready－queue中

ready-queue是否为空

Y

N
Running<=id
Running<＝逐个将redy_pc中的PCB

阻塞Running
N

Y
Running=idle
Y

N
将Running从ready_queue中删除，再将running加入block_queueb

更新新进程就绪队列进程优先数，优先数加1

是否创建新PCB
N

Y
创建新进程并加入到ready_queue中

随机 对block_queue中的进程PCB询问是否要唤醒？

处理完了吗
Y

N
是否要唤醒
N

Y
将其从blick_queuek队列是中删除，再将其加入ready_queuek

2、优先权调度
（1）输入1选择优先权调度算法模拟。
（2）输入开始进程个数n，创建n个PCB并加入就绪队列ready_queue中。
（3）就绪队列ready_queue不为空，调度就绪队列中第一个进程运行，否则，从闲逛队列idleprocess中调度闲逛进程运行。
（4）在运行过程中，当遇到阻塞，则该进程插入到阻塞队列block_queue中，且将该进程从ready_queue中删除。
（5）如果运行时间CPUtime大于等于Alltime，该进程运行完毕，释放该进程；否则插入到就绪队列中。
（6）更新就绪队列中的优先级数。
（7）随机对阻塞队列block_queue中的进程PCB询问是否要唤醒，唤醒，即从唤醒队列中选择第一个进程，且插入就绪队列中；阻塞队列中没有阻塞进程返回。
（8）重复上述步骤，直到本次调度结束。

3、轮转调度
（1）输入2选择优先权调度算法模拟。
（2）输入开始进程个数n，创建n个PCB并加入就绪队列ready_queue中。
（3）就绪队列ready_queue不为空，调度就绪队列中第一个进程运行，否则，从闲逛队列idleprocess中调度闲逛进程运行。
（4）在运行过程中，当遇到阻塞，则该进程插入到阻塞队列block_queue中，且将该进程从ready_queue中删除。
（5）如果运行时间CPUtime大于等于Alltime，该进程运行完毕，释放该进程；否则插入到就绪队列中。
（6）随机对阻塞队列block_queue中的进程PCB询问是否要唤醒，唤醒，即从唤醒队列中选择第一个进程，且插入就绪队列中；阻塞队列中没有阻塞进程返回。
（7）如果时间到，本次调度结束，否则重复上述步骤，直到本次调度结束。

输入开始进程数n

创建n个PCB并加入ready－queue中

ready-queue是否为空

Y

N
Running<=id
Running<＝逐个将redy_pc中的PCB

阻塞Running
N

Y
Running=idle
Y

N
将Running从ready_queue中删除，再将running加入block_queueb

是否创建新PCB
N

Y
创建新进程并加入到ready_queue中

随机 对block_queue中的进程PCB询问是否要唤醒 ？

处理完了吗
Y

N
是否要唤醒
N

Y
将其从blick_queuek队列是中删除，再将其加入ready_queuek

Y

四、实验过程中遇到的问题及解决方案
1、请仔细阅读动态优先权的进程调度算法的模拟实现代码,说明该算法与教材中介绍的算法做了哪些简单化处理.
优先权模拟时优先权是随机产生，在实际的系统中，系统进程的优先权高于一般用户进程的优先权。
2、为什么对进程的优先数可按上述原则进行修改?
最高优先权调度算法仅照顾了优先权高的进程，当不断有优先权高的进程需调度时，而优先权低的进程将很难得到处理机的调度，所以进程在就绪队列中每呆一个时间片，优先数增加1，使优先权低的进程不总是忙等。
3、请给出设计实现的轮转发进程调度算法的设计思想.
时间轮转调度算法：系统将所有的就像进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给首进程，并令其执行一个时间片。当执行的时间片用完时，发出中断请求，调度程序便据此信号来停止该进程的执行，并将其送到就绪队列的末尾，如此反复，就可以保证就绪队列中的所有进程在一个给定的时间内，均能获得一时间片处理机执行时间。
4、在实际的进程调度中，除了按调度算法选择下一个执行的进程外,还应处理哪些工作?
最高优先权调度算法，常用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可以用于实时系统中：时间轮转调度算法，一般用于分时系统中。
五、课程设计总结
1、当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业，装入内存，当用于进程调度算法时，该算法是把处理及分配给就绪队列中优先权最高的进程。
2、当系统空闲（就绪队列为空）时，系统运行闲逛进程，否则运行其他进程，发生变迁（就绪à运行）
3、在运行进程（包括闲逛进程）的过程中，可能发生变迁2(运行à阻塞)，即将运行进程插入到阻塞队列（闲逛进程不能不被阻塞），可能有其他的进程创建PCB，还可能唤醒阻塞队列中的某些进程PCB，发生变迁3（阻塞à就绪），即从阻塞队列中插入就绪队列中。
4、时间片运行结束后，若进程累积占用CPU时间大于等于进程需要运行时间，则进程执行结束，释放其PCB。若进程累积占用CPU时间小于进程需要运行时间，发生变迁4（运行à就绪），即将当前运行的进程插入就绪队列中。

附：进程调度算法代码
// process.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "iostream.h"
#define NULL 0
#define false 0
#define true 1

bool _state=0;
struct PCB
{
int ID;
int priority;
int CPUtime;
int ALLtime;
int State;
PCB* next;
};

void init();/*产生idle进程，输入用户进程数目，调用insert()*/
void print(PCB *pcb);/*输出进程属性信息*/
void print_init(PCB *pcb);/*输出所有PCB的初始值*/
void insert();/*生成进程属性信息，插入进程就绪队列*/
void Run_priority(PCB *pcb);/*运行进程，随机阻塞进程、产生新进程，插入就绪队列，唤醒阻塞进程*/
void block(PCB *pcb);/*调用destroy()将进程插入阻塞队列*/
void wakeup();/*唤醒进程，插入就绪队列*/
void proc_priority();/*优先权调度算法模拟*/
//void Run_loop(PCB *pcb);
void proc_loop();/*轮转法调度算法模拟*/
void update(PCB *pcb);/*更新进程信息*/
void pushback_queue(PCB *queue,PCB *item);/*将item插入到队列的尾部*/
void insert_queue(PCB *queue,PCB *item);/*将item插入到队列中，使得插入后，队列中按照优先级从高到低有序*/
void sort_queue(PCB *&queue);/*对queue中的结点进行排序，按照优先级从大到小*/
PCB *ready_queue,*block_queue,*idleprocess;/*就绪队列，阻塞队列及闲逛进程指针变量*/

int main(int argc, char* argv[])
{
int i=0;
while(1)
{
cout<<"\\**********PROCESS**********/";
cout<<("\n Please select a num in(1,2,0) ");
cout<<("\n 1--priority ");
cout<<("\n 2--loop ");
cout<<("\n 0-- exit\n");
cout<<"Please select a num:";
cin>>i;
while(i)
{

if(i==1)
{
cout<<("\n This is a example for priority processing: \n ");
init();
proc_priority();
}
else if (i==2)
{
cout<<("\n This is a example for round robin processing: \n ");
init();
proc_loop();
}
else
{
cout<<"Please select a num in(1,2,0)\n";
}
cout<<"Please select a num:";
cin>>i;
}
return 0;
}
}
///////输出所有PCB的初始值
void print_init(PCB *pcb)
{
PCB* temp=pcb->next ;
cout<<("\nID priority CPUtime ALLtime State");
while(temp!=NULL)
{
cout<<"\n"<<temp->ID<<" "<<temp->priority<<" "<<temp->CPUtime<<" "<<temp->ALLtime;
if(temp->State==0)
cout<<(" ready");
else if(temp->State ==1)
cout<<(" running");
else
cout<<(" blocked");
temp=temp->next;
}
}
///////输出进程属性信息
void print(PCB *pcb)
{
PCB *temp;
temp=pcb;
if(pcb->ID==0)
cout<<("\nThe idle peocess id running!");
else
{
cout<<"\n"<<temp->ID<<" "<<temp->priority<<" "<<temp->CPUtime<<" "<<temp->ALLtime;
if(temp->State==0)
cout<<(" ready");
else if(temp->State ==1)
cout<<(" running");
else
cout<<(" blocked");
}
}
///////将item插入到队列中，使得插入后，队列中按照优先级从高到低有序
void insert_queue(PCB *queue,PCB *item)
{
PCB *p,*q;
q=queue;p=q->next;
while(p!=0&&p->priority>=item->priority)
{
q=p;
p=p->next;
}
if(p==0)
{
item->next =0;
q->next=item;
}
else
{
item->next =p;
q->next =item;
}
}
///////将item插入到阻塞队列的尾部
void pushback_queue(PCB *queue,PCB *item)
{
PCB *p,*q;
q=queue,p=q->next;
while(p!=0)
{
q=p;
p=p->next;
}
item->next =q->next ;
q->next =item;
}
///////对queue中的结点进行排序，按照优先级从大到小
void sort_queue(PCB *&queue)
{
PCB *temp=new PCB;
temp->next =0;
while(queue->next )
{
PCB *p;
p=queue->next;
queue->next =p->next ;
insert_queue(temp,p);
}
queue->next =temp->next ;
delete temp;
}
///////生成进程属性信息，插入进程就绪队列,显示进程信息
void insert()
{
PCB *newp=0;
static long id =0;
newp=new PCB;
id++;
newp->ID =id;
newp->State=0;
newp->CPUtime=0;
newp->priority=rand()%3+1;
newp->ALLtime=rand()%3+1;
newp->next =NULL;
pushback_queue(ready_queue,newp);
//print(newp);
//cout<<("建立: Creating -> ready\n");
}
////////生成n个进程属性信息，插入进程就绪队列，显示进程信息
void insert(int n)
{
for(int i=0;i<n;i++)
insert();
}
///////产生idle进程，输入用户进程数目，调用insert()
void init()
{
block_queue=new PCB;
block_queue->next=0;
ready_queue=new PCB;
ready_queue->next=0;

int i=0,pcb_number=-1;//闲逛进程放入就绪队列
idleprocess=NULL;
idleprocess=(PCB *)malloc(sizeof(PCB));
idleprocess->ID=0;
idleprocess->State=0;
idleprocess->CPUtime=0;
idleprocess->priority=0;
idleprocess->ALLtime=0;
idleprocess->next=NULL;

idleprocess->next=ready_queue->next;//闲逛进程放入就绪队列
ready_queue->next=idleprocess;
//也可以假定初始时系统中只有一个idle进程
//输入初始进程的个数
while(pcb_number<0)
{
cout<<("Input the number of PCB to be start:");
cin>>pcb_number;
}
cout<<("\nID priority CPUtime ALLtime State\n");
for(;i<pcb_number;i++)
insert();

cout<<"*就绪队列初始化成功"<<endl;
::print_init(ready_queue);
cout<<endl;
}
///////调用destroy()将进程插入阻塞队列
void block(PCB *pcb)
{
pcb->State=2;
pcb->CPUtime-=2;
if(pcb->CPUtime<=0)
{
pcb->CPUtime+=2;
}
cout<<"\nThe process no"<<pcb->ID<<" is blocked!";
print(pcb);
cout<<(" 变迁2：running -> blocked\n");
pcb->next=block_queue->next;
block_queue->next =pcb;
}
///////更新进程信息,就绪队列中进程的优先级均增加1
void update(PCB *pcb)
{
PCB *temp=pcb->next;
while(temp&&temp->next )
{
temp->priority++;
temp=temp->next;
}
}
///////唤醒进程，插入就绪队列
void wakeup()
{
if(block_queue->next==0)/*此时没有阻塞的进程，无所谓的唤醒*/
return ;
PCB *q,*p;
while(true)
{
q=block_queue;
p=q->next;
while(p&&rand()%20!=1)
{
q=p;
p=p->next;
}
if(p!=0)
{
q->next =p->next ;
break;
}
}
p->State=0;
cout<<endl;
print(p);
cout<<" 变迁3: blocked -> ready"<<endl;
insert_queue(ready_queue,p);
}
///////运行进程，随机阻塞进程、产生新进程，插入就绪队列，唤醒阻塞进程
void Run_priority(PCB *pcb)
{
if(pcb->ID==0)
{
insert_queue(ready_queue,pcb);
print(pcb);
cout<<"变迁1: ready -> running\n";
}
else
{
pcb->State=1;
pcb->CPUtime+=4;
pcb->priority=pcb->priority -3;/*每运行一个时间片，其优先数减3*/
if(pcb->priority <1)
pcb->priority=1;
print(pcb);
printf("变迁1: ready -> running\n");
if(rand()%3==1)/*PCB不是闲逛进程，满足条件侧阻塞此进程*/
{
if(pcb->CPUtime-2<pcb->ALLtime)
block(pcb);
else/*已执行完毕，应该销毁进程*/
{
cout<<'\n';
cout<<"The process no"<<pcb->ID<<" is completed! 销毁：running->Destroy"<<endl;
delete pcb;
}
}
else/*否则看该进程是否执行完毕，如果执行完，则释放，否则再次放入就绪队列*/
{
if(pcb->CPUtime>=pcb->ALLtime)/*释放*/
{
cout<<'\n';
cout<<"The process no "<<pcb->ID<<" if completed! 销毁：running -> Destrory"<<endl;
delete pcb;
}
else
{
::insert_queue(::ready_queue,pcb);
}
}
}
update(ready_queue);/*更新就绪队列的优先级数*/
if(rand()%5==1)
{
insert(3);
::sort_queue(ready_queue);
}
if(rand()%7==1)
wakeup();
}
///////运行进程，随机阻塞进程、产生新进程，插入就绪队列，唤醒阻塞进程
void Run_loop(PCB *pcb)
{
if(pcb->ID==0)
{
insert_queue(ready_queue,pcb);
print(pcb);
cout<<"变迁1: ready -> running\n";
}
else
{
pcb->State=1;
pcb->CPUtime=pcb->ALLtime;
print(pcb);
printf("变迁1: ready -> running\n");
if(rand()%3==1)/*PCB不是闲逛进程，满足条件侧阻塞此进程*/
{
_state=1;
block(pcb);
}
else
{
cout<<'\n';
cout<<"The process no "<<pcb->ID<<" if completed! 销毁：running -> Destrory"<<endl;
delete pcb;
}
}
if(rand()%5==1)
{
insert(3);
}
if(rand()%7==1)
wakeup();
}
///////优先权调度算法模拟
void proc_priority()
{
sort_queue(ready_queue);
PCB *temp=0,*running=0;
int times=0;
cout<<"*调度前:";
::print_init(ready_queue);
for(;times<5;times++)
{
running=ready_queue->next;
ready_queue->next =running->next ;
cout<<endl;
cout<<"*调度开始"<<endl;
Run_priority(running);
}
cout<<"\n*本次调度结束。"<<endl;
}
///////轮转调度算法模拟
void proc_loop()
{

PCB *temp=0,*running=0;
int times=10;
cout<<"*调度前:";
::print_init(ready_queue);
while(1)
{
running=ready_queue->next;
ready_queue->next =running->next ;
cout<<endl;
if(times>0)
{
times=times-running->ALLtime;//每次运行一个进程减去ALLtime;
if(times>=0)
{
Run_loop(running);
}
else if(_state) //如果运行时被阻塞，则运行2个时间单位
{
times=times+2;
_state=0;
cout<<"5487584574389574 fgfgfgfgf gfgfg38954378954375894378954375";
}
else
pushback_queue(block_queue,running);//时间不过，则阻塞该进程，放到阻塞队列
}
else if(times<=0)
{
cout<<"\n*本次调度时间片到!";
break;
}
}
cout<<"\n*本次调度结束。"<<endl;
}

Linux进程管理
一、实验目的
进程描述符即为进程控制块。Linux的进程控制块由task_struct结果表示，其结构在sched.h里定义。主要进城标识、调度相关信息、进程虚拟空间信息、文件相关信息、信号处理信息、记账信息及统计信息、描述进程间关系的指针等。
加深对进程概念的理解，明确进程和程序的区别，进一步认识并发的实质，通过分析进程争用资源的现象，学习解决进程互斥的方法，了解Linux系统中进程通信的基本原理。
二、实验内容
阅读Linux的sched.h源码文件，加深对进程管理概念的理解。阅读Linux的fork.c源码文件，分析进程的创建过程。
学习Linux系统进行C程序的编译调式方法。GCC是GNU project Cand C++compiler宿写，是C/C++语言的编译器。因其后来可以多种语言的开发，现在改变为GNC Compiler Collection。使用gcc hello.c-o hello可以生成执行的文件hello。
Linux的进程状态有五种：
TASK_RUNNING（运行）：无论进程是否正在占用CPU，只要具备运行条件，都处于该状态。Linux把处于该状态的所有PCB组织成一个可运行队列run_queue,调度程序从这个队列只中选择进程运行。
TASK_INTERRUPTIBLE（可中断阻塞）：Linux将阻塞态划分成TASK_UNINTERRUPTIBLE、TASK_STOPPED、TASK_ZOMBILE三种不同的状态： TASK_UNINTERRUPTIBLE（不可中断唤醒）：处于该状态的进程只有当资源有效时被唤醒，不能通过信号或定时中断唤醒；TASK_STOPPED（暂停）：处于该状态的进程只能通过其他进程的信号才能唤醒；TASK_ZOMBILE（僵死）：进程已结束但尚未消亡，已经释放了大部分资源，PCB仍未被释放。处于TASK_UNINTERRUPTIBLE状态的进程资源有效时被唤醒，也可以通过信号或定时中断唤醒。
三、实验步骤
1、进程的创建
编写一段程序，使用系统调用fork（）创建两个进程。当此程序运行时，在系统中有一个父进程和两个子进程活动。让每个进程在屏幕上显示一个字符：父进程显示字符“A”,子进程分别显示字符“B”和字符“C”。
#include<stdio.h>
void main()
{
int p1,p2;
while(p1=fork()==-1);//创建子进程
if(p1==0)
putchar('b');
else
{
while((p2==fork())==-1);//创建子进程
if(p2==0)
putchar('c');
else
putchar('a');//父进程
}
}
2、进程的控制
#include<stdio.h>
void main()
{
int p1,p2;
while(p1=fork()==-1);//创建子进程
if(p1==0)
for(int i;i<10;i++)
printf("daugheter%d\n",i);
else
{
while((p2==fork())==-1);//创建子进程
if(p2==0)
for(int i;i<10;i++)
printf("son%d\n",i);
else
for(int i;i<10;i++)
printf("parent%d\n",i);
}
}

#include<stdio.h>
#include<unistd.h>
#include<sys/wait.h>
#include<sys/stat.h>
#include<sys/types.h>
#include<fcntl.h>

void main()
{
int fd,spid,ppid;
char str[80];
fd=open("myfile",O_RDWR|O_CREAT,0644);
if((cpid=fork())==-1)
{
lseek(fd,0,0);
exit(1);
}
else if(cpid>0)
{
lseek(fd,0,0);
if(lockf(fd,0,0)==-1)
{
perror("lock failure");
exit(1);
}
printf("I am a parent process,my pid is %d\n",getid());
printf("Please input a string:\n");
scanf("%s",str);
lseek(fd,0,0);
write(fd,str,sizeof(str));
lseek(fd,0,0);
if(lockf(fd,0,0)==-1)
{
perror("unlock failure");
exit(1);
}
else
{
sleep(1);
lseek(fd,0,0);
if(lockf(fd,0,0)==-1)
{
perror("lock failure");
exit(1);
}
lseek(fd,0,0);
read(fd,str,sizeof(str));
lseek(fd,0,0);
if(lockf(fd,0,0)==-1)
{
perror("unlock failure");
exit(1);
}
printf("\nI am a parent process,my pid is %d\n",getid());
printf("Please input a string:\n");
printf("%s\n",str);
}
}
}

3、软中断通信
编制一段程序，使其实现进程的软中断通信。
使用