操作系統實驗報告16

實驗內容

• 實驗內容：CPU 調度。
  • 討論課件 Lecture19-20 中 CPU 調度算法的例子，嘗試基于 POSIX API 設計一個簡單調度器（不考慮資源競爭問題）：
    • 創建一些 Pthread 線程任務，建立一個管理鏈隊列，結點內容起碼包括到達時間、WCT、優先級、調度狀態（運行、就緒、阻塞）等調度參數；
    • 每個任務有一個調度信號量，任務啟動后在其調度信號量上執行 wait；
    • 調度器按照調度策略對處于運行態的任務（如果有的話）的調度信號量執行 wait，并選取適當任務的調度信號量執行 signal；
    • 實現簡單調度策略：FCFS、SJF、Priority。分別計算任務平均等待時間。
  • 拓展問題1：設計若干資源信號量模擬資源競爭情況；增加時間片參數實現 RR 調度；驗證優先級反轉；建立多個鏈隊列實現多級反饋調度。
  • 拓展問題2：設計一個搶占式優先策略實時調度器，測試在一個給定的工作負載下優先級反轉的情況。

實驗環境

• 架構：Intel x86_64 (虛擬機)
• 操作系統：Ubuntu 20.04
• 匯編器：gas (GNU Assembler) in AT&T mode
• 編譯器：gcc

技術日志

實驗內容原理

• CPU調度程序
  • 每當CPU空閑時，操作系統就應從就緒隊列中選擇一個進程來執行。進程執行選擇短期調度程序或CPU調度程序。調度程序從內存中選擇一個能夠執行的進程，并為其分配CPU。
  • 注意,就緒隊列不必是先進先出隊列。就緒隊列的實現可以是FIFO隊列、優先隊列、樹或簡單的無序鏈表等。然而，在概念上，就緒隊列內的所有進程都要排隊以便等待在CPU上運行。隊列內的記錄通常為進程控制塊（PCB）。
• 搶占調度
  • 需進行CPU調度的情況可分為以下四種：
    • 當一個進程從運行狀態切換到等待狀態時（例如，I/O請求，或wait()調用以便等待一個子進程的終止）。
    • 當一個進程從運行狀態切換到就緒狀態時（例如，當出現中斷時）。
    • 當一個進程從等待狀態切換到就緒狀態時（例如，I/O完成）。
    • 當一個進程終止時。
  • 對于第1種和第4種情況，除了調度沒有選擇。一個新進程（如果就緒隊列有一個進程存在）必須被選擇執行。不過，對于第2種和第3種情況，還是有選擇的。
  • 如果調度只能發生在第1種和第4種情況下，則調度方案稱為非搶占的或協作的；否則，調度方案稱為搶占的。
    • 在非搶占調度下，一旦某個進程分配到CPU，該進程就會一直使用CPU，直到它終止或切換到等待狀態。
  • 當多個進程共享數據時，搶占調度可能導致競爭情況。
