內核同步原語 操作系統(tǒng)課程設計

1、青島理工大學操作系統(tǒng)課程設計報告院（系）： 計算機工程學院 專業(yè)： 計算機科學與技術 班級： 計算131 學生姓名： 鐘曉俊 學號： 201307020 魏正迪 201307025 題目： 設計內核同步原語 起迄日期: 2016.06.27-2016.07.08 設計地點: 現代教育中心303 指 導 教 師: 熊曉云 20152016年度 第 2 學期完成日期: 2016 年 7 月 13 日一、 課程設計目的通過本次課設，掌握操作系統(tǒng)中信號量signal（）與wait（）的工作原理，和在Linux內核中增加系統(tǒng)調用函數的方法，了解對Linux內核重新進行編譯、連接的過程。另編寫一個用戶測試

2、程序，調用新添加的的系統(tǒng)調用。在此期間，可以進一步熟悉Linux系統(tǒng)操作，初步接觸到嵌入式系統(tǒng)。同時，通過模擬實現的方式來體現操作系統(tǒng)的管理原理與算法，進而深刻理解操作系統(tǒng)的運行機制和數據結構?？梢蕴岣哌\用操作系統(tǒng)知識解決實際問題的能力；鍛煉實際的編程能力、創(chuàng)新能力及團隊組織、協作開發(fā)軟件的能力；還能提高調查研究、查閱技術文獻、資料以及編寫軟件設計文檔的能力。二、 課程設計內容 1、設計要求： 1)要求設計三個原語實現操作系統(tǒng)中信號量signal（）與wait（）功能：Request（）、Release（）和Broadcast（）。 Request（）類似wait（）操作，該原語允許多個進程因

3、一個事件而阻塞，每次產生阻塞時均會發(fā)出一個消息，“有多少個進程處于阻塞狀態(tài)?！?Release（）類似signal（）操作，當一個進程產生這個事件的信號時，該原語會喚醒處于阻塞隊列中的第一個進程，并發(fā)出一個消息“進程XX解除了阻塞狀態(tài)，尚有XX個進程處于阻塞狀態(tài)?！保蝗绻谛盘柈a生時，沒有進程因為這個事件阻塞，那么這個信號無效，不產生任何消息。 Broadcast（）是類似一個廣播操作，當一個進程產生這個事件的信號時，該原語會喚醒處于阻塞隊列中的所有進程，并發(fā)出一個消息“廣播，所有進程解除了阻塞狀態(tài)?！?；如果在信號產生時，沒有進程因為這個事件阻塞，那么這個信號無效，不產生任何消息。 2)編寫一

4、個測試程序，驗證原語的正確性。 3)要求在實驗報告中列出Linux內核的版本與編譯過程。 2、小組成員分工如下：鐘曉俊負責課程設計報告的編寫及協助魏正迪查找資料； 魏正迪負責內核的配置并在其Linux內核中添加系統(tǒng)調用，進行程序測試等。三、 系統(tǒng)分析與設計1、系統(tǒng)分析操作系統(tǒng)對進程的控制是依據用戶命令和系統(tǒng)狀態(tài)來決定的。進程控制的功能是創(chuàng)建和撤消進程，完成進程狀態(tài)的轉換。進程控制程序屬于操作系統(tǒng)的內核程序。 一條原語由若干條機器指令組成，是機器指令的延伸，能完成一個特定的功能，是一種特殊的系統(tǒng)調用命令。它的特點是執(zhí)行時不可中斷，且不允許原語并發(fā)執(zhí)行，即原子性。 對系統(tǒng)中所有

5、進程的生命歷程進行控制的原語稱為進程控制原語，與進程控制有關的操作原語有：創(chuàng)建原語（create）、停止原語（halt）、掛起原語（suspend）、激活原語（active）、阻塞原語（block）、喚醒原語（wakeup）等基本原語。 內核是系統(tǒng)的控制和協調的中心，在管態(tài)下運行。功能需求如下： 1)Linux內核的編譯安裝過程并添加系統(tǒng)調用。 2)設計三個原語（Request、Release、Broadcast）實現操作系統(tǒng)中信號量signal（）與wait（）功能。 注：Request原語實現某進程請求一個資源的功能； Release原語實現某進程釋放一個資源的功能； Broad

