前言

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

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

• First Come, First Served(FCFS)

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

但是對于一個需要和用戶進行交互的進程，這種調(diào)度算法就會造成體驗非常不好，因為周轉(zhuǎn)時間需要完成一整個隊列的任務(wù)，非常的長

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

• Shortest Job First（SJF）

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

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

• RR

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

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

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

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

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

schedule

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

• task_struct是用來描述一個進程的結(jié)構(gòu)體

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

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

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

• 找到數(shù)值最大的一個couter，也就是運行時間最少的一個進程，切換到它的進程

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

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

• 清任務(wù)數(shù)組和描述符表項

• 之后初始化8253定時器

• 最后是設(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其實就是根據(jù)描述符各個位的作用來進行設(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)時間，又照顧了周轉(zhuǎn)時間。

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

轉(zhuǎn)載于:https://www.cnblogs.com/secoding/p/11422525.html

總結(jié)

以上是生活随笔為你收集整理的我是如何学习写一个操作系统（六）：进程的调度的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。