静态优先级调度算法
__ 成绩(五级制):________
武汉科技大学城市学院
《操作系统》实验报告
院 系 武汉科技的大学城市学院
学生专业 _信科________
年级 班 _大三________
课程名称 _操作系统_
实验题目 _进程调度________
学生姓名 __宋骋_______
指导教师 __郭冀生____
2013年 11 月 4 日
实验二 进程调度
一、实验目的
进程是操作系统最重要的概念之一,进程调度又是操作系统核心的重要内
容。通过该实验,要求同学们了解各进程在执行过程中的状态和参数的变
化情况,以便于观察诸进程的调度过程。
二、实验内容及要求
按剥夺式优先数法对三个进程P1,p2,p3进行模拟调度,各进程的优先数静
态设置,其中P1的优先数最高,P3的优先数最低。每个进程都处于执行
E(execute),就绪R(ready)和等待W(wait)三种状态之一,并假定初始状态均
为R. 。
三个进程有如下同步关系:P1因等待事件1被阻塞后由P2发现并唤醒之,
P2因等待事件2被阻塞后由P3发现并唤醒之。
当系统进入运行,在完成必要的初始化工作以后便进入进程调度,首先选
择优先数最高的进程使其进入执行(分配CPU )。当执行进程因等待某个
事件被阻塞或唤醒某个等待进程时,转入进程调度。
如果被唤醒的进程的优先数大于现行的执行进程,则剥夺现行进程的执行
权,而将CPU 分配给被唤醒的进程。当系统处于死锁或三个进程都执行
完毕时系统退出运行。
系统中应用到如下数据结构:
*进程控制块PCB ;
*信号量sem ;
*其它需要的数据结构。由自己设计。
三、实验原理及步骤
根据现代操作系统的特征
1.并发性(concurrence) ;
2.共享性(sharing);
3.虚拟性(virtual);
4.异步性(asynchronism) 。
模拟出进程在执行中的状态变化过程;
体会进程申请资源、使用资源、归还资源;
体会死锁。
步骤(参考框图)
4、 算法和流程图
可强占优先调度算法实现过程流程图(如下图):
四、程序运行
1 选择输入执行程序(如下图)
2 可强占优先调度算法图(如下图)
五. 设计总结:
通过该课程设计,加深了对系统进程调度机制的理解。在抢占方式中实践了“抢占” 必须
遵循的原则:优先权原则。认识了几种进程调度算法的优缺点以及应用范围。加强C++的编
程能力,实现类的封
装。
附录:
程序及注释(用红色黑体标注自己设计的函数)
//进程PCB 类和模拟cpu 的进程类的声明
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MAX_PHILOSOPHERS 3 //待测试的哲学家数
#define ZERO 48 //数字0的ASCII 码
#define DELAY rand()%25
struct PCB
{
char p_name[20];
int p_priority;
int p_needTime;
int p_runTime;
char p_state;
char deadlock();
struct PCB* next;
};
void HighPriority();
void deadlock();
void Information();//形参的改变映射给实参 说白了就是实参传过去不用return 返回就可以
把实参改变
char Choice();
struct PCB* SortList(PCB* HL);
int main(int argc,char *argv[])
{
Information();
char choice = Choice();
switch(choice)
{
case '1':
system("cls");
HighPriority();
break;
case '2':
system("cls");
void deadlock();
break;
default:
break;
}
system("pause");
return 0;
}
void Information()
{
printf("\n\n");
printf(" ********************************************* \n");
printf(" 模拟进程调度算法\n");
printf(" ********************************************* \n\n\n");
printf(" 静态优先级调度算法");
printf(" 死锁问题");
printf(" 按回车键进入演示程序");
getchar();
system("cls");
system("cls");
}
char Choice()
{
printf("\n\n");
printf(" ********************************************* \n");
printf(" 进程调度演示\n");
printf(" ********************************************* \n\n\n");
printf(" 1. 演示最高优先数优先算法。\n");
printf(" 2. 演示死锁问题。\n");
printf(" 3. 退出程序。\n\n\n\n");
printf(" 选择进程调度方法:");
printf("select a function(1~3):");
char ch = getchar();
return ch;
system("cls");
}
void HighPriority()
{
struct PCB *processes, *pt;
//pt作为临时节点来创建链表
processes = pt = (struct PCB*)malloc(sizeof(struct PCB));
for (int i = 1; i != 4; ++i)
{
struct PCB *p = (struct PCB*)malloc(sizeof(struct PCB));
printf("进程号No.%d:\n", i);
printf("输入进程名:");
scanf("%s", p->p_name);
printf("输入进程优先数:");
scanf("%d", &p->p_priority);
printf("输入进程运行时间:");
scanf("%d", &p->p_needTime);
p->p_runTime = 0;
p->p_state = 'W';
p->next = NULL;
pt = p;
printf("\n\n");
}
getchar(); //接受回车
//processes作为头结点来存储链表
processes = processes->next;
int cases = 0;
struct PCB *psorted = processes;
while (1)
{
++cases;
pt = processes;
//对链表按照优先数排序
//psorted用来存放排序后的链表
psorted = SortList(psorted);
printf("The execute number: %d\n\n", cases);
printf("**** 当前正在运行的进程是:%s\n", psorted->p_name);
psorted->p_state = 'R';
printf("qname state super ndtime runtime\n");
printf("%s\t%c\t%d\t%d\t%d\t\n\n", psorted->p_name, psorted->p_state, psorted->p_priority, psorted->p_needTime, psorted->p_runTime);
pt->p_state = 'W';
psorted->p_runTime++;
psorted->p_priority--;
printf("**** 当前就绪状态的队列为:\n\n");
//pt指向已经排序的队列
pt = psorted->next;
while (pt != NULL)
{
printf("qname state super ndtime runtime\n");
printf("%s\t%c\t%d\t%d\t%d\t\n\n", pt->p_name, pt->p_state, pt->p_priority, pt->p_needTime, pt->p_runTime);
pt = pt->next;
}
//pt指向已经排序的链表,判断链表是否有已用时间啊等于需要时间的 pt = psorted;
struct PCB *ap;
ap = NULL; //ap指向pt 的前一个节点
while (pt != NULL)
{
if (pt->p_needTime == pt->p_runTime)
{
if (ap == NULL)
pt = psorted->next;
psorted = pt;
}
else
ap->next = pt->next;
}
ap = pt;
pt = pt->next;
}
if (psorted->next == NULL)
break;
getchar();
}
}
struct PCB* SortList(PCB* HL)
{
struct PCB* SL;
SL = (struct PCB*)malloc(sizeof(struct PCB));
SL = NULL;
struct PCB* r = HL;
while (r != NULL)
{
struct PCB* t = r->next;
struct PCB* cp = SL;
struct PCB* ap = NULL;
while (cp != NULL)
{
if (r->p_priority > cp->p_priority)
break;
else
{
ap = cp;
cp = cp->next;
}
}
if (ap == NULL)
{
r->next = SL;
SL = r;
}
else
{
r->next = cp;
ap->next = r;
}
r = t;
}
return SL;
}
//
HANDLE h_mutex_chopsticks[MAX_PHILOSOPHERS]; //互斥体数组,每根筷子需要一个互斥体
int thread_number[MAX_PHILOSOPHERS]={1,2,3};//定义死锁的个数
//会产生死锁的哲学家线程
int deadlock_philosopher(LPVOID data){
int philosopher_number=*(int *)(data); //哲学家编号
for(;;)
{
srand( (unsigned)time( NULL ) * ( philosopher_number+ 1) );
Sleep(DELAY);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",(ZERO+philosopher_number));
WaitForSingleObject(h_mutex_chopsticks[philosopher_number], INFINITE);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," got chopstick ",(ZERO+philosopher_number));
Sleep(DELAY/4);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",(ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS));
WaitForSingleObject(h_mutex_chopsticks[((1+philosopher_number)%MAX_PHILOSOPHERS)], INFINITE);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," got chopstick ",(ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS));
printf("%s%c%s\n","Philosopher ",ZERO+philosopher_number," is eating.");
Sleep(DELAY);
ReleaseMutex(h_mutex_chopsticks[philosopher_number]);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," released chopstick ",ZERO+philosopher_number);
ReleaseMutex(h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS]);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," released chopstick ",(ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS));
Sleep(DELAY);
} // end for
return 0;
}
//死锁时的初始化程序
void deadlock()
{
char choice;
int i=0;
HANDLE h_thread[MAX_PHILOSOPHERS];
printf("可能出现死锁的哲学家就餐问题\n");
for(i=0;i
{
h_mutex_chopsticks[i]=CreateMutex(NULL,FALSE,NULL);
};
for(i=0;i
{
h_thread[i]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(deadlock_philosopher),&thread_number[i],0,NULL);
};
WaitForMultipleObjects(MAX_PHILOSOPHERS,h_thread,TRUE,-1);
do
{
choice=(char)getch();
}while( choice!='2');
system("cls");
deadlock();
printf("\nPress any key to return to main menu.");
getch();
system("cls");
}
//通过按序分配资源预防死锁的哲学家线程
int ordered_allocation_philosopher(LPVOID data)
int philosopher_number=*(int *)(data);
for(;;)
{
srand( (unsigned)time( NULL ) * ( philosopher_number+ 1) );
Sleep(DELAY);
if(philosopher_number==MAX_PHILOSOPHERS-1){
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",(ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS));
WaitForSingleObject(h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS], INFINITE);
Sleep(DELAY/4);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",ZERO+philosopher_number);
WaitForSingleObject(h_mutex_chopsticks[philosopher_number], INFINITE);
}
else{
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",ZERO+philosopher_number);
WaitForSingleObject(h_mutex_chopsticks[philosopher_number], INFINITE); Sleep(DELAY/4);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS);
WaitForSingleObject(h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS], INFINITE);
}
printf("%s%c%s\n","Philosopher ",ZERO+philosopher_number," is eating.");
Sleep(DELAY);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is releasing chopstick ",ZERO+philosopher_number);
ReleaseMutex(h_mutex_chopsticks[philosopher_number]);
printf("%s%c%s%c\n","Philosopher ",ZERO+philosopher_number," is releasing chopstick ",ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS);
ReleaseMutex(h_mutex_chopsticks[(1+philosopher_number)%MAX_PHILOSOPHERS]);
Sleep(DELAY);
} // end for
return 0;
}
//通过按序分配资源预防死锁的初始化程序
void ordered_allocation()
{
char choice;
int i=0;
HANDLE h_thread[MAX_PHILOSOPHERS];
printf("可能出现死锁的哲学家就餐问题\n");
for(i=0;i
h_mutex_chopsticks[i]=CreateMutex(NULL,FALSE,NULL);
};
for(i=0;i
h_thread[i]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(ordered_allocation_philosopher),&thread_number[i],0,NULL);
};
WaitForMultipleObjects(MAX_PHILOSOPHERS,h_thread,TRUE,-1);
do
{
choice=(char)getch();
}while( choice!='2');
system("cls");
deadlock();
printf("\nPress any key to return to main menu.");
getch();
system("cls");
}