6、cast原語實現廣播喚醒所有進程并釋放它們的功能。 3)編寫一個用戶測試程序，驗證設計原語的正確性。數據需求的數據流圖如圖1所示： 操作員事件隊列 建立事件事件資源數 阻塞事件 可用資源數釋放一個事件 操作員 釋放所有事件 事件資源數資源數 總資源數 資源數資源數資源數 資源數資源數圖1 數據需求的數據流圖重要數據結構的說明，以及在關鍵算法中的作用如下： （1）進程阻塞需要一個等待隊列，所有等待同一事件號的進程都掛接到該隊列。所以我們需要定義一個結構體myevevt_t，包含事件號eventnum，資源數目value以及等待隊列的指針等數據 （2）另外我們需要定義兩個全局的指針變量來為實現事件

7、的隊列操作：分別是鏈頭指針myevent_t * lpmyevent_head 和鏈尾指針myevent_t * lpmyevent_end 。這里著重說明信號量機制的實現；增加了變量資源數value，每次進行wait（）操作的時候，判斷資源數是否足夠，如果資源數足夠，則將資源數減1，否則將進程放到一個等待隊列中去；每次進行signal（）操作時候，本系統(tǒng)中只需要判斷等待隊列上是否有進程在等待，如果沒有，說明現在的資源數是充足的，沒有進程出現等待的現象，需要將資源數加1；如果等待隊列上已經有進程在等待，需要將隊列頭部的進程喚醒。其中最重要的是對資源數的同步實現，對于資源計數，本系統(tǒng)使用了原子變

8、量。（3）在進程添加到隊列的時候，使用了獨占等待的方法，使用了add_to_queue_exclusive,該函數將進程放到指定的隊列尾部，而且置上exclusive標記。 在阻塞時，Request中使用一個函數來使相應進程阻塞。 在喚醒時，Release中使用wakeup()將指定隊列上的進程喚醒，Broadcast使用一定的函數喚醒所有進程。2、系統(tǒng)設計：設計的內核同步原語要求具有以下功能：能夠使多個進程阻塞在某一特定的事件上,直到另一進程完成這一事件釋放相關資源,給內核發(fā)送特定消息然后由內核喚醒這些被阻塞的進程。如果沒有進程阻塞在這個事件上,則消息被忽略。為了實現這些功能，可以編寫 4

9、個系統(tǒng)調用來實現這些功能要求:1)新建一個事件的系統(tǒng)調用函數:int sys_Create(int eventNum,int value);生成一個事件,返回該事件的 ID,如果參數為 0,表示是一個新的事件,否則就是一個已經存在的事件。2)將進程阻塞到一個事件的系統(tǒng)調用函數:int sys_Request(int eventNum);進程阻塞到 eventNum 事件,直到該事件完成才被喚醒。3)喚醒一個阻塞進程的系統(tǒng)調用函數:int sys_Release(int eventNum);喚醒一個等待eventNum 事件的進程,如果隊列為空,則忽略。4)撤銷所有阻塞進程的系統(tǒng)調用函數:int

10、 sys_Broadcast(int eventNum);喚醒所有等待eventNum事件的進程，如果信號產生時，隊列為空，則無效。然后我們需要把代碼集成到內核中，然后進行測試，主要工作如下： 設計事件的數據結構和系統(tǒng)調用函數。 1)說明一個事件查找函數。 2)建立或查找事件的系統(tǒng)調用，它返回建立的信事件的編號。 3)等待事件的系統(tǒng)調用。 4)喚醒等待事件進程的系統(tǒng)調用。 5)撤銷某個事件的系統(tǒng)調用。 6)重新編譯內核，用新內核重啟系統(tǒng)。 7)測試設計的同步機制。3、模塊設計：程序模塊圖如圖2所示： 內核同步原語查找事件scheventNum()創(chuàng)建事件Create()阻塞事件Request(

11、)喚醒事件Release()撤銷事件Broadcast()圖2 程序模塊圖建立事件的系統(tǒng)調用函數流程圖如圖3所示： 開始 運行函數Create() 事件數不為零Y 遍歷已存在的事件N創(chuàng)建新事件事件是否 定位到位？Y返回事件號 結束N return 0圖3 建立事件Create()的系統(tǒng)調用函數流程圖阻塞事件Request()的系統(tǒng)調用函數流程圖如圖4所示： 開始遍歷存在事件 是否定位到 事件？YN資源數減1返回事件號 結束 資源數>0?獲取事件的資源數Y 阻塞，等待被喚醒然后 資源數value減1 return 0YN圖4 阻塞事件Request()的系統(tǒng)調用函數流程圖喚醒一個阻塞事件R

