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

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

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的狀態。

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.

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

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

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就不用再檢查了

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頁)

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

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

Deadline 5/23 24:00 am Please tar your code and e-mail to kidd@arbor.ee.ntu.edu.tw entitled as your_student_ID_p2.tar.gz make clean (submit source code only) tar zcvf r92921100_p2.tar.gz nachos-4.0

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上供大家參考