106 OS homework 2-2 成果報告書
組長：B10401023 蔡溱
組員：B10401020 林祐邦
組員：B10415007 曾俊翔
github: https://github.com/Yuukuni/final-xv6
🙂 使用情境說明(包含流程圖)
xv6原本的CPU排程是使用RR(Round-Robin scheduling)，而我們增加以下幾種，在make時選擇排程方式，並藉由ps、foo、nice、sanity test比較其差異。
- DEFAULT(RR)：
先進入processor的process先執行，若timeout還沒執行完則排至waiting queue的最後，輪到下一個執行。
- PRIORITY：
將每個process加上priority，預設為10，數字越小優先度越高。以下的code用來表示排程情況：
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
//每次都從table最前面的開始
struct proc *highP = 0; //最後挑出執行的process
struct proc *p1 = 0; //用來和highP比較priority大小的
if(p->state != RUNNABLE)
continue;
highP = p; //找到第一個狀態為RUNNABLE的訂為暫時挑出的p
for(p1 = ptable.proc; p1 < &ptable.proc[NPROC]; p1++)
if((p1->state == RUNNABLE) && (highP->priority > p1->priority))
highP = p1; //要是目前找到的p1的prioruty值比較小(權限較高)，將highP改為p1
if(highP != 0)
p = highP; //要是有找到highP，p=highP，否則p=原本執行的process
也就是說，每次會從排序下來最前面待執行process開始找出priority值最低的執行。
-
FIFO(First In First Out)：
先被create的child process先執行，而且沒有時間限制。 -
Static Multilevel queue scheduling(SML)：
1.為preemptive的排程方式，priority分為3個等級(數字3最高)，並產生3個priority queue，預設為2，若一個process呼叫fork()，則child會和parent的priority相同。
2.只有等到priority較高的queue為空時(等於queue裡的process全部執行完)，priority較低的queue才會開始執行。
3.使用者可透過nice這個system call改變每個process的priority。
- Sanity test介紹
呼叫sanity n後，會fork 3n個child process，等全部process執行完畢後，輸出每一個的統計資料：
pid除以三會整除的是CPU-bound process(CPU)，跑100次1000000 iterations的dummy loop
pid除以三會餘1的是short tasks based CPU-bound process(CPU-S)，跑100次1000000 iterations的dummy loop，每一次迴圈結束後讓出CPU
pid除以三會餘2的是I/O-bound process(I/O)，做100次sleep(1)來模擬等待I/O時的情況
Average sleeping time：平均一個process在SLEEPING的時間
Average sleeping time：平均一個process在RUNNING的時間
Average ready time：平均一個process等待CPU的時間
Average turnaround time：平均一個process完成的時間(包括waiting及running)
😇 成功畫面
1. DEFAULT
- init
- foo 4
- ps
- sanity
2. PRIORITY
- init
- foo 4
- ps
- sanity
- nice(change priority)
nice用法：-p為change priority、7為pid、3為欲更改的priority
由圖可見，child 7更改後的priority為3，較其他process高，因此狀態改為RUNNING。
3. FIFO
- init
- foo 4 & ps
- sanity
4. SML
- init
- foo 4
- ps
- SMLsanity
🏃 實作過程(修改哪些檔案[含圖片])
新增：
-
foo.c
-
nice.c
-
sanity.c
-
SMLsanity.c
修改(反白部分)：
-
Makefile
-
defs.c
int wait2(int*, int*, int*);
void wakeup(void*);
void yield(void);
-
init.c
-
proc.c
#ifdef PRIORITY
p->priority = 10;
#else
#ifdef SML
p->priority = 2;
#endif
#endif
p->ctime = ticks;
p->retime = 0;
p->rutime = 0;
p->stime = 0;
int wait2(int *retime, int *rutime, int *stime) {
struct proc *p;
int havekids, pid;
acquire(&ptable.lock);
for(;;){
// Scan through table looking for zombie children.
havekids = 0;
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
if(p->parent != myproc())
continue;
havekids = 1;
if(p->state == ZOMBIE){
// Found one.
*retime = p->retime;
*rutime = p->rutime;
*stime = p->stime;
pid = p->pid;
kfree(p->kstack);
p->kstack = 0;
freevm(p->pgdir);
p->state = UNUSED;
p->pid = 0;
p->parent = 0;
p->name[0] = 0;
p->killed = 0;
p->ctime = 0;
p->retime = 0;
p->rutime = 0;
p->stime = 0;
p->priority = 0;
release(&ptable.lock);
return pid;
}
}
// No point waiting if we don't have any children.
if(!havekids || myproc()->killed){
release(&ptable.lock);
return -1;
}
// Wait for children to exit. (See wakeup1 call in proc_exit.)
sleep(myproc(), &ptable.lock); //DOC: wait-sleep
}
}
#ifdef DEFAULT
if(p->state != RUNNABLE)
continue;
#else
#ifdef PRIORITY
struct proc *highP = 0;
struct proc *p1 = 0;
if(p->state != RUNNABLE)
continue;
// Choose the process with highest priority (among RUNNABLEs)
highP = p;
for(p1 = ptable.proc; p1 < &ptable.proc[NPROC]; p1++){
if((p1->state == RUNNABLE) && (highP->priority > p1->priority))
highP = p1;
}
if(highP != 0)
p = highP;
#else
#ifdef FIFO
struct proc *minP = 0;
if(p->state != RUNNABLE)
continue;
// ignore init and sh processes from FIFO
if(p->pid > 1)
{
if (minP != 0){
// here I find the process with the lowest creation time (the first one that was created)
if(p->ctime < minP->ctime)
minP = p;
}
else
minP = p;
}
// If I found the process which I created first and it is runnable I run it
//(in the real FCFS I should not check if it is runnable, but for testing purposes I have to make this control, otherwise every time I launch
// a process which does I/0 operation (every simple command) everything will be blocked
if(minP != 0 && minP->state == RUNNABLE)
p = minP;
#else
#ifdef SML
struct proc *foundP = 0;
uint priority = 1;
int index1 = 0;
int index2 = 0;
int index3 = 0;
foundP = findReadyProcess(&index1, &index2, &index3, &priority);
if (foundP != 0)
p = foundP;
else{
if(p->state != RUNNABLE)
continue;
}
#endif
#endif
#endif
#endif
void
yield(void)
{
acquire(&ptable.lock); //DOC: yieldlock
myproc()->state = RUNNABLE;
sched();
release(&ptable.lock);
}
void updatestatistics() {
struct proc *p;
acquire(&ptable.lock);
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
switch(p->state) {
case SLEEPING:
p->stime++;
break;
case RUNNABLE:
p->retime++;
break;
case RUNNING:
p->rutime++;
break;
default:
;
}
}
release(&ptable.lock);
}
#ifdef SML
/*
this method will find the next process to run
*/
struct proc* findReadyProcess(int *index1, int *index2, int *index3, uint *priority) {
int i;
struct proc* proc2;
notfound:
for (i = 0; i < NPROC; i++) {
switch(*priority) {
case 1:
proc2 = &ptable.proc[(*index1 + i) % NPROC];
if (proc2->state == RUNNABLE && proc2->priority == *priority) {
*index1 = (*index1 + 1 + i) % NPROC;
return proc2; // found a runnable process with appropriate priority
}
case 2:
proc2 = &ptable.proc[(*index2 + i) % NPROC];
if (proc2->state == RUNNABLE && proc2->priority == *priority) {
*index2 = (*index2 + 1 + i) % NPROC;
return proc2; // found a runnable process with appropriate priority
}
case 3:
proc2 = &ptable.proc[(*index3 + i) % NPROC];
if (proc2->state == RUNNABLE && proc2->priority == *priority){
*index3 = (*index3 + 1 + i) % NPROC;
return proc2; // found a runnable process with appropriate priority
}
}
}
if (*priority == 1) {//did not find any process on any of the prorities
*priority = 3;
return 0;
}
else {
*priority -= 1; //will try to find a process at a lower priority (ighter value of priority)
goto notfound;
}
return 0;
}
#endif
- proc.h
void updatestatistics();
struct proc* findReadyProcess(int *index1, int *index2, int *index3, uint *priority);
- syscall.c、syscall.h、sysproc.c、user.h、usys.h
皆為syscall類，以一張圖示意
😎 結論
xv6原本是使用Round-Robin scheduling，雖然因為有timeout而不會產生starvation的問題，卻不是optimal的排程演算法，因此我們嘗試了其他三種並測試CPU time。
PRIORITY：若一直有優先度較高的process被create，可能會造成starvation。
FIFO：不會造成starvation，但若是排在前面的process執行時間長的話，後面的process會等待很久。
SML：是一個fixed-priority的排程方式，一開始將process的priority設為多少就進入相對應的queue，不會自動改變priority，必須透過system call才能改變。DML(Dynamic Multilevel queue scheduling)為改善這個缺點的另一種排程方式。
📅 組員分工
蔡溱：新增ps、foo、nice等system call，增加foo.c、nice.c，修改Makefile、syscall.c、syscall.h、sysproc.c、user.h。
林祐邦：將排程演算法加入原本xv6的proc.c中的scheduler()，並加入演算法中其他所需的function，例如：findReadyProcess(位於proc.c)，加入sanity.c、SMLsanity.c。
曾俊翔：尋找並理解各種排程方式演算法，修改演算法使系統運作更快。