106 OS homework 2-2 成果報告書

組長：B10415028、張博雅、rich0432@gmail.com
組員：B10415029、呂芯萍
組員：B10401015、林恆毅
github: https://github.com/jenny86520/OS_HW-Group3

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

函式名稱	功能說明
pinit	初始化程序表(ptable)的Lock，將其初始值設為 0
allocproc	找到程序表中沒有使用到的程序(UNUSED)，如果有找到，則設定它的狀態為EMBRYO，分配空間給它，並回傳該程序的位址
growproc	將現在程序(cp)的空間擴展n個bytes，成功則回傳0，失敗則傳回-1
ksegment	設定cpu的資料，及其記憶體分配的位址，並初始化其區域變數和當前程序
usegment	設定使用者空間中segment的資料，如果當前程序為空，代表cpu為呆滯狀態，則須將segment的資料清空
fork	創建一個新的程序，其資料由當前程序複製過去，並設定其狀態為RUNNABLE。將其父程序(parent)指向當前程序，回傳其pid值
userinit	在main.c被調用一次，主要設定第一個程序的內容
scheduler	選擇一個可以執行的程序(RUNNABLE)來執行，透過 swtch 來執行下一個程序，當現在的程序釋放 cpu，且 swtch 返回 scheduler，scheduler 才能挑選下個程序，然後重複一樣的程序
sched	調用 swtch，將當前暫存器的值存起來，並將控制權交給 scheduler
yield	調用 sched，通常是在 cpu 時間(time slice)用完的時候會呼叫 yield。他會將原本程序的狀態由 RUNNING 改成 RUNNABLE，下次 scheduler 才能找到它並執行
forkret	程序第一次 swtch 會先到這裡，並且藉由呼叫 forkret1 返回 user mode
sleep	設定當前程序的頻道(chan)，將其狀態改成 SLEEPING，然後將控制權還給 scheduler，如果再次 switch 被喚醒，則將其頻道設為空
wakeup1	喚醒指定頻道上的所有程序，將他們的狀態設為 RUNNABLE
wakeup	調用 wakeup1
kill	將指定 pid 之程序的 killed 設為 1，如果其狀態 SLEEPING，則將其設為 RUNNABLE，此時並不會真正的殺掉這個程序，而是等到某個時間點執行到 trap 函式時，判斷如果其 killed 為 1，才會調用 exit 函式
exit	結束當前程序，將其狀態改成 ZOMBIE，同時喚醒其父程序。如果它有子程序，也將他們的狀態改成 ZOMBIE，並將他們的父程序(parent)指向 initproc
wait	如果當前程序有子程序的狀態為 ZOMBIE，則將其子程序空間釋放，並且回傳其子程序的 pid，若其沒有子程序則回傳 -1
procdump	除錯用，顯示程序的狀態

😇 成功畫面

我們測試了:

兩個CPU-bound process
(跑 100 次 1000000 次的迴圈)
兩個short tasks based CPU-bound process
(跑 100 次 1000000 次的迴圈) &
(在每一次100次迴圈後 yield CPU)
兩個I/O bound process
(我們使用sleep)

General sanity test

FCFS (First come - First Served)

SML (Multi - level queue scheduling)

Priority scheduling test (SML)

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

Scheduling policy

修改的檔案：

Main： proc.c, sanity.c , SMLsanity.c
Others： Makefile, param.h, , syscall.c, syscall.h, sysproc.c, user.h, usys.S, console.h

FCFS

FCFS(first come first serve)是先來先做的意思，所以我們找過所有ptable的proc時找出最小的ctime(creation time)，也就是最先抵達的意思(愈小的process)，優先取得CPU控制權，然後執行它。一旦一個 process 佔用了 CPU，它就會一直使用直到終止。

這是SML最主要的function,用來尋找下一個process來執行。
SML是一種擁有固定優先權的排程。
將單一層的ready queue 進一步分成許多優先權等級的ready queue，以下的code中case3是最高priority，case2是中的priority，case1則是最低的priority。每個process會有一個適當的優先權位置，若是沒發現任何的process在這些case當中，將直接return掉。

這個部分則是先將priority設成最高，利用上面的function來尋找下一個process並決定優先權。
SML的特點是能增加scheduling design的flexbility但會有starvation的現象。

Sanity Test

general sanity test
fork出3*n個process

 3n分別為以下三點：
1. process with (pidmod 3 = 0)－CPU-bound process (CPU)
 - 執行100次的1000000次迭代(iterations)的虛擬循環(dummy loop)
2. process with (pidmod 3 = 1)－short tasks based CPU-bound process (S-CPU)
 - 執行100次的1000000次迭代(iterations)的虛擬循環(dummy loop)
 - 等待100次虛擬循環結束，對CPU執行yield 
      [yield：用來指派執行另一個process (0：successful / -1：otherwise)]
3. process with (pidmod 3 = 2)－I/O bound process (IO)
 - 模擬100次I/O的等待(*sleep(1)*)，使其虛擬睡眠(dummy sleeps)

priority schedule test (SML)

執行排程決定優先權(set_prio())

Print
process
- ID
- type (CPU / S-CPU / IO)
- ready time, run time, sleep time, turnaround time

fork 3 * n 結束後的結果 (對於每一種process type的時間)
- Average ready time (平均等待CPU的時間)
- Average run time (平均執行時間)
- Average sleep time (平均sleep的工作時間)
- Average turnaround time (平均工作完成的時間)

😎 結論

討論了一個月的報告內容，最後決定實做兩種不同的排程、產生process與SML排程的測試。

FCFS

了解到FCFS是先進先做，因為不可以插隊成為了最公平的方法，但無法防止Convoy Effect(有點類似塞車)，所以排班效益最差，唯一的好處就是易於實作。

SML則是有固定優先權的排程，能插隊(Queue與Queue之間的排班多採取preemptive priority)，雖會造成不公平的現象，但可以增加scheduling design的flexibility，唯一的缺點是無法預防starvation的發生且不允許process在各個queue中移動。

Sanity Test

測試程式學習到fork的使用與排程的使用，由測試結果可知優先權的排列情況與時間長度。

📅 組員分工

林恆毅First come - First Served (FCFS)
Modify the code and let it work.
Test the final code and print it out.
張博雅Multi - level queue scheduling (SML)
Reasearch how the schedule works.
Add the comment by ourself on the code.
呂芯萍Sanity Test
Find the code which needs to modify.
To sum up all the file.
Push file to github.