• 調度算法
  • 先到先服務（FCFS）調度
    • 是非搶占式算法
    • 采用這種方案，先請求CPU的進程首先分配到CPU。
    • FCFS策略可以通過FIFO隊列容易地實現。當一個進程進入就緒隊列時，它的PCB會被鏈接到隊列尾部。當CPU空閑時，它會分配給位于隊列頭部的進程，并且這個運行進程從隊列中移去。
    • FCFS調度代碼編寫簡單并且理解容易。缺點是，平均等待時間往往很長。
    • 護航效果：所有其他進程都等待一個大進程釋放CPU。與讓較短進程先進行相比，這會導致CPU和設備的使用率降低。
  • 最短作業優先（SJF）調度
    • 有非搶占式也有搶占式算法
    • 這個算法將每個進程與其下次CPU執行的長度關聯起來。當CPU變為空閑時，它會被賦給具有最短CPU執行的進程。如果兩個進程具有同樣長度的CPU執行，那么可以由FCFS來處理。
    • 注意，一個更為恰當的表示是最短下次CPU執行算法，這是因為調度取決于進程的下次CPU執行的長度，而不是其總的長度。
    • 當一個新進程到達就緒隊列而以前進程正在執行時，就需要選擇使用非搶占式算法還是搶占式算法了。新進程的下次CPU執行，與當前運行進程的尚未完成的CPU執行相比，可能還要小。
      • 搶占SJF算法會搶占當前運行進程。
      • 非搶占SJF算法會允許當前運行進程以先完成CPU執行。
    • 搶占SJF調度有時稱為最短剩余時間優先調度
  • 優先級調度（Priority）
    • 有非搶占式也有搶占式算法
    • 每個進程都有優先級與其關聯，而具有最高優先級的進程會分配到CPU。具有相同優先級的進程按FCFS順序調度。
    • 當一個進程到達就緒隊列時，比較它的優先級與當前運行進程的優先級。如果新到達進程的優先級高于當前運行進程的優先級，那么搶占優先級調度算法就會搶占CPU。非搶占式優先級調度算法只是將新的進程加到就緒隊列的頭部。
    • 優先級調度算法的一個主要問題是無窮阻塞或饑餓。就緒運行但是等待CPU的進程可以認為是阻塞的。優先級調度算法可讓某個低優先級進程無窮等待CPU。
    • 低優先級進程的無窮等待問題的解決方案之一是老化。老化逐漸增加在系統中等待很長時間的進程的優先級。

設計報告

調度器設計圖

代碼設計

