106 OS homework 2-2 成果報告書

組長：F10615008、劉林
組員：F10615007、杜致遠
github: https://github.com/sixzeroo/xv6-public

🙂 使用情境說明(包含流程圖)

Lazy Allocation Memory

正常情況下process都是先申請Memory，然後再使用。但是有一個process有的時候會一次性申請非常多的Memory，但是可能又不會用到，比如說多餘的array空間。

所以就可以進行一些優化，當process申請的時候不給其分配Memory，直到其使用這個Memory的時候才allocate memory 給這個process。

實作Lazy Allocation Memory主要分為兩個部分：申請Memory的時候不實際分配Memory、使用的時候Allocate memory

申請Memory的時候不實際分配Memory

當process申請Memory的時候只是增加process的Memory大小指標，但是不給其分配實際的memory：

原來process申請Memory的流程：

修改以後，只增加process的size而不實際分配Memory：

使用的時候Allocate memory

當process真正需要使用Memory的時候回因為找不到address而發生page fault，這個時候再allocate memory：

Scheduling:Multilevel feedback queue with priorit

通過proc.c中的scheduler部份我們可以看出xv6採用的是Round Robin算法來進行排程，由於這個排程演算法非常簡單，缺乏靈活性，因此我們修改了scheduler部份，實現一個帶priority的multilevel feedback queue，在每個隊列中採用優先級高的程序先執行的算法，在各個隊列之間優先級越低的隊列有越多的執行時間。這樣我們可以將系統程序的優先級提高，也可以手動修改程序的priority從而指定某些程序優先執行。

基本設置

增加systemcall以及用戶程序說明

演算法說明

第一隊列中包含priority為0-3的程序，第二隊列中包含priority為4-14的程序，第三隊列中包含priority為15-20的程序。

第一隊列中的程序每次分到一個時間片，即1/100sec，除非手動調整否則其priority不會發生改變。
第二隊列中的程序每次分到500（為了便於顯示效果，此處將數據設定得比較大）個時間片，即5sec。為了避免starvation，執行5sec後該程序的priority就會+1，當其priority達到15，即進入第三隊列。若有新的程序產生且其優先級高於它，則會轉去執行優先級更高的程序。
第三隊列中的程序每次分到1000個時間片，即10sec。每執行1000個時間片，priority即+1，直到其priority升到20為止。

對於init和sh我們分配了最高的優先級0，其他從shell中執行的程序我們會分配優先級為4，都屬於第一隊列；對於其他程序，像fork出來的子程序，默認優先級為5。

流程圖

系統運行流程圖

實際上運行起來之後就是在scheduler中的swtch(&(c->scheduler),p->context)和shed中的swtch(&p->context,mucpu()->scheduler)這兩行代碼之間來回切換

scheduler部份，原始流程圖

scheduler部份，修改後的流程圖

😇 成功畫面

Lazy Allocation Memory

Scheduling:Multilevel feedback queue with priorit

default priority

初始時，可以看到init和sh的priority最高，從shell執行的ps的priority為4

從shell執行的mkprc默認priority也是4，但是fork出的子程序默認priority為5

第二隊列（priority：5～14）priority增加情況

可以看到當7（pid）運行了500個時間片後，他的優先級就會由5上升到6，時間片重新開始計數

第三隊列（priority：15～20）priority增加情況

在執行了1000個時間片之後，11的優先級由15變成了16

優先級高的process會優先執行

可以看到，由於18的優先級較7要高，所以一直在執行18，7的priority(11)和rrnum(312)都沒有發生變化，說明它並沒有得到執行，且18每執行500個時間片後，

修改程序的優先級

用chpr程序將6的priority由10變為6（紅色部分）；藍色部份可以看到6的優先級提高後將一直執行優先級較高的6。

🏃 實作過程(修改哪些檔案[含圖片])

Lazy Allocation Memory

修改核心部分：

sysproc.c

diff --git a/sysproc.c b/sysproc.c
index 0686d29..ed1021f 100644
--- a/sysproc.c
+++ b/sysproc.c
@@ -45,14 +45,23 @@ sys_getpid(void)
 int
 sys_sbrk(void)
 {
-  int addr;
+  int addr,newsz;
   int n;
+  struct proc *p;

   if(argint(0, &n) < 0)
     return -1;
-  addr = myproc()->sz;
-  if(growproc(n) < 0)
-    return -1;
+  p = myproc();
+  addr = p->sz;
+  newsz = addr + n;
+  // 不能够超过kernel virtual address
+  if(newsz >= KERNBASE)
+         return -1;
+  // 只改變adress而不分配Memory
+  p->sz = newsz ;
+//  if(growproc(n) < 0)
+//    return -1;
+  cprintf("pid %d sbrk memory but not allocate physical memory\n",p->pid);
   return addr;
 }

