实验一进程调度
实验性质：设计
建议学时：6学时
实验目的：
通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统 性能的评价方法。
实验内容；
设计程序模拟进程的轮转法调度过程。假设初始状态为：有n个进程处于就绪状态，有m个进 程处于阻塞状态。釆用轮转法进程调度算法进行调度。调度过程中，假设处于执行状态的进程不会阻 塞，且每过t个时间片系统释放资源，唤醒处于阻塞队列队首的进程。
程序要求如下：
1） 输出系统中进程的调度次序；
2） 计算CPU利用率。
实现提示：
用C语言实现提示：
1） 程序中进程可用PCB表示，其类型描述如下：
struct PCB_type { char name ; 〃进程名 int state ; //进程状态 2 表示“执行"状态 1——表示“就绪”状态 0——表示“阻塞”状态 int cpu_time ; 〃运行需要的CPU时间（需运行的时间片个数） }
2） 设置两个队列，将处于“就绪”状态的进程PCB挂在队列ready中；将处于“阻塞”状态的 进程PCB挂在队列blocked中。队列类型描述如下：
struct QueueNode{ struct PCB_type PCB; Struct QueueNode *next; }
并设全程量：
struct QueueNode ready_head=NULL, //ready队列队首指针 *ready_tail=NULL, //ready队列队尾指针 *blocked_head=NULL, //blocked队列队首指针 *blocked_tail=NULL; //blocked队列队尾指针
3）设计子程序
start_stateO； 〃读入假设的数据，设置系统初始状态 dispathO； 〃模拟调度 calculate。； //计算 CPU 利用率
实验要求：
1） 上机前仔细编好程序；
2） 上机时独立调试程序；
3） 提交实验报告，包括纸质稿和电子稿两部分。实验报告要求详见实验报告模板。
测试用数据：
n=2 （处于就绪状态的进程的个数）
m=3 （处于阻塞状态的进程的个数）
t=5 （每过t个时间片系统释放资源，唤醒处于阻塞队列队首的进程）
测试用例：
代码展示
#include <iostream> #include <fstream> using namespace std; struct PCB_type { char name; /* 0:阻塞 1:就绪 2:执行 */ int state; /* 需要的CPU时间，即运行的时间片个数 */ double cpu_time; }; struct QueueNode { PCB_type PCB; QueueNode *next; }; QueueNode *ready_head = NULL, *ready_tail = NULL, *blocked_head = NULL, *blocked_tail = NULL; int all_time = 0; int free_time = 0; double time_slice_len = 1; // 函数声明 void start_state(); void dispath(); void calculate(); void ready_Enqueue(QueueNode *p); void blocked_Enqueue(QueueNode *p); void ready_Dequeue(); void blocked_Dequeue(); QueueNode *ready_Front(); QueueNode *blocked_Front(); int main() { start_state(); dispath(); calculate(); system("pause"); return 0; } void start_state() { ifstream f; f.open("OS\\test1.txt"); int ready_pcb_num, blocked_pcb_num; f >> ready_pcb_num; f >> blocked_pcb_num; // 就绪队列初始化 for (int i = 0; i < ready_pcb_num; i++) { QueueNode *p = new QueueNode; f >> p->PCB.name >> p->PCB.cpu_time; p->PCB.state = 1; p->next = NULL; ready_Enqueue(p); } // 阻塞队列初始化 for (int i = 0; i < blocked_pcb_num; i++) { QueueNode *p = new QueueNode; f >> p->PCB.name >> p->PCB.cpu_time; p->PCB.state = 0; p->next = NULL; blocked_Enqueue(p); } cout << "The processes in the ready queue are:" << endl; if (ready_head == NULL) { cout << "The ready queue is empty"; } else { QueueNode *p = ready_head; while (p) { cout << p->PCB.name << " " << p->PCB.state << " " << p->PCB.cpu_time << endl; p = p->next; } } // 输入t int t; f >> t; } void dispath() { cout << "Start scheduling" << endl; while (ready_head != NULL || blocked_head != NULL) { if (ready_head != NULL) { QueueNode *tmp = ready_Front(); ready_Dequeue(); tmp->PCB.state = 2; tmp->PCB.cpu_time -= time_slice_len; all_time++; printf("Time slice %d: process %c scheduling\n", all_time, tmp->PCB.name); if (tmp->PCB.cpu_time < time_slice_len) { printf("process %c over!\n", tmp->PCB.name); } else { ready_Enqueue(tmp); } } else { all_time++; free_time++; printf("Time slice %d: Free a slice of time\n", all_time); } if (blocked_head != NULL && all_time % 5 == 0) { QueueNode *tmp = blocked_Front(); blocked_Dequeue(); ready_Enqueue(tmp); } } } void calculate() { cout << "CPU Utilization rate: " << ((all_time - free_time) / (double)all_time) * 100 << "%" << endl; } // 队列实现 void ready_Enqueue(QueueNode *p) { if (ready_head == NULL) { ready_head = ready_tail = p; } else { ready_tail->next = p; ready_tail = p; } } void blocked_Enqueue(QueueNode *p) { if (blocked_head == NULL) { blocked_head = blocked_tail = p; } else { blocked_tail->next = p; blocked_tail = p; } } void ready_Dequeue() { QueueNode *temp = ready_head; if (ready_head == NULL) { printf("ready Queue is Empty\n"); return; } if (ready_head == ready_tail) { ready_head = ready_tail = NULL; } else { ready_head = ready_head->next; } } void blocked_Dequeue() { QueueNode *temp = blocked_head; if (blocked_head == NULL) { printf("blocked Queue is Empty\n"); return; } if (blocked_head == blocked_tail) { blocked_head = blocked_tail = NULL; } else { blocked_head = blocked_head->next; } } QueueNode *ready_Front() { return ready_head; } QueueNode *blocked_Front() { return blocked_head; }