12、elease()的系統(tǒng)調用函數流程圖如圖5所示： 開始遍歷存在的事件 是否定位到 事件？YN資源數value減1返回事件號 結束 value>0?獲取事件的資源數Y 阻塞，等待被喚醒然后 資源數value減1 return 0YN圖5 喚醒一個阻塞事件Release()的系統(tǒng)調用函數流程圖喚醒所有阻塞進程Broadcast()的系統(tǒng)調用函數流程圖如圖6所示： 開始遍歷已存在事件 是否定位到 事件？YN返回事件號 結束調用wake_up_all(),喚醒多有阻塞進程Y return 0kfree(releaseItem)，釋放事件結點圖6 喚醒所有阻塞進程Broadcast()的系統(tǒng)調用函

13、數流程圖四、系統(tǒng)測試與調試分析1、系統(tǒng)測試（1）新建事件Create()的系統(tǒng)調用函數功能測試表測試說明測試名稱內核同步原語測試目的驗證添加的系統(tǒng)調用功能是否成功實現測試技術單元測試測試方法黑盒測試法測試用例測試內容新建事件Create()的系統(tǒng)調用函數功能測試數據申請的資源數：3預期結果成功創(chuàng)建一個事件，事件號為:XX資源數為：3測試結果成功創(chuàng)建一個事件，事件號為:XX資源數為：3（2）阻塞事件Request()的系統(tǒng)調用函數功能測試表測試說明測試名稱內核同步原語測試目的驗證添加的系統(tǒng)調用功能是否成功實現測試技術單元測試測試方法黑盒測試法測試用例測試內容阻塞事件Request()的系統(tǒng)調用函

14、數功能測試數據事件號：XX預期結果已經成功申請一個資源給事件XX測試結果已經成功申請一個資源給事件XX（3）喚醒事件Release()的系統(tǒng)調用函數功能測試表測試說明測試名稱內核同步原語測試目的驗證添加的系統(tǒng)調用功能是否成功實現測試技術單元測試測試方法黑盒測試法測試用例測試內容喚醒事件Release()的系統(tǒng)調用函數功能測試數據事件號：XX預期結果已經釋放了事件XX的一個資源測試結果已經釋放了事件XX的一個資源（4）喚醒所有事件Broadcast()的系統(tǒng)調用函數功能測試表測試說明測試名稱內核同步原語測試目的驗證添加的系統(tǒng)調用功能是否成功實現測試技術單元測試測試方法黑盒測試法測試用例測試內容喚

