【正文】 臨界區(qū) */ state[i] = THINKING。 /* 記錄下第 i 個(gè)哲學(xué)家已經(jīng)完成進(jìn)餐 */ test (LEFT)。 /* 測試左側(cè)是否能進(jìn)餐 */ test (RIGHT)。 /* 測試右側(cè)是否能進(jìn)餐 */ up (amp。mutex)。 /* 退出臨界區(qū) */ } void test(i) /* i: 某個(gè)哲學(xué)家的編號 , 從 0 到 N1 */ { if (state[i] == HUNGRY amp。amp。 state[LEFT] != EATING amp。amp。 state[RIGHT] != EATING) { state[i] = EATING。 up(amp。s[i])。 /* 喚醒阻塞 */ } } 如果第一個(gè)進(jìn)入，通過 test來表示自己的狀態(tài)，表示可以進(jìn)餐，如果他完成以后，通過 test標(biāo)識可以進(jìn)餐的人的標(biāo)號，在 test函數(shù)里將阻塞的進(jìn)程喚醒，即每個(gè)哲學(xué)家放下叉子之后，再去判斷兩側(cè)的是否有阻塞，如果有，將它喚醒，之后，放開對臨界區(qū)的控制，讓兩側(cè)的哲學(xué)家進(jìn)餐。 函數(shù)只以 philosopher為主函數(shù)，其余的均為被調(diào)用的函數(shù)。不是單獨(dú)的進(jìn)程。 屬于多個(gè)進(jìn)程訪問有限資源類問題。 讀者 寫者問題 問題描述： 有一個(gè)許多進(jìn)程共享的數(shù)據(jù)區(qū)，這個(gè)數(shù)據(jù)區(qū)可以是一個(gè)文件或者主存的一塊空間，甚至可以是一組處理器寄存器，有一些只讀取這個(gè)數(shù)據(jù)區(qū)的進(jìn)程，和一些只向數(shù)據(jù)區(qū)中寫數(shù)據(jù)的進(jìn)程。此外，還需要滿足： 。 ； ，禁止任何讀進(jìn)程讀文件。 數(shù)據(jù)庫的訪問模型 typedef int semaphore。 /* 根據(jù)需要自定義 */ semaphore mutex = 1。 /* 控制對 ’ rc’的訪問 */ semaphore db = 1。 /* 控制對數(shù)據(jù)庫的訪問 */ int rc = 0。 /* 正在讀或準(zhǔn)備讀的進(jìn)程數(shù) */ void reader(void) { while (TRUE) { /* 無限循環(huán) */ down(amp。mutex)。 /* 禁止對 ’ rc’的訪問 */ rc = rc + 1。 /* 讀者進(jìn)入 */ if (rc == 1) down(amp。db)。 /* 如果是第一個(gè)讀者 ... */ up(amp。mutex)。 /* 恢復(fù) 允許訪問 ’ rc’ */ read_data_base()。 /* 訪問數(shù)據(jù) */ down (amp。mutex)。 /* 禁止對 ’ rc’的訪問 */ rc = rc 1。 /* 讀者離開 */ if (rc == 0) up(amp。db)。 /* 如果是最后一個(gè)讀者 ... */ up(amp。mutex)。 /* 恢復(fù)允許訪問 ’ rc’ */ use_data_read()。 /* 非臨界區(qū) */ } } void writer (void) { while (TRUE) { /* 無限循環(huán) */ think_up_data ()。 /* 非臨界區(qū) */ down (amp。db)。 /* 鎖定臨界區(qū) — 數(shù)據(jù)庫 */ write_data_base ( )。 /* 更新數(shù)據(jù) */ up (amp。db)。 /* 釋放對臨界區(qū)的控制 — 數(shù)據(jù)庫 */ } } 局限性：只要有一個(gè)讀者在，則就可以允許更多的讀者進(jìn)入，而此時(shí)如果有更新數(shù)據(jù)的需求，但也會(huì)被無限制的掛起。 故此種解法為讀者優(yōu)先。 寫進(jìn)程優(yōu)先 解決 讀者 —寫者問題 問題描述：由于采用讀者優(yōu)先時(shí)。只要至少一個(gè)讀進(jìn)程在讀，就為讀保留了數(shù)據(jù)區(qū)的控制權(quán)，所以寫進(jìn)程可能會(huì)被餓死。 故需要增加如下限制信息： 為了保證一個(gè)寫進(jìn)程聲明想寫時(shí)，不允許新的讀進(jìn)程訪問該數(shù)據(jù)區(qū)，需要增加額外的信號量和變量： **信號量 rsem:當(dāng)至少有一個(gè)寫進(jìn)程準(zhǔn)備訪問數(shù)據(jù)區(qū)時(shí)，用來禁止所有的讀進(jìn)程； **變量 writecount:控制 rsem的設(shè)置； **信號量 y:控制 writecount的更新。 一個(gè)額外的信號量 z，為了寫進(jìn)程優(yōu)先，不要多余的讀進(jìn)程在rsem里等待，將多余的讀進(jìn)程放入 z中，在那里排隊(duì)。 進(jìn)程中的隊(duì)列狀態(tài) 系統(tǒng)中只有讀進(jìn)程 a)設(shè)置 db； b)沒有隊(duì)列 系統(tǒng)中只有寫進(jìn)程 a)設(shè)置 db和 rsem； b)寫進(jìn)程在 db上排隊(duì) 系統(tǒng)中既有讀進(jìn)程又有寫進(jìn)程 ,讀優(yōu)先 系統(tǒng)中即有讀進(jìn)程又有寫進(jìn)程 ,寫優(yōu)先 a)讀進(jìn)程設(shè)置 db。 b)寫進(jìn)程設(shè)置 rsem； c)所有寫進(jìn)程在 db上排隊(duì)； d)一個(gè)讀進(jìn)程在 rsem上排隊(duì)； e)其他讀進(jìn)程在 z上排隊(duì)。 a)寫進(jìn)程設(shè)置 db。 b)寫進(jìn)程設(shè)置 rsem； c) 寫進(jìn)程在 db上排隊(duì)； d)一個(gè)讀進(jìn)程在 rsem上 排 隊(duì)； e)其他讀進(jìn)程在 z上排隊(duì)。 int readcount , writecount Semaphore mutex=1,y=1,z=1,db=1,rsem=1。 Void reader() { while (TRUE){ down( z)。 down(rsem)。 down(mutex)。 readcount++。 if (readcount==1) { down(db)。 } up (mutex)。 up (rsem)。 up(z)。 READUNIT()。 down (mutex)。 Void writer() { while(TRUE) { down(y)。 writecount++。 if(writecount==1){ down(rsem)。} /*阻塞新的讀進(jìn)程進(jìn)入 */ up(y)。 down(db)。 WRITEUNIT()。 up(db)。 down(y)。 writecount。 if(writecount==0){ up(rsem)。} /*所有寫進(jìn)程完成，允許新讀者進(jìn)入 */ up(y)。 } } 理發(fā)師睡覺問題 問題描述 :理發(fā)店里有一位理發(fā)師，一次給一名顧客理發(fā)，店里有 N把椅子，故最多會(huì)有 N個(gè)顧客在等待，如果新來的顧客沒有位置，則會(huì)離開，即等待的隊(duì)列有上限；當(dāng)沒有顧客的時(shí)候理發(fā)師開始睡覺，直到有顧客把它喚醒為止。 特殊的多進(jìn)程對有界資源的使用。 define CHAIRS 5 /* 椅子的數(shù)目 */ typedef int semaphore。 /* 自定義 */ semaphore customers = 0。 /* 等待服務(wù)的 顧客數(shù)目 */ semaphore barbers = 0。 /* 理發(fā)師的數(shù)目 */ semaphore mutex = 1。 /* 互斥量 */ int waiting = 0。 /* 等待的顧客（未理發(fā)的） */ void barber(void) { while (TRUE) { down(customers)。 /* 無顧客就去睡眠 */ down(mutex)。 /* 鎖定臨界區(qū) */ waiting = waiting 1。 /* 等候的顧客數(shù)減一 */ up(barbers)。 /* 一個(gè)理發(fā)師開始理發(fā) */ up(mutex)。 /* 釋放剛才的鎖定’ */ Cut_hair()。 /* 理發(fā) */ } } void customer(void) { down(mutex)。 /* 進(jìn)入臨界區(qū) */ if (waiting CHAIRS) { /* 沒有椅子就離開 */ waiting = waiting + 1。 /* 等待的顧客數(shù)目加一 */ up(customers)。 /* 有必要的喚醒理發(fā)師 */ up(mutex)。 /* 解除鎖定 */ down(barbers)。 /* 沒理發(fā)師給他服務(wù)就睡覺 */ get_haircut()。 /* 否則，等候服務(wù) */ } else { up(mutex)。 /* 否則就離開 */ } } g_hMutex = CreateMutex(NULL,FALSE,NULL)。 g_hFullSemaphore= = CreateSemaphore(NULL,SIZE_OF_BUFFER1,SIZE_OF_BUFFER1,NULL)。 g_hEmptySemaphore = CreateSemaphore(NULL,0,SIZE_OF_BUFFER1,NULL)。 hThreads[i]=CreateThread(NULL,0,Producer,NULL,0,amp。producerID[i])。 WaitForSingleObject(g_hFullSemaphore,INFINITE)。 WaitForSingleObject(g_hMutex,INFINITE)。 ReleaseMutex(g_hMutex)。 ReleaseSemaphore(g_hEmptySemaphore,1,NULL)。 進(jìn)程調(diào)度 ** 調(diào)度的類型 (scheduling) 1. 按照調(diào)度的層次 ? 作業(yè)：又稱為 宏觀調(diào)度 、 高級調(diào)度 。從用戶工作流程的角度，一次提交若干個(gè)流程，其中每個(gè)程序按進(jìn)程調(diào)度。時(shí)間上通常是分鐘、小時(shí)或天。 ? 內(nèi)外存交換：又稱為 中級調(diào)度 。從存儲(chǔ)器資源的角度。將進(jìn)程的部分或全部換出到外存上，將當(dāng)前所需部分換入到內(nèi)存。指令和數(shù)據(jù)必須在內(nèi)存里才能被 CPU直接訪問。 ? 進(jìn)程或線程：又稱為 微觀調(diào)度 、 低級調(diào)度 。從 CPU資源的角度，執(zhí)行的單位。 時(shí)間上通常是毫秒 。因?yàn)閳?zhí)行頻繁，要求在實(shí)現(xiàn)時(shí)達(dá)到高效率。 AdmitRunningReadySuspendExitReadyBlockedDispatchTimeoutEventWaitEventOccursReleaseBlockedSuspendSuspendNewEventOccursActivateSuspendActivateAdmitSuspend宏觀調(diào)度微觀調(diào)度中級調(diào)度 ?長期 (longterm)：將進(jìn)程投入 允許執(zhí)行 進(jìn)程緩沖池中，或送到 退出 進(jìn)程緩沖池中。進(jìn)程狀態(tài)： New－ Ready suspend, Running － Exit ?中期 (mediumterm)：將進(jìn)程的部分或全部加載到內(nèi)存中。進(jìn)程狀態(tài)： Ready － Ready suspend, Blocked －Blocked suspend ?短期 (shortterm)：選擇哪個(gè)進(jìn)程在處理機(jī)上執(zhí)行。進(jìn)程狀態(tài)： Ready － Running I/O調(diào)度：選擇哪個(gè) I/O等待進(jìn)程，使其請求可以被空閑的 I/O設(shè)備進(jìn)行處理。 OS的分類 ?批處理調(diào)度－－應(yīng)用場合：大中型主機(jī)集中計(jì)算，如工程計(jì)算、理論計(jì)算（流體力學(xué)） ?分時(shí)調(diào)度、實(shí)時(shí)調(diào)度：通常沒有專門的作業(yè)調(diào)度 ?多處理機(jī)調(diào)度 ** 調(diào)度的性能準(zhǔn)則 我們可從不同的角度來判斷處理機(jī)調(diào)度算法的性能，如用戶的角度、處理機(jī)的角度和算法實(shí)現(xiàn)的角度。實(shí)際的處理機(jī)調(diào)度算法選擇是一個(gè)綜合的判斷結(jié)果。 從兩個(gè)方面分析： 1 . 從用戶方面來考慮： 2 . 從系統(tǒng)角度來考慮。 1. 面向用戶的調(diào)度性能準(zhǔn)則 ? 周轉(zhuǎn)時(shí)間：作業(yè)從提交到完成（得到結(jié)果）所經(jīng)歷的時(shí)間。包括：在收容隊(duì)列中等待， CPU上執(zhí)行，就緒隊(duì)列和阻塞隊(duì)列中等待，結(jié)果輸出等待－－批處理系統(tǒng) 平均周轉(zhuǎn)時(shí)間 T 平均帶權(quán)周轉(zhuǎn)時(shí)間（帶權(quán)周轉(zhuǎn)時(shí)間 W是 T(周轉(zhuǎn) )/T(CPU執(zhí)行 )〕 ? 響應(yīng)時(shí)間：用戶輸入一個(gè)請求（如擊鍵）到系統(tǒng)給出首次響應(yīng)（如屏幕顯示）的時(shí)間－－分時(shí)系統(tǒng) ? 截止時(shí)間：開始截止時(shí)間和完成截止時(shí)間－－實(shí)時(shí)系統(tǒng)，與周轉(zhuǎn)時(shí)間有些相似。 ? 公平性：不因作業(yè)或進(jìn)程本身的特性而使上述指標(biāo)過分惡化。如長作業(yè)等待很長時(shí)間。 ? 優(yōu)先級：可以使關(guān)鍵任務(wù)達(dá)到更好的指標(biāo)。 2. 面向系統(tǒng)的調(diào)度性能準(zhǔn)則 ?吞吐量：單位時(shí)間內(nèi)所完成的作業(yè)數(shù)，跟作業(yè)本身特性和調(diào)度算法都有關(guān)系－－批處理系統(tǒng) ? 平均周轉(zhuǎn)時(shí)間不是吞吐量的倒數(shù)，因?yàn)椴l(fā)執(zhí)行的作業(yè)在時(shí)間上可以重疊。如：在 2小時(shí)內(nèi)完成 4個(gè)作業(yè)，而每個(gè)周轉(zhuǎn)時(shí)間是 1小時(shí)，則吞吐量是 2個(gè)作業(yè) /小時(shí) ?處理機(jī)利用率：－－大中型主機(jī) ?各種設(shè)備的均衡利