一、實(shí)驗(yàn)?zāi)繕?biāo)
加深對操作系統(tǒng)CPU調(diào)度以及調(diào)度算法的理解
二、實(shí)驗(yàn)內(nèi)容
1.思路
1）
- 單處理器環(huán)境下，針對最短作業(yè)優(yōu)先算法(SJF)和優(yōu)先級調(diào)度算法(Priority)，分別模擬實(shí)現(xiàn)搶占調(diào)度和非搶占調(diào)度的調(diào)度程序
- 設(shè)計(jì)使用三個(gè)隊(duì)列，分別為就緒隊(duì)列(readyQueue)、運(yùn)行隊(duì)列(runningQueue)、等待隊(duì)列(waitingQueue)
- 進(jìn)程狀態(tài)三種，分別為就緒狀態(tài)：0、運(yùn)行狀態(tài)：1、等待狀態(tài)：2
- 輸入：task.txt 文件和指定調(diào)度算法
- task.txt 文件為需要調(diào)度的進(jìn)程集
- 非搶占 SJF: sjf
- 搶占 SJF: psjf
- 非搶占 Priority: pprio
- 搶占 Priority: prio
- 輸出：按照所指定的調(diào)度算法，顯示調(diào)度結(jié)果
- 比如：P2:2、P1:2、P3:1、P4:5
2）1數(shù)據(jù)結(jié)構(gòu)
本次實(shí)驗(yàn)的數(shù)據(jù)結(jié)構(gòu)參考了 pintos 中的線程調(diào)度：使? PCB 結(jié)構(gòu)體表示進(jìn)程、使?雙向鏈表管理進(jìn)程。
PCB 結(jié)構(gòu)體定義如下：
typedef struct PCB {
int pid; // pid
int time_release; // release time
int time_cpu; // total CPU execution time
int time_remaining; // remaining CPU execution tine
int priority; // priority
enum ProcessState state; // process state
struct PCB* prev; // previous process pointer
struct PCB* next; // next process pointer
} PCB;
為何適配該實(shí)驗(yàn)，雙向鏈表上實(shí)現(xiàn)了?些常?的操作函數(shù)。由于本實(shí)驗(yàn)中需要通過進(jìn)程的優(yōu)先級和剩余 CPU 時(shí)間進(jìn)?排序，所以還參考 pintos 實(shí)現(xiàn)了有序插?的操作。
1 /* Operations on list. */
2 List* list_create();
3 void list_delete(List* list);
4
5 /* Iteration operations */
6 ListElem* list_begin(List* list);
7 ListElem* list_next(ListElem* elem);
8 ListElem* list_end(List* list);
9
10 /* Removal operations. */
11 ListElem* list_remove(ListElem* elem);
12 ListElem* list_pop_front(List* list);
13
14 /* Insertion operations. */
15 void list_insert(ListElem* before, ListElem* elem);
16 void list_insert_ordered(List* list, ListElem* elem,
17 list_less_func* less_func);
18 void list_push_back(List* list, ListElem* elem);
19
20 /* Get list properties. */
21 size_t list_size(List* list);
22 int list_empty(List* list);
3）算法
本實(shí)驗(yàn)中?先計(jì)算出運(yùn)?完所有進(jìn)程所需要的 CPU 區(qū)間?度 T，然后使? for 循環(huán)，令 i 從0 遍歷到 T-1 來模擬實(shí)際 CPU 調(diào)度中定時(shí)器產(chǎn)?的時(shí)間?到時(shí)中斷：i 每增加 1，代表 CPU執(zhí)?了?個(gè)時(shí)間?，此時(shí)應(yīng)該重新進(jìn)?調(diào)度。
下?以最短作業(yè)優(yōu)先調(diào)度為例概述調(diào)度算法，優(yōu)先級調(diào)度算法與此類似，代碼也極其相似。
在?個(gè)新的時(shí)間?到來時(shí)，將 CPU 分配給哪?個(gè)進(jìn)程有兩個(gè)需要考慮的因素 — 進(jìn)程的到達(dá)時(shí)間與進(jìn)程的剩余 CPU 區(qū)間。假如當(dāng)前到來的是第 i 個(gè)時(shí)間?，只有到達(dá)時(shí)間（release time）?于等于 i 的進(jìn)程才有機(jī)會被分配 CPU；隨后我們需要在些進(jìn)程中選擇剩余 CPU 區(qū)間最短的作為執(zhí)?進(jìn)程。
由此得到的結(jié)論就是，我們需要先對進(jìn)程的到達(dá)時(shí)間作為第?優(yōu)先級、剩余 CPU 區(qū)間作為第?優(yōu)先級進(jìn)?排序。本實(shí)驗(yàn)采?的?法是在進(jìn)程創(chuàng)建的時(shí)候就將其按照上述兩個(gè)優(yōu)先級插?到ready queue 中，使 ready queue 成為?個(gè)優(yōu)先級隊(duì)列。在?搶占式調(diào)度中，?個(gè)進(jìn)程執(zhí)?完?需執(zhí)?其他操作；?在搶占式調(diào)度中，?個(gè)進(jìn)程在該時(shí)間?內(nèi)執(zhí)?完后，需要判斷其剩余 CPU 區(qū)間是否為 0，如果為 0，則需要將其重新按照上述兩個(gè)優(yōu)先級插?到隊(duì)列中。
同理，如果采?優(yōu)先級調(diào)度，上述的排列規(guī)則變?yōu)榈竭_(dá)時(shí)間使第?優(yōu)先級，?進(jìn)程優(yōu)先級是第?優(yōu)先級。
2.代碼
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
enum ProcessState {
PROCESS_READY,
PROCESS_RUNNING
};
typedef struct PCB {
int pid;
int time_release;
int time_cpu;
int time_remaining;
int priority;
enum ProcessState state;
struct PCB* prev;
struct PCB* next;
} PCB;
typedef PCB ListElem;
typedef struct List {
ListElem head;
ListElem tail;
} List;
/* Compares the value of two list elements A and B, given
auxiliary data AUX. Returns true if A is less than B, or
false if A is greater than or equal to B. */
typedef int list_less_func(const ListElem* a,
const ListElem* b);
PCB* process_running;
List* ready_queue;
List* terminated_list;
char file_name[] = "sched.txt";
FILE* file;
/* Operations on list. */
List* list_create();
void list_delete(List* list);
ListElem* list_begin(List* list);
ListElem* list_next(ListElem* elem);
ListElem* list_end(List* list);
ListElem* list_remove(ListElem* elem);
ListElem* list_pop_front(List* list);
void list_insert(ListElem* before, ListElem* elem);
void list_insert_ordered(List* list, ListElem* elem,
list_less_func* less_func);
void list_push_back(List* list, ListElem* elem);
size_t list_size(List* list);
int list_empty(List* list);
/* Operations on process. */
PCB* process_create(int pid, int time_release, int priority, int time_exec);
void process_sched_sjf(int cpu_time);
void process_sched_psjf(int cpu_time);
int process_cmp_sjf(const ListElem* a, const ListElem* b);
void process_sched_prio(int cpu_time);
void process_sched_pprio(int cpu_time);
int process_cmp_prio(const ListElem* a, const ListElem* b);
void process_print(int cnt);
void print_header(int cpu_time);
int get_total_cpu_time();
PCB* load_process_from_file();
int main() {
int cpu_time, mode;
PCB* process;
file = fopen(file_name, "r");
ready_queue = list_create();
terminated_list = list_create();
printf("Input schedule mode.\n1: sjf, 2: psjf, 3: prio, 4:pprio.\n");
scanf("%d", &mode);
switch (mode) {
case 1: {
while ((process = load_process_from_file()) != NULL) {
list_insert_ordered(ready_queue, process, process_cmp_sjf);
}
cpu_time = get_total_cpu_time();
printf("\n\n");
print_header(cpu_time);
process_sched_sjf(cpu_time);
printf("\n\n");
} break;
case 2: {
while ((process = load_process_from_file()) != NULL) {
list_insert_ordered(ready_queue, process, process_cmp_sjf);
}
cpu_time = get_total_cpu_time();
printf("\n\n");
print_header(cpu_time);
process_sched_psjf(cpu_time);
printf("\n\n");
} break;
case 3: {
while ((process = load_process_from_file()) != NULL) {
list_insert_ordered(ready_queue, process, process_cmp_prio);
}
cpu_time = get_total_cpu_time();
printf("\n\n");
print_header(cpu_time);
process_sched_prio(cpu_time);
printf("\n\n");
} break;
case 4: {
while ((process = load_process_from_file()) != NULL) {
list_insert_ordered(ready_queue, process, process_cmp_prio);
}
cpu_time = get_total_cpu_time();
printf("\n\n");
print_header(cpu_time);
process_sched_pprio(cpu_time);
printf("\n\n");
} break;
default:
break;
}
list_delete(ready_queue);
list_delete(terminated_list);
return 0;
}
List* list_create() {
List* list = (List*)malloc(sizeof(List));
if (!list) {
printf("list_create(): malloc failed.\n");
exit(1);
}
list->head.prev = NULL;
list->head.next = &list->tail;
list->tail.prev = &list->head;
list->tail.next = NULL;
return list;
}
void list_delete(List* list) {
ListElem* elem;
while (!list_empty(list)) {
elem = list_pop_front(list);
free(elem);
}
free(list);
}
ListElem* list_begin(List* list) {
return list->head.next;
}
ListElem* list_next(ListElem* elem) {
return elem->next;
}
ListElem* list_end(List* list) {
return &list->tail;
}
ListElem* list_remove(ListElem* elem) {
elem->prev->next = elem->next;
elem->next->prev = elem->prev;
return elem->next;
}
ListElem* list_pop_front(List* list) {
ListElem* front = list_begin(list);
list_remove(front);
return front;
}
void list_insert(ListElem* before, ListElem* elem) {
elem->prev = before->prev;
elem->next = before;
before->prev->next = elem;
before->prev = elem;
}
void list_push_back(List* list, ListElem* elem) {
list_insert(list_end(list), elem);
}
void list_insert_ordered(List* list, ListElem* elem,
list_less_func* less_func) {
ListElem* e;
for (e = list_begin(list); e != list_end(list); e = list_next(e))
if (less_func(elem, e))
break;
list_insert(e, elem);
}
size_t list_size(List* list) {
ListElem* elem;
size_t cnt = 0;
for (elem = list_begin(list); elem != list_end(list); elem = list_next(elem))
cnt++;
return cnt;
}
int list_empty(List* list) {
return (list_begin(list) == list_end(list));
}
PCB* process_create(int pid, int time_release, int priority, int time_exec) {
PCB* process = (PCB*)malloc(sizeof(PCB));
if (!process) {
printf("process_create(): malloc failed.\n");
exit(1);
}
process->pid = pid;
process->time_release = time_release;
process->time_cpu = time_exec;
process->time_remaining = time_exec;
process->priority = priority;
process->state = PROCESS_READY;
return process;
}
void process_sched_sjf(int cpu_time) {
int i = 0;
PCB* next;
for (; i < cpu_time; i++) {
process_running = list_begin(ready_queue);
for (next = list_next(process_running); next != list_end(ready_queue); next = list_next(next)) {
if (next->time_release > i)
break;
if (next->time_remaining < process_running->time_remaining)
process_running = next;
}
i += process_running->time_remaining - 1;
list_remove(process_running);
list_push_back(terminated_list, process_running);
process_print(process_running->time_remaining);
}
}
void process_sched_psjf(int cpu_time) {
int i = 0;
PCB* next;
for (; i < cpu_time; ++i) {
process_running = list_begin(ready_queue);
for (next = list_next(process_running); next != list_end(ready_queue); next = list_next(next)) {
if (next->time_release > i)
break;
if (next->time_remaining < process_running->time_remaining)
process_running = next;
}
process_running->time_remaining--;
process_print(1);
if (process_running->time_remaining > 0) {
list_remove(process_running);
list_insert_ordered(ready_queue, process_running, process_cmp_sjf);
} else {
list_remove(process_running);
list_push_back(terminated_list, process_running);
}
}
}
int process_cmp_sjf(const ListElem* a, const ListElem* b) {
if (a->time_release != b->time_release)
return (a->time_release < b->time_release);
else
return (a->time_remaining < b->time_remaining);
}
void process_sched_prio(int cpu_time) {
int i = 0;
PCB* next;
for (; i < cpu_time; i++) {
process_running = list_begin(ready_queue);
for (next = list_next(process_running); next != list_end(ready_queue); next = list_next(next)) {
if (next->time_release > i)
break;
if (next->priority < process_running->priority)
process_running = next;
}
i += process_running->time_remaining - 1;
list_remove(process_running);
list_push_back(terminated_list, process_running);
process_print(process_running->time_remaining);
}
}
void process_sched_pprio(int cpu_time) {
int i = 0;
PCB* next;
for (; i < cpu_time; ++i) {
process_running = list_begin(ready_queue);
for (next = list_next(process_running); next != list_end(ready_queue); next = list_next(next)) {
if (next->time_release > i)
break;
if (next->priority < process_running->priority)
process_running = next;
}
process_running->time_remaining--;
process_print(1);
if (process_running->time_remaining > 0) {
list_remove(process_running);
list_insert_ordered(ready_queue, process_running, process_cmp_prio);
} else {
list_remove(process_running);
list_push_back(terminated_list, process_running);
}
}
}
int process_cmp_prio(const ListElem* a, const ListElem* b) {
if (a->time_release != b->time_release)
return (a->time_release < b->time_release);
else
return (a->priority < b->priority);
}
void process_print(int cnt) {
int i = 0;
for (; i < cnt; ++i)
printf(" P%d ", process_running->pid);
}
void print_header(int cpu_time) {
int i = 0;
for (; i < cpu_time; ++i)
printf("|_____");
printf("|\n");
for (i = 0; i <= cpu_time; ++i)
printf("%-6d", i);
printf("\n");
}
int get_total_cpu_time() {
int total_cpu_time = 0;
ListElem* elem = list_begin(ready_queue);
for (; elem != list_end(ready_queue); elem = list_next(elem))
total_cpu_time += elem->time_remaining;
return total_cpu_time;
}
PCB* load_process_from_file() {
int pid, time_release, time_cpu, priority;
PCB* process = NULL;
if (fscanf(file, "%d%d%d%d", &pid, &time_release, &priority, &time_cpu) != EOF) {
process = process_create(pid, time_release, priority, time_cpu);
}
return process;
}
3.過程及運(yùn)行結(jié)果展示
從文本文件中輸入信息（格式：進(jìn)程ID， 到達(dá)時(shí)間， 優(yōu)先級， 運(yùn)行時(shí)間）
非搶占式最短作業(yè)優(yōu)先調(diào)度
搶占式最短作業(yè)優(yōu)先調(diào)度
非搶占式優(yōu)先級調(diào)度
搶占式優(yōu)先級調(diào)度
文章來源：http://www.zghlxwxcb.cn/news/detail-456530.html
三、實(shí)驗(yàn)結(jié)論
通過本實(shí)驗(yàn)對于調(diào)度算法有了更加深刻的理解。
-最短作業(yè)優(yōu)先調(diào)度：
搶占式：當(dāng)新進(jìn)來的進(jìn)程的CPU區(qū)間比當(dāng)前執(zhí)行的進(jìn)程所剩的CPU區(qū)間短，則搶占。
非搶占：為下一個(gè)最短優(yōu)先，因?yàn)樵诰途w隊(duì)列中選擇最短CPU區(qū)間的進(jìn)程放在隊(duì)頭。
-優(yōu)先級調(diào)度算法：SJF是特殊的優(yōu)先級調(diào)度算法，以CPU區(qū)間長度的倒數(shù)為優(yōu)先級。
搶占式為如果進(jìn)來的進(jìn)程優(yōu)先級高于運(yùn)行的進(jìn)程，則替換。
非搶占式只是在就緒隊(duì)列中按優(yōu)先級排隊(duì)。
缺點(diǎn)：無線阻塞或饑餓。前者為一個(gè)優(yōu)先級高且運(yùn)行時(shí)間長的進(jìn)程一直阻塞，后者為優(yōu)先級低的進(jìn)程永遠(yuǎn)都得不到執(zhí)行。文章來源地址http://www.zghlxwxcb.cn/news/detail-456530.html
到了這里，關(guān)于【操作系統(tǒng)實(shí)驗(yàn)6】CPU調(diào)度程序模擬實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