// scheduler.c文件 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #include <sys/time.h> #include <pthread.h> #include <semaphore.h> #include <signal.h>#define STATUS_RUNNING 1 // 運行調度狀態 #define STATUS_READY 2 // 就緒調度狀態 #define STATUS_WAITING 3 // 阻塞調度狀態#define POLICY_FCFS 1 // 先到先服務調度策略 #define POLICY_SJF_PEM 2 // 搶占式最短作業優先調度策略 #define POLICY_SJF_NOT_PEM 3 // 非搶占式最短作業優先調度策略 #define POLICY_PRIORITY_PEM 4 // 搶占式優先級調度策略 #define POLICY_PRIORITY_NOT_PEM 5 // 非搶占式優先級調度策略#define MAX_TASK_NUM 100 // 最大任務個數typedef struct node {int arrival_time; // 到達時間int WCT; // 最壞預期執行時間int priority; // 優先級int schedule_status; // 調度狀態pthread_t ptid; // 線程號sem_t wait_sem; // 任務啟動時的調度等待信號量struct node *next; // 指向下一個結點的指針 } Tasknode; // 管理鏈隊列結點結構typedef struct {Tasknode *head; // 管理鏈隊列表頭pthread_t sched_ptid; // 調度器線程的線程號pthread_mutex_t sched_mutex; // 調度器互斥鎖int schedule_policy; // 調度策略int finished_task; // 完成任務的個數 } Scheduler; // 調度器結構Scheduler sched; // 調度器 sigset_t zeromask; // 阻塞線程函數sigsuspend()所用參數 long wait_sum_time = 0; // 單個線程等待總時間long begin_us, run_us; // 總計時器部分，測試用 struct timeval t_time;// 初始化調度器 void init_scheduler(int task_num); // 創建任務管理信息結點 Tasknode* creat_thread_node(int arrival_time, int WCT, int priority);// 每個線程執行的任務 void *task_runner(void *arg); // 調度器運行線程 void *schedule_runner(void *arg);// 將任務信息結點按照調度策略放入管理鏈隊列 void fcfs(Tasknode *new_node); void sjf_pem(Tasknode *new_node); void sjf_not_pem(Tasknode *new_node); void priority_pem(Tasknode *new_node); void priority_not_pem(Tasknode *new_node);// 向管理鏈隊列添加任務 void add_task(Tasknode *node, int sched_policy); // 從管理鏈隊列刪除任務 void delete_task();// 發送信號阻塞線程，直到接收到一個新的信號 void thread_wait_sighand(int signo); // 發送信號使阻塞線程繼續運行 void thread_cont_sighand(int signo); // 調度器線程接收信號后調度器選擇一個任務，即表頭任務運行 void sched_run_sighand(int signo);// 打印任務信息列表，測試用 void print_tasklist(int *arrival_time, int *WCT, int *priority, int task_num); // 計算任務平均等待時間 double cal_aver_wait_time(int *arrival_time, int *WCT, int *priority, int task_num, int sched_policy);// 調度器運行線程 void *schedule_runner(void *arg) {int task_num = *(int *)arg;// 當完成任務個數等于總任務個數時，調度器線程退出while (sched.finished_task != 5 * task_num);pthread_exit(0); }// 創建任務管理信息結點 Tasknode* creat_thread_node(int arrival_time, int WCT, int priority) {Tasknode *new_node = (Tasknode *)malloc(sizeof(Tasknode));// 設置線程的到達時間，最長預期執行時間，優先級new_node->arrival_time = arrival_time;new_node->WCT = WCT;new_node->priority = priority;new_node->next = NULL;// 初始化線程的調度等待信號量為0int ret = sem_init(&new_node->wait_sem, 1, 0);if (ret == -1) {perror("creat_thread_node(): sem_init-wait_sem");exit(1);}return new_node; }// 初始化調度器 void init_scheduler(int task_num) {// 管理鏈隊列的表頭為空sched.head = NULL;// 調度策略默認為先到先服務sched.schedule_policy = POLICY_FCFS;// 已經完成任務個數為0sched.finished_task = 0;// 初始化調度器互斥鎖pthread_mutex_init(&sched.sched_mutex, NULL);// 創建調度器運行線程int ret = pthread_create(&sched.sched_ptid, NULL, &schedule_runner, &task_num);if (ret != 0) {fprintf(stderr, "init_scheduler(): pthread_create error: %s\n", strerror(ret));exit(1);} }// 將任務信息結點按照先到先服務策略放入管理鏈隊列 void fcfs(Tasknode *new_node) {// 如果管理鏈隊列的表頭為空，那么直接插入結點if (sched.head == NULL) {sched.head = new_node;return;}// 找到管理鏈隊列的表尾，插入結點Tasknode *cur_node = sched.head;while (cur_node->next != NULL) {cur_node = cur_node->next;}cur_node->next = new_node; }// 將任務信息結點按照搶占式最短作業優先策略放入管理鏈隊列 void sjf_pem(Tasknode *new_node) {// 如果管理鏈隊列的表頭為空，那么直接插入結點if (sched.head == NULL) {sched.head = new_node;return;}// 如果結點的WCT小于表頭結點的WCT，那么直接在表頭結點之前插入結點else if (new_node->WCT < sched.head->WCT) {new_node->next = sched.head;sched.head = new_node;return;}Tasknode *cur_node = sched.head;Tasknode *pre_node = NULL;while (cur_node != NULL && new_node->WCT >= cur_node->WCT) {pre_node = cur_node;cur_node = cur_node->next;}pre_node->next = new_node;new_node->next = cur_node; }// 將任務信息結點按照非搶占式最短作業優先策略放入管理鏈隊列 void sjf_not_pem(Tasknode *new_node) {// 如果管理鏈隊列的表頭為空，那么直接插入結點if (sched.head == NULL) {sched.head = new_node;return;}// 尋找管理鏈隊列中前一個結點的WCT小于等于結點，后一個結點的WCT大于結點的位置插入結點，如果沒有那么就在表尾插入結點Tasknode *cur_node = sched.head->next;Tasknode *pre_node = sched.head;while (cur_node != NULL && new_node->WCT >= cur_node->WCT) {pre_node = cur_node;cur_node = cur_node->next;}pre_node->next = new_node;new_node->next = cur_node; }// 將任務信息結點按照搶占式優先級策略放入管理鏈隊列 void priority_pem(Tasknode *new_node) {// 如果管理鏈隊列的表頭為空，那么直接插入結點if (sched.head == NULL) {sched.head = new_node;return;}// 如果結點的優先級大于表頭結點的優先級，那么直接在表頭結點之前插入結點else if (new_node->priority > sched.head->priority) {new_node->next = sched.head;sched.head = new_node;return;}// 尋找管理鏈隊列中前一個結點的WCT小于等于結點，后一個結點的WCT大于結點的位置插入結點，如果沒有那么就在表尾插入結點Tasknode *cur_node = sched.head;Tasknode *pre_node = NULL;while (cur_node != NULL && new_node->priority <= cur_node->priority) {pre_node = cur_node;cur_node = cur_node->next;}pre_node->next = new_node;new_node->next = cur_node; }// 將任務信息結點按照非搶占式優先級策略放入管理鏈隊列 void priority_not_pem(Tasknode *new_node) {// 如果管理鏈隊列的表頭為空，那么直接插入結點if (sched.head == NULL) {sched.head = new_node;return;}// 尋找管理鏈隊列中前一個結點的優先級大于等于結點，后一個結點的優先級小于結點的位置插入結點，如果沒有那么就在表尾插入結點Tasknode *cur_node = sched.head->next;Tasknode *pre_node = sched.head;while (cur_node != NULL && new_node->priority <= cur_node->priority) {pre_node = cur_node;cur_node = cur_node->next;}pre_node->next = new_node;new_node->next = cur_node; }// 向管理鏈隊列添加任務 void add_task(Tasknode *node, int sched_policy) {// 獲取調度器的互斥鎖，防止其它線程更改調度器pthread_mutex_lock(&sched.sched_mutex);// 如果有任務正在運行，那么先阻塞這個任務，將這個任務的調度狀態改為就緒態if (sched.head != NULL) {pthread_kill(sched.head->ptid, SIGUSR1);sched.head->schedule_status = STATUS_READY;}// 添加的任務信息結點的調度狀態為阻塞態node->schedule_status = STATUS_WAITING;// 根據調度策略，向管理鏈隊列中插入任務信息結點switch (sched_policy) {case POLICY_FCFS :fcfs(node);break;case POLICY_SJF_PEM:sjf_pem(node);break;case POLICY_SJF_NOT_PEM:sjf_not_pem(node);break;case POLICY_PRIORITY_PEM:priority_pem(node);break;case POLICY_PRIORITY_NOT_PEM:priority_not_pem(node);break;}sleep(0);// 向調度器線程發送信號，選取適當的任務執行pthread_kill(sched.sched_ptid, SIGUSR2);// 釋放調度器的互斥鎖pthread_mutex_unlock(&sched.sched_mutex); }// 從管理鏈隊列刪除任務 void delete_task() {// 獲取調度器的互斥鎖，防止其它線程更改調度器pthread_mutex_lock(&sched.sched_mutex);// 運行完了的任務結點是管理鏈隊列的頭結點，釋放其資源Tasknode *temp = sched.head;sched.head = sched.head->next;sem_destroy(&temp->wait_sem);free(temp);temp = NULL;// 如果管理鏈隊列中還有任務，那么繼續運行if (sched.head != NULL) {pthread_kill(sched.head->ptid, SIGCONT);}// 釋放調度器的互斥鎖pthread_mutex_unlock(&sched.sched_mutex); }// 每個線程執行的任務 void *task_runner(void *arg) {int ret;// 計時器部分long start_us, end_us;struct timeval t;// 獲取每個線程的任務信息結點Tasknode *task_node = (Tasknode *)arg;struct timespec req, rem;// 設置這個任務信息結點的線程號task_node->ptid = pthread_self();// 設置線程運行時間為任務信息結點中的最長預期執行時間req.tv_sec = task_node->WCT;req.tv_nsec = 0;// 線程休眠任務信息結點中的到達時間后再加入管理鏈隊列，模擬到達時間sleep(task_node->arrival_time);// 獲取任務到達時間gettimeofday(&t, 0);start_us = (long)(t.tv_sec * 1000 * 1000) + t.tv_usec;add_task(task_node, sched.schedule_policy);// 獲取任務開始時間gettimeofday(&t_time, 0);run_us = (long)(t_time.tv_sec * 1000 * 1000) + t_time.tv_usec;// 打印這個執行任務的線程的開始任務時間點，測試用printf("Task ptid = %ld starts at Time: %lf sec\n", pthread_self(), (double)(run_us - begin_us) / 1000000.0);// 線程先阻塞，等待調度器調度sem_wait(&task_node->wait_sem);// 線程休眠時間模擬執行時間，如果有信號中斷，ret返回-1，剩余時間存儲rem中ret = nanosleep(&req, &rem);// 返回中斷后繼續休眠剩余時間模擬完整執行時間while (ret < 0) {req = rem;ret = nanosleep(&req, &rem);}// 獲取結束時間gettimeofday(&t, 0);end_us = (long)(t.tv_sec * 1000 * 1000) + t.tv_usec;// 打印任務結束時間gettimeofday(&t_time, 0);run_us = (long)(t_time.tv_sec * 1000 * 1000) + t_time.tv_usec;// 打印這個執行任務的線程的結束任務時間點，測試用printf("Task ptid = %ld ends at Time: %lf sec\n", pthread_self(), (double)(run_us - begin_us) / 1000000.0);// 等待時間為實際運行時間減去預期執行時間wait_sum_time += end_us - start_us - task_node->WCT * 1000 * 1000;// 執行完后從管理鏈隊列中刪除任務結點delete_task();// 調度器已完成的任務數加一sched.finished_task++;pthread_exit(0); }// 發送信號阻塞線程，直到接收到一個新的信號 void thread_wait_sighand(int signo) {// 獲取當前時間gettimeofday(&t_time, 0);run_us = (long)(t_time.tv_sec * 1000 * 1000) + t_time.tv_usec;// 打印這個執行任務的線程的阻塞時間點，測試用printf("Task ptid = %ld stops at Time: %lf sec\n", pthread_self(), (double)(run_us - begin_us) / 1000000.0);sigsuspend(&zeromask); }// 發送信號使阻塞線程繼續運行 void thread_cont_sighand(int signo) {// 獲取當前時間gettimeofday(&t_time, 0);run_us = (long)(t_time.tv_sec * 1000 * 1000) + t_time.tv_usec;// 打印這個執行任務的線程的阻塞之后繼續運行時間點，測試用printf("Task ptid = %ld continues at Time: %lf sec\n", pthread_self(), (double)(run_us - begin_us) / 1000000.0); }// 調度器線程接收信號后調度器選擇一個任務，即表頭任務運行 void sched_run_sighand(int signo) {// 如果這個任務處于阻塞態，那么先轉為就緒態，再轉為運行態，用sem_post()函數開始運行任務if (sched.head->schedule_status == STATUS_WAITING) {sched.head->schedule_status = STATUS_READY;sched.head->schedule_status = STATUS_RUNNING;sem_post(&sched.head->wait_sem);// 獲取任務執行時間點 gettimeofday(&t_time, 0);run_us = (long)(t_time.tv_sec * 1000 * 1000) + t_time.tv_usec;// 打印這個執行任務的線程的運行任務時間點，測試用printf("Task ptid = %ld starts to run at Time: %lf sec\n", sched.head->ptid, (double)(run_us - begin_us) / 1000000.0);}// 如果這個任務處于就緒態，那么轉為運行態，發送信號使其繼續運行else if (sched.head->schedule_status == STATUS_READY) {sched.head->schedule_status = STATUS_RUNNING;pthread_kill(sched.head->ptid, SIGCONT);} }// 打印任務信息列表，測試用 void print_tasklist(int *arrival_time, int *WCT, int *priority, int task_num) {printf("Task list:\n");printf("------------------------------\n");printf("|Id|Arrival time|WCT|Priority|\n");printf("------------------------------\n");for (int i = 0; i < task_num; ++i) {printf("|%2d| %3d |%3d| %2d |\n", i + 1, arrival_time[i], WCT[i], priority[i]);}printf("------------------------------\n");printf("\n"); }// 計算任務平均等待時間 double cal_aver_wait_time(int *arrival_time, int *WCT, int *priority, int task_num, int sched_policy) {int ret;pthread_t ptid[MAX_TASK_NUM];double aver_wait_time;printf("\n----------------------------------------------------------\n");printf("schedule policy: ");// 打印調度策略switch (sched_policy) {case POLICY_FCFS :printf("FCFS\n\n");break;case POLICY_SJF_PEM:printf("SJF(preemptive)\n\n");break;case POLICY_SJF_NOT_PEM:printf("SJF(not preemptive)\n\n");break;case POLICY_PRIORITY_PEM:printf("Priority(preemptive)\n\n");break;case POLICY_PRIORITY_NOT_PEM:printf("Priority(not preemptive)\n\n");break;}// 打印任務列表print_tasklist(arrival_time, WCT, priority, task_num);// 設置調度策略sched.schedule_policy = sched_policy;wait_sum_time = 0;// 獲取計時開始時間gettimeofday(&t_time, 0);begin_us = (long)(t_time.tv_sec * 1000 * 1000) + t_time.tv_usec;// 根據信息創建任務信息結點和相應的線程for (int i = 0; i < task_num; i++) {Tasknode *new_node = creat_thread_node(arrival_time[i], WCT[i], priority[i]);ret = pthread_create(&ptid[i], NULL, &task_runner, (void *)new_node);if(ret != 0) {fprintf(stderr, "pthread_create error: %s\n", strerror(ret));exit(1);}printf("Task%d ptid:%ld\n", i + 1, ptid[i]);}printf("\n");// 主線程等待所有子線程運行結束后再繼續執行for (int i = 0; i < task_num; i++) {ret = pthread_join(ptid[i], NULL);if(ret != 0) {fprintf(stderr, "pthread_join error: %s\n", strerror(ret));exit(1);}}// 計算任務平均等待時間printf("\nThe waiting time = %lf sec\n", (double)wait_sum_time / 1000000.0);aver_wait_time = (double)wait_sum_time / 1000000.0 / (double)task_num;printf("The average of waiting time = %lf sec\n", aver_wait_time);printf("----------------------------------------------------------\n");return aver_wait_time; }int main() {int arrival_time[MAX_TASK_NUM];int WCT[MAX_TASK_NUM];int priority[MAX_TASK_NUM];int task_num;printf("Please input the number of tasks: ");scanf("%d", &task_num);// 設置不同捕捉信號的信號處理函數struct sigaction act1, act2, act3;memset(&act1, 0, sizeof(act1));memset(&act2, 0, sizeof(act2));memset(&act3, 0, sizeof(act3));sigemptyset(&act1.sa_mask);sigemptyset(&act2.sa_mask);sigemptyset(&act3.sa_mask);act1.sa_flags = 0;act2.sa_flags = 0;act3.sa_flags = 0;act1.sa_handler = thread_wait_sighand;act2.sa_handler = thread_cont_sighand;act3.sa_handler = sched_run_sighand;// 設置捕捉到SIGUSR1后信號處理函數為使線程阻塞sigaction(SIGUSR1, &act1, NULL);// 設置捕捉到SIGCONT后信號處理函數為使阻塞的線程繼續sigaction(SIGCONT, &act2, NULL);// 設置捕捉到SIGUSR2后信號處理函數為使調度器選擇一個任務運行sigaction(SIGUSR2, &act3, NULL);// 初始化調度器init_scheduler(task_num);// 輸入每個任務的到達時間，最長預期運行時間，優先級等for (int i = 0; i < task_num; i++) {printf("Please input task%d's arrival_time, WCT, priority:\n", i + 1);scanf("%d %d %d", &arrival_time[i], &WCT[i], &priority[i]);}double aver_wait_time_fcfs = cal_aver_wait_time(arrival_time, WCT, priority, task_num, POLICY_FCFS);double aver_wait_time_sjf_pem = cal_aver_wait_time(arrival_time, WCT, priority, task_num, POLICY_SJF_PEM);double aver_wait_time_sjf_not_pem = cal_aver_wait_time(arrival_time, WCT, priority, task_num, POLICY_SJF_NOT_PEM);double aver_wait_time_priority_pem = cal_aver_wait_time(arrival_time, WCT, priority, task_num, POLICY_PRIORITY_PEM);double aver_wait_time_priority_not_pem = cal_aver_wait_time(arrival_time, WCT, priority, task_num, POLICY_PRIORITY_NOT_PEM);// 打印不同調度策略平均等待時間列表printf("\nAverage waiting time list(sec):\n");printf("-----------------------------------------------\n");printf("| Policy |Average waiting time|\n");printf("-----------------------------------------------\n");printf("| FCFS | %10lf |\n", aver_wait_time_fcfs);printf("| SJF(preemptive) | %10lf |\n", aver_wait_time_sjf_pem);printf("| SJF(not preemptive) | %10lf |\n", aver_wait_time_sjf_not_pem);printf("| Priority(preemptive) | %10lf |\n", aver_wait_time_priority_pem);printf("|Priority(not preemptive)| %10lf |\n", aver_wait_time_priority_not_pem);printf("-----------------------------------------------\n"); }

