作业系统 Project 4.doc

1、1作業系統 Project 4實做 semaphore 系統呼叫繳交日期：請上課程網頁查詢繳交網頁：請上助教課程網頁提供檔案：proj4.zip 上繳檔案；awkos_sem.hawkos_sem.c1. 簡介：Unix 為 semaphore 提供了一組系統呼叫。在上一個 project 中，P(S),V(S)實際上是包裝了 Unix 系統呼叫 semget, semop, 以及 semctl。semget 用來向作業系統要求一個 semaphore array。semop 用來增減 semaphore 的值。而 semctl 用來讀取 semaphore 的資訊。不過因為 Unix 的 s

2、emaphore 系統呼叫的參數與功能過於複雜。本作業已經幫你做許多的簡化。要完成本作業，你只要實做兩個系統呼叫如下：int sys_semget(int ipc_key, int init_val);int sys_semop(int semid, int op);sys_semget 的功能是要求作業系統配置一個 semaphore。此系統呼叫接受一個整數與一個初始值。第一個整數稱之為 ipc_key。兩個 user processes 如果想要共同存取同一個 semaphore，必須在呼叫 sys_semget() 時給定相同的 ipc_key。同學可以參照測試用的 test1.c 與

3、test2.c 了解 sys_semget 的用法。sys_semget 的細部功能如下：此系統呼叫首先搜尋已存在的semaphore，檢查是否有某個 semaphore 擁有一樣的 ipc_key。若有，則傳回該 semaphore 的 semphore id，並忽略初始值。若沒有，則配置一個新的semaphore，並按照 init_val 初始化新的 semaphore。最後，傳回新的semaphore 的 semaphore id。sys_semop 的功能是用來增減 semaphore 的值。sys_semop(semid,-1) 相當於 P(semid),而 sys_semop(se

4、mid,1) 相當於 V(semid)。也就是說，當 user 2program 執行 sys_semop(semid,-1) 時，若 semaphore 的值已經小於等於0，則把 semaphore 的值減 1，然後 block 此 user program，把此 user program 從 runqueue 移除，然後串連到此 semaphore 的 wait queue 中。然後呼叫 schedule 安排下一個 user process 來執行。相反的當 op = 1 而有一個以上的 process 等待在此 semaphore 的 wait queue，此系統呼叫除了增加semap

5、hore 的值之外，還按照先來先到的順序，從 wait queue 移除一個process 到 runqueue 當中。為了簡化你們的實做，請假定 op 的可能值只有 1 或-1。呼叫成功時傳回 0，若失敗時傳回-1。2. 檔案內容解說此次所提供的檔案與第二個作業 (實做 sys_sleep) 相差不多。關於 Linux 如何用 process_list 串連所有 process，以及用 runqueue 串連所有可執行的processes 等等的資料結構，請自行下載 project 2 的 handout。上述待完成的兩個系統呼叫 templates，全部都放置於 awkos_sem.c。3

6、. 實做步驟解說在 sem.h 中已經幫你定義了一個 semaphore 的資料結構 sem_struct。你可以依需要自行刪減。在 sem.h 中還用 sem_struct 宣告了 semarray。在這個array 中的每一個 sem_struct，若 used 為 0 時則表示這個 sem_struct 目前沒有人使用。若 used 為 1 時則表示目前這個 sem_struct 已經配置給一個semaphore 使用，而其 array index 就是這個 semaphore 的 semaphore id。 所以當 sys_semget 被呼叫時，請先搜尋 ipc_key 是否等於任何

7、一個使用中的 sem_struct 的 ipc_key。若有，則傳回該 sem_struct 的 array index 即可。若找不到，則請找一個未使用的 sem_strcut 來配置給新的 semaphore。sem_struct 中最重要的 field 是 list_head semqueue_head。它用來把blocked 在這個 semaphore 的 processes 的 task_struct 串連起來。例如，假設目前 process_list 有四個 processes，而呼叫 sys_semop(semid,-1)的 process 為 test1.c.，所以 curre

8、nt 指向 test1.c，如圖 1 。這時候在 sys_semop 裡面應該先呼叫 list_del( 把 test1 的 task_struct 串連到 semqueue_head 所帶頭的 wait queue 中。結果如圖 2。在圖 2 中，底下顯示了其中一個 sem_struct。它包含了一個 semqueue_head，用來串連 block 在此 semaphore 的所有processes。3圖 1。圖 2。做完上述的資料結構處理之後，此時 sys_semop 應該呼叫 schedule()以便從runqueue 中找出下一個 process 來執行。假設過了一段時間之後，tes

9、t2 也呼叫 sys_semop(semid,-1)而 block 在這個semaphore 上。則圖 2 將變成如圖 3。4圖 3反過來說，當 sys_semop(semid,1) 被呼叫時，此系統呼叫應該從semqueue_head 的最前面叫醒 test1，把 test1 放回 runqueue 中，讓 test1 能被排程起來繼續執行。4. 正確的輸出結果提供的檔案中有兩個測試檔 test1.c test2.c. 當你的實做完整而且正確時，編譯之後的執行檔的執行結果應該是111111122222211111112222221111111222222.編譯的方法在 project 2 的 handout 中有描述。或者你直接執行 make 即可。55. 注意事項你應該完整的測試你實做的系統呼叫，助教將準備額外的測試檔來測試你的實做。