操作系統(tǒng)重點(diǎn)知識(shí)總結(jié)

效勞程序。效勞程序。第一章引論1、操作系統(tǒng)定義〔P1〕操作系統(tǒng)是配置在計(jì)算機(jī)硬件上的第一層軟件，是對(duì)硬件系統(tǒng)的首次擴(kuò)大。是一組控制和管理計(jì)算機(jī)硬件和軟件資源、合理地對(duì)各類作業(yè)進(jìn)展調(diào)度以及方便用戶使用的程序的集合。2、操作系統(tǒng)的作用〔P2〕OS作為用戶與計(jì)算機(jī)硬件系統(tǒng)之間的接OS作為計(jì)算機(jī)系統(tǒng)資源的管理者OS實(shí)現(xiàn)了對(duì)計(jì)算機(jī)資源的抽象3、推動(dòng)操作系統(tǒng)開展的主要?jiǎng)恿Α睵4〕不斷提高計(jì)算機(jī)資源的利用率方便用戶器件的不斷更新迭代計(jì)算機(jī)體系構(gòu)造的不斷開展4、多道批處理系統(tǒng)的特征及優(yōu)缺點(diǎn)「、〔P8〕特征：多道性、無(wú)序性、調(diào)度性優(yōu)點(diǎn)：資源利用率高系統(tǒng)吞吐量大缺點(diǎn)：平均周轉(zhuǎn)時(shí)間長(zhǎng)無(wú)交互能力〔單道、多道都是〕5、分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)特征的比擬〔P12〕多路性〔實(shí)時(shí)系統(tǒng)的多路性主要表現(xiàn)在系統(tǒng)周期性地對(duì)多路信息的采集、以及對(duì)多個(gè)對(duì)象或多個(gè)執(zhí)行機(jī)制進(jìn)展控制。分時(shí)系統(tǒng)中的多路性則和用戶有關(guān)，時(shí)多時(shí)少。〕獨(dú)立性及時(shí)性：〔實(shí)時(shí)系統(tǒng)對(duì)及時(shí)性的要求更嚴(yán)格,實(shí)時(shí)控制系統(tǒng)以控制對(duì)象要求的開場(chǎng)截止時(shí)間或完成截止時(shí)間來(lái)確定?！辰换バ?實(shí)時(shí)系統(tǒng)的交互性僅限于*些專用可靠性:實(shí)時(shí)系統(tǒng)對(duì)可靠性的要求更高，否則經(jīng)濟(jì)損失及后果無(wú)法預(yù)料。6、操作系統(tǒng)的根本特征〔P14〕〔并發(fā)、共享、虛擬和異步其中并發(fā)特征是操作系統(tǒng)最重要的特征是其他特征的前提〕并發(fā)性共享性〔互斥共享方式、同時(shí)方式〕虛擬性〔時(shí)分復(fù)用技術(shù)〔虛擬處理機(jī)技術(shù)、虛擬設(shè)備技術(shù)〕、空分復(fù)用技術(shù)〔虛擬磁盤技術(shù)、虛擬存儲(chǔ)器技術(shù)〕〕異步性〔進(jìn)程的異步性：進(jìn)程是以人們不可預(yù)知的速度向前推進(jìn)的〕7、操作系統(tǒng)的主要功能「、〔P18〕處理機(jī)管理功能〔進(jìn)程控制〔1、進(jìn)程互斥方式：進(jìn)程或者線程在對(duì)臨界資源進(jìn)展時(shí)，應(yīng)采取互斥方式；2、進(jìn)程同步方式：相互合作去完成共同任務(wù)的諸進(jìn)程貨線程〕、進(jìn)程通信、調(diào)度〔作業(yè)調(diào)度、進(jìn)程調(diào)度〕〕存儲(chǔ)器管理功能〔存分配、存保護(hù)、地址映射、存擴(kuò)大〕設(shè)備管理功能〔緩沖管理、設(shè)備分配、設(shè)備處理〕文件管理功能〔文件存儲(chǔ)空間的管理、目錄管理、文件的讀/寫管理和保護(hù)〕用戶接〔命令接〔聯(lián)機(jī)用戶接、脫機(jī)用戶接〕程序接、圖形接〕第二章進(jìn)程管理1、程序順序執(zhí)行時(shí)的特征〔P34〕順序性：嚴(yán)格按照程序所規(guī)定的次序執(zhí)行。封閉性：程序在封閉環(huán)境下運(yùn)行，系統(tǒng)中所有資源的狀態(tài)只有本程序才能改變它?？稍佻F(xiàn)性：只要初始條件一樣，無(wú)論怎樣執(zhí)行，其結(jié)果都是一樣的。2、程序并發(fā)執(zhí)行時(shí)的特征〔提高了系統(tǒng)吞吐量〕1〔P36〕連續(xù)性：并發(fā)執(zhí)行的實(shí)體之間相互制約，造成程序的執(zhí)行出現(xiàn)連續(xù)，而不連續(xù)。非封閉性：多個(gè)程序共享系統(tǒng)資源，因而其狀態(tài)有多個(gè)程序改變，從而失去封閉性。不可再現(xiàn)性：封閉性的失去必然導(dǎo)致不可再現(xiàn)性。3、進(jìn)程及其特征〔P37〕進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過(guò)程，是系統(tǒng)進(jìn)展資源分配和調(diào)度的一個(gè)獨(dú)立單位。進(jìn)程是程序的一次執(zhí)行進(jìn)程實(shí)體：由程序段、相關(guān)的數(shù)據(jù)段和PCB構(gòu)成特征：構(gòu)造特征動(dòng)態(tài)性〔進(jìn)程最根本的特征〕并發(fā)性〔引人進(jìn)程的目的：為了使其進(jìn)程實(shí)體能和其他的進(jìn)程實(shí)體并發(fā)執(zhí)行；而程序〔沒(méi)有建立PCB〕不能并發(fā)執(zhí)行〕獨(dú)立性異步性4、進(jìn)程的根本狀態(tài)及其轉(zhuǎn)換圖「、〔P38〕就緒(Ready)狀態(tài)執(zhí)行狀態(tài)阻塞狀態(tài)〔典型事例：請(qǐng)求I/O、申請(qǐng)緩沖空間等〕5、引入掛起狀態(tài)的原因r1〔P39〕終端用戶的請(qǐng)求父進(jìn)程請(qǐng)求負(fù)荷調(diào)節(jié)的需要操作系統(tǒng)的需要6、具有掛起狀態(tài)的進(jìn)程狀態(tài)及其轉(zhuǎn)換圖7、進(jìn)程控制塊及其作用〔P41〕PCB是一種數(shù)據(jù)構(gòu)造，是進(jìn)程實(shí)體的一局部，記錄了操作系統(tǒng)所需的、用于描述進(jìn)程的當(dāng)前情況以及控制進(jìn)程運(yùn)行的全部信息。作用：使一個(gè)在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序含數(shù)據(jù))，成為一個(gè)能獨(dú)立運(yùn)行的根本單位，一個(gè)能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程?；蛘哒f(shuō)，OS是根據(jù)PCB來(lái)對(duì)并發(fā)執(zhí)行的進(jìn)程進(jìn)展控制和管理的。PCB是進(jìn)程存在與否的唯一標(biāo)志，隨著進(jìn)程的建立而建立，隨著進(jìn)程的撤消而撤消。創(chuàng)立進(jìn)程就是創(chuàng)立PCB?！?進(jìn)程之間的兩種制約關(guān)系〔P48〕間接制約一一競(jìng)爭(zhēng)資源一一進(jìn)程互斥直接制約一一相互合作一一進(jìn)程同步9、臨界資源「、〔P48〕OS中把一次只能被一個(gè)進(jìn)程使用的資源成為臨界資源。10、臨界區(qū)〔10、臨界區(qū)〔P50:]11、同步機(jī)構(gòu)應(yīng)遵循的規(guī)則〔P50〕空閑讓進(jìn)、忙則等待、有限等待、讓權(quán)等待12、利用信號(hào)量實(shí)現(xiàn)前驅(qū)關(guān)系算法P(54)——P(55)13、經(jīng)典同步算法〔生產(chǎn)者-消費(fèi)者問(wèn)題,哲學(xué)家就餐問(wèn)題和讀者-寫者問(wèn)題〕略14、進(jìn)程通信的類型〔&〕/氐級(jí)：信號(hào)量進(jìn)程通信J共享存儲(chǔ)器系統(tǒng)〔基于共享數(shù)據(jù)構(gòu)造或存儲(chǔ)區(qū)的通信方式〕'高級(jí)J消息傳遞系統(tǒng)〔直接、間接〕管道通信系統(tǒng)〔必須提供的協(xié)調(diào)能力：互斥、同步、確定對(duì)方是否存在〕15、線程的定義〔P72〕現(xiàn)代OS引入的比進(jìn)程更小的可以獨(dú)立運(yùn)行、調(diào)度的根本單位，是輕型實(shí)體，不擁有資源。16、線程和進(jìn)程比擬線程又稱為輕型進(jìn)程，通常一個(gè)進(jìn)程都擁有假設(shè)干個(gè)線程，至少也有一個(gè)〔多線程OS中的進(jìn)程不是一個(gè)可執(zhí)行的實(shí)體〕1、調(diào)度：傳統(tǒng)OS中，進(jìn)程是擁有資源的根本單位，獨(dú)立調(diào)度、分派的根本單位。引入線程后，則把線程作為調(diào)度和分派的根本單位，而進(jìn)程作為擁有資源的根本單位2、并發(fā)性：引入線程的OS中，進(jìn)程之間可以并發(fā)執(zhí)行，在一個(gè)進(jìn)程中的多個(gè)線程之間也可以；這樣使得OS具有更好的并發(fā)性，從而能更加有效的提高系統(tǒng)資源的利用率和吞吐量3、擁有資源：線程不能擁有資源4、系統(tǒng)開銷：就切換代價(jià)而言，進(jìn)程遠(yuǎn)高于線程17、線程的屬性〔P73〕輕型實(shí)體獨(dú)立調(diào)度和分派的根本單位可并發(fā)執(zhí)行共享進(jìn)程資源第三章處理機(jī)調(diào)度與死鎖「高級(jí)調(diào)度〔P84〕又稱為作業(yè)調(diào)度。即從外存的后備隊(duì)列中選擇一個(gè)作業(yè)，為它創(chuàng)立進(jìn)程，分配必要的資源，并將新進(jìn)程插入主存的就緒隊(duì)列上。注意：分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)無(wú)作業(yè)調(diào)度。JCB〔作業(yè)控制塊〕；是作業(yè)在系統(tǒng)中存在的標(biāo)志，其中保存了系統(tǒng)對(duì)作業(yè)進(jìn)展管理和調(diào)度所需的全部信息2、低級(jí)調(diào)度「、〔P86〕又稱進(jìn)程調(diào)度或短程調(diào)度，即從就緒隊(duì)列中選擇一個(gè)進(jìn)程進(jìn)入運(yùn)行狀態(tài)〔非搶占方式、可搶占方式〕。調(diào)度的對(duì)象是進(jìn)程〔多批道處理、分時(shí)、實(shí)時(shí)三種類型的OS中都有〕3、中級(jí)調(diào)度〔頃〕中程調(diào)度為了提高存利用率和系統(tǒng)吞吐量〔引入目的〕，為此，應(yīng)使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用存資源，而將它們調(diào)至外存。適當(dāng)時(shí)機(jī)再將其調(diào)回存。這種調(diào)度稱為中級(jí)調(diào)度。4、進(jìn)程調(diào)度的兩種方式「、〔P86〕1、非搶占方式〔一旦給進(jìn)程分配處理機(jī)，一直讓他運(yùn)行下去，直到完成再把處理機(jī)分配給其他進(jìn)程〕2、搶占方式〔允許調(diào)度程序根據(jù)*些原則去暫停*個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一個(gè)進(jìn)程〕5、搶占的原則泌八〔P8/〕優(yōu)先權(quán)原則短作業(yè)〔進(jìn)程〕優(yōu)先原則時(shí)間片原則6、操作系統(tǒng)選擇調(diào)度方式和調(diào)度算法的假設(shè)干準(zhǔn)則〔P90〕面向用戶的準(zhǔn)則〔周轉(zhuǎn)時(shí)間短、響應(yīng)時(shí)間快、截止時(shí)間的保證、優(yōu)先權(quán)準(zhǔn)則〕設(shè)干準(zhǔn)則〔P90〕面向系統(tǒng)的準(zhǔn)則〔系統(tǒng)吞吐量高、處理機(jī)利用率好、各類資源的平衡利用〕7、周轉(zhuǎn)時(shí)間〔P92〕周轉(zhuǎn)時(shí)間：是指從作業(yè)被提交給系統(tǒng)開場(chǎng)，7、周轉(zhuǎn)時(shí)間〔P92〕到作業(yè)完成為止的這段時(shí)間間隔周轉(zhuǎn)時(shí)間=完成時(shí)間-到達(dá)時(shí)間待權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/效勞時(shí)間8、針對(duì)各種調(diào)度算法〔先來(lái)先效勞，短進(jìn)程優(yōu)先，優(yōu)先權(quán)〕，計(jì)算周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間，平均周轉(zhuǎn)時(shí)間、平均帶權(quán)周轉(zhuǎn)時(shí)間9、吞吐量指在單位時(shí)間系統(tǒng)所完成的作業(yè)數(shù)10、多級(jí)反應(yīng)隊(duì)列調(diào)度算法的原理、性能該算法用于進(jìn)程調(diào)度，主要是為解決前面各種進(jìn)程調(diào)度算法存在的各種不同問(wèn)題而設(shè)計(jì)的一種考慮綜合因素的調(diào)度算法。其思想如下：1、設(shè)置多個(gè)就緒隊(duì)列，不同隊(duì)列具有不同優(yōu)先級(jí)，第一個(gè)隊(duì)列優(yōu)先級(jí)最高，以后次之。給不同隊(duì)列分配不同大小的時(shí)間片，第一個(gè)隊(duì)列最小，以后次之〔皆為前者的二倍〕。有的系統(tǒng)也將最后一級(jí)隊(duì)列不劃分時(shí)間片。2、當(dāng)有一個(gè)新進(jìn)程進(jìn)入存后，首先將它放入第一隊(duì)列的末尾，按FCFS〔先來(lái)先效勞〕原則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如果它能在該時(shí)間片完成，便可準(zhǔn)備撤離系統(tǒng)；假設(shè)不能則將它放在第二列的隊(duì)尾。。。。。。3、僅當(dāng)前一級(jí)隊(duì)列為空時(shí)才調(diào)度下一級(jí)隊(duì)列中的進(jìn)程。算法采用搶占式調(diào)度策略。執(zhí)行的進(jìn)程在規(guī)定的時(shí)間片為執(zhí)行完畢，則進(jìn)入下一級(jí)隊(duì)列的隊(duì)尾，新進(jìn)程則進(jìn)入第一級(jí)隊(duì)列的隊(duì)尾。性能：〔較好的性能，能滿足各種類型的用戶〕1、終端型作業(yè)用戶2、短批處理作業(yè)用戶3、長(zhǎng)批處理作業(yè)用戶11、死鎖、產(chǎn)生死鎖原因、必要條件〔叩3〕死鎖是指兩個(gè)或多個(gè)進(jìn)程由于資源競(jìng)爭(zhēng)而造成的一種僵局，假設(shè)無(wú)外力作用，這些進(jìn)程將永遠(yuǎn)無(wú)法向前推進(jìn)。產(chǎn)生死鎖的原因：競(jìng)爭(zhēng)資源〔可剝奪和非剝奪性資源、競(jìng)爭(zhēng)非剝奪性資源、競(jìng)爭(zhēng)臨時(shí)性資源〕進(jìn)程推進(jìn)順序非法〔請(qǐng)求和釋放資源的順序不當(dāng)〕必要條件：互斥條件：進(jìn)程間必須互斥使用*些資源才可能產(chǎn)生死鎖。請(qǐng)求保持條件：進(jìn)程已經(jīng)占有至少一個(gè)資源，但又提出了新的資源請(qǐng)求。不剝奪條件：進(jìn)程已經(jīng)獲得的資源不能被剝奪。環(huán)路等待條件：在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程一一資源環(huán)形鏈。12、處理死鎖的根本方法〔P105〕預(yù)防死鎖：通過(guò)設(shè)置*些限制條件，破壞四個(gè)必要條件中的一個(gè)或幾個(gè)。該方法比擬簡(jiǎn)單，但由于限制條件過(guò)于嚴(yán)格，往往導(dǎo)致系統(tǒng)資源利用率和吞吐量低。防止死鎖：不需事先預(yù)防，但在資源的動(dòng)態(tài)分配時(shí)，用*種方法防止系統(tǒng)進(jìn)入不平安狀態(tài)，從而防止死鎖。該方法比擬難于實(shí)現(xiàn)，但往往可獲得較高資源利用率和系統(tǒng)吞吐量。死鎖的檢測(cè)與解除：允許系統(tǒng)產(chǎn)生死鎖，但能及時(shí)檢測(cè)出來(lái)，并通過(guò)*些措施解除。該方法實(shí)現(xiàn)難度最大，但往往可獲得較好的資源利用率和系統(tǒng)吞吐量。13、預(yù)防死鎖的方法*106〕預(yù)防死鎖的方法是使四個(gè)必要條件中的第2、3、4個(gè)條件不能成立，來(lái)防止發(fā)生死鎖。至于必要條件1，因?yàn)樗怯稍O(shè)備固有性能決定的，不僅不能改變，還應(yīng)加以保證。〔互斥條件破壞不了〕摒棄“請(qǐng)求和保持條件：資源靜態(tài)分配摒棄“不剝奪條件：資源的動(dòng)態(tài)分配摒棄“環(huán)路等待條件：資源有序分配14、平安狀態(tài)〔P107〕所謂平安狀態(tài)，是指系統(tǒng)能按*種進(jìn)程順序(P1,P2,…，Pn)(稱<P1,P2,…，Pn〉序列為平安序列)，來(lái)為每個(gè)進(jìn)程Pi分配其所需資源，直至14、平安狀態(tài)〔P107〕15、銀行家算法P(109)16、死鎖定理〔P113〕S狀態(tài)是死鎖的充分條件是，當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡(jiǎn)化的。該充分條件被稱為死鎖定理第四章存儲(chǔ)器管理1、程序裝入的方式〔晾9〕絕對(duì)裝入方式：完全按照目標(biāo)程序中所給定的地址裝入存，即目標(biāo)程序中使用的是絕對(duì)地址。該絕對(duì)地址既可在編譯或匯編是給出，也可由程序員直接賦予?？芍囟ㄎ谎b入方式：通常是把在裝入時(shí)對(duì)目標(biāo)程序中指令和數(shù)據(jù)的修改正程稱為重定位。又因?yàn)榈刂纷儞Q通常是在裝入時(shí)一次完成的，以后不再改變，故稱為靜態(tài)重定位動(dòng)態(tài)運(yùn)行時(shí)裝入方式：在這種方式下動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)展。因此，裝入存后的所有地址都仍是相對(duì)地址。顯然為使指令的執(zhí)行不受影響，進(jìn)展這種地址的動(dòng)態(tài)轉(zhuǎn)換，就必須有專門的硬件機(jī)構(gòu)解決2、重定位、靜態(tài)重定位、動(dòng)態(tài)重定位*119〕重定位：我們把裝入時(shí)對(duì)目標(biāo)程序中的指令地址和數(shù)據(jù)地址的修改正程稱為重定位。靜態(tài)重定位：如果重定位是在裝入時(shí)由裝入程序一次性完成的，則稱為靜態(tài)重定位。動(dòng)態(tài)重定位：在這種方式下動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)展。3、存的連續(xù)分配方式有哪些.〔P123、存的連續(xù)分配方式有哪些.〔P121〕固定分區(qū)分配動(dòng)態(tài)〔可變式〕分區(qū)分配可重定位分區(qū)分配4、動(dòng)態(tài)分區(qū)分配算法首次適應(yīng)算法循環(huán)首次適應(yīng)算法最正確適應(yīng)算法最壞適應(yīng)算法快速適應(yīng)算法5、對(duì)換技術(shù)〔P129〕對(duì)換技術(shù)，是指把存中暫時(shí)不能運(yùn)行的進(jìn)程或5、對(duì)換技術(shù)〔P129〕6、緊湊或拼接技術(shù)〔P127〕緊湊技術(shù)，是指通過(guò)移動(dòng)存中作業(yè)的位置，把原先分散的小分區(qū)拼接成一個(gè)大分區(qū)的方法。在每次拼接后，都必須對(duì)移動(dòng)了的程序或數(shù)據(jù)進(jìn)展重定位7、根本分頁(yè)管理原理、地址變換過(guò)程P(130)8、分段系統(tǒng)的根本原理、地址變換過(guò)程P(136)9、分頁(yè)與分段的主要區(qū)別1〔P138〕頁(yè)是信息的物理單位，分頁(yè)是為了實(shí)現(xiàn)離散分配方式，以消減存的外零頭，提高存利用率，分頁(yè)是由于系統(tǒng)管理的需要而不是用戶的需要。段則是信息的邏輯單位，分段的目的是為了能更好地滿足用戶的需要。頁(yè)的大小固定且由系統(tǒng)決定；而段的長(zhǎng)度卻不固定，取決于用戶所編寫的程序。分頁(yè)的作業(yè)地址空間是一維的，即單一的線性地址空間；而分段的作業(yè)地址空間則是二維的。10、虛擬存儲(chǔ)器的定義、特征〔P143〕定義:虛擬存儲(chǔ)器就是僅把作業(yè)的一局部裝入存便可運(yùn)行的存儲(chǔ)器系統(tǒng)，具體說(shuō)就是指具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)存容量進(jìn)展擴(kuò)大的一種存儲(chǔ)器系統(tǒng)。特性：離散性：即非連續(xù)性，這是實(shí)現(xiàn)虛擬存儲(chǔ)器管理技術(shù)的前提；屢次性：一個(gè)作業(yè)被分成屢次調(diào)入存；對(duì)換性：允許在作業(yè)運(yùn)行過(guò)程中換入、換出；虛擬性：能夠從邏輯上擴(kuò)大存容量。11、頁(yè)面置換算法：計(jì)算缺頁(yè)次數(shù)、置換次數(shù)、缺頁(yè)率、置換率P(150)第五章設(shè)備管理1、設(shè)備管理的對(duì)象:設(shè)備、設(shè)備控制器、通道2、I/O控制方式及開展宗旨「、〔P167〕I/O系統(tǒng)是用于實(shí)現(xiàn)數(shù)據(jù)的輸入，輸出及數(shù)據(jù)存儲(chǔ)的系統(tǒng)I/O控制方式：程序I/O方式〔忙等待方式〕中斷驅(qū)動(dòng)I/O方式直接存儲(chǔ)器DMA控制方式I/O通道控制方式開展宗旨：盡量較少主機(jī)對(duì)I/O控制的干預(yù)，把主機(jī)從繁雜的I/O控制事務(wù)中解脫出來(lái)，以便更多的去完成數(shù)據(jù)處理任務(wù)。3、緩沖引入的原因〔P172〕緩和CPU與I/O設(shè)備間速度不匹配的矛盾。中斷響應(yīng)時(shí)間的限制。提高CPU和I/O設(shè)備之間的并行性。4、設(shè)備獨(dú)立性5、SPOOLING5、SPOOLING原理、組成、特點(diǎn)、共享打〕原理：在聯(lián)機(jī)情況下實(shí)現(xiàn)的外圍印機(jī)原理〔P190SPOOLING印機(jī)原理〔P190SPOOLINGSpooling系統(tǒng)的組成：輸入井和輸出井輸入緩沖區(qū)和輸出緩沖區(qū)〔為了緩和CPU與磁盤之間速度不匹配的矛盾〕輸入進(jìn)程和輸出進(jìn)程請(qǐng)求打印隊(duì)列SPOOLing系統(tǒng)的特點(diǎn)：提高了I/O的速度。將獨(dú)占設(shè)備改造為共享設(shè)備。實(shí)現(xiàn)了虛擬設(shè)備功能。共享打印機(jī)原理：共享打印機(jī)技術(shù)已被廣泛地用于多用戶系統(tǒng)和局域網(wǎng)絡(luò)中。當(dāng)用戶進(jìn)程請(qǐng)求打印輸出時(shí)，SPOOLing系統(tǒng)同意為它打印輸出，但并不真正立即把打印機(jī)分配給該用戶進(jìn)程，而只為它做兩件事：由輸出進(jìn)程在輸出井中為之申請(qǐng)一個(gè)空閑磁盤塊區(qū)，并將要打印的數(shù)據(jù)送入其中；輸出進(jìn)程再為用戶進(jìn)程申請(qǐng)一空白的用戶請(qǐng)求打印表，并將用戶的打印要求填入其中，再將該表掛到請(qǐng)求打印隊(duì)列上。6、磁盤時(shí)間包括什么.〔P193〕尋道時(shí)間Ts旋轉(zhuǎn)延遲時(shí)間Tt減少對(duì)CPU的中斷頻率，放寬對(duì)CPU傳輸時(shí)間Tt減少對(duì)CPU的中斷頻率，放寬對(duì)CPU7、磁盤調(diào)度算法：計(jì)算平均尋道長(zhǎng)度P(194)第六章文件管理1、文件文件是指由創(chuàng)立者所定義的、具有文件名的一組相關(guān)元素的集合，可分為有構(gòu)造文件和無(wú)構(gòu)造文件兩種。在有構(gòu)造的文件中，文件由假設(shè)干個(gè)相關(guān)記錄組成；而無(wú)構(gòu)造文件則被看成是一個(gè)字符流。文件在文件系統(tǒng)中是一個(gè)最大的數(shù)據(jù)單位，它描述了一個(gè)對(duì)象集。2、文件的邏輯構(gòu)造及分類〔P208〕文件的邏輯構(gòu)造分為兩大類：有構(gòu)造文件：即記錄式文件；記錄的長(zhǎng)度分為定長(zhǎng)記錄和變長(zhǎng)記錄無(wú)構(gòu)造文件：即流式文件〔被看成字符流〕。3、文件的物理構(gòu)造及分類〔P213〕文件的物理構(gòu)造直接與外存分配方式有關(guān)?？煞譃椋哼B續(xù)分配方式時(shí)的順序式文件構(gòu)造。分配方式時(shí)的式文件構(gòu)造。索引分配方式時(shí)的索引式文件構(gòu)造。4、文件外存分配方式「、〔P213〕連續(xù)分配。分配。索引分配。5、文件目錄，目錄查詢方式文件目錄是一種數(shù)據(jù)構(gòu)造，用于標(biāo)識(shí)系統(tǒng)中的文件及其物理地址，供檢索時(shí)使用，是文件數(shù)據(jù)塊的有序集合。目錄查詢方式：線性檢索法Hash方法6、目錄管理的要求實(shí)現(xiàn)“按名存取。提高對(duì)目錄的檢索速度。文件共享。允許文件重名。7、文件控制塊為了能對(duì)一個(gè)文件進(jìn)展正確的存取，必須為文件設(shè)置用于描述和控制的數(shù)據(jù)構(gòu)造，稱之為文件控制塊〔包含三大信息：根本信息、存取控制信息、使用信息〕8、索引節(jié)點(diǎn)概念，為什么引入索引節(jié)點(diǎn).索引節(jié)點(diǎn):采用將文件名與文件描述信息分開的方法，將文件描述信息單獨(dú)形成一個(gè)數(shù)據(jù)構(gòu)造叫索引節(jié)點(diǎn)簡(jiǎn)稱i節(jié)點(diǎn)。引入原因：由于檢索目錄文件只用到文件名，即用不到該文件的描述信息，且在檢索目錄時(shí)索引節(jié)點(diǎn)不用調(diào)入存，從而大大節(jié)省了系統(tǒng)開銷。9、文件存儲(chǔ)空間的管理方法空閑表法空閑鏈表法位示圖法成組法〔空閑表法和空閑鏈表法都不適合大型文件系統(tǒng)〕10、成組法的空閑盤塊組織、分配回收過(guò)程順序掃描位示圖，從中找出一個(gè)或一組其值為“0的二進(jìn)制位(“0表示空閑時(shí))。將所找到的一個(gè)或一組二進(jìn)制位，轉(zhuǎn)換成與之相應(yīng)的盤塊號(hào)假定找到的其值為“0的二進(jìn)制位，位于位示圖的第i行、第j列，則其相應(yīng)的盤塊號(hào)應(yīng)按下式計(jì)算：b=n(i-1)+j式中，n代表每行的位數(shù)。修改位示圖，令map[i,j=1?？臻e盤塊的分配與回收：當(dāng)系統(tǒng)要為用戶分配文件所需的盤塊時(shí)，首先檢查空閑盤塊號(hào)棧是否上鎖，如未上鎖，便從棧頂取出一空閑盤塊號(hào)，將與之對(duì)應(yīng)的盤塊分配給用戶，然后將棧頂指針下移一格。假設(shè)該盤塊號(hào)已是棧底，即S.free(0)這是當(dāng)前棧中最后一個(gè)可分配的盤塊號(hào)。由于在該盤塊號(hào)所對(duì)應(yīng)的盤塊中記有下一組可用的盤塊號(hào)，因此，須調(diào)用磁盤讀過(guò)程，將棧底盤塊號(hào)所對(duì)應(yīng)盤塊的容讀入棧中，作為新的盤塊號(hào)棧的容，并把原棧底對(duì)應(yīng)的盤塊分配出去。在系統(tǒng)回收空閑盤塊時(shí)，將回收盤塊的盤塊號(hào)記入空閑盤塊號(hào)棧的頂部，并執(zhí)行空閑盤塊數(shù)加1操作。當(dāng)棧中空閑盤塊號(hào)數(shù)目已達(dá)1時(shí)，表示棧已滿，便將現(xiàn)有棧中的1個(gè)盤塊號(hào)，記入新回收的盤塊中，再將其盤塊號(hào)作為新棧底。第七章操作系統(tǒng)接1、操作系統(tǒng)接分為用戶接和程序接〔概念〕。用戶接包括命令接、圖形接等。2、程序接程序接是由一組系統(tǒng)調(diào)用組成。系統(tǒng)調(diào)用是在OS核心設(shè)置的一組實(shí)現(xiàn)系統(tǒng)功能的子程序〔過(guò)程〕。第八章網(wǎng)絡(luò)操作系統(tǒng)1、網(wǎng)絡(luò)操作系統(tǒng)的功能數(shù)據(jù)通信，網(wǎng)絡(luò)資源共享，應(yīng)用互操作，網(wǎng)絡(luò)管理應(yīng)用互操作包括：信息互通性和信息互用性。在Internet下，主要利用TCP/IP協(xié)議實(shí)現(xiàn)信息的互通性。2、網(wǎng)絡(luò)操作系統(tǒng)提供的效勞：域名效勞，目錄效勞，Web效勞3、目錄管理記錄了網(wǎng)絡(luò)中的三大資源物理設(shè)備，網(wǎng)絡(luò)效勞和用戶的名字，屬性和位置。1、進(jìn)程同步互斥問(wèn)題*信號(hào)量類型:整型(忙等待)、記錄型、AND型、一般信號(hào)量集解決的問(wèn)題：1、描述前趨關(guān)系：根據(jù)前趨圖，各邊分別設(shè)置信號(hào)量，初值為0；假設(shè)*邊從*節(jié)點(diǎn)出發(fā)，在此節(jié)點(diǎn)操作后，對(duì)該邊對(duì)應(yīng)信號(hào)量作signal操作；假設(shè)*邊指向*節(jié)點(diǎn)，在此節(jié)點(diǎn)操作前，對(duì)該邊對(duì)應(yīng)信號(hào)量作wait錯(cuò)作；Vara,b,c,d,e,f,g,h,i,j:semaphore:=0,0,0,0,0,0,0,0;beginparbeginbeginS1;signal(a);signal(b);end;beginwait(a);S2;signal(c);signal(d);end;beginwait(b);S3;signal(e);signal(f);end;beginwait(c);S4;signal(g);end;beginwait(d);S5;signal(h);end;beginwait(e);S6;signal(i);end;beginwait(f);S7;signal(j);end;beginwait(g);wait(h);wait(i);waitS8);end;parendend2、進(jìn)程互斥問(wèn)題〔資源共享〕*根據(jù)臨界資源的種類設(shè)置信號(hào)量的個(gè)數(shù)，初值為各臨界資源的可用數(shù)量；*在臨界資源前，對(duì)對(duì)應(yīng)信號(hào)量作wait操作；在完畢后作signal操作，即將臨界區(qū)放在wait和signal之間。3、進(jìn)程同步〔相互合作〕*為同步雙方設(shè)置各自的信號(hào)量，初值為其初始狀態(tài)可用的資源數(shù)(故該信號(hào)量稱為資源信號(hào)量或私有信號(hào)量；*同步雙方任一進(jìn)程在進(jìn)入臨界區(qū)之前，應(yīng)先對(duì)自己的信號(hào)量執(zhí)行wait(<己方信號(hào)量>)操作，以測(cè)試是否有自己可用的資源。假設(shè)有資源可用，則進(jìn)入臨界區(qū)，否則阻塞；同步雙方任一進(jìn)程離開臨界區(qū)后，應(yīng)對(duì)合作方對(duì)方)的信號(hào)量執(zhí)行signal(對(duì)方信號(hào)量>)操作，以通知(假設(shè)對(duì)方處于阻塞狀態(tài)，則喚醒它)對(duì)方已有資源可用對(duì)方已可進(jìn)入臨界區(qū))*有一個(gè)閱覽室，共有1個(gè)座位，讀者進(jìn)入時(shí)必須先在一登記表上登記，該表為每一個(gè)座位列一表目，包括座號(hào)和讀者等，讀者離開時(shí)要消掉登記的信息，試用wait,signal原語(yǔ)描述各個(gè)進(jìn)程之間的同步互斥關(guān)系。Vars,muta*:semaphore:=1,1;Reader:BeginRepeatWait(s);Wait(mute*);登記；Signal(mute*);閱覽圖書；Wait(mute*);取消登記；Signal(mute*);Signal(s);Untilfasleend桌上有一個(gè)盤子，每次只能放一個(gè)水果，爸爸專向盤中放蘋果，媽媽專向盤中放橘子，兒子專等吃盤里的桔子，女兒專等吃盤里的蘋果。只要盤子空，爸爸媽媽可向盤中放水果，僅當(dāng)盤中有自己需要的水果時(shí)，兒子或女兒可從中取出，請(qǐng)給出他們四人之間的同步關(guān)系程序。VARs,so,sa:semaphore:=1,0,0;//s表示盤空，so表示橘子，sa表示蘋果。parbeginFather:beginrepeatwait(s);putapple();signal(sa);untilfalseendMother:beginrepeatwait(s);putorange();signal(so);untilfalseendSon:beginrepaetwait(so);eatorange();signal(s);untilfalseenddaughter:beginrepeatwait(sa);eatapple();signal(s);untilfalseuntilfalse四個(gè)工人的合作endparend設(shè)公共汽車上有一位司機(jī)和一位售票員，它們的活動(dòng)如下：司機(jī)：?jiǎn)?dòng)車輛，行車，到站停車，售票員：售票；到站開門，關(guān)門請(qǐng)分析司機(jī)與售票員之間的同步關(guān)系，如何用PV操作實(shí)現(xiàn)。答：為了平安起見，顯然要求：關(guān)車門后才能啟動(dòng)車輛；到站停車后才能開車門。所以司機(jī)和售票員在到站、開門、關(guān)門、啟動(dòng)車輛這幾個(gè)活動(dòng)之間存在著同步關(guān)系。用兩個(gè)信號(hào)量S1、S2分別表示可以開車和可以開門，S1的初值為1,S2的初值為0。用PV操作實(shí)現(xiàn)司機(jī)進(jìn)程和售票員進(jìn)程同步的算法描述如下：司機(jī)：P〔S1〕；啟動(dòng)車輛；正常行車；到站停車；V〔S2〕；售票員：售票；P〔S2〕；開車門；關(guān)車門；V〔S1〕；生產(chǎn)者消費(fèi)者問(wèn)題三個(gè)進(jìn)程兩個(gè)緩沖區(qū)倆倆合作〔下頁(yè)〕；設(shè)自行車生產(chǎn)車間有兩個(gè)貨架，貨架A可以存放8個(gè)車架，貨架B可以存放20個(gè)車輪；又設(shè)有4個(gè)工人，他們的活動(dòng)是重復(fù)勞動(dòng)，分別為：工人1加工一個(gè)車架放入貨架A中；工人2、3分別加工車輪放入貨架B中〔每人每次放入1個(gè)車輪〕；工人4從貨架A中取一個(gè)車架，再?gòu)呢浖蹷中取兩個(gè)車輪，組裝成一輛自行車。試用PV操作實(shí)現(xiàn)1、系統(tǒng)中有是三個(gè)進(jìn)程GET,PRO和PUT,共用兩個(gè)緩沖區(qū)BUF1和BUF2。假設(shè)BUF1中最多可放8個(gè)信息，BUF2中最多可放5個(gè)信息。GET進(jìn)程負(fù)責(zé)不斷地將信息送入BUF1中，PRO進(jìn)程負(fù)責(zé)從BUF1中取出信息進(jìn)展處理，并將處理結(jié)果送到BUF2中，PUT進(jìn)程負(fù)責(zé)從BUF2中讀取結(jié)果并輸出。試用wait,signal原語(yǔ)〔P、V操作〕實(shí)現(xiàn)GET,PRO,PUT進(jìn)程之間的同步算法。1、var:mute*1,mute*2,empty1,empty2,full11,full2=1,1,8,5,0,0；GET:begin〔repeatwait(empty1);wait(mute*1);送入BUF1；;signal(mute*1);signal(full);untilfalseendPRO:beginrepeatwait(full1);wait(mute*1);從BUF1中取信息加工；signal(mute*1);signal(empty1);wait(empty2);wait(mute*2);將加工后的信息放入BUF2;signal(mute*2);signal(full2);untilfalseendPUT:beginrepeatwait(full2);wait(mute*2);從BUF2中取信息輸出；signal(mute*2);signal(empty2);untilfalseend【分析】設(shè)置資源信號(hào)量和互斥信號(hào)量如下：信號(hào)量Aempty表示貨架A的空位數(shù)，其初值為8；信號(hào)量Afull表示貨架A上存放的車架數(shù)，其初值為0；信號(hào)量Bempty表示貨架B的空位數(shù)，其初值為20；信號(hào)量Bfull表示貨架B上存放的車輪數(shù)，其初值為0；信號(hào)量mute*用于互斥〔初值為1〕。VarAempty,Afull,Bempty,Bfull,mute*:semaphore;Aempty.value:=8;Afull.value:=0;Bempty.value:=20;Bfull.value:=0;mute*t.value:=1;wheelcount:integer:=0;Beginparbeginworker1:beginrepeat生產(chǎn)一個(gè)車架；wait(Aempty);//看看貨架A上是否有空位置車架放到貨架A上；signal(Afull);/貨架A上的車架數(shù)增1，并通知工人4untilfalse;endWorker2，3:beginrepeat生產(chǎn)一個(gè)車輪；wait(Bempty);//看看貨架B上是否有空位置wait(mute*);將車輪放到貨架B上；signal(mute*);signal(Bfull);/貨架B上的車輪數(shù)增1，并通知工人4untilfalse;endWorker4:beginrepeatwait(Afull);wait(Bfull);wait(Bfull);取一個(gè)車架和兩個(gè)車輪；signal(Aempty);signal(Bempty);signal(Bempty);組裝一輛自行車；untilfalseendparendend哲學(xué)家就餐問(wèn)題〔非死鎖算法〕至多允許4個(gè)哲學(xué)家同時(shí)取左邊的筷子，這樣能至少保證一個(gè)哲學(xué)家能就餐，并在用畢后釋放他用過(guò)的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐?！舱?qǐng)學(xué)生考慮算法的描述〕僅當(dāng)哲學(xué)家左右兩只筷子均可用時(shí)，才允許他拿起筷子進(jìn)餐?！灿肁ND信號(hào)量機(jī)制〕規(guī)定奇數(shù)號(hào)哲學(xué)家先拿左邊筷子，然后再拿右邊筷子；而偶數(shù)號(hào)哲學(xué)家先拿右邊筷子，然后再拿左邊筷子?！?〕varchopstick:array[0,…，4]ofsemaphore:=1,1,1,1,1;Sm:semaphore:=4;beginrepeatwait(Sm);wait(chopstick[i]);wait(chopstick[(i+1)mod5]);eat;signal(chopstick[i]);signal(chopstick[(i+1)mod5);signal(Sm);think;untilfalseEnd〔2〕varchopstick:array[0,...,4]ofsemaphore:=1,1,1,1,1;beginrepeatswait(chopstick[i]，chopstick[(i+1)mod5]);eat;ssignal(chopstick[i]，chopstick[(i+1)mod5);think;untilfalseend〔3〕varchopstick:array[0,...,4]ofsemaphore:=1,1,1,1,1;beginrepeatifimod2=0thenbeginwait(chopstick[i]);wait(chopstick[(i+1)mod5]);end;elsebeginwait(chopstick[(i+1)mod5]);wait(chopstick[i]);end;eat;signal(chopstick[i]);signal(chopstick[(i+1)mod5);think;untilfalseEnd讀者寫者問(wèn)題及變形一-獨(dú)木橋問(wèn)題假定有如下獨(dú)木橋問(wèn)題：過(guò)橋時(shí)，同一方向的行人可連續(xù)過(guò)橋，當(dāng)*一方有人過(guò)橋時(shí)，另一方向的行人必須等待；當(dāng)*一方向無(wú)人過(guò)橋時(shí)，另一方向的行人可以過(guò)橋。試用信號(hào)量機(jī)制解決。答案：(1)將獨(dú)木橋的兩個(gè)方向分別標(biāo)記為A和B。用整型變量countA和countB分別表示A、B方向上已在獨(dú)木橋上的行人數(shù)。初值為0。需要設(shè)置三個(gè)初值都為1的互斥信號(hào)量：SA用來(lái)實(shí)現(xiàn)對(duì)countA的互斥，SB用來(lái)實(shí)現(xiàn)對(duì)countB的互斥，mute*用來(lái)實(shí)現(xiàn)對(duì)獨(dú)木橋的互斥使用。(2)A方向行人過(guò)橋：BeginP(SA);countA=countA+1;if(countA==1)P(mute*);V(SA);過(guò)橋；(SA);countA=countA-1;if(countA==0)V(mute*);V(SA);EndB方向行人過(guò)橋：BeginP(SB);countB=countB+l;if(countB==1)P(mute*);V(SB);過(guò)橋；P(SB);countB=countB-l;if(countB==0)V(mute*);V(SB);End處理機(jī)調(diào)度算法：先來(lái)先效勞調(diào)度算法該算法既可用于作業(yè)調(diào)度又可用于進(jìn)程調(diào)度，用于前者時(shí)，每次調(diào)度都是從外存后備隊(duì)列中選擇一個(gè)或多個(gè)作業(yè)，將它們調(diào)入存，為它們分配資源、創(chuàng)立進(jìn)程，然后將新建進(jìn)程放入就緒隊(duì)列。用于后者時(shí)，每次調(diào)度時(shí)從就緒隊(duì)列中選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，把處理機(jī)分配給它，使其運(yùn)行。FCFS算法的特點(diǎn)如下：利于長(zhǎng)作業(yè)〔進(jìn)程〕，而不利于短作業(yè)〔進(jìn)程〕利于CPU繁忙型作業(yè)〔進(jìn)程〕，而不利于I/O型繁忙作業(yè)〔進(jìn)程〕作業(yè)平均等待時(shí)間長(zhǎng)系統(tǒng)吞吐量不高短作業(yè)謎程)優(yōu)先調(diào)度算法短作業(yè)謎程)優(yōu)先調(diào)度算法SJ(P)F,是指對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先(SJF)的調(diào)度算法，是從后備隊(duì)列中選擇一個(gè)或假設(shè)干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)將它們調(diào)入存運(yùn)行。而短進(jìn)程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生*事件而被阻塞放棄處理機(jī)時(shí)，再重新調(diào)度ABCDE平均0L2i眼莎時(shí)浦135T」FCFS完成時(shí)何4?12J13圖垮桐4G1G-U1225-515SJF5?或時(shí)同19估6心同特瞬4B1$39￡㈱購(gòu)刎11STM￡.1該算法的特點(diǎn)如下:能有效降低作業(yè)平均等待時(shí)間能提高系統(tǒng)吞吐量對(duì)長(zhǎng)作業(yè)不利未考慮作業(yè)的緊迫程度，因而不能保證緊迫型作業(yè)或進(jìn)程得到及時(shí)處理。由于作業(yè)或進(jìn)程的長(zhǎng)短是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定，因而不免存在差異。高優(yōu)先權(quán)優(yōu)先調(diào)度算法非搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)算法【例3-3】設(shè)有一個(gè)最多可有兩道作業(yè)同時(shí)裝入存執(zhí)行的批處理系統(tǒng)，作業(yè)調(diào)度采用最短作業(yè)優(yōu)先調(diào)度算法，進(jìn)程調(diào)度采用搶占式靜態(tài)優(yōu)先權(quán)調(diào)度算法，今有如下純計(jì)算型作業(yè)序列〔表中所列進(jìn)程優(yōu)先數(shù)中，數(shù)值越小優(yōu)先權(quán)越高〕：列出所有作業(yè)進(jìn)入存時(shí)間及完畢時(shí)間。計(jì)算平均周轉(zhuǎn)時(shí)間。平均周轉(zhuǎn)時(shí)間=(50+30+55+55)/4=47.5(分鐘).高響應(yīng)比優(yōu)先調(diào)度算法只使用作業(yè)調(diào)度)優(yōu)先權(quán)=〔等待時(shí)間+要求效勞時(shí)間〕/要求效勞時(shí)間=響應(yīng)時(shí)間/要求效勞時(shí)間=Rp算法特點(diǎn)：如果作業(yè)的等待時(shí)間一樣，則要求效勞的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。當(dāng)要求效勞的時(shí)間一樣時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長(zhǎng)，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來(lái)先效勞。(3)對(duì)于長(zhǎng)作業(yè)，作業(yè)的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí)，其優(yōu)先級(jí)便可升到很高，從而也可獲得處理機(jī)?！纠?-4]設(shè)有一個(gè)最多可有兩道作業(yè)同時(shí)裝入存執(zhí)行的批處理系統(tǒng)，作業(yè)調(diào)度采用高響應(yīng)比優(yōu)先調(diào)度算法，進(jìn)程調(diào)度采用搶占式靜態(tài)優(yōu)先權(quán)調(diào)度算法，今有如下純計(jì)算型作業(yè)序列〔假設(shè)表中所列進(jìn)程優(yōu)先數(shù)中，數(shù)值越小優(yōu)先權(quán)越高〕：⑴列出所有作業(yè)進(jìn)入存時(shí)間及完畢時(shí)間。計(jì)算平均周轉(zhuǎn)時(shí)間。平均周轉(zhuǎn)時(shí)間=(75+30+45+55)/4=51.25(分鐘)3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法時(shí)間片輪轉(zhuǎn)法利用銀行家算法防止死鎖銀行家算法中的數(shù)據(jù)構(gòu)造可利用資源向量Available。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。最大需求矩陣Ma*。這是一個(gè)nxm的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。⑶分配矩陣Allocation這也是一個(gè)nxm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。(4)需求矩陣Need。這也是一個(gè)nxm的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。Need[i,j=Ma*[i,J-Allocation[i,j銀行家算法設(shè)Request是進(jìn)程P.的請(qǐng)求向量，如果Request.[j]=K,表示進(jìn)程七需要K個(gè)％類型的資源。當(dāng)Pj發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)展檢查：⑴如果Request.[j]<Need[i,J,便轉(zhuǎn)向步驟2;否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值。(2)如果Request[j]<Available[j],便轉(zhuǎn)向步驟(3);否則，表示尚無(wú)足夠資源，Pj須等待。系統(tǒng)試探著把資源分配給進(jìn)程P.,并修改下面數(shù)據(jù)構(gòu)造中的數(shù)值：Available[j]:=Avaitable[j]-Requesti[j];Allocatioifi,j:=Allocation[i,j+Requesti[j]；Need[i,j:=Need[i,j-Request.[j]；系統(tǒng)執(zhí)行平安性算法，檢查此次資源分配后，系統(tǒng)是否處于平安狀態(tài)。假設(shè)平安，才正式將資源分配給進(jìn)程Pi,以完本錢次分配；否則，將本次的試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程Pi等待。平安性算法(1)設(shè)置兩個(gè)向量：①工作向量Work:它表示系統(tǒng)可提供應(yīng)進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行平安算法開場(chǎng)時(shí)，Work:=Available;②Finish:它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開場(chǎng)時(shí)先做Finish[i]:=false;當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finish[i]：=true。2)從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：①Finish[i]=false;②Need[i,j<Work[j];假設(shè)找到，執(zhí)行步驟⑶浴則，執(zhí)行步驟⑷。當(dāng)進(jìn)程七獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：Work[j]：=Work[j]+Allocation[i,j;Finish[i]：=true;gotostep2;如果所有進(jìn)程的Finish[i]=true都滿足，則表示系統(tǒng)處于平安狀態(tài)；否則，系統(tǒng)處于不平安狀態(tài)。銀行家算法之例假定系統(tǒng)中有五個(gè)進(jìn)程｛P,P,P,P,P｝01234和三類資源｛A,B,C｝，各種資源的數(shù)量分別為10、5、7,在T°時(shí)刻的資源分配情況如圖3-15所示。圖3-15T°時(shí)刻的資源分配表T°時(shí)刻的平安性：圖3-16T°時(shí)刻的平安序列P］請(qǐng)求資源：P］發(fā)出請(qǐng)求向量Request卜1,0,2),系統(tǒng)按銀行家算法進(jìn)展檢查：Request1(1,0,2KNeed1(1,2,2)Request1(1,0,2KAvailable1(3,3,2)系統(tǒng)先假定可為P］分配資源，并修改Available,Allocatioq和Need1向量，由此形成的資源變化情況如圖3-15中的圓括號(hào)所示。再利用平安性算法檢查此時(shí)系統(tǒng)是否平安。圖3-17P］申請(qǐng)資源時(shí)的平安性檢查P4請(qǐng)求資源：P4發(fā)出請(qǐng)求向量Request4(3,3,0),系統(tǒng)按銀行家算法進(jìn)展檢查：Request4(3,3,0)<Neec