執行命令：

gcc scheduler.c -pthread ./a.out

驗證各個調度算法的正確性

測試用例1：

3 0 5 1 2 4 3 4 3 2 TaskArrival TimeWCTPriority

1	0	5	1
2	2	4	3
3	4	3	2

先到先服務調度策略：

可以看到，任務1在0s時開始執行；
在2s時任務2到達，運行著的任務1先阻塞，加入任務2后調度器根據先到先服務策略繼續選擇任務1執行，任務1在2s時繼續執行，任務2阻塞；
在4s時任務3到達，運行著的任務1先阻塞，加入任務3后調度器根據先到先服務策略繼續選擇任務1執行，任務1在4s時繼續執行，任務3阻塞；
在5s時任務1結束，調度器根據先到先服務策略選擇任務2執行，任務2在5s繼續執行；
在9s時任務2結束，調度器根據先到先服務策略選擇任務3執行，任務2在9s繼續執行；
在12s時任務3結束，任務全部完成。

過程符合先到先服務的調度策略。

甘特圖：

計算等待時間為 (0 - 0) + (5 - 2) + (9 - 4) = 8
計算平均等待時間為 8 / 3 = 2.67s
計算也正確。

搶占式最短作業優先調度策略：

可以看到，任務1在0s時開始執行；
在2s時任務2到達，運行著的任務1先阻塞，加入任務2后，由于任務2的WCT比任務1小，所以調度器根據搶占式最短作業優先調度策略，選擇任務2執行，任務2在2s時開始執行，任務1阻塞；
在4s時任務3到達，運行著的任務2先阻塞，加入任務3后，由于任務3的WCT比任務2小，所以調度器根據搶占式最短作業優先調度策略選擇任務3執行，任務3在4s時開始執行，任務2阻塞；
在7s時任務3結束，調度器根據搶占式最短作業優先調度策略選擇任務2執行，任務2在7s繼續執行；
在9s時任務2結束，調度器根據搶占式最短作業優先調度策略選擇任務1執行，任務1在9s繼續執行；
在12s時任務3結束，任務全部完成。