trap.c

diff --git a/trap.c b/trap.c
index 41c66eb..3b6e2d0 100644
--- a/trap.c
+++ b/trap.c
@@ -47,6 +47,29 @@ trap(struct trapframe *tf)
   }

   switch(tf->trapno){
+
+  // 出现page fault情况的处理
+  case T_PGFLT:
+  {
+    uint a = PGROUNDDOWN(rcr2());
+    struct proc* p = myproc();
+
+    // allocate pyhsical memory , return address
+    char *mem = kalloc();
+    // 没有memory 可以分配的情况
+    if(mem == 0)
+    {
+      cprintf("kalloc error : out of memory!\n");
+      // 结束proces
+      p->killed = 1;
+    }
+    // 清空memory
+    memset(mem,0,PGSIZE);
+    // 创建一个与其相连的一个virtual memory 的PTEs
+    cprintf("pid %d trap page fault, allocate memory to it \n",p->pid);
+    mappages(p->pgdir, (char*)a, PGSIZE, V2P(mem), PTE_W|PTE_U);
+    break;
+  }
   case T_IRQ0 + IRQ_TIMER:
     if(cpuid() == 0){
       acquire(&tickslock);

Scheduling:Multilevel feedback queue with priorit

主要修改：proc.c中的scheduler函數

void
scheduler(void)
{
  struct proc *p;
  int prev_priority=201;
  for(;;){
    // Enable interrupts on this processor.
    sti();

    // Loop over process table looking for highest priority process
    acquire(&ptable.lock);
    for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
      if(p->state != RUNNABLE)
        continue;
      if(p->priority < prev_priority){
          prev_priority = p->priority;
      }
    }

    //Loop over process table to schedule high priority process:
    for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
      if(p->state != RUNNABLE)
        continue;
      if(p->priority == prev_priority){

      // 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);
        p->state = RUNNING;
        swtch(&cpu->scheduler, p->context);
        switchkvm();

        // Process is done running for now.
        // It should have changed its p->state before coming back.
        proc = 0;
      }
    }
    release(&ptable.lock);
  }
}

proc.c中的cps

int
cps()
{
  struct proc *p;

  //enable interrupts on this processor.
  sti();

  //loop over process table looking for process with pid
  acquire(&ptable.lock);
  cprintf("name \t pid \t state \t \t priority rrnum \n");
  for(p= ptable.proc; p < &ptable.proc[NPROC]; p++){
    if(p->state == SLEEPING )
      cprintf("%s \t %d \t SLEEPING \t %d \t %d\n ", p->name,p->pid,p->priority,p->rrnum);
    else if(p->state == RUNNING)
      cprintf("%s \t %d \t RUNNING \t %d \t %d\n ", p->name, p->pid,p->priority,p->rrnum);
    else if(p->state == RUNNABLE)
      cprintf("%s \t %d \t RNNABLE \t %d \t %d\n ", p->name, p->pid,p->priority,p->rrnum);
  }

  release(&ptable.lock);

  return 22;
}

proc.c中的chpr

int
chpr(int pid,int priority)
{
  struct proc*p;

  acquire(&ptable.lock);
  for(p=ptable.proc; p<&ptable.proc[NPROC];p++){
    if(p->pid == pid){
      p->priority = priority;
      break;
    }
  }
  release(&ptable.lock);

  return pid;
}

用戶程序chpr.c

include "types.h"
#include "stat.h"
#include "user.h"
#include "fcntl.h"

int 
main(int argc, char *argv[]){
  int priority, pid;

  if(argc<3){
    printf(2,"usage: nice pid priority\n");
    exit();
  }
  pid=atoi (argv[1]);
  priority = atoi(argv[2]);
  if(priority<0||priority>20){
    printf(2,"invalid priority(0-20)\n");
    exit();
  }
  printf(1,"pid=%d,pr=%d\n",pid,priority);
  chpr(pid,priority);

  exit();
}

另外有修改

😎 結論

在實作的過程中發現實際操作系統的修改要比單純的設計算法複雜許多。因為對於xv6的整個系統沒有完整徹底的了解，在修改系統的過程中自己覺得邏輯成立的修改卻引發了許多不明所以的bug。雖然許多bug到現在還是不明所以，但是整個的修改過程中學到了很多知識，除了熟悉了主要修改部分的排程演算法在系統整合的過程中對於整個系統初始化，process分配Memory的過程，運行，分頁，user和kernel之間的切換，時鐘中斷的概念等，也有了更深的理解。

📅 組員分工

Lazy Allocation Memory:劉林
Scheduling:Multilevel feedback queue with priorit：杜致遠