15、醒所有事件Broadcast()的系統(tǒng)調用函數功能測試數據事件號：XX預期結果已經釋放了事件XX的全部資源測試結果已經釋放了事件XX的全部資源預期結果如下：2、調試分析這次遇到的主要問題是內核的編譯和向內核中增加新的系統(tǒng)調用。內核的編譯對細節(jié)要求很高。1>例如：當你新添加的系統(tǒng)調用的函數為無參的函數時void name()這種格式并不正確，正確的格式為void name(void);用第一種形式時，進行內核編譯操作(# make install)時會有錯誤提示。2>由于內核中的文件都是只讀文件，并沒有修改的權限，所以需要用root權限來對文件進行操作，進行操作的方式有兩種：第一種是

16、#gedit 文件路徑 然后直接保存；第二種為#vi 文件路徑 這種方式最后退出的時候需要用特定的命令才能保存#w !sudo tee % 通過這種方式進行保存。方式一中會遇到時間超時的提示(自己覺得是文件太多，檢索時間過長)，只有用第二種方式。3>調試小技巧：當編譯內核成功時，但是系統(tǒng)調用調不出來，卡死或者以殺死時，需要使用printk內核調試函數例如：最后通過命令dmesg命令查看程序從哪里中斷，就在那里解決。提醒內核編譯繁瑣，容易出錯，要耐心。五、用戶手冊.本實驗在ununtu14.04系統(tǒng)上操作，原來內核為4.2.2，要編譯的內核版本為3.14.57。到linux官網https:

17、//下載純凈的內核源碼linux-3.14.57.tar.gz將下載到的壓縮包移動到根目錄下/usr/src目錄下；通過命令將源碼解壓tar vxf linux-3.14.57.tar.gz linux-3.14.57 然后進入linux-3.14.57目錄下操作(此次操作大部分都在此目錄下操作)1. 獲取權限并進入內核解壓目錄2.修改文件 a.在文件中添加系統(tǒng)調用 b.修改系統(tǒng)調用表的內容 c.寫入系統(tǒng)調用處理程序聲明注：聲明的順序必須和調用表的順序一樣3. 安裝工具#apt-get install libncurses5-dev4. 清除以前編譯的內核信息#ma

18、ke mrproper（第一次編譯不需此命令）5. 配置內核#make oldconfig6.編譯內核#make -j87.安裝模塊#make modules_install8. 安裝內核#make install9. 創(chuàng)建initrd文件mkinitranfs 3.14.57 -o /boot/initrd.img-3.14.5710. 更新引導項update-grub11. 重啟reboot之后啟動頁面會出現新編譯的內核和原有的內核選項進行選擇12. 重啟之后查看內核已使用新的內核13. 調用新加的系統(tǒng)調用(1).創(chuàng)建后多次申請資源，直到阻塞(2).打開新的終端，釋放資源，終端1中的進程自

19、動釋放(3).多個程序阻塞時，打開新的終端調用broadcast釋放所有的14. 執(zhí)行dmesg查看系統(tǒng)調用中printk打印輸出的信息六、程序清單新加的系統(tǒng)調用函數源碼1.yuan.c#include <linux/wait.h>#include <linux/sched.h>#include <linux/slab.h>#include <asm/atomic.h>typedef struct _myeventint eventNum;atomic_t value;wait_queue_head_t p; struct _myevent *n

20、ext;myevent_t;myevent_t * lpmyevent_head = NULL ; myevent_t * lpmyevent_end = NULL ;myevent_t * scheventNum(int eventNum, myevent_t *prev)myevent_t *tmp = lpmyevent_head;*prev = NULL;while(tmp)if(tmp->eventNum = eventNum)return tmp;*prev = tmp;tmp = tmp->next;return NULL;asmlinkage int sys_Cre

21、ate(int eventNum,int value)myevent_t *new_event = 0;myevent_t *prev = 0;int result ;if(!scheventNum( eventNum, &prev) new_event = (myevent_t *) kmalloc(sizeof(myevent_t),GFP_KERNEL);init_waitqueue_head(&new_event->p);new_event->next = NULL;new_event->p.task_list.next = &new_even

22、t->p.task_list;new_event->p.task_list.prev = &new_event->p.task_list;if(!lpmyevent_head)new_event->eventNum = eventNum;lpmyevent_head =lpmyevent_end= new_event;else new_event->eventNum = eventNum;lpmyevent_end->next=new_event;lpmyevent_end=new_event;atomic_set(&new_event-&g

23、t;value,value);result = new_event->eventNum;return result;elsereturn eventNum;asmlinkage int sys_Request(int eventNum)myevent_t *tmp;myevent_t *prev = NULL;if(tmp = scheventNum( eventNum, &prev) != NULL)printk("wait:value is %d",atomic_read(&tmp->value);if (atomic_read(&t

24、mp->value) > 0)atomic_dec(&tmp->value);printk("wait:i've dec value to <%d>",atomic_read(&tmp->value);return eventNum;printk("wait:value should be 0 to sleep->value:%dn",atomic_read(&tmp->value);DEFINE_WAIT(wait); /prepare_to_wait(&tmp&g

25、t;p,&wait,TASK_INTERRUPTIBLE);set_current_state(TASK_INTERRUPTIBLE);add_wait_queue_exclusive(&tmp->p,&wait); schedule(); finish_wait(&tmp->p,&wait);printk("wait:now i'm back and value is :%dn",atomic_read(&tmp->value);return eventNum;return 0;asmlinkage

26、 int sys_Release(int eventNum)myevent_t *tmp = NULL;myevent_t *prev = NULL;if(tmp = scheventNum(eventNum,&prev) != NULL) if (list_empty(&(tmp->p.task_list) atomic_inc(&tmp->value);printk("signal:so list is empty and value now is(added):%dn",atomic_read(&tmp->value)

27、;return eventNum;printk("signal:so i'm going to wake up one exclusive processn");wake_up(&tmp->p); return eventNum;return 0;asmlinkage int sys_Broadcast(int eventNum)myevent_t *prev=NULL;myevent_t *releaseItem;if(releaseItem = scheventNum(eventNum,&prev) != NULL)if( releaseItem = lpmyevent_end) lpmyevent_