過程符合搶占式最短作業優先的調度策略。

甘特圖：

計算等待時間為 (9 - 2) + (7 - 4) + (4 - 4) = 10
計算平均等待時間為 10 / 3 = 3.33s
計算也正確。

非搶占式最短作業優先調度策略：

可以看到，任務1在0s時開始執行；
在2s時任務2到達，運行著的任務1先阻塞，加入任務2后，雖然任務2的WCT比任務1小，但是調度器根據非搶占式最短作業優先調度策略，繼續選擇任務1執行，任務1在2s時繼續執行，任務2阻塞；
在4s時任務3到達，運行著的任務1先阻塞，加入任務3后，雖然任務3的WCT比任務1小，但是調度器根據非搶占式最短作業優先調度策略繼續選擇任務1執行，任務1在4s時繼續執行，任務3阻塞；
在5s時任務1結束，調度器根據非搶占式最短作業優先調度策略選擇WCT更小的任務3執行，任務3在5s繼續執行；
在8s時任務3結束，調度器根據非搶占式最短作業優先調度策略選擇任務2執行，任務2在8s繼續執行；
在12s時任務2結束，任務全部完成。

過程符合非搶占式最短作業優先的調度策略。

甘特圖：

計算等待時間為 (0 - 0) + (8 - 2) + (5 - 4) = 7
計算平均等待時間為 7 / 3 = 2.33s
計算也正確。

