Nachos Project Assignment 2

Presentation on theme: "Nachos Project Assignment 2"— Presentation transcript:

1 Nachos Project Assignment 2
CPU schedualing TA: Hung-Leng Chen

2 Assignment 1.Implement system call “Sleep”
2.Implement Shortest-Job-First scheduling

3 System Call: Sleep 1.請研究 userprog/exception.cc, userprog/syscall.h, test/start.s 這三個檔案以了解system call是如何實作的。 2.請實作Sleep(int x)這個system call,把呼叫這個system call的thread block住,並且在x次的timer interrupts以後才又回到READY的狀態。

4 System Call: Sleep (cont.)
The user program is responsible for (defined in code/test/start.s) Storing the system codes in Register 2 Storing the arguments in Register 4 ,5, 6, and 7. ExceptionHandler in code/userprog/exception.cc Fetch system call number in Register 2. Add new exception handler’s switch case in switch …case section Declare a new system call in code/userprog/syscall.h Define a new system call ID Declare the interface for Nachos system calls, which will be called by the user program.

5 System Call: Sleep (cont.)
The low level operation to support the new declared system call in code/test/start.s. .globl PrintInt .ent PrintInt PrintInt: addiu $2,$0,SC_PrintInt //*put system call number in register 2 syscall //* all parameter of this system call will be stored in //* register4, 5, 6, and 7 by MIPS machine automatically. j $31 .end PrintInt

6 System Call: Sleep (Hint)
1.修改exception.cc, syscall.h, start.s 2.修改thread/alarm.cc, thread/alarm.h, 增加WaitUntil(int x)來處理Sleep(int x)這個system call 增加一個class來管理這些因為呼叫Sleep(x)而處於BLOCK狀態的threads

7 System Call: Sleep (Hint)
Alarm.cc: 每一次的CPU timer interrupts都會呼叫CallBack()，將目前執行的thread yield. Your jobs: 記錄timer interrupts次數才知道sleep的thread是否該被叫醒 Create a thread list管理sleep中的thread WaitUntil(int x)將呼叫sleep system code的thread block, 放進sleep thread list中 記得要產生一個interrupt 記得要記錄這個thread要sleep x timer interrupts 呼叫thread->sleep(false)讓thread sleep。（在thread/thread.cc裡） WakeUp將thread叫醒 When? 每次timer interrupts時都要檢查整個sleep thread list,看看有誰該wake up. 偷吃步: 可以sort這個list, 只要檢查到有thread不用wake up,後面的list就不用再檢查了

8 SJF Scheduling Nachos 內定的 scheduling algorithm 是 Round-Robin, 我們接下來將加入 non-preemptive SJF scheduling 用n+1 = tn + (1- )n 來預估下一個CPU burst n : 第n個預估的CPU burst長度 tn : 第n個實際的CPU burst長度  : 取0.5, 0 = 0 (一次timer interrupt代表CPU burst加1 公式請參考課本156頁)

9 SJF Scheduling (Hint) 由於是non-preemptive，所以當timer interrupts時不用將thread yield. 什麼時候有可能換thread執行？ 需要記錄每個thread實際CPU burst長度(timer interrupts數目),與預測將來CPU burst長度 在哪裡可以得到這個資訊？ 何時該進行預測？ 可以寫成兩個版本,不強迫一定要用參數決定RR還是SJF. (寫出來的話會加分)

10 SJF Scheduling (Hint) Begin Running Per timer interrupt:
Invoke Sleep(x) Per timer interrupt: 1.Record actual CPU burst 2.叫醒應該起床的threads 1.Set next predicted CPU burst 2.Insert this thread to Sleeping thread lists 3.Invoke thread->Sleep

11 Deadline 5/23 24:00 am Please tar your code and to entitled as your_student_ID_p2.tar.gz make clean (submit source code only) tar zcvf r _p2.tar.gz nachos-4.0

12 Grading Policy Results of your project 70% Project 2 report 30%
請自行設計一組(或多組)test case來證明你的project是對的,針對RR scheduling和SJF scheduling都要能work。 同時放到nachos下面去run的thread,個數至少3個。 請將test result output印在報告中。 如何compile test program請參考project 1 reference solution. 助教的test case和result放在web上供大家參考