我是如何學(xué)習(xí)寫一個(gè)操作系統(tǒng)（六）：進(jìn)程的調(diào)度

前言

既然引進(jìn)了多進(jìn)程，其實(shí)也就是在進(jìn)程之間來回切換，那么就會(huì)有進(jìn)程之間的調(diào)度問題。實(shí)則是在可運(yùn)行進(jìn)程之間分配有限的處理器時(shí)間資源的內(nèi)核子系統(tǒng)。

幾個(gè)簡單的CPU調(diào)度算法

*
First Come, First Served(FCFS)


其實(shí)就是一個(gè)先進(jìn)先出隊(duì)列了，也就是說先申請的進(jìn)程，先執(zhí)行。當(dāng)CPU空閑時(shí)，它會(huì)分配給位于隊(duì)列頭部的進(jìn)程，并且這個(gè)運(yùn)行進(jìn)程從隊(duì)列中移去。FCFS調(diào)度代碼編寫簡單并且理解容易。

但是對于一個(gè)需要和用戶進(jìn)行交互的進(jìn)程，這種調(diào)度算法就會(huì)造成體驗(yàn)非常不好，因?yàn)橹苻D(zhuǎn)時(shí)間需要完成一整個(gè)隊(duì)列的任務(wù)，非常的長

但FCFS調(diào)度算法是非搶占的。一旦 CPU 分配給了一個(gè)進(jìn)程，該進(jìn)程就會(huì)使用 CPU 直到釋放 CPU 為止，即程序終止或是請求I/O。

*
Shortest Job First（SJF）

SJF調(diào)度算法就指對短作業(yè)或者短進(jìn)程優(yōu)先調(diào)度的算法，將每個(gè)進(jìn)程與其估計(jì)運(yùn)行時(shí)間進(jìn)行關(guān)聯(lián)選取估計(jì)計(jì)算時(shí)間最短的作業(yè)投入運(yùn)行。這樣就可以縮短周轉(zhuǎn)時(shí)間

最短作業(yè)優(yōu)先（SJF）調(diào)度算法將每個(gè)進(jìn)程與其下次CPU執(zhí)行的長度關(guān)聯(lián)起來。當(dāng) CPU 變?yōu)榭臻e時(shí)，它會(huì)被賦給具有最短 CPU
執(zhí)行的進(jìn)程。如果兩個(gè)進(jìn)程具有同樣長度的 CPU 執(zhí)行那么可以由FCFS來處理。

*
RR

該算法中，將一個(gè)較小時(shí)間單元定義為時(shí)間量或時(shí)間片。時(shí)間片的大小通常為
10~100ms。就緒隊(duì)列作為循環(huán)隊(duì)列。CPU調(diào)度程序循環(huán)整個(gè)就緒隊(duì)列，為每個(gè)進(jìn)程分配不超過一個(gè)時(shí)間片的CPU。

為了實(shí)現(xiàn)RR調(diào)度，我們再次將就緒隊(duì)列視為進(jìn)程的 FIFO 隊(duì)列。新進(jìn)程添加到就緒隊(duì)列的尾部。CPU
調(diào)度程序從就緒隊(duì)列中選擇第一個(gè)進(jìn)程，將定時(shí)器設(shè)置在一個(gè)時(shí)間片后中斷，最后分派這個(gè)進(jìn)程。

調(diào)度算法的折中

在運(yùn)行的許多進(jìn)程里，有的進(jìn)程更關(guān)心響應(yīng)時(shí)間，有的進(jìn)程更關(guān)心周轉(zhuǎn)時(shí)間，所以調(diào)度算法就需要折中，但是如何折中又是一個(gè)問題。

Linux0.11 調(diào)度算法

schedule

schedule是Linux0.11里最主要的調(diào)度算法，但是十分簡潔

*
task_struct是用來描述一個(gè)進(jìn)程的結(jié)構(gòu)體

task_struct的counter是調(diào)度算法實(shí)現(xiàn)折中的一個(gè)關(guān)鍵，它既用來表示分配的時(shí)間片，又用來表示進(jìn)程的優(yōu)先級

*
首先從任務(wù)數(shù)組中最后一個(gè)任務(wù)開始循環(huán)檢測一些域


如果設(shè)置過任務(wù)的定時(shí)值alarm，并且已經(jīng)過期(alarm<jiffies)，則在信號位圖中置SIGALRM信號，即向任務(wù)發(fā)送SIGALARM信號。然后清alarm。還有一些信號量相關(guān)的會(huì)在后面再提

*
找到數(shù)值最大的一個(gè)couter，也就是運(yùn)行時(shí)間最少的一個(gè)進(jìn)程，切換到它的進(jìn)程

*

當(dāng)執(zhí)行完一回的輪轉(zhuǎn)就會(huì)重新分配一次時(shí)間片，這時(shí)候?qū)τ谝呀?jīng)輪轉(zhuǎn)過的進(jìn)程，時(shí)間片將會(huì)被設(shè)置為初值，但是對于那些阻塞的進(jìn)程，時(shí)間片將會(huì)增加，也就是進(jìn)行了一次折中的調(diào)度。
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，這個(gè)函數(shù)內(nèi)核調(diào)度程序的初始化子程序，就是初始化一些中斷和描述符

*
首先調(diào)用set_tss_desc和set_ldt_desc設(shè)置進(jìn)程0的tss和ldt

*
清任務(wù)數(shù)組和描述符表項(xiàng)

*
之后初始化8253定時(shí)器

*
最后是設(shè)置時(shí)鐘中斷和系統(tǒng)調(diào)用中斷
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); }
設(shè)置描述符

_set_tssldt_desc其實(shí)就是根據(jù)描述符各個(gè)位的作用來進(jìn)行設(shè)置
#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,%1\n\t" \ "movw %%ax,%2\n\t" \ "rorl $16,%%eax\n\t" \ "movb
%%al,%3\n\t" \ "movb $" type ",%4\n\t" \ "movb $0x00,%5\n\t" \ "movb
%%ah,%6\n\t" \ "rorl $16,%%eax" \ ::"a" (addr), "m" (*(n)), "m" (*(n+2)), "m"
(*(n+4)), \ "m" (*(n+5)), "m" (*(n+6)), "m" (*(n+7)) \ )
設(shè)置中斷
#define _set_gate(gate_addr,type,dpl,addr) \ __asm__ ("movw %%dx,%%ax\n\t" \
"movw %0,%%dx\n\t" \ "movl %%eax,%1\n\t" \ "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)
小結(jié)

這一篇主要看了一下Linux0.11里的調(diào)度算法，十分的簡潔，但是又照顧了響應(yīng)時(shí)間，又照顧了周轉(zhuǎn)時(shí)間。

然后提了一下內(nèi)核調(diào)度程序的初始化子程序，其實(shí)就是根據(jù)之前說的設(shè)置一些描述符和中斷處理

• ? 上一篇： Flutter之禪 內(nèi)存優(yōu)化篇
• ? 下一篇： 如何使用 Spring Boot 開發(fā)郵件系統(tǒng)？