搶占式優先級調度策略：

可以看到，任務1在0s時開始執行；
在2s時任務2到達，運行著的任務1先阻塞，加入任務2后，由于任務2的優先級比任務1大，所以調度器根據搶占式優先級調度策略，選擇任務2執行，任務2在2s時開始執行，任務1阻塞；
在4s時任務3到達，運行著的任務2先阻塞，加入任務3后，由于任務3的優先級比任務2小，所以調度器根據搶占式優先級調度策略繼續選擇任務2執行，任務2在4s時繼續執行，任務3阻塞；
在6s時任務2結束，調度器根據搶占式優先級調度策略選擇優先級更大的任務3執行，任務3在6s繼續執行；
在9s時任務3結束，調度器根據搶占式優先級調度策略選擇任務1執行，任務1在9s繼續執行；
在12s時任務1結束，任務全部完成。

過程符合搶占式優先級的調度策略。

甘特圖：

計算等待時間為 (9 - 2) + (2 - 2) + (6 - 4) = 9
計算平均等待時間為 9 / 3 = 3s
計算也正確。

非搶占式優先級調度策略：

可以看到，任務1在0s時開始執行；
在2s時任務2到達，運行著的任務1先阻塞，加入任務2后，雖然任務2的優先級比任務1大，但是調度器根據非搶占式優先級調度策略，繼續選擇任務1執行，任務1在2s時繼續執行，任務2阻塞；
在4s時任務3到達，運行著的任務1先阻塞，加入任務3后，雖然任務3的優先級比任務1大，但是調度器根據非搶占式優先級調度策略繼續選擇任務1執行，任務1在4s時繼續執行，任務3阻塞；
在5s時任務1結束，調度器根據非搶占式優先級調度策略選擇優先級更大的任務2執行，任務2在5s繼續執行；
在9s時任務2結束，調度器根據非搶占式優先級調度策略選擇任務3執行，任務3在9s繼續執行；
在12s時任務3結束，任務全部完成。

