山東大學(xué)操作系統(tǒng)實(shí)驗(yàn)六完整版

山東大學(xué)操作系統(tǒng)實(shí)驗(yàn)HENsystemofficeroom【HEN16H-HENS2AHENS8Q8-HENH1688】軟件學(xué)院操作系統(tǒng)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目：實(shí)驗(yàn)六、死鎖問(wèn)題實(shí)驗(yàn)學(xué)號(hào)：0124日期：2013年05月23日班級(jí)：5班 姓名：韓俊曉Email：實(shí)驗(yàn)?zāi)康模和ㄟ^(guò)本實(shí)驗(yàn)觀察死鎖產(chǎn)生的現(xiàn)象，考慮解決死鎖問(wèn)題的方法。從而進(jìn)一步加深對(duì)于死鎖問(wèn)題的理解。掌握解決死鎖問(wèn)題的幾種算法的編程和調(diào)試技術(shù)。練習(xí)怎樣構(gòu)造管程和條件變量，利用管程機(jī)制來(lái)避免死鎖和饑俄問(wèn)題的發(fā)生。實(shí)驗(yàn)要求：在兩個(gè)城市南北方向之間存在一條鐵路，多列火車可以分別從兩個(gè)城市的車站排隊(duì)等待進(jìn)入車道向?qū)Ψ匠鞘行旭?，該鐵路在同一時(shí)間，只能允許在同一方向上行車，如果同時(shí)有相向的火車行駛將會(huì)撞車。請(qǐng)模擬實(shí)現(xiàn)兩個(gè)方向行車，而不會(huì)出現(xiàn)撞車或長(zhǎng)時(shí)間等待的情況。您能構(gòu)造一個(gè)管程來(lái)解決這個(gè)問(wèn)題嗎？硬件環(huán)境：實(shí)驗(yàn)室計(jì)算機(jī)軟件環(huán)境：—Linux操作系統(tǒng)gccversion實(shí)驗(yàn)步驟：1.實(shí)驗(yàn)說(shuō)明：管程-Monitor管程是一種高級(jí)抽象數(shù)據(jù)類型，它支持在它的函數(shù)中隱含互斥操作。結(jié)合條件變量和其他一些低級(jí)通信原語(yǔ)，管程可以解決許多僅用低級(jí)原語(yǔ)不能解決的同步問(wèn)題。利用管程可以提供一個(gè)不會(huì)發(fā)生死鎖或饑餓現(xiàn)象的對(duì)象;哲學(xué)家就餐問(wèn)題和Java語(yǔ)言中的synchronized對(duì)象都是很好的管程的例子.管程封裝了并發(fā)進(jìn)程或線程要互斥執(zhí)行的函數(shù)。為了讓這些并發(fā)進(jìn)程或線程在管程內(nèi)互斥的執(zhí)行，進(jìn)入管程的進(jìn)/線程必須獲取到管程鎖或二值信號(hào)量條件變量ConditionVariables條件變量提供了一種對(duì)管程內(nèi)并發(fā)協(xié)作進(jìn)程的同步機(jī)制。如果沒有條件變量，管程就不會(huì)有很有用。多數(shù)同步問(wèn)題要求在管程中說(shuō)明條件變量。條件變量代表了管程中一些并發(fā)進(jìn)程或線程可能要等待的條件。一個(gè)條件變量管理著管程內(nèi)的一個(gè)等待隊(duì)列。如果管程內(nèi)某個(gè)進(jìn)程或線程發(fā)現(xiàn)其執(zhí)行條件為假，則該進(jìn)程或線程就會(huì)被條件變量掛入管程內(nèi)等待該條件的隊(duì)列。如果管程內(nèi)另外的進(jìn)程或線程滿足了這個(gè)條件，則它會(huì)通過(guò)條件變量再次喚醒等待該條件的進(jìn)程或線程，從而避免了死鎖的產(chǎn)生。所以，一個(gè)條件變量C應(yīng)具有兩種操作()和()。當(dāng)管程內(nèi)同時(shí)出現(xiàn)喚醒者和被喚醒者時(shí)，由于要求管程內(nèi)的進(jìn)程或線程必須互斥執(zhí)行，因此就出現(xiàn)了兩種樣式的條件變量：MesaStyle（signal-and-continue）:喚醒者進(jìn)程或線程繼續(xù)執(zhí)行，被喚醒者進(jìn)程或線程等到喚醒者進(jìn)程或線程阻塞或離開管程后再執(zhí)行。HoareStyle（signal-and-wait）:被喚醒者進(jìn)程或線程立即執(zhí)行，喚醒者進(jìn)程或線程阻塞，直道被喚醒者阻塞或離開管程后再執(zhí)行。實(shí)驗(yàn)6單行道（過(guò)橋）問(wèn)題可以通過(guò)管程很好的解決?？梢园褑涡械?橋封裝為一個(gè)管程類，橋上通過(guò)的車輛是進(jìn)入管程的進(jìn)/線程，可以通過(guò)創(chuàng)建多個(gè)車輛進(jìn)/線程并隨機(jī)產(chǎn)生它們的行進(jìn)方向，并指定橋上可同時(shí)行駛的車輛的個(gè)數(shù)來(lái)模擬該問(wèn)題的各種現(xiàn)場(chǎng)隨機(jī)情況。一個(gè)正確的實(shí)驗(yàn)結(jié)果應(yīng)能實(shí)現(xiàn)在各種隨機(jī)現(xiàn)場(chǎng)情況下車輛進(jìn)程不會(huì)逆向上橋（死鎖），也不會(huì)使車少方向上的車輛無(wú)機(jī)會(huì)上橋（饑餓）.在linux系統(tǒng)中可以利用進(jìn)程間通信（interprocesscommunication）IPC中的3個(gè)對(duì)象：共享內(nèi)存、信號(hào)燈數(shù)組、消息隊(duì)列，來(lái)解決協(xié)作并發(fā)進(jìn)程間的同步與互斥的問(wèn)題。1）共享內(nèi)存是OS內(nèi)核為并發(fā)進(jìn)程間交換數(shù)據(jù)而提供的一塊內(nèi)存區(qū)（段）。如果段的權(quán)限設(shè)置恰當(dāng)，每個(gè)要訪問(wèn)該段內(nèi)存的進(jìn)程都可以把它映射到自己私有的地址空間中。如果一進(jìn)程更新了段中數(shù)據(jù)，那么其他進(jìn)程立即會(huì)看到這一更新。進(jìn)程創(chuàng)建的段也可由另一進(jìn)程讀寫。linux中可用命令ipcs-m觀察共享內(nèi)存情況。$ipcs-m SharedMemorySegments key shmid ownerperms bytes nattchstatus0x00000000327682student6003932162dest0x00000000360451student6001966082dest0x00000000393220student6001966082destkey共享內(nèi)存關(guān)鍵值shmid共享內(nèi)存標(biāo)識(shí)owner共享內(nèi)存所由者（本例為student）perm共享內(nèi)存使用權(quán)限（本例為student可讀可寫）byte共享內(nèi)存字節(jié)數(shù)nattch共享內(nèi)存使用計(jì)數(shù)status共享內(nèi)存狀態(tài)上例說(shuō)明系統(tǒng)當(dāng)前已由student建立了一些共享內(nèi)存,每個(gè)都有兩個(gè)進(jìn)程在共享。2）信號(hào)燈數(shù)組是OS內(nèi)核控制并發(fā)進(jìn)程間共享資源的一種進(jìn)程同步與互斥機(jī)制。linux中可用命令ipcs-s觀察信號(hào)燈數(shù)組的情況。$ipcs-s SemaphoreArrays key semid owner perms nsemsTOC\o"1-5"\h\z0000000163844apache600 10x4d00f259294920beagleind600 80x00000159425995student644 1semid信號(hào)燈的標(biāo)識(shí)號(hào)nsems信號(hào)燈的個(gè)數(shù)其他字段意義同以上共享內(nèi)存所述。上例說(shuō)明當(dāng)前系統(tǒng)中已經(jīng)建立多個(gè)信號(hào)燈。其中最后一個(gè)標(biāo)號(hào)為425996是由student建立的，它的使用權(quán)限為644,信號(hào)燈數(shù)組中信號(hào)燈個(gè)數(shù)為1個(gè)。3） 消息隊(duì)列是OS內(nèi)核控制并發(fā)進(jìn)程間共享資源的另一種進(jìn)程同步機(jī)制。linux中可用命令ipcs-q觀察消息隊(duì)列的情況。$ipcs-q MessageQueues key msqidownerpermsused-bytesmessages0x000001c80 root644 8 1msgmid消息隊(duì)列的標(biāo)識(shí)號(hào)used-bytes消息的字節(jié)長(zhǎng)度messages消息隊(duì)列中的消息條數(shù)其他字段意義與以上兩種機(jī)制所述相同。上例說(shuō)明當(dāng)前系統(tǒng)中有一條建立消息隊(duì)列，標(biāo)號(hào)為0,為root所建立，使用權(quán)限為644,每條消息8個(gè)字節(jié),現(xiàn)有一條消息。4） 在權(quán)限允許的情況下您可以使用ipcrm命令刪除系統(tǒng)當(dāng)前存在的IPC對(duì)象中的任一個(gè)對(duì)象。ipcrm-m21482刪除標(biāo)號(hào)為21482的共享內(nèi)存。ipcrm-s32673刪除標(biāo)號(hào)為32673的信號(hào)燈數(shù)組。ipcrm-q18465刪除標(biāo)號(hào)為18465的消息隊(duì)列。在linux的proc文件系統(tǒng)中有3個(gè)虛擬文件動(dòng)態(tài)記錄了由以上ipcs命令顯示的當(dāng)前IPC對(duì)象的信息，它們分別是：/proc/sysvipc/shm共享內(nèi)存/proc/sysvipc/sem信號(hào)量/proc/sysvipc/msg消息隊(duì)列我們可以利用它們?cè)诔绦驁?zhí)行時(shí)獲取有關(guān)IPC對(duì)象的當(dāng)前信息。IPC對(duì)象有關(guān)的系統(tǒng)調(diào)用函數(shù)原型都聲明在以下的頭文件中：#include<sys/>#include<sys/>創(chuàng)建一段共享內(nèi)存系統(tǒng)調(diào)用語(yǔ)法：#include<sys/>intshmget(key_tkey,intsize,intflags);key共享內(nèi)存的鍵值,可以為IPC_PRIVATE,也可以用整數(shù)指定一個(gè)size共享內(nèi)存字節(jié)長(zhǎng)度f(wàn)lags共享內(nèi)存權(quán)限位。shmget調(diào)用成功后，如果key用新整數(shù)指定，且flags中設(shè)置了IPC_CREAT位，則返回一個(gè)新建立的共享內(nèi)存段標(biāo)識(shí)符。如果指定的key已存在則返回與key關(guān)聯(lián)的標(biāo)識(shí)符。不成功返回-1令一段共享內(nèi)存附加到調(diào)用進(jìn)程中的系統(tǒng)調(diào)用語(yǔ)法：#include<sys/>char*shmat(intshmid,char*shmaddr,intflags)shmid由shmget創(chuàng)建的共享內(nèi)存的標(biāo)識(shí)符shmaddr總為0,表示用調(diào)用者指定的指針指向共享段flags共享內(nèi)存權(quán)限位shmat調(diào)用成功后返回附加的共享內(nèi)存首地址令一段共享內(nèi)存從到調(diào)用進(jìn)程中分離出去的系統(tǒng)調(diào)用語(yǔ)法：#include<sys/>intshmdt(char*shmadr);shmadr進(jìn)程中指向附加共享內(nèi)存的指針shmdt調(diào)用成功將遞減附加計(jì)數(shù)，當(dāng)計(jì)數(shù)為0,將刪除共享內(nèi)存。調(diào)用不成功返回-1。創(chuàng)建一個(gè)信號(hào)燈數(shù)組的系統(tǒng)調(diào)用有語(yǔ)法:#include<sys/>intsemget(key_tkey,intnsems,intflags);key信號(hào)燈數(shù)組的鍵值,可以為IPC_PRIVATE,也可以用整數(shù)指定一個(gè)nsems信號(hào)燈數(shù)組中信號(hào)燈的個(gè)數(shù)flags信號(hào)燈數(shù)組權(quán)限位。如果key用整數(shù)指定，應(yīng)設(shè)置IPC_CREAT位。semget調(diào)用成功，如果key用新整數(shù)指定，且flags中設(shè)置了IPC_CREAT位，則返回一個(gè)新建立的信號(hào)等數(shù)組標(biāo)識(shí)符。如果指定的整數(shù)key已存在則返回與key關(guān)聯(lián)的標(biāo)識(shí)符。不成功返回-1操作信號(hào)燈數(shù)組的系統(tǒng)調(diào)用語(yǔ)法:#include<sys/>intsemop(intsemid,structsembuf*semop,unsignednops);semid由semget創(chuàng)建的信號(hào)燈數(shù)組的標(biāo)識(shí)符semop指向sembuf數(shù)據(jù)結(jié)構(gòu)的指針nops信號(hào)燈數(shù)組元素的個(gè)數(shù)。semop調(diào)用成功返回0,不成功返回T。控制信號(hào)燈數(shù)組的系統(tǒng)調(diào)用語(yǔ)法:#include<sys/>intsemctl(intsemid,intsemnum,intcmd,unionsemunarg);semid由semget創(chuàng)建的信號(hào)燈數(shù)組的標(biāo)識(shí)符semnum該信號(hào)燈數(shù)組中的第幾個(gè)信號(hào)燈cmd對(duì)信號(hào)燈發(fā)出的控制命令。例如:GETVAL返回當(dāng)前信號(hào)燈狀態(tài)SETVAL設(shè)置信號(hào)燈狀態(tài)IPC_RMID刪除標(biāo)號(hào)為semid的信號(hào)燈arg保存信號(hào)燈狀態(tài)的聯(lián)合體,信號(hào)燈的值是其中一個(gè)基本成員unionsemun{intval;/*valueforSETVAL*/};semctl執(zhí)行不成功返回T,否則返回指定的cmd的值。創(chuàng)建消息隊(duì)列的系統(tǒng)調(diào)用語(yǔ)法:#include<sys/>intmsgget(key_tkey,intflags)key消息隊(duì)列的鍵值,可以為IPC_PRIVATE,也可以用整數(shù)指定一個(gè)flags消息隊(duì)列權(quán)限位。msgget調(diào)用成功，如果key用新整數(shù)指定，且flags中設(shè)置了IPC_CREAT位，則返回一個(gè)新建立的消息隊(duì)列標(biāo)識(shí)符。如果指定的整數(shù)key已存在則返回與key關(guān)聯(lián)的標(biāo)識(shí)符。成功返回-1。追加一條新消息到消息隊(duì)列的系統(tǒng)調(diào)用語(yǔ)法：intmsgsnd(intmsqid,structmsgbuf*msgp,size_tmsgsz,intmsgflg);msqid由消息隊(duì)列的標(biāo)識(shí)符msgp消息緩沖區(qū)指針。消息緩沖區(qū)結(jié)構(gòu)為：structmsgbuf{longmtype;/*消息類型，必須大于0*/charmtext[1]; /*消息數(shù)據(jù)，長(zhǎng)度應(yīng)于msgsz聲明的一致*/}msgsz消息數(shù)據(jù)的長(zhǎng)度msgflg為0表示阻塞方式，設(shè)置IPC_NOWAIT表示非阻塞方式msgsnd調(diào)用成功返回0,不成功返回T。從到消息隊(duì)列中讀出一條新消息的系統(tǒng)調(diào)用語(yǔ)法：intmsgrcv(intmsqid,structmsgbuf*msgp,size_tmsgsz,longmsgtype,intmsgflg);msqid由消息隊(duì)列的標(biāo)識(shí)符msgp消息緩沖區(qū)指針。消息緩沖區(qū)結(jié)構(gòu)為：structmsgbuf{longmtype;/*消息類型，必須大于0*/msgsz消息數(shù)據(jù)的長(zhǎng)度msgtype決定從隊(duì)列中返回哪條消息：=0返回消息隊(duì)列中第一條消息〉0返回消息隊(duì)列中等于mtype類型的第一條消息?！?返回mtype〈二type絕對(duì)值最小值的第一條消息。msgflg為0表示阻塞方式，設(shè)置IPC_NOWAIT表示非阻塞方式msgrcv調(diào)用成功返回0,不成功返回T。刪除消息隊(duì)列的系統(tǒng)調(diào)用語(yǔ)法：#include〈sys/〉intmsgctl(intmsqid,intcmd,structmsqid_ds*buf);msqid由消息隊(duì)列的標(biāo)識(shí)符cmd控制命令。常用的有：IPC_RMID刪除msgid標(biāo)識(shí)的消息隊(duì)列IPC_STAT為非破壞性讀，從隊(duì)列中讀出一個(gè)msgid_ds結(jié)構(gòu)填充緩沖bufIPC_SET改變隊(duì)列的UID,GID,訪問(wèn)模式和最大字節(jié)數(shù)。msgctl調(diào)用成功返回0,不成功返回T。調(diào)試過(guò)程：1)建立以下名為的頭文件：#include〈iostream〉#include〈〉#include〈〉#include〈〉#include<sys/>#include<sys/>#include<sys/>#include<sys/>#include<sys/>#include<sys/>/*信號(hào)燈控制用的共同體*/typedefunionsemuns{intval;}Sem_uns;義一個(gè)單行道管程的條件變量類：classCondition{public:Condition