106 OS homework 2-2 成果報告書

組長：B10415048、楊宗儒
組員：B10415040、杜佳謙
github: https://github.com/s2g090123/xv6-public

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

我們此次project實作process scheduling的功能，實作了三種排程方法，包含xv6預設的Round-Roubin Algorithm(RR)、Priority Algorithm、Lottery Algorithm。以下介紹這三種排程以及各自的流程，我們將逐一說明:

Round-Roubin Algorithm(RR)
為了公平地調度process，RR採用time-sharing的方式，每個process提供一個CPU允許的時間，一旦時間到，就會強迫它離開CPU。

Priority Algorithm
每個process都會有一個屬於自己的priority，就是決定哪個process要先執行的順序，priority值越低的優先度越高，反之則優先度越低。
但是此方法會有可能造成satarvation，因為優先度高的process將被高頻率的呼叫，會導致優先度低的process無法被執行，故會發生starvation。我們為了解決starvation的問題，當我們的process做完要換人做的時候，便會將剛剛running process的priority降低，而在runnable process增加，這樣就可以將starvation的問題解決。

Lottery Algorithm
Lottery Algorithm是一種採用機率的調度方法，剛開始我們讓每個process所持有的票是相同的，系統會隨機選取票來選擇下一個要執行的process。
我們可以給予一個process持有相對大量的票，使得他獲得相對較高的選擇機會。
Lottery Algorithm解決了starvation問題，它確保每一個process手中都至少持有一張票，被選擇的機率絕對不會是0。

😇 成功畫面

透過createp，生成兩個子process，進行比較。
Round-Roubin Algorithm(RR)

Priority Algorithm
子process的priority值初始為10。
可透過nice來更改process的priority值。

以下為透過每次的priority +1-1，來解決starvation問題。

Lottery Algorithm
初始持有的ticket為1。
可透過nice來更改process持有的ticket。

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

在makefile中
此次project新增的system call為以下三個:

在show.c中
用來顯示ptable中processes的狀態、pid、parent id、priority、ticket、runtime、name。

在createp.c中
新增子process，以便我們測試scheduling。

在init.c中
print出我們現在所使用的排程方法。

在nice.c中
用來更改processes的priority、tickets。

在proc.c中
實作修改process的priority

實作修改process的ticket

計算runnable processes中總共的tickets

實作Default(RR)

實作Priority

加上priority +1-1，解決starvation

實作Lottery

😎 結論

scheduler在OS中是個不可或缺的腳色，好的scheduler可以增加系統的效能，壞的scheduler則會使整個系統當掉。
沒有所謂最好的scheduler，只有在看當下環境，以及所要提供的服務，來決定最適當的scheduler。

在實作的過程中，除了要想出新的排程方法之外，還要去想這個排程是否會造成starvation，像此次project中，我們所使用到的變數priority、ticket，在process中新增他們，是否就會因此造成問題，在想出starvation問題的解答，使得這次的project增加了許多困難度。

📅 組員分工

B10415048 楊宗儒 新增system call、新增priority scheduler、解決starvation問題

B10415040 杜佳謙 新增system call、新增lottery scheduler、資料查詢