過程符合非搶占式優先級的調度策略。

甘特圖：

計算等待時間為 (0 - 0) + (5 - 2) + (9 - 4) = 8
計算平均等待時間為 8 / 3 = 2.67s
計算也正確。

可以看出，各個調度算法基本正確。

測試用例2：

5 0 3 1 2 6 3 4 4 4 6 5 2 8 2 5 TaskArrival TimeWCTPriority

1	0	3	1
2	2	6	3
3	4	4	4
4	6	5	2
5	8	2	5

執行截圖：

甘特圖：

[(0 - 0) + (3 - 2) + (9 - 4) + (13 - 6) + (18 - 8)] / 5 = 23 / 5 = 4.6

[(0 - 0) + (3 - 2 + 15 - 2) + (4 - 4) + (10 - 6) + (8 - 8)] / 5 = 18 / 5 = 3.6

[(0 - 0) + (3 - 2) + (11 - 4) + (15 - 6) + (9 - 8)] / 5 = 18 / 5 = 3.6

[(19 - 0) + (10 - 2) + (4 - 4) + (14 - 6) + (8 - 8)] / 5 = 33 / 5 = 6.6

[(0 - 0) + (3 - 2) + (11 - 4) + (15 - 6) + (9 - 8)] / 5 = 18 / 5 = 3.6

經過計算，結果基本正確。

測試用例3：

4 0 7 1 2 4 3 4 1 4 5 4 2 TaskArrival TimeWCTPriority

1	0	7	1
2	2	4	3
3	4	1	4
4	5	4	2

執行截圖：

經過計算，結果基本正確。

測試用例4：

4 0 8 1 1 4 3 2 9 4 3 5 2 TaskArrival TimeWCTPriority

1	0	8	1
2	1	4	3
3	2	9	4
4	3	5	2

執行截圖：

經過計算，結果基本正確。

總結

以上是生活随笔為你收集整理的操作系统实验报告16：CPU 调度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。