實(shí)驗(yàn)要求
實(shí)驗(yàn)要求參考實(shí)驗(yàn)樓課程副渴。
實(shí)驗(yàn)?zāi)康?/h1>
- 掌握Linux下的多進(jìn)程編程技術(shù)翼悴；
- 通過(guò)對(duì)進(jìn)程運(yùn)行軌跡的跟蹤來(lái)形象化進(jìn)程的概念信卡；
- 在進(jìn)程運(yùn)行軌跡跟蹤的基礎(chǔ)上進(jìn)行相應(yīng)的數(shù)據(jù)統(tǒng)計(jì)隔缀，從而能對(duì)進(jìn)程調(diào)度算法進(jìn)行實(shí)際的量化評(píng)價(jià)，更進(jìn)一步加深對(duì)調(diào)度和調(diào)度算法的理解坐求，獲得能在實(shí)際操作系統(tǒng)上對(duì)調(diào)度算法進(jìn)行實(shí)驗(yàn)數(shù)據(jù)對(duì)比的直接經(jīng)驗(yàn)蚕泽。
實(shí)驗(yàn)內(nèi)容
- 基于模板“process.c”編寫(xiě)多進(jìn)程的樣本程序晌梨，實(shí)現(xiàn)如下功能：所有子進(jìn)程都并行運(yùn)行桥嗤，每個(gè)子進(jìn)程的實(shí)際運(yùn)行時(shí)間一般不超過(guò)30秒；父進(jìn)程向標(biāo)準(zhǔn)輸出打印所有子進(jìn)程的id仔蝌，并在所有子進(jìn)程都退出后才退出泛领；
- 在Linux0.11上實(shí)現(xiàn)進(jìn)程運(yùn)行軌跡的跟蹤×簿基本任務(wù)是在內(nèi)核中維護(hù)一個(gè)日志文件/var/process.log渊鞋，把從操作系統(tǒng)啟動(dòng)到系統(tǒng)關(guān)機(jī)過(guò)程中所有進(jìn)程的運(yùn)行軌跡都記錄在這一log文件中。
- 在修改過(guò)的0.11上運(yùn)行樣本程序，通過(guò)分析log文件锡宋，統(tǒng)計(jì)該程序建立的所有進(jìn)程的等待時(shí)間儡湾、完成時(shí)間（周轉(zhuǎn)時(shí)間）和運(yùn)行時(shí)間，然后計(jì)算平均等待時(shí)間执俩，平均完成時(shí)間和吞吐量徐钠。可以自己編寫(xiě)統(tǒng)計(jì)程序役首，也可以使用python腳本程序——stat_log.py（hit-oslab/common/files）——進(jìn)行統(tǒng)計(jì)尝丐。
- 修改0.11進(jìn)程調(diào)度的時(shí)間片，然后再運(yùn)行同樣的樣本程序衡奥，統(tǒng)計(jì)同樣的時(shí)間數(shù)據(jù)爹袁，和原有的情況對(duì)比，體會(huì)不同時(shí)間片帶來(lái)的差異矮固。
實(shí)驗(yàn)步驟
process.c 代碼
在實(shí)現(xiàn)的process.c中失息，一共fork 了5個(gè)進(jìn)程。
int main(int argc, char * argv[])
{
int pid, stat_addr;
if (! (pid = fork())) {
cpuio_bound(30, 1, 1);
} else {
printf("fork %d.\n", pid);
if (! (pid = fork())) {
cpuio_bound(30, 30, 0);
} else {
printf("fork %d.\n", pid);
if (! (pid = fork())) {
cpuio_bound(30, 0, 30);
} else {
printf("fork %d.\n", pid);
if (! (pid = fork())) {
cpuio_bound(30, 9, 1);
} else {
printf("fork %d.\n", pid);
if (! (pid = fork())) {
cpuio_bound(30, 1, 9);
} else {
printf("fork %d.\n", pid);
}
}
}
}
}
wait(&stat_addr);
return 0;
}
程序運(yùn)行軌跡的跟蹤
日志文件的格式
參考實(shí)驗(yàn)課程文檔乏屯。
打開(kāi)日志文件
同上根时。
寫(xiě)日志文件
同上。
尋找狀態(tài)切換點(diǎn)
關(guān)于進(jìn)程運(yùn)行狀態(tài)的綜述和狀態(tài)切換圖辰晕，可以參考《Linux內(nèi)核完全剖析：基于0.12內(nèi)核》：P175蛤迎。
進(jìn)程的新建（N）及由新建（N）切換到就緒（N）狀態(tài)
新建進(jìn)程是由fork()實(shí)現(xiàn)的，該函數(shù)在內(nèi)核中實(shí)現(xiàn)為sys_fork()含友。sys_fork()函數(shù)位于kernel/system_call.s: 208替裆。
sys_fork:
call find_empty_process
testl %eax,%eax
js 1f
push %gs
pushl %esi
pushl %edi
pushl %ebp
pushl %eax
call copy_process
addl $20,%esp
1: ret
find_empty_process函數(shù)用于獲取系統(tǒng)中一個(gè)可用的pid，而copy_process函數(shù)負(fù)責(zé)創(chuàng)建一個(gè)子進(jìn)程窘问，并把父進(jìn)程的所有寄存器內(nèi)容直接復(fù)制給子進(jìn)程辆童。
copy_process位于kernel/fork.c: 68。
int copy_process(int nr,long ebp,long edi,long esi,long gs,long none,
long ebx,long ecx,long edx,
long fs,long es,long ds,
long eip,long cs,long eflags,long esp,long ss)
{
struct task_struct *p;
int i;
struct file *f;
p = (struct task_struct *) get_free_page();
if (!p)
return -EAGAIN;
task[nr] = p;
*p = *current; /* NOTE! this doesn't copy the supervisor stack */
p->state = TASK_UNINTERRUPTIBLE;
/* =========== modified =========== */
fprintk(3, "%ld\t%c\t%ld\n", current->pid, 'N', jiffies);
/* =========== modified =========== */
p->pid = last_pid;
p->father = current->pid;
/* 省略若干代碼 */
p->state = TASK_RUNNING; /* do this last, just in case */
/* =========== modified =========== */
fprintk(3, "%ld\t%c\t%ld\n", current->pid, 'J', jiffies);
/* =========== modified =========== */
return last_pid;
copy_process函數(shù)實(shí)現(xiàn)的功能包括：
- 為新任務(wù)的task_struct分配內(nèi)存惠赫，并將當(dāng)前當(dāng)前任務(wù)的task_struct復(fù)制給新任務(wù)把鉴。
- 修改新任務(wù)的task_struct。此時(shí)儿咱。需要將新任務(wù)的狀態(tài)設(shè)置為不可中斷狀態(tài)庭砍，防止其被內(nèi)核調(diào)度執(zhí)行。筆者認(rèn)為混埠，此時(shí)新任務(wù)已經(jīng)完成了新建（N）狀態(tài)怠缸。
- 修改任務(wù)狀態(tài)段（TSS）數(shù)據(jù)。此時(shí)钳宪，需要設(shè)置TSS中的內(nèi)核棧信息（ss0:dsp0）揭北，將傳入函數(shù)的參數(shù)賦給TSS中對(duì)應(yīng)的寄存器扳炬，保存本任務(wù)的LDT描述符和狀態(tài)位圖。值得注意的是搔体，在設(shè)置寄存器時(shí)恨樟，需要將新任務(wù)的eax的值置為0，而對(duì)于父任務(wù)來(lái)說(shuō)疚俱，eax的值是find_empty_process函數(shù)的返回值厌杜。這也就是父進(jìn)程調(diào)用fork函數(shù)返回子進(jìn)程的ID，而子進(jìn)程調(diào)用fork函數(shù)返回0的原因计螺。
- 復(fù)制進(jìn)程頁(yè)表夯尽；處理文件引用數(shù)；在GDT表中設(shè)置新任務(wù)是TSS段和LDT段描述符登馒；設(shè)置進(jìn)程之間的關(guān)系列表指針匙握。
- 將任務(wù)置為可運(yùn)行狀態(tài)。此時(shí)陈轿，新任務(wù)處于就緒（J）狀態(tài)圈纺。
進(jìn)程的就緒（J）狀態(tài)和運(yùn)行（R）狀態(tài)之間的切換
在linux-0.11的內(nèi)核代碼中是不區(qū)分就緒狀態(tài)和運(yùn)行狀態(tài)的，二者都是TASK_RUNNING麦射。所以代碼中并沒(méi)有顯示地對(duì)這兩種狀態(tài)切換的代碼蛾娶。
實(shí)現(xiàn)進(jìn)程切換的代碼是switch_to(int)(kernel/sched.c: 141)函數(shù)。在切換進(jìn)程之前的代碼實(shí)現(xiàn)了進(jìn)程調(diào)度的算法潜秋，這些將在下文中討論蛔琅。進(jìn)程調(diào)度算法按照一定的策略找到下個(gè)執(zhí)行的進(jìn)程的ID(next)，使用switch_to函數(shù)將cpu的使用權(quán)交給next號(hào)進(jìn)程峻呛。需要注意的是罗售，next號(hào)進(jìn)程可能就是當(dāng)前正在執(zhí)行的進(jìn)程，所以首先要判斷next進(jìn)程是否是當(dāng)前進(jìn)程钩述。只有當(dāng)二者不相等時(shí)寨躁，才真正地發(fā)生了進(jìn)程的調(diào)度。next號(hào)進(jìn)程就由就緒狀態(tài)切換到運(yùn)行狀態(tài)牙勘。而如果當(dāng)前進(jìn)程是運(yùn)行狀態(tài)职恳，則其狀態(tài)需要切換到就緒態(tài)。
這里展開(kāi)分析一下方面，在linux-0.11的內(nèi)核中放钦，何時(shí)會(huì)將正在運(yùn)行的程序轉(zhuǎn)換成就緒狀態(tài)。在實(shí)驗(yàn)說(shuō)明文檔中有過(guò)說(shuō)明葡幸，對(duì)于linux-0.11系統(tǒng)來(lái)說(shuō)最筒，有一個(gè)長(zhǎng)度為10ms的tick贺氓。這個(gè)tick不僅僅是作為統(tǒng)計(jì)進(jìn)程的單位蔚叨，而且定時(shí)芯片（8253/8254）會(huì)每隔10ms向系統(tǒng)發(fā)出一次時(shí)間終端請(qǐng)求（int 0x20床蜘，時(shí)間中斷的代碼在kernel/sys_call.s: 176）。而系統(tǒng)在響應(yīng)時(shí)間中斷時(shí)蔑水，會(huì)調(diào)用do_timer(long gpl)函數(shù)（kernel/sched.c: 305）邢锯。如果當(dāng)前正在執(zhí)行的用戶進(jìn)程的時(shí)間片已經(jīng)用完（即GPL == 3，且current->count == 0）搀别，該函數(shù)會(huì)調(diào)用schedule()函數(shù)進(jìn)行進(jìn)程調(diào)度操作丹擎，則當(dāng)前程序很有可能被切換到就緒狀態(tài)。
/* =========== modified =========== */
if (task[next] != current) {
if (current->state == TASK_RUNNING) {
fprintk(3, "%ld\t%c\t%ld\n", current->pid, 'J', jiffies);
}
fprintk(3, "%ld\t%c\t%ld\n", task[next]->pid, 'R', jiffies);
}
/* =========== modified =========== */
switch_to(next);
進(jìn)程由運(yùn)行（R）狀態(tài)切換到阻塞（W）狀態(tài)
當(dāng)一個(gè)進(jìn)程需要等待一個(gè)外部事件時(shí)歇父，就需要將自身的狀態(tài)由運(yùn)行態(tài)切換到阻塞態(tài)蒂培。常見(jiàn)的外部事件包括等待I/O和等待其他進(jìn)程的消息等。在內(nèi)核中榜苫，等待同一個(gè)資源的進(jìn)程隱式地構(gòu)成一個(gè)等待隊(duì)列护戳，采用后進(jìn)先出（FILO）的策略。等待隊(duì)列的數(shù)據(jù)結(jié)構(gòu)可以參考《Linux內(nèi)核完全剖析：基于0.12內(nèi)核》：P299垂睬。在linux-0.11的內(nèi)核代碼中將進(jìn)程切換至阻塞態(tài)的函數(shù)是sleep_on(kernel/sched.c: 151)和interruptible_sleep_on(kernel/sched.c: 167)媳荒。
這2個(gè)函數(shù)的作用就是將暫時(shí)無(wú)法運(yùn)行的進(jìn)程切換到阻塞態(tài)，并將該進(jìn)程的task_struct添加到等待隊(duì)列中驹饺。之后钳枕，會(huì)調(diào)用schedule()函數(shù)將CPU分配給其他的進(jìn)程。當(dāng)進(jìn)程被喚醒而重新執(zhí)行時(shí)就會(huì)執(zhí)行schedule()之后的語(yǔ)句赏壹，并把比它早進(jìn)入等待隊(duì)列的一個(gè)進(jìn)程喚醒鱼炒，即從阻塞態(tài)切換到就緒態(tài)。
interruptible_sleep_on與sleep_on的功能基本類(lèi)似蝌借，只是在進(jìn)行調(diào)度之前田柔，把當(dāng)前任務(wù)設(shè)置成可中斷等待狀態(tài)，并在本任務(wù)被喚醒后還需要判斷自己是否為等待隊(duì)列中的第一個(gè)任務(wù)骨望。如果不是硬爆，則需要將自己重新設(shè)置成可中斷等待狀態(tài)，并執(zhí)行schedule()函數(shù)擎鸠，讓出CPU的執(zhí)行權(quán)缀磕。
下面展示的是打印process.log的語(yǔ)句。
在sleep_on中：
void sleep_on(struct task_struct **p)
{
struct task_struct *tmp;
if (!p)
return;
if (current == &(init_task.task))
panic("task[0] trying to sleep");
tmp = *p;
*p = current;
current->state = TASK_UNINTERRUPTIBLE;
/* =========== modified =========== */
fprintk(3, "%ld\t%c\t%ld\n", current->pid, 'W', jiffies);
/* =========== modified =========== */
schedule();
if (tmp) {
tmp->state=0;
/* =========== modified =========== */
fprintk(3, "%ld\t%c\t%ld\n", tmp->pid, 'J', jiffies);
/* =========== modified =========== */
}
}
在interruptible_sleep_on中
void interruptible_sleep_on(struct task_struct **p)
{
struct task_struct *tmp;
if (!p)
return;
if (current == &(init_task.task))
panic("task[0] trying to sleep");
tmp=*p;
*p=current;
repeat: current->state = TASK_INTERRUPTIBLE;
/* =========== modified =========== */
fprintk(3, "%ld\t%c\t%ld\n", current->pid, 'W', jiffies);
/* =========== modified =========== */
schedule();
if (*p && *p != current) {
(**p).state=0;
/* =========== modified =========== */
fprintk(3, "%ld\t%c\t%ld\n", (*p)->pid, 'J', jiffies);
/* =========== modified =========== */
goto repeat;
}
*p=NULL;
if (tmp) {
tmp->state=0;
/* =========== modified =========== */
fprintk(3, "%ld\t%c\t%ld\n", tmp->pid, 'J', jiffies);
/* =========== modified =========== */
}
}
除了上述的2個(gè)函數(shù)可以實(shí)現(xiàn)將進(jìn)程從執(zhí)行狀態(tài)切換到阻塞狀態(tài)劣光，sys_pause()(kernel/sched.c: 144)和sys_waitpid(kernel/exit.c: 142)也可以做到袜蚕。
當(dāng)schedule函數(shù)發(fā)現(xiàn)系統(tǒng)中沒(méi)有可執(zhí)行的任務(wù)時(shí)，就會(huì)切換到0號(hào)任務(wù)绢涡，而0號(hào)任務(wù)就會(huì)循環(huán)執(zhí)行sys_pause牲剃，將自己設(shè)置為可中斷的阻塞態(tài)。理論上雄可，該系統(tǒng)調(diào)用將導(dǎo)致進(jìn)程進(jìn)入睡眠狀態(tài)凿傅，直到收到一個(gè)用于終止進(jìn)程或者促使進(jìn)程調(diào)用的信號(hào)量缠犀。然而這些功能在0.11版本內(nèi)核中沒(méi)有沒(méi)實(shí)現(xiàn)。
int sys_pause(void)
{
current->state = TASK_INTERRUPTIBLE;
/* =========== modified =========== */
if (current->pid != 0) {
fprintk(3, "%ld\t%c\t%ld\n", current->pid, 'W', jiffies);
}
/* =========== modified =========== */
schedule();
return 0;
}
而sys_waitpid函數(shù)的功能則是對(duì)任務(wù)數(shù)組進(jìn)行掃描聪舒，如果其中有子進(jìn)程不處于退出狀態(tài)或者僵死狀態(tài)辨液，則將父進(jìn)程切換到可中斷的阻塞狀態(tài)。
進(jìn)程由阻塞（W）狀態(tài)切換到就緒（J）狀態(tài)
將進(jìn)程由阻塞態(tài)切換到就緒態(tài)的函數(shù)箱残，除了之前小節(jié)中提到的sleep_on和interruptible_sleep_on函數(shù)滔迈，wake_up和schedule函數(shù)也能完成該切換。
wake_up函數(shù)直接將等待隊(duì)列中的第一個(gè)任務(wù)喚醒：
void wake_up(struct task_struct **p)
{
if (p && *p) {
(**p).state=0;
/* =========== modified =========== */
fprintk(3, "%ld\t%c\t%ld\n", (*p)->pid, 'J', jiffies);
/* ========== modified =========== */
*p=NULL;
}
}
而在schedule函數(shù)中被辑，首先會(huì)檢測(cè)進(jìn)程的報(bào)警定時(shí)值（alarm）燎悍，并將處于可中斷狀態(tài)且接收到信號(hào)的進(jìn)程喚醒。
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;
/* =========== modified =========== */
fprintk(3, "%ld\t%c\t%ld\n", (*p)->pid, 'J', jiffies);
/* =========== modified =========== */
}
}
}
進(jìn)程的退出
進(jìn)程退出狀態(tài)的設(shè)置是在do_exit(kernel/exit.c: 102)中實(shí)現(xiàn)的盼理。
該函數(shù)釋放當(dāng)前進(jìn)程的代碼段和數(shù)據(jù)段所占的內(nèi)存頁(yè)间涵，執(zhí)行與文件系統(tǒng)相關(guān)的清理工作，最后將進(jìn)程狀態(tài)設(shè)置為僵死狀態(tài)榜揖，并給退出碼賦值勾哩。
進(jìn)程時(shí)間統(tǒng)計(jì)
由于process.c在運(yùn)行時(shí)會(huì)在終端上打印fork的子進(jìn)程編號(hào)，在進(jìn)行時(shí)間統(tǒng)計(jì)時(shí)举哟，最好只統(tǒng)計(jì)這些進(jìn)程思劳。
chen@chen:oslab$ ./stat_log.py process.log 13 14 15 16 17
(Unit: tick)
Process Turnaround Waiting CPU Burst I/O Burst
13 3158 1631 800 727
14 3190 2125 1065 0
15 3172 32 0 3139
16 3171 2036 1019 115
17 3144 610 300 2234
Average: 3167.00 1286.80
Throughout: 0.16/s
由上面的統(tǒng)計(jì)可以看出，處理器繁忙的進(jìn)程的等待時(shí)間也很長(zhǎng)妨猩，而I/O繁忙的進(jìn)程的等待時(shí)間會(huì)相對(duì)短一些潜叛。
調(diào)度算法修改
分析代碼可知，0.11的調(diào)度算法是選取counter值最大的就緒進(jìn)程進(jìn)行調(diào)度壶硅。其中運(yùn)行態(tài)進(jìn)程（即current）的counter數(shù)值會(huì)隨著時(shí)鐘中斷而不斷減1（時(shí)鐘中斷10ms一次）威兜，所以是一種比較典型的時(shí)間片輪轉(zhuǎn)調(diào)度算法。另外庐椒，由上面的程序可以看出椒舵，當(dāng)沒(méi)有counter值大于0的就緒進(jìn)程時(shí)，要對(duì)所有的進(jìn)程做(*p)->counter = ((*p)->counter >> 1) + (*p)->priority约谈。其效果是對(duì)所有的進(jìn)程（包括阻塞態(tài)進(jìn)程）都進(jìn)行counter的衰減笔宿，并再累加priority值。這樣棱诱，對(duì)正被阻塞的進(jìn)程來(lái)說(shuō)泼橘，一個(gè)進(jìn)程在阻塞隊(duì)列中停留的時(shí)間越長(zhǎng)，其優(yōu)先級(jí)越大迈勋，被分配的時(shí)間片也就會(huì)越大炬灭。所以總的來(lái)說(shuō)，Linux 0.11的進(jìn)程調(diào)度是一種綜合考慮進(jìn)程優(yōu)先級(jí)并能動(dòng)態(tài)反饋調(diào)整時(shí)間片的輪轉(zhuǎn)調(diào)度算法靡菇。
時(shí)間片counter和優(yōu)先級(jí)priority的初始化在include/sched.h: 113重归。
#define INIT_TASK \
{ 0,15,15, //分別對(duì)應(yīng)state;counter;和priority;
只需要修改這個(gè)宏里的數(shù)字米愿，就可以修改counter和priority的初始值。
