我是如何學習寫一個作業系統（六）：進程的調度
- 2019 年 10 月 3 日
- 筆記
前言
既然引進了多進程，其實也就是在進程之間來回切換，那麼就會有進程之間的調度問題。實則是在可運行進程之間分配有限的處理器時間資源的內核子系統。
幾個簡單的CPU調度演算法
First Come, First Served(FCFS)
其實就是一個先進先出隊列了，也就是說先申請的進程，先執行。當CPU空閑時，它會分配給位於隊列頭部的進程，並且這個運行進程從隊列中移去。FCFS調度程式碼編寫簡單並且理解容易。
但是對於一個需要和用戶進行交互的進程，這種調度演算法就會造成體驗非常不好，因為周轉時間需要完成一整個隊列的任務，非常的長
但FCFS調度演算法是非搶佔的。一旦 CPU 分配給了一個進程，該進程就會使用 CPU 直到釋放 CPU 為止，即程式終止或是請求I/O。
Shortest Job First（SJF）
SJF調度演算法就指對短作業或者短進程優先調度的演算法，將每個進程與其估計運行時間進行關聯選取估計計算時間最短的作業投入運行。這樣就可以縮短周轉時間
最短作業優先（SJF）調度演算法將每個進程與其下次CPU執行的長度關聯起來。當 CPU 變為空閑時，它會被賦給具有最短 CPU 執行的進程。如果兩個進程具有同樣長度的 CPU 執行那麼可以由FCFS來處理。
RR
該演算法中，將一個較小時間單元定義為時間量或時間片。時間片的大小通常為 10~100ms。就緒隊列作為循環隊列。CPU調度程式循環整個就緒隊列，為每個進程分配不超過一個時間片的CPU。
為了實現RR調度，我們再次將就緒隊列視為進程的 FIFO 隊列。新進程添加到就緒隊列的尾部。CPU 調度程式從就緒隊列中選擇第一個進程，將定時器設置在一個時間片後中斷，最後分派這個進程。
調度演算法的折中
在運行的許多進程里，有的進程更關心響應時間，有的進程更關心周轉時間，所以調度演算法就需要折中，但是如何折中又是一個問題。
Linux0.11 調度演算法
schedule
schedule是Linux0.11里最主要的調度演算法，但是十分簡潔
task_struct是用來描述一個進程的結構體
task_struct的counter是調度演算法實現折中的一個關鍵，它既用來表示分配的時間片，又用來表示進程的優先順序
首先從任務數組中最後一個任務開始循環檢測一些域
如果設置過任務的定時值alarm，並且已經過期(alarm<jiffies)，則在訊號點陣圖中置SIGALRM訊號，即向任務發送SIGALARM訊號。然後清alarm。還有一些訊號量相關的會在後面再提
找到數值最大的一個couter，也就是運行時間最少的一個進程，切換到它的進程
當執行完一回的輪轉就會重新分配一次時間片，這時候對於已經輪轉過的進程，時間片將會被設置為初值，但是對於那些阻塞的進程，時間片將會增加，也就是進行了一次折中的調度。
void schedule(void) { int i,next,c; struct task_struct ** p; /* check alarm, wake up any interruptible tasks that have got a signal */ for(p = &LAST_TASK ; p > &FIRST_TASK ; --p) if (*p) { if ((*p)->alarm && (*p)->alarm < jiffies) { (*p)->signal |= (1<<(SIGALRM-1)); (*p)->alarm = 0; } if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) && (*p)->state==TASK_INTERRUPTIBLE) (*p)->state=TASK_RUNNING; } /* this is the scheduler proper: */ while (1) { c = -1; next = 0; i = NR_TASKS; p = &task[NR_TASKS]; while (--i) { if (!*--p) continue; if ((*p)->state == TASK_RUNNING && (*p)->counter > c) c = (*p)->counter, next = i; } if (c) break; for(p = &LAST_TASK ; p > &FIRST_TASK ; --p) if (*p) (*p)->counter = ((*p)->counter >> 1) + (*p)->priority; } switch_to(next); }init
我們在順便來看一下sched_init，這個函數內核調度程式的初始化子程式，就是初始化一些中斷和描述符
首先調用set_tss_desc和set_ldt_desc設置進程0的tss和ldt
清任務數組和描述符表項
之後初始化8253定時器
最後是設置時鐘中斷和系統調用中斷
void sched_init(void) { int i; struct desc_struct * p; if (sizeof(struct sigaction) != 16) panic("Struct sigaction MUST be 16 bytes"); set_tss_desc(gdt+FIRST_TSS_ENTRY,&(init_task.task.tss)); set_ldt_desc(gdt+FIRST_LDT_ENTRY,&(init_task.task.ldt)); p = gdt+2+FIRST_TSS_ENTRY; for(i=1;i<NR_TASKS;i++) { task[i] = NULL; p->a=p->b=0; p++; p->a=p->b=0; p++; } /* Clear NT, so that we won't have troubles with that later on */ __asm__("pushfl ; andl $0xffffbfff,(%esp) ; popfl"); ltr(0); lldt(0); outb_p(0x36,0x43); /* binary, mode 3, LSB/MSB, ch 0 */ outb_p(LATCH & 0xff , 0x40); /* LSB */ outb(LATCH >> 8 , 0x40); /* MSB */ set_intr_gate(0x20,&timer_interrupt); outb(inb_p(0x21)&~0x01,0x21); set_system_gate(0x80,&system_call); }設置描述符
_set_tssldt_desc其實就是根據描述符各個位的作用來進行設置
#define set_tss_desc(n,addr) _set_tssldt_desc(((char *) (n)),((int)(addr)),"0x89") #define set_ldt_desc(n,addr) _set_tssldt_desc(((char *) (n)),((int)(addr)),"0x82") #define _set_tssldt_desc(n,addr,type) __asm__ ("movw $104,%1nt" "movw %%ax,%2nt" "rorl $16,%%eaxnt" "movb %%al,%3nt" "movb $" type ",%4nt" "movb $0x00,%5nt" "movb %%ah,%6nt" "rorl $16,%%eax" ::"a" (addr), "m" (*(n)), "m" (*(n+2)), "m" (*(n+4)), "m" (*(n+5)), "m" (*(n+6)), "m" (*(n+7)) )設置中斷
#define _set_gate(gate_addr,type,dpl,addr) __asm__ ("movw %%dx,%%axnt" "movw %0,%%dxnt" "movl %%eax,%1nt" "movl %%edx,%2" : : "i" ((short) (0x8000+(dpl<<13)+(type<<8))), "o" (*((char *) (gate_addr))), "o" (*(4+(char *) (gate_addr))), "d" ((char *) (addr)),"a" (0x00080000)) #define set_intr_gate(n,addr) _set_gate(&idt[n],14,0,addr) #define set_system_gate(n,addr) _set_gate(&idt[n],15,3,addr) 小結
這一篇主要看了一下Linux0.11里的調度演算法，十分的簡潔，但是又照顧了響應時間，又照顧了周轉時間。
然後提了一下內核調度程式的初始化子程式，其實就是根據之前說的設置一些描述符和中斷處理