操作系统实验报告 ( 进程调度算
)
操作系统实验报告
实验 1 进程调度算法
报告日期： 2016-6-10
姓 名：
学 号：
班 级：
任课教师：
实验 1 进程调度算法
一、实验内容
按优先数调度算法实现处理器调度。
二、实验目的
在采用多道程序设计的系统中， 往往有若干个进程同时处于就绪状态。
当就绪进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占用处理器。
本实验模拟在单处理器情况下的处理器调度，帮助学生加深了解处理器调度的工作。
三、实验原理
设计一个按优先数调度算法实现处理器调度的程序。
假定系统有五个进程，每一个进程用一个进程控制块 PCB 来代表，进程控制块的格式为：
进程名
指针
要求运行时
间
优先数
状态
其中，进程名——作为进程的标识， 假设五个进程的进程名分别为 P1，P2，P3，P4，P5。
指针——按优先数的大小把五个进程连成队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程中的指针为“ 0”。
要求运行时间——假设进程需要运行的单位时间数。
优先数——赋予进程的优先数， 调度时总是选取优先数大的进程先执行。
状态——可假设有两种状态， “就绪”状态和“结束”状态。五个进程的初始状态都为 “就绪”，用“ R”表示，当一个进程运行结束后，它的状态为“结束”，用“ E”表示。
在每次运行你所设计的处理器调度程序
之前，为每个进程任意确定它的 “优先数”和“要求运行时间”。
为了调度方便，把五个进程按给定的优先数从大到小连成队列。用一单元指出队首进程，用指针指出队列的连接情况。例：
队首标志
K 2
K
1
2
3
4
5
P
P
P
P
P
1
K
K
K
K
2
3
4
5
0
K 4
K 5
K 3
K 1
2
3
1
2
4
1
5
3
4
2
R
R
R
R
R
PC
PC
PC
PC
PC
B1
B2
B3
B4
B5
处理器调度总是选队首进程运行。采用动态改变优先数的办法， 进程每运行一次优先数就减“ 1”。由于本实验是模拟处理器调度，所以，对被选中的进程并不实际的启动运行，而是执行：
优先数 -1
要求运行时间 -1
来模拟进程的一次运行。
提醒注意的是： 在实际的系统中， 当一个进程被选中运行时， 必须恢复进程的现场， 让它占有处理器运行， 直到出现等待事件或运行结束。
在这里省去了这些工作。
(5) 进程运行一次后，若要求运行时间 0，则再将它加入队列 （按优先数大小插入， 且置队首标志）；若要求运行时间 =0，则把它的状态修改成“结束”（E），且退出队列。
若“就绪”状态的进程队列不为空，则重复上面（ 4）和（5）的步骤，直到所有进程都成为“结束”状态。
在所设计的程序中应有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化。
为五个进程任意确定一组 “优先数”和“要求运行时间”，启动所设计的处理器调度程序，
显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。
四、实验内容
1.画出算法流程图
程序中使用的数据结构及符号说明。
1>结构体
typedef
struct
PCB
// 封装进程结构体
{
char name[2];
int time;
int prior_num;
char state;
struct PCB*next;
} PCB,* pPCB;// 结构体名为 PCB，pPCB是指向结构体的指针
2>链表
pPCBCreateLink( PCB* arr )
{
int i = 0;
int j = 0; int pos = 0; int pos1 = 0; pPCBhead =
NULL;
for
(i = 0; i <
N; i++)
// 先找出优先级最高的进程，赋给
头结点
{
if
( arr [i].prior_num ==
N)
{
pos = i;
break ;
}
}
head = & arr [pos];
for
(i =
N - 1; i > 0; i--)
// 按优先级大小依次找到其
他进程，链起来
{
for (j = 0; j < N; j++)
{
if ( arr [j].prior_num == i)
{
pos1 = j;
break ;
}
}
arr [pos].next = & arr [pos1];
pos = pos1;
}
return head; // 返回头结点
}
源程序
#define _CRT_SECURE_NO_WARNINGS1
#ifndef _SCHEDULING_H__
#define _SCHEDULIHG_H__
#define
N 5
#include
<stdio.h>
#include
<stdlib.h>
#include
<time.h>
#include
<string.h>
typedef
struct
PCB
// 封装进程结构体
{
char name[2];
int
time;
int
prior_num;
char state;
struct
PCB*next;
} PCB, *
pPCB; // 结构体名为 PCB，pPCB是指向结构体的指针
pPCBCreateLink(
PCB*arr);
//
创建链表把 5个进程链起来
void InitPCB( PCB*arr,
int
*a);
// 初始化进程
pPCBrunPCB( PCB*arr,
pPCBpcb);
// 进程运行
void printPCB(
PCB*arr);
// 输出进程的初始状态
void random( int
a[],
int
n);
// 将数组内容打乱顺序
void PrintRun(
pPCBhead);
// 输出运行后的进程
#endif
#include
"head.h"
void random( int
a[],
int
n)
{
int
index, tmp, i;
srand(( unsigned int )time( NULL));
for
(i = 0; i <
n; i++)
{
index = rand() % (
n - i) + i;
if (index != i)
{
tmp =
a[i];
a[i] =
a[index];
a[index] = tmp;
}
}
}
pPCBCreateLink(
PCB* arr )
{
int
i = 0;
int
j = 0;
int
pos = 0;
int
pos1 = 0;
pPCBhead =
NULL;
for
(i = 0; i <
N; i++)
//
先找出优先级最高的进程，赋给头结点
{
if ( arr [i].prior_num ==
N)
{
pos = i;
break ;
}
}
head = & arr [pos];
for
(i = N - 1; i > 0; i--)
// 按优先级大小依次找到其他进程，链
起来
{
for (j = 0; j <
N; j++)
{
if ( arr [j].prior_num == i)
{
pos1 = j;
break ;
}
}
arr [pos].next = & arr [pos1];
pos = pos1;
}
return head; // 返回头结点
}
void
InitPCB(
PCB* arr , int
* a)
{
int
i = 0;
char *str[] = {
"p1" ,
"p2" ,
"p3" , "p4" , "p5" };
for (i = 0; i <
N; i++)
// 将5个进程初始化
{
strcpy(
arr [i].name, str[i]);
arr [i].prior_num =
a[i];
arr [i].state =
'R'
;
arr [i].next =
NULL;
arr [i].time = (rand() % 4) + 1;
// 这里将所需运行时间控制在
4以
内
}
}
void
printPCB(
PCB* arr )
//
打印进程最初状态
{
int
i = 0;
for (i = 0; i <
N; i++)
{
printf(
" 进程名称： %s\n",
arr [i].name);
printf(
" 进程优先级： %d\n", arr [i].prior_num);
printf(
" 进程所需运行时间： %d\n",
arr [i].time);
printf(
" 进程当前状态： %c\n" , arr
[i].state);
printf(
"\n"
);
}
}
pPCBrunPCB( pPCB head, pPCB pcb) // 进程执行函数
{
int i = 0;
pPCBcur= head;
pPCBprev = NULL;
while (cur)
{
cur->time--; // 先让进程的时间和优先级减一
cur->prior_num--;
if (cur->time == 0)
// 判断所需运行时间是否为
0
{
if (cur ==
head)
// 判断是否是头结点
{
cur->state = 'E' ;
head = head->next;
cur = head;
}
else
{
cur->state = 'E' ;
prev->next = cur->next;
cur = cur->next;
}
}
else // 若时间不为 0，指针向后移动
{
prev = cur;
cur = cur->next;
}
}
return head;
}
void PrintRun( pPCBhead)
{
pPCBcur = head;
printf( " 进程运行： \n" );
while (cur)
{
printf( " 进程名称： %s\n", cur->name);
printf( " 进程优先级： %d\n", cur->prior_num);
printf( " 所需运行时间： %d\n", cur->time);
printf( " 当前状态： %c\n", cur->state);
printf( "\n" );
cur = cur->next;
}
}
#include "head.h"
int main()
{
PCBpcb;
pPCBhead;
int a[] = { 1, 2, 3, 4, 5 };
random(a, N);
PCBarr[ N];
InitPCB(arr,a);
printPCB(arr);
head = CreateLink(arr);
printf( " 运行一次： \n" );
head = runPCB(head, &pcb);
PrintRun(head);
printf( " 运行二次： \n" );
head = runPCB(head, &pcb);
PrintRun(head);
printf( " 运行三次： \n" );
head = runPCB(head, &pcb);
PrintRun(head);
getchar();
return 0;
}
程序运行时的初值和运行结果初始状态：
运行一次：
运行两次：
运行三次：
五、实验小结
在用程序模拟实现进程的优先数调度过程中， 我对操作系统的进
程调度理解也越来越深刻， 不断的调试 BUG 让我很有成就感， 同时，
这个实验花费了我大量时间让我觉得我还需要有进一步的提升。