实验课程：操作系统
实验名称：进程调度的设计与实现 （综合实验）
第一部分 实验内容
1．实验目标
1、 综合应用下列知识点设计并实现操作系统的进程调度：邻接表，布尔数组，非阻塞输入，图形用户界面GUI，进程控制块，进程状态转换，多级反馈队列进程调度算法。
2、 加深理解操作系统进程调度的过程。
3、 加深理解多级反馈队列进程调度算法。
2. 实验任务
1、 用一种熟悉的语言，如C、PASCAL或C++等，编制程序。
2、 采用多级反馈队列调度算法进行进程调度。
3. 实验设备及环境
PC；C/C++等编程语言。
4. 实验主要步骤
(1) 根据实验目标，明确实验的具体任务；
(2) 编写程序实现进程调度算法；
(3) 设计实验数据并运行程序、记录运行的结果；
(4) 分析实验结果；
(5) 实验后的心得体会。
第二部分 问题及算法
1. 问题描述
(1) 采用一种熟悉的语言，如C、PASCAL或C++等，编制程序。
(2) 采用多级反馈队列调度算法进行进程调度。
(3) 每个进程对应一个PCB。在PCB中包括进程标识符pid、进程的状态标识status、进程优先级priority、进程的队列指针next和表示进程生命周期的数据项life（在实际系统中不包括该项）。
(4) 创建进程时即创建一个PCB，各个进程的pid都是唯一的，pid是在1到100范围内的一个整数。可以创建一个下标为1到100的布尔数组，“真”表示下标对应的进程标识号是空闲的，“假”表示下标对应的进程标识号已分配给某个进程。
(5) 进程状态status的取值为“就绪ready”或“运行run”，刚创建时，状态为“ready”。被进程调度程序选中后变为“run”。
(6) 进程优先级priority是0到49范围内的一个随机整数。
(7) 进程生命周期life是1到5范围内的一个随机整数。
(8) 初始化时，创建一个邻接表，包含50个就绪队列，各就绪队列的进程优先级priority分别是0到49。
(9) 为了模拟用户动态提交任务的过程，要求动态创建进程。进入进程调度循环后，每次按ctrl+f即动态创建一个进程，然后将该PCB插入就绪队列中。按ctrl+q退出进程调度循环。
(10) 在进程调度循环中，每次选择优先级最大的就绪进程来执行。将其状态从就绪变为运行，通过延时一段时间来模拟该进程执行一个时间片的过程，然后优先级减半，生命周期减一。设计图形用户界面GUI，在窗口中显示该进程和其他所有进程的PCB内容。如果将该运行进程的生命周期不为0，则重新把它变为就绪状态，插入就绪队列中；否则该进程执行完成，撤消其PCB。以上为一次进程调度循环。
(11) 在上机实现该程序之后，要求写出实验报告，其中包括实验名称、实验目的、实验内容、程序的主要流程图、实验心得和主要源程序清单等。
2. 多级反馈队列进程调度算法的一般思路
(1) 进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。
(2) 首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。
(3) 对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。
(4) 在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。
3. 算法实现的关键点
队列的切换和优先级的变化。
第三部分 实验结果与分析
1. 实验数据及结果
实验数据为随机数据，所以结果也为随机值，故见下文
2. 实验分析及结论
由于不会关于GUI的相关程序，所以做不了GUI界面，故而比较难看。
第四部分 心得与展望
1. 自我评价及心得体会
看起来很简单，但是做起来很复杂，需要很长一段时间。
2. 展望
以后有时间要学GUI编程。
第五部分 附录
1. 主要界面
2. 源程序
/**
made by FrankieCCT
time:2013.5.19 7:13
main.cpp
**/
#include "myQueue.h"
int main()
{
char chioce;
PCB *tmp_pcb;
int i;
int flag = 0;
fill(&pid_queue[0],&pid_queue[100],true);
while (1)
{
menu();
cin >> chioce;
switch (chioce)
{
case 'y':
case 'Y':
tmp_pcb = get_a_random_ready_PCB();
insert_pcb(tmp_pcb, tmp_pcb->priority);
break;
case 'n':
case 'N':
break;
default:
puts("illegal!");
system("pause");
system("cls");
continue;
break;
}
for (i = 49; i > -1; i--)
{
if (p_queue[i].first_task != NULL)
{
puts("上一时间片运行情况：");
tmp_pcb = p_queue[i].first_task;
tmp_pcb->status = RUN_PCB;
cout << "pid: " << p_queue[i].first_task->pid
<< "\t的进程被选中,将之状态变为run, 生命周期由"
<< p_queue[i].first_task->life--;
cout << "变为" << p_queue[i].first_task->life << endl;
p_queue[i].first_task->status = READY_PCB;
if (p_queue[i].first_task->life > 0)
{
cout << "生命周期不为0,将之状态变为ready,优先级由"
<< tmp_pcb->priority;
cout << "变为" << tmp_pcb->priority/2
<<"后插入对应队列。" << endl;
tmp_pcb->priority /= 2;
insert_pcb(tmp_pcb, tmp_pcb->priority);
}
else if (p_queue[i].first_task->life == 0)
{
cout << "生命周期变成0，所以进程结束，该PCB被撤销." << endl;
pid_queue[p_queue[i].first_task->pid] = true;
}
p_queue[i].first_task = p_queue[i].first_task->next;
break;
}
}
if (i == -1)
{
puts("all complete!");
}
puts("现在线程情况：");
for (i = 49; i > -1; i--)
{
if (p_queue[i].first_task != NULL)
{
cout << "queue " << i << ": " << endl;
cout << "pid: " << p_queue[i].first_task->pid
<< "\tlife: " << p_queue[i].first_task->life << endl;
tmp_pcb = p_queue[i].first_task->next;
while (tmp_pcb != NULL)
{
cout << "pid: " <<tmp_pcb->pid
<< "\tlife: " << tmp_pcb->life << endl;
tmp_pcb = tmp_pcb->next;
}
}
}
}
return 0;
}
/**
made by FrankieCCT
time:2013.5.19 7:13
myQueue.h
**/
#ifndef MYQUEUE_H_INCLUDED
#define MYQUEUE_H_INCLUDED
#include <iostream>
using namespace std;
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#define MAX_PID_NUM 101
#define MAX_PCB_NUM 50
#define READY_PCB 1
#define RUN_PCB 2
struct PCB;
int get_available_pid();
void menu();
PCB *get_a_random_ready_PCB();
bool pid_queue[MAX_PID_NUM];
struct PCB
{
int pid;
int status;
int priority;
PCB *next;
int life;
PCB()
{
srand(time(0));
status = READY_PCB;
pid = get_available_pid();
if (pid == -1)
{
puts("full pid queue!");
system("pause");
abort();
}
else
{
pid_queue[pid] = false;
}
next = NULL;
priority = rand() % 49 + 1;
life = rand() % 5 + 1;
}
PCB(const PCB&pcb)
{
status = pcb.status;
pid = pcb.pid;
next = pcb.next;
priority = pcb.priority;
life = pcb.life;
}
};
struct PCB_queue
{
PCB *first_task;
PCB_queue()
{
first_task = NULL;
}
};
int get_available_pid()
{
for (int i = 0; i < 101; i++)
if (pid_queue[i])
return i;
return -1;
}
void menu()
{
puts("是否新建进程？（Y/N）");
}
PCB *get_a_random_ready_PCB()
{
PCB *a_pcb = new PCB();
cout << "一个pid为" << a_pcb->pid
<< "，生命周期为" << a_pcb->life
<< ", 优先级为" << a_pcb->priority
<< "的进程被创建。" << endl;
return a_pcb;
}
PCB_queue p_queue[MAX_PCB_NUM];
void insert_pcb(PCB *tmp_pcb, int i)
{
PCB *tmp_pcb_other;
if (p_queue[i].first_task == NULL)
{
p_queue[i].first_task = tmp_pcb;
p_queue[i].first_task->next = NULL;
}
else
{
tmp_pcb_other = p_queue[i].first_task;
while (tmp_pcb_other->next != NULL)
{
tmp_pcb_other = tmp_pcb_other->next;
}
tmp_pcb_other->next = tmp_pcb;
tmp_pcb_other->next->next = NULL;
}
}
#endif // MYQUEUE_H_INCLUDED
参考文献
l 《操作系统教程》谢旭东，朱明华，张练兴，李宏伟等，机械工业出版社，2013年