106 OS homework 2-2 成果報告書
組長：B10415016、楊璿譯
組員：B10415039、曾柏誠
github: https://github.com/BryantTseng/xv6-public
🙂 使用情境說明(包含流程圖)
實作scheduling功能，共包含三種演算法:
- Round Robin(RR)
- First Come First Serve(FCFS)
- Priority
以下將針對此三種方法作使用情境之說明。
First Come First Serve(FCFS) Algorithm
當第一個process到來時，將先執行其需求，若同時有許多process可被服務(runnable)，則選擇抵達時間最早的process執行，故其便無starvation的問題，因為每個process都將被執行到，但若先抵達的process，須執行時間較長，則會導致平均等待時間變長。
Priority Algorithm
scheduler將會給與每個process一個優先度，其會挑選優先度最高的先執行，執行完後挑次高的執行，若同時有優先度相同的process，則選擇到達時間低的執行。但此種方法便有可能發生satarvation，因為高優先度的process若可能被高頻率的呼叫，將會導致低優先度的process無法被執行，故會發生starvation。而我們解決方式為，process在完成任務便將priority-1，而同時若有process之優先度為1者則+1，這樣便可解決starvation的問題
Round Robin(RR) Algorithm
Scheduler將會定一段執行時間，規定每個process使用cpu資源時的時間長短，當規定時間一到便直接換下一個process使用，故不會有starvation的問題，雖然如此，但訂定執行時間須注意一些問題
- 當執行時間太短，會造成系統一直做 context switch，降低 CPU 的 Throughput
- 若將時間訂的太長， RR 便幾乎等於 FCFS。
😇 成功畫面
透過 GeneralTest 指令模擬出 CPU-bound 以及 I/O-bound 的process
然後分別用 Default(RR)、FCFS、Priority 三種不同的排程演算法執行
並觀察在不同的scheduler演算法下process的執行順序為何?
- Default (RR):
- 輸入GeneralTest測試指令
- Allocate出 10 個process
- 因為pid = 4的process為最早進來的，故最先做
- 其次為pid = 5的process，故pid = 4在執行時間結束後須將CPU資源讓給pid 5使用
- 再來換pid = 6的process執行
- 再來換pid = 7的process執行
- 再來換pid = 8的process執行
- 再來換pid = 9的process執行
- 再來換pid = 10的process執行
- 再來換pid = 11的process執行
- 再來換pid = 12的process執行
- 再來換pid = 13的process執行
- 因為所有process皆已輪完，故從頭(pid = 4)執行
- 輸入GeneralTest測試指令
- First Come First Service (FCFS)
- 輸入GeneralTest測試指令
- allocate出10個process
- 4的creation time最小，故最先做
- 其次為pid = 5的process最早，故4做完換5
- 再來為pid = 6的process
- 再來為pid = 7的process
- 再來為pid = 8的process
- 再來為pid = 9的process
- 再來為pid = 10的process
- 再來為pid = 11的process
- 再來為pid = 12的process
- 再來為pid = 13的process
- Print出平均每個 CPU-bound 和 I/O-bound processes的四種時間，分別為
- Ready time
- Running time
- Sleeping time
- Turnaround time
- 輸入GeneralTest測試指令
- Priority
- 輸入GeneralTest指令
- 產生5個process
- 因為所有process的priority一樣，故挑選creation time最小的(pid = 4)
- 再來以pid = 4之process為開頭往後尋找可執行的process，而之後第一個runnable且priority最高者為pid = 5之process，故挑選pid = 5的process執行
- 再來以pid = 5之process為開頭往後尋找可執行的process，而之後第一個runnable且priority最高者為pid = 6之process，故挑選pid = 6的process執行
- 再來以pid = 6之process為開頭往後尋找可執行的process，而之後第一個runnable且priority最高者為pid = 7之process，故挑選pid = 7的process執行
- 而此同時有4個process之priority為3，而不能挑選pid = 4 or 5的原因為
- 若挑選pid = 4 or 5，便會造成前三個process無限循環，並導致starvation problem
- 若挑選pid = 4 or 5，便會造成前三個process無限循環，並導致starvation problem
- 再來以pid = 7之process為開頭往後尋找可執行的process，而之後第一個runnable且priority最高者為pid = 8之process，故挑選pid = 8的process執行
- 再來以pid = 6之process為開頭往後尋找可執行的process，但 因為pid = 8之process以為ptable之最後一個process
- 故從頭開始找，以 最高優先度與state等於runnable的條件 為優先
- 輸入GeneralTest指令
🏃 實作過程(修改哪些檔案[含圖片])
defs.h
- 新增system call至此標頭檔
void scheduler(void) __attribute__((noreturn));
int set_prio(int);
proc.c
- allocproc(void)
- 在process table中allocate一塊空間存放process
static struct proc* allocproc(void)
{
struct proc *p;
char *sp;
acquire(&ptable.lock);
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
if(p->state == UNUSED){
break;
}
}
if(p->state!=UNUSED){
release(&ptable.lock);
return 0;
}
p->state = INIT;
p->pid = nextpid++;
p->ctime = ticks;
p->retime = 0;
p->rutime = 0;
p->stime = 0;
p->fake[0] = '*';
p->fake[1] = '*';
p->fake[2] = '*';
p->fake[3] = '*';
p->fake[4] = '*';
p->fake[5] = '*';
p->fake[6] = '*';
p->fake[7] = '*';
release(&ptable.lock);
// Allocate kernel stack.
if((p->kstack = kalloc()) == 0){
p->state = UNUSED;
return 0;
}
sp = p->kstack + KSTACKSIZE;
// Leave room for trap frame.
sp -= sizeof *p->tf;
p->tf = (struct trapframe*)sp;
// Set up new context to start executing at forkret,
// which returns to trapret.
sp -= 4;
*(uint*)sp = (uint)trapret;
sp -= sizeof *p->context;
p->context = (struct context*)sp;
memset(p->context, 0, sizeof *p->context);
p->context->eip = (uint)forkret;
cprintf("allocate, pid: %d, creation time: %d, process name: %s, now time: %d\n\n", p->pid, p->ctime, p->name, ticks);
return p;
}
- findReadyProcess(int* index1, int* index2, int* index3, uint* priority)
- 用來尋找符合priority之process來執行
#ifdef SML
/*
this method will find the next process to run
*/
struct proc* findReadyProcess(int *index1, int *index2, int *index3, uint *wantedPriority) {
int i;
struct proc* newProc;
while(1){
for (i = 0; i < NPROC; i++) {
switch(*wantedPriority) {
case 1:
newProc = &ptable.proc[(*index1 + i) % NPROC];
if (newProc->state == RUNNABLE && newProc->priority == *wantedPriority) {
*index1 = (*index1 + 1 + i) % NPROC;
return newProc; // found a runnable process with appropriate priority
}
case 2:
newProc = &ptable.proc[(*index2 + i) % NPROC];
if (newProc->state == RUNNABLE && newProc->priority == *wantedPriority) {
*index2 = (*index2 + 1 + i) % NPROC;
return newProc; // found a runnable process with appropriate priority
}
case 3:
newProc = &ptable.proc[(*index3 + i) % NPROC];
if (newProc->state == RUNNABLE && newProc->priority == *wantedPriority){
*index3 = (*index3 + 1 + i) % NPROC;
return newProc; // found a runnable process with appropriate priority
}
}
}
if (*wantedPriority == 1) {//did not find any process on any of the prorities
*wantedPriority = 3;
return 0;
}
else {
*wantedPriority -= 1; //will try to find a process at a lower priority
continue;
}
}
return 0;
}
#endif
- scheduler(void)
- 根據不同的演算法做process排程
void scheduler(void)
{
struct proc *p;
int index1 = 0;
int index2 = 0;
int index3 = 0;
int x = index1;
index1 = x;
x = index2;
index2 = x;
x = index3;
index3 = x;
for(;;){
// Enable interrupts on this processor.
sti();
// Loop over process table looking for process to run.
acquire(&ptable.lock);
// the differnt options for scheduling policies, chosen during compilation
#ifdef DEFAULT//default scheduler round robin
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
if(p->state != RUNNABLE)
continue;
// Switch to chosen process. It is the process's job
// to release ptable.lock and then reacquire it
// before jumping back to us.
proc = p;
switchuvm(p);
//cprintf("RR, pid: %d, creation time: %d, process name: %s, now time: %d\n\n", p->pid, p->ctime, p->name, ticks);
p->state = RUNNING;
cprintf("==============================================\n");
procdump();
cprintf("==============================================\n");
//cprintf("\n\n");
//procdump();
// cprintf("\n\n");
swtch(&cpu->scheduler, proc->context);
switchkvm();
// cprintf("%d+%s\n",p->pid,p->name);
// Process is done running for now.
// It should have changed its p->state before coming back.
proc = 0;
}
#else
#ifdef FCFS //Scheduler select FCFS
struct proc *minP = NULL;
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
if(p->state == RUNNABLE){//check if state is runnable
if (minP!=NULL){//not a null process
if(p->ctime < minP->ctime)//find the earlist createtime process
minP = p;
}
else
minP = p;//first time in loop, set to minp
}
}
if (minP!=NULL){
p = minP;//the process with the smallest creation time
proc = p;
switchuvm(p);
p->state = RUNNING;
cprintf("==============================================\n");
procdump();
cprintf("==============================================\n");
swtch(&cpu->scheduler, proc->context);
switchkvm();
// Process is done running for now.
// It should have changed its p->state before coming back.
proc = 0;
}
#else
#ifdef SML//Scheduler select priority
uint priority = 3;
p = findReadyProcess(&index1, &index2, &index3, &priority);
if (p == 0) {
release(&ptable.lock);
continue;
}
proc = p;
switchuvm(p);
p->state = RUNNING;
cprintf("==============================================\n");
procdump();
cprintf("==============================================\n");
swtch(&cpu->scheduler, proc->context);
switchkvm();
// Deal the starvation problem
if(p->priority > 2)// let the priority of running process minus 1
p->priority--;
// let the priority of non-running process minus 1
struct proc *temp;
for(temp = ptable.proc; temp < &ptable.proc[NPROC]; temp++)
{
if(temp->pid != p->pid && temp->priority < 3){
temp->priority++;//add other process's priority
}
}
proc = 0;
#endif
#endif
#endif
release(&ptable.lock);
}
}
- updateRecord(void)
- 用來紀錄每個process的runtime、sleeptime、waitingtime
void updateRecord() {
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);
}
- set_prio(int priority)
- 用來設定該process之優先度
int set_prio(int priority) {
if (priority < 1 || priority > 3)
return -1;
acquire(&ptable.lock);
proc->priority = priority;
release(&ptable.lock);
return 0;
}
- decpriority(void)
- 用來將該process之優先度減一
void decpriority(void) {
// acquire(&ptable.lock);
proc->priority = proc->priority == 1 ? 1 : proc->priority - 1;
// release(&ptable.lock);
}
proc.h
- 在struct新增幾項用來記錄process相關時間的變數
struct proc {
char name[16]; // Process name (debugging)
int pid; // Process ID
uint sz; // Size of process memory (bytes)
pde_t* pgdir; // Page table
char *kstack; // Bottom of kernel stack for this process
enum procstate state; // Process state
struct proc *parent; // Parent process
struct trapframe *tf; // Trap frame for current syscall
struct context *context; // swtch() here to run process
void *chan; // If non-zero, sleeping on chan
int killed; // If non-zero, have been killed
struct file *ofile[NOFILE]; // Open files
struct inode *cwd; // Current directory
uint ctime; // Process creation time
int stime; //process SLEEPING time
int retime; //process READY(RUNNABLE) time
int rutime; //process RUNNING time
int priority;
int tickcounter;
char fake[8];
};
GeneralTest.c
- 用來模擬不同類型之process，來測試排程效果
int
main(int argc, char *argv[])
{
if (argc != 3){
printf(1, "Usage: GeneralTest <n> <SchedulerType>\n");
exit();
}
#ifndef SML
int i;
int n;
int j = 0;
int k;
int retime;
int rutime;
int stime;
int sums[2][3];
for (i = 0; i < 2; i++)
for (j = 0; j < 3; j++)
sums[i][j] = 0;
n = atoi(argv[1]);
i = n; //unimportant
int pid;
for (i = 0; i < 2 * n; i++) {
j = i % 2;
pid = fork();
if (pid == 0) {//child
j = (getpid() - 4) % 2; // ensures independence from the first son's pid when gathering the results in the second part of the program
switch(j) {
case 0: //CPU bound process (CPU):
for (k = 0; k < 100; k++){
for (j = 0; j < 1000000; j++){}
}
case 1:// simulate I/O bound process (IO)
for(k = 0; k < 1; k++){
sleep(1);
}
break;
}
exit(); // children exit here
}
continue; // father continues to spawn the next child
}
for (i = 0; i < 2 * n; i++) {
pid = wait2(&retime, &rutime, &stime);
int res = (pid) % 2; // correlates to j in the dispatching loop
switch(res) {
case 0: // CPU bound processes
printf(1, "CPU-bound, pid: %d, ready: %d, running: %d, sleeping: %d, turnaround: %d\n", pid, retime, rutime, stime, retime + rutime + stime);
sums[0][0] += retime;
sums[0][1] += rutime;
sums[0][2] += stime;
break;
case 1: // simulating I/O bound processes
printf(1, "I/O-bound, pid: %d, ready: %d, running: %d, sleeping: %d, turnaround: %d\n", pid, retime, rutime, stime, retime + rutime + stime);
sums[1][0] += retime;
sums[1][1] += rutime;
sums[1][2] += stime;
break;
}
}
for (i = 0; i < 2; i++)
for (j = 0; j < 3; j++)
sums[i][j] /= n;
printf(1, "\n\nCPU bound:\nAverage ready time: %d\nAverage running time: %d\nAverage sleeping time: %d\nAverage turnaround time: %d\n\n\n", sums[0][0], sums[0][1], sums[0][2], sums[0][0] + sums[0][1] + sums[0][2]);
printf(1, "\n\nI/O bound:\nAverage ready time: %d\nAverage running time: %d\nAverage sleeping time: %d\nAverage turnaround time: %d\n\n\n", sums[1][0], sums[1][1], sums[1][2], sums[1][0] + sums[1][1] + sums[1][2]);
#endif
#ifdef SML
int i;
int n;
int j = 0;
int k;
int retime;
int rutime;
int stime;
int sums[3][3];
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
sums[i][j] = 0;
n = atoi(argv[1]);
i = n; //unimportant
int pid;
for (i = 0; i < n; i++) {
j = i % 3;
pid = fork();
if (pid == 0) {//child
j = (getpid() - 4) % 3; // ensures independence from the first son's pid when gathering the results in the second part of the program
#ifdef SML
switch(j) {
case 0:
set_prio(1);
break;
case 1:
set_prio(2);
break;
case 2:
set_prio(3);
break;
}
#endif
for (k = 0; k < 100; k++){
for (j = 0; j < 1000000; j++){}
}
for (k = 0; k < 100; k++){
for (j = 0; j < 1000000; j++){}
}
for (k = 0; k < 100; k++){
for (j = 0; j < 1000000; j++){}
}
for (k = 0; k < 100; k++){
for (j = 0; j < 1000000; j++){}
}
for (k = 0; k < 100; k++){
for (j = 0; j < 1000000; j++){}
}
exit(); // children exit here
}
continue; // father continues to spawn the next child
}
for (i = 0; i < 3 * n; i++) {
pid = wait2(&retime, &rutime, &stime);
int res = (pid - 4) % 3; // correlates to j in the dispatching loop
switch(res) {
case 0: // CPU bound processes
printf(1, "Priority 1, pid: %d, ready: %d, running: %d, sleeping: %d, turnaround: %d\n", pid, retime, rutime, stime, retime + rutime + stime);
sums[0][0] += retime;
sums[0][1] += rutime;
sums[0][2] += stime;
break;
case 1: // CPU bound processes, short tasks
printf(1, "Priority 2, pid: %d, ready: %d, running: %d, sleeping: %d, turnaround: %d\n", pid, retime, rutime, stime, retime + rutime + stime);
sums[1][0] += retime;
sums[1][1] += rutime;
sums[1][2] += stime;
break;
case 2: // simulating I/O bound processes
printf(1, "Priority 3, pid: %d, ready: %d, running: %d, sleeping: %d, turnaround: %d\n", pid, retime, rutime, stime, retime + rutime + stime);
sums[2][0] += retime;
sums[2][1] += rutime;
sums[2][2] += stime;
break;
}
}
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
sums[i][j] /= n;
printf(1, "\n\nPriority 1:\nAverage ready time: %d\nAverage running time: %d\nAverage sleeping time: %d\nAverage turnaround time: %d\n\n\n", sums[0][0], sums[0][1], sums[0][2], sums[0][0] + sums[0][1] + sums[0][2]);
printf(1, "Priority 2:\nAverage ready time: %d\nAverage running time: %d\nAverage sleeping time: %d\nAverage turnaround time: %d\n\n\n", sums[1][0], sums[1][1], sums[1][2], sums[1][0] + sums[1][1] + sums[1][2]);
printf(1, "Priority 3:\nAverage ready time: %d\nAverage running time: %d\nAverage sleeping time: %d\nAverage turnaround time: %d\n\n\n", sums[2][0], sums[2][1], sums[2][2], sums[2][0] + sums[2][1] + sums[2][2]);
#endif
exit();
}
sh.c
- 印出現在所用之排程方法為何
printf(1, "Selected scheduling policy: ");
#ifdef DEFAULT
printf(1, "Round Robin\n");
#else
#ifdef FCFS
printf(1, "FCFS\n");
#else
#ifdef SML
printf(1, "Priority\n");
#endif
#endif
#endif
syscall.c
- 宣告system call的關聯
extern int sys_set_prio(void);
syscall.h
- 宣告system call的代號
#define SYS_set_prio 24
makefile
- 新增指令進入點
UPROGS=\
_cat\
_echo\
_forktest\
_grep\
_init\
_kill\
_ln\
_ls\
_mkdir\
_rm\
_sh\
_stressfs\
_usertests\
_wc\
_zombie\
_GeneralTest\
_PriorityTest\
- 修改qemu需運用到的cpu核心數
ifndef CPUS
CPUS := 1
endif
sysproc.c
- 新增set priority及修改排程方法之system call
int sys_set_prio(void) {
int priority;
argint(0, &priority);
return set_prio(priority);
}
😎 結論
- 每種不同的系統提供 不同的服務，所適合的Schedular也不同 ，應該考慮使用情境之後依據需求挑選Schedular
- 而在實做Schedular時有幾個須注意到的點
- 加入priority時避免Starvation的問題
- Round Robin每次分配到使用CPU的時間長短都是需要依據狀況做調整的
- Schedular在OS中扮演極為重要的角色，一個好的schedular可以讓整個System的運作更加流暢
- 在設計Schedular時須注意到系統可能有好幾個core(Schedular)所以在偵錯時候可能出現結果會和心中所預想的結果不一樣，可以先將虛擬機設定為單核心（Schedular)，方便偵錯
📅 組員分工
B10415016 楊璿譯
- 撰寫system call
- 撰寫三種schedular演算法
- 研讀系統source code
B10415039 曾柏誠
- 撰寫test case program
- 資料查詢