实验目的
撑握进程调度的概念 学习Linux内核源码编写风格
重点理解进程调度策略算法，包括FCFS、RR、SRT、Feedback的调度算法。
实验内容：
验证test4.c，
理解FIFO和RR两种算法 编写SRT和Feedback两种算法，测试运行结果，编写实验报告。
本文仅提供实验内容2的代码，并且本文代码在test4.c代码文件之上添加内容来实现实验内容2。代码未整理，可能有些凌乱。
/***************进程调度实验**************/
/*****************************************
采用的是linux0.12的内核编写风格，可参考赵炯的《Linux内核完全剖析》
Author.gdong.guan
版权所有，仅供学习，不要发布到网上
******************************************/
#include<cstdio>
#include<sys/time.h>
#include<malloc.h>
#include<cstdlib>
#define NR_TASKS 64 //系统支持的进程个数
#define TASK_RUNNING 0 //就绪态
#define TASK_UNINTERRUPTIBLE 2 //不可中断的睡眠状态
#define TASK_ZOMBIE 3 //僵死态
//进程表项
struct task_struct {
long pid; //进程号
long state; //进程运行状态
long priority; //优先数
long counter; //进程剩余时间片
long start_time; //进程开始时间
long excute_time; //进程执行时间
long flag;
};
struct task_struct init_task = {
.pid = 0,
.state = 0,
.priority = 0,
.counter = 0,
.start_time = 0,
.excute_time = 0,
.flag = -1
};
struct task_struct *current = &init_task;
unsigned long volatile jiffies = 0; //系统滴答数
struct task_struct *task[NR_TASKS] = {&init_task,}; //进程指针数组
#define FIRST_TASK task[0]
#define LAST_TASK task[NR_TASKS-1]
struct run_q { //进程就绪队列
struct task_struct *data;
struct run_q *next;
};
struct run_q *head = nullptr, *end = nullptr, *r_temp;
#define N_PROCESS 5 //进程个数
#define MAX_RUNTIME 100 //最长运行时间
int process[N_PROCESS][2] = {
{0, 20},
{2, 6},
{4, 4},
{6, 5},
{8, 2}};//进程初始值
int totalExcuteTime = 0; //cpu总的运行时间
int runState[N_PROCESS][MAX_RUNTIME] = {0}; //进程运行状态的记录
void checkProcessCome(); //判断是否有进程到达，如果有则创建进程
void pause(); //0号进程的运行体
void schedule_f(); //FCFS调度程序
void schedule_r(); //RR调度程序
void schedule_s();
void schedule_b();
void switch_to(int pid); //进程切换
void init(); //基于优先级调度器的初始化
void run(int pid); //普通进程的运行体
void myfork(int pid); //进程创建
void mydelete(int pid); //进程清除
typedef void funtype();
funtype *schedule = nullptr;
int main(int argc, char **argv) {
int i, j;
int choice;
while (true) {
printf("please choice the schedule measure:\n");
printf("f : 先到先服务的调度策略\n");
printf("r : 轮循的调度策略\n");
printf("s : 最短剩余时间策略\n");
printf("b : 反馈策略\n");
printf("q : 退出\n");
printf("choice = ");
choice = getchar();
if (choice == '\n')
choice = getchar();
switch (choice) {
case 'f':
schedule = schedule_f;
break;
case 'r':
schedule = schedule_r;
break;
case 's':
schedule = schedule_s;
break;
case 'b':
schedule = schedule_b;
break;
case 'q':
return 0;
default : {
schedule = nullptr;
printf("please input the true symbol(b or f or s or or r or q)!\n\n");
continue;
}
}
printf("task id Start Service time\n");
for (i = 0; i < N_PROCESS; i++) {
printf("task %2d: %6d %6d\n", i + 1, process[i][0], process[i][1]);
totalExcuteTime += process[i][1];
}
//调度
init();
//打印进程调度情况
printf("Scheduling result\n");
printf("time : 0%*c%d\n", totalExcuteTime - 2, ' ', totalExcuteTime);
for (i = 0; i < N_PROCESS; i++) {
printf("task %2d: ", i + 1);
for (j = 0; j < totalExcuteTime; j++) {
if (runState[i][j] == 1) printf("#");
else printf(" ");
runState[i][j] = 0;
}
printf("\n");
}
while ((head != nullptr) && (head != end)) {
r_temp = head;
head = head->next;
free(r_temp);
}
if (head) {
free(head);
head = nullptr;
end = nullptr;
}
current = &init_task;
jiffies = 0;
totalExcuteTime = 0;
printf("\n");
}
return 0;
}
void schedule_f() {
int i, next, c;
struct task_struct **p;
c = 9999;
next = 0;
i = NR_TASKS;
p = &task[NR_TASKS];
while (--i) {
if (!*--p)
continue;
if ((*p)->state == TASK_RUNNING && (*p)->start_time < c)
c = (*p)->start_time, next = i;
}
switch_to(next);
}
void schedule_r() {
int next;
next = 0;
if (current->state != TASK_RUNNING) {
r_temp = head;
if (head == end) {
head = nullptr;
end = nullptr;
} else {
head = head->next;
end->next = head;
}
free(r_temp);
} else if (head) {
head = head->next;
end = end->next;
}
if (head) next = head->data->pid;
switch_to(next);
}
void schedule_s() {
int sub = 0, min_time = MAX_RUNTIME;
for (int i = 1; task[i]; i++) {
int remain_exe_time;
remain_exe_time = process[i - 1][1] - task[i]->excute_time;
if (remain_exe_time <= min_time && remain_exe_time != 0) {
sub = i;
min_time = remain_exe_time;
}
}
if (sub == 0) {
printf("No Process!");
}
switch_to(task[sub]->pid);
}
int last_mission = -1;
void schedule_b() {
if (last_mission != -1) {
if (task[last_mission]->state != TASK_ZOMBIE && task[last_mission]->flag != 0) {
task[last_mission]->flag--;
switch_to(last_mission);
return;
}
if (task[last_mission]->flag != 0) {
if (task[last_mission]->state == TASK_ZOMBIE) {
printf("CHECK");
}
}
}
float index;
int sum = 0, i, sub;
for (i = 1; task[i]; i++) {
sum += process[i - 1][1] - task[i]->excute_time;
}
index = static_cast<float>(sum) / static_cast<float>(i);
int next;
next = 0;
if (current->state != TASK_RUNNING) {
r_temp = head;
if (head == end) {
head = nullptr;
end = nullptr;
} else {
head = head->next;
end->next = head;
}
free(r_temp);
} else if (head) {
head = head->next;
end = end->next;
}
for (i = 1; task[i]; i++) {
if (task[i]->pid == head->data->pid){
sub = i;
break;
}
}
if (process[sub - 1][1] - head->data->excute_time > index) {
head->data->flag = 2;
} else {
head->data->flag = 1;
}
if (head) next = head->data->pid;
last_mission = sub;
head->data->flag--;
switch_to(next);
}
void switch_to(int pid) {
if (pid)
run(pid);
else
pause();
}
void myfork(int pid) {
struct timeval now{};
struct run_q *p;
task[pid] = (struct task_struct *) malloc(sizeof(struct task_struct));
task[pid]->state = TASK_UNINTERRUPTIBLE;
task[pid]->pid = pid;
gettimeofday(&now, nullptr);
srand(now.tv_usec);
task[pid]->priority = 2 + (int) (4.0f * rand() / (RAND_MAX + 1.0f));
task[pid]->counter = task[pid]->priority;
task[pid]->start_time = jiffies;
task[pid]->excute_time = 0;
task[pid]->state = TASK_RUNNING;
p = (struct run_q *) malloc(sizeof(struct run_q));
p->data = task[pid];
if (head == nullptr) {
head = end = p;
head->next = end;
end->next = head;
} else {
end->next = p;
end = p;
end->next = head;
}
}
void mydelete(int pid){
free(task[pid]);
}
void checkProcessCome() {
int i;
for (i = 0; i < N_PROCESS; i++) {
if (process[i][0] == jiffies)
myfork(i + 1);
}
}
void init() {
int i;
for (i = 1; i < NR_TASKS; i++) {
task[i] = nullptr;
}
checkProcessCome();
schedule();
}
void pause() {
current = task[0];
//printf("running task %d\n",pid);
//usleep(1000000);
jiffies++;
totalExcuteTime++;
checkProcessCome();
schedule();
}
void run(int pid) {
int i;
current = task[pid];
runState[pid - 1][jiffies] = 1;
//printf("running task %d\n",pid);
//usleep(1000000);
jiffies++;
task[pid]->counter--;
task[pid]->excute_time++;
//判断进程是否运行完，如果是则将进程杀死
if (task[pid]->excute_time == process[pid - 1][1]) {
task[pid]->state = TASK_ZOMBIE;
}
//判断所有进程是否都运行完，如果是则结束
if (jiffies >= totalExcuteTime) return;
checkProcessCome();
schedule();
}
如有错误请指正。
文章评论