計(jì)算機(jī)導(dǎo)論課件：操作系統(tǒng)

3.1處?理?器?管?理3.2存儲(chǔ)管理3.3設(shè)備管理3.4文件管理操作系統(tǒng)3.1處?理?器?管?理3.1.1程序的并發(fā)執(zhí)行處理器管理的任務(wù)是當(dāng)多道程序并發(fā)執(zhí)行時(shí)，合理、自動(dòng)地分配CPU給各道程序，以提高CPU的利用率。所謂程序的并發(fā)執(zhí)行是指一組在邏輯上互相獨(dú)立的程序，在執(zhí)行過(guò)程中，其執(zhí)行時(shí)間在客觀上互相重疊，即一個(gè)程序的執(zhí)行尚未結(jié)束，另一程序的執(zhí)行已經(jīng)開始的執(zhí)行方式。與此對(duì)應(yīng)的是程序的順序執(zhí)行和并行執(zhí)行。程序的順序執(zhí)行是指一個(gè)程序執(zhí)行結(jié)束之后才開始執(zhí)行下一個(gè)程序的執(zhí)行方式。程序的并行執(zhí)行是指在多CPU系統(tǒng)中，多道程序同時(shí)執(zhí)行的執(zhí)行方式。因此，程序的并發(fā)執(zhí)行不同于并行執(zhí)行，程序的并發(fā)執(zhí)行是宏觀上的，程序“同時(shí)”執(zhí)行，微觀上，程序“交替”執(zhí)行。那么，程序如何并發(fā)執(zhí)行以提高CPU的利用率？設(shè)有三道程序A、B、C，每道程序分成輸入、處理、輸出三個(gè)程序段。例如，程序A分成輸入程序段AI、處理程序段AC、輸出程序段AO。如果這三道程序順序執(zhí)行，則當(dāng)執(zhí)行輸入程序段時(shí)，CPU和輸出設(shè)備空閑；當(dāng)執(zhí)行處理程序段時(shí)，輸入設(shè)備和輸出設(shè)備空閑；當(dāng)執(zhí)行輸出程序段時(shí)，輸入設(shè)備和CPU空閑，這樣，CPU及其它系統(tǒng)資源利用率低下。這三道程序可以如圖3-3所示地并發(fā)執(zhí)行，這樣，在虛線表示的某個(gè)時(shí)間段上，AO占用輸出設(shè)備、BC占用CPU、CI占用輸入設(shè)備，各個(gè)系統(tǒng)資源都充分利用。3.1.2進(jìn)程當(dāng)多道程序并發(fā)執(zhí)行時(shí)，程序可能“走走停?！保瑸榱烁玫乜刂撇l(fā)執(zhí)行的程序，引入了進(jìn)程。進(jìn)程是指程序?qū)o定數(shù)據(jù)集，在處理器上的一次執(zhí)行過(guò)程。進(jìn)程與程序既相關(guān)又不相同，進(jìn)程包括程序、數(shù)據(jù)和進(jìn)程控制塊；進(jìn)程與程序不是一一對(duì)應(yīng)的，一個(gè)程序可以創(chuàng)建多個(gè)進(jìn)程，一個(gè)進(jìn)程也可以由多個(gè)程序創(chuàng)建；進(jìn)程具有動(dòng)態(tài)性、生命期，因創(chuàng)建而產(chǎn)生、因調(diào)度而執(zhí)行、因得不到資源而暫停執(zhí)行、因撤消而消亡，程序只是靜態(tài)指令集合。傳統(tǒng)進(jìn)程是資源分配的基本單位，也是調(diào)度執(zhí)行的基本單位。當(dāng)進(jìn)程切換時(shí)，系統(tǒng)開銷較大，所以系統(tǒng)中的進(jìn)程不能太多，切換也不能過(guò)于頻繁，這就限制了并發(fā)程度，于是引入線程，線程是進(jìn)程的一個(gè)實(shí)體。引入線程之后，進(jìn)程繼續(xù)作為資源分配的基本單位，而線程作為新的調(diào)度執(zhí)行的基本單位。一個(gè)進(jìn)程的多個(gè)線程可以并發(fā)執(zhí)行，并且切換時(shí)的系統(tǒng)開銷較小，從而提高了并發(fā)程度。在進(jìn)程生命周期內(nèi)，根據(jù)資源分配或者調(diào)度執(zhí)行情況，進(jìn)程可以在就緒態(tài)、執(zhí)行態(tài)、阻塞態(tài)三個(gè)基本狀態(tài)之間轉(zhuǎn)換，如圖3-4所示。(1)就緒態(tài)：進(jìn)程已經(jīng)獲得除CPU之外的其它所需資源，一旦獲得CPU即可運(yùn)行，并等待分配CPU的狀態(tài)。(2)執(zhí)行態(tài)：進(jìn)程占有CPU并在CPU上執(zhí)行的狀態(tài)。(3)阻塞態(tài)：進(jìn)程尚未獲得除CPU之外的其它所需資源，即使獲得CPU也無(wú)法運(yùn)行，等待分配其它資源的狀態(tài)。進(jìn)程創(chuàng)建之后處于就緒態(tài)。就緒態(tài)進(jìn)程可以有多個(gè)，它們排成一個(gè)就緒隊(duì)列。當(dāng)CPU空閑時(shí)，按照進(jìn)程調(diào)度策略從就緒隊(duì)列中選擇一個(gè)進(jìn)程分配CPU，該進(jìn)程從就緒態(tài)轉(zhuǎn)換為執(zhí)行態(tài)。阻塞態(tài)進(jìn)程可以有多個(gè)，它們的阻塞原因可能相同也可能不同，它們按照阻塞原因排成隊(duì)列。當(dāng)?shù)却氖录l(fā)生時(shí)，例如，數(shù)據(jù)輸入完畢，喚醒等待該事件的進(jìn)程，進(jìn)程從阻塞態(tài)轉(zhuǎn)換為就緒態(tài)。3.1.3進(jìn)程控制因共享與競(jìng)爭(zhēng)資源，進(jìn)程之間將產(chǎn)生相互制約關(guān)系，主要表現(xiàn)為進(jìn)程互斥和進(jìn)程同步。1．進(jìn)程互斥進(jìn)程互斥是指一組并發(fā)進(jìn)程在同一時(shí)刻要求同一臨界資源而相互排斥。所謂臨界資源是指一次只能供一個(gè)進(jìn)程使用的資源。2．進(jìn)程同步進(jìn)程同步是指一組并發(fā)進(jìn)程為共同完成一個(gè)任務(wù)而相互合作。事實(shí)上，進(jìn)程互斥和進(jìn)程同步經(jīng)常同時(shí)出現(xiàn)。如果不對(duì)并發(fā)進(jìn)程所需資源的動(dòng)態(tài)分配加以控制，則可能出現(xiàn)死鎖。所謂死鎖是指一組并發(fā)進(jìn)程彼此互相等待對(duì)方所擁有的資源，且這組并發(fā)進(jìn)程在得到對(duì)方所擁有的資源之前不會(huì)釋放自己所擁有的資源，從而造成各并發(fā)進(jìn)程想得到資源又得不到而不能繼續(xù)向前推進(jìn)的狀態(tài)。為了解決死鎖，系統(tǒng)可以破壞死鎖產(chǎn)生的必要條件，盡可能地預(yù)防與避免死鎖，系統(tǒng)也可以建立檢測(cè)和解除死鎖的機(jī)制，即當(dāng)檢測(cè)到死鎖發(fā)生時(shí)，采用資源剝奪或進(jìn)程撤銷解除死鎖。3.2存儲(chǔ)管理3.2.1存儲(chǔ)管理方案存儲(chǔ)管理是指內(nèi)存儲(chǔ)器的管理，管理任務(wù)包括內(nèi)存的分配、回收、保護(hù)及擴(kuò)充。管理方案有分區(qū)存儲(chǔ)管理、分頁(yè)存儲(chǔ)管理、虛擬存儲(chǔ)管理、段式存儲(chǔ)管理和段頁(yè)式存儲(chǔ)管理等。1．分區(qū)存儲(chǔ)管理分區(qū)存儲(chǔ)管理是早期的存儲(chǔ)管理方案，其基本思想是：把內(nèi)存的用戶區(qū)劃分成若干區(qū)域，每個(gè)區(qū)域分配給一個(gè)用戶程序使用，并限定它們只能在自己的區(qū)域中運(yùn)行。區(qū)域的劃分方法有固定分區(qū)、可變分區(qū)和可重定位分區(qū)等。分區(qū)存儲(chǔ)管理要求程序裝入連續(xù)的內(nèi)存區(qū)域中，如果不能滿足這個(gè)要求，就需要以移動(dòng)區(qū)域使之連續(xù)為代價(jià)。為此，引入分頁(yè)存儲(chǔ)管理。2．分頁(yè)存儲(chǔ)管理分頁(yè)存儲(chǔ)管理的基本思想是：把內(nèi)存空間(實(shí)際內(nèi)存的存儲(chǔ)空間)分成若干個(gè)大小相等的塊。物理地址(內(nèi)存地址)包括塊號(hào)和塊內(nèi)地址，把虛擬空間(程序需要的存儲(chǔ)空間)分成若干個(gè)大小與塊相等的頁(yè)；邏輯地址(虛擬空間的地址，也稱為虛擬地址)包括頁(yè)號(hào)和頁(yè)內(nèi)地址。內(nèi)存分配和回收以塊為單位，一個(gè)塊存儲(chǔ)一個(gè)頁(yè)，邏輯上連續(xù)的頁(yè)可以存儲(chǔ)在物理上不連續(xù)的塊中，采用頁(yè)表存儲(chǔ)塊和頁(yè)的映射關(guān)系即每個(gè)頁(yè)的頁(yè)號(hào)、塊號(hào)等信息。上述存儲(chǔ)管理方案，不論是分區(qū)存儲(chǔ)管理還是分頁(yè)存儲(chǔ)管理，都要求程序整個(gè)裝入內(nèi)存，如果不能滿足這個(gè)要求，程序就無(wú)法運(yùn)行。為此，目前的存儲(chǔ)管理采用虛擬存儲(chǔ)管理技術(shù)，它可以提供比實(shí)際內(nèi)存大得多的虛擬內(nèi)存，保證多道程序的并發(fā)執(zhí)行。3．虛擬存儲(chǔ)管理虛擬存儲(chǔ)管理技術(shù)的基本思想是：當(dāng)程序運(yùn)行時(shí)，不是將程序一次性全部從外存裝入內(nèi)存，而是先裝入將要執(zhí)行的部分，再逐步調(diào)入需要的部分，調(diào)出不要的部分。這樣，程序大小不受內(nèi)存容量的限制，都可以調(diào)入內(nèi)存運(yùn)行。虛擬存儲(chǔ)管理技術(shù)主要有請(qǐng)求頁(yè)式管理、請(qǐng)求段式管理、請(qǐng)求段頁(yè)式管理等。下面重點(diǎn)介紹請(qǐng)求頁(yè)式管理技術(shù)。3.2.2請(qǐng)求頁(yè)式管理請(qǐng)求頁(yè)式管理是在分頁(yè)存儲(chǔ)管理的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)和頁(yè)面置換而形成的虛擬存儲(chǔ)管理技術(shù)。請(qǐng)求頁(yè)式管理的基本思想是：把內(nèi)存空間分成若干個(gè)大小相等的塊，物理地址包括塊號(hào)和塊內(nèi)地址，把虛擬空間分成若干個(gè)大小與塊相等的頁(yè)，邏輯地址包括頁(yè)號(hào)和頁(yè)內(nèi)地址。內(nèi)存分配和回收以塊為單位，一個(gè)塊存儲(chǔ)一個(gè)頁(yè)，邏輯上連續(xù)的頁(yè)可以存儲(chǔ)在物理上不連續(xù)的塊中，采用頁(yè)表存儲(chǔ)塊和頁(yè)的映射關(guān)系即每個(gè)頁(yè)的頁(yè)號(hào)、塊號(hào)、中斷位(作為是否裝入內(nèi)存的標(biāo)志)等信息。當(dāng)程序運(yùn)行時(shí)，先裝入將要執(zhí)行的頁(yè)到塊中，并設(shè)置頁(yè)表；當(dāng)訪問(wèn)某個(gè)邏輯單元時(shí)，先根據(jù)邏輯地址計(jì)算該單元的頁(yè)號(hào)和頁(yè)內(nèi)地址，然后查頁(yè)表，通過(guò)中斷位判斷該頁(yè)是否在內(nèi)存中：如果在內(nèi)存，得到該單元在內(nèi)存中的塊號(hào)和塊內(nèi)地址，再計(jì)算該單元的物理地址，最后根據(jù)物理地址訪問(wèn)相應(yīng)內(nèi)存單元；否則發(fā)生缺頁(yè)中斷，則需要請(qǐng)求調(diào)頁(yè)，即分配一個(gè)塊，將該頁(yè)調(diào)入內(nèi)存，并修改頁(yè)表，之后按在內(nèi)存的方式處理，即根據(jù)該單元在內(nèi)存中的塊號(hào)和塊內(nèi)地址計(jì)算該單元的物理地址，根據(jù)物理地址訪問(wèn)相應(yīng)的內(nèi)存單元。當(dāng)請(qǐng)求調(diào)頁(yè)時(shí)，如果內(nèi)存沒有空閑塊，就需要根據(jù)一定的算法進(jìn)行頁(yè)面置換，即調(diào)出不需要的頁(yè)，再調(diào)入需要的頁(yè)，同時(shí)修改頁(yè)表。若頁(yè)面置換算法選擇不當(dāng)，則可能造成抖動(dòng)現(xiàn)象，即剛被換出的頁(yè)又被訪問(wèn)，需要重新調(diào)入，從而導(dǎo)致系統(tǒng)頻繁置換頁(yè)面。常用的頁(yè)面置換算法有最佳置換算法、先進(jìn)先出置換算法、最近最少未使用置換算法以及最近未用置換算法。3.3設(shè)備管理3.3.1程序查詢方式程序查詢方式如圖3-6所示。CPU在運(yùn)行主程序的過(guò)程中，如果需要設(shè)備進(jìn)行數(shù)據(jù)輸入輸出，就會(huì)啟動(dòng)設(shè)備。在設(shè)備準(zhǔn)備期間，CPU處于查詢等待狀態(tài)，即CPU不停地主動(dòng)查詢?cè)O(shè)備就緒與否，直至設(shè)備就緒，從而進(jìn)行數(shù)據(jù)交換，數(shù)據(jù)輸入/輸出結(jié)束，CPU繼續(xù)運(yùn)行主程序。在這種設(shè)備管理方式下，CPU利用率低下，因?yàn)樵谠O(shè)備準(zhǔn)備期間，CPU處于查詢等待狀態(tài)。3.3.2中斷控制方式中斷是指計(jì)算機(jī)在運(yùn)行程序過(guò)程中，當(dāng)遇到需要緊急處理的事件時(shí)，暫停運(yùn)行當(dāng)前程序，轉(zhuǎn)去運(yùn)行處理緊急事件的程序(中斷服務(wù)程序)，當(dāng)處理緊急事件的程序運(yùn)行結(jié)束后，再繼續(xù)運(yùn)行暫停的程序。中斷控制方式包括中斷請(qǐng)求與中斷響應(yīng)兩類。中斷控制方式如圖3-7所示。CPU在運(yùn)行主程序的過(guò)程中，如果需要設(shè)備進(jìn)行數(shù)據(jù)輸入/輸出，就會(huì)啟動(dòng)設(shè)備。在設(shè)備準(zhǔn)備期間，CPU繼續(xù)運(yùn)行主程序，設(shè)備就緒后向CPU發(fā)出中斷請(qǐng)求，CPU收到中斷請(qǐng)求后判斷是否進(jìn)行中斷響應(yīng)，如果響應(yīng)，CPU暫停運(yùn)行主程序，轉(zhuǎn)去運(yùn)行中斷服務(wù)程序，進(jìn)行數(shù)據(jù)交換，數(shù)據(jù)輸入/輸出結(jié)束，CPU返回繼續(xù)運(yùn)行主程序。與程序查詢方式相比，中斷控制方式提高了CPU利用率，因?yàn)樵谠O(shè)備準(zhǔn)備期間，CPU可以繼續(xù)運(yùn)行主程序而無(wú)需等待。3.4文件管理3.4.1多重索引結(jié)構(gòu)文件的三級(jí)索引結(jié)構(gòu)如圖3-8所示。文件的索引節(jié)點(diǎn)不僅存儲(chǔ)了文件名、文件大小等文件描述信息，還存儲(chǔ)了若干找到文件數(shù)據(jù)信息的指針。圖中包括直接塊指針12項(xiàng)，一次間接塊指針、二次間接塊指針和三次間接塊指針各1項(xiàng)。所謂直接塊是存儲(chǔ)文件數(shù)據(jù)信息的數(shù)據(jù)塊，即通過(guò)直接塊指針找到一個(gè)數(shù)據(jù)塊，該數(shù)據(jù)塊中存儲(chǔ)的是文件數(shù)據(jù)信息。一次間接塊是存儲(chǔ)直接塊地址的數(shù)據(jù)塊，即通過(guò)一次間接塊指針找到一個(gè)數(shù)據(jù)塊，該數(shù)據(jù)塊中存儲(chǔ)的是若干直接塊地址，再通過(guò)這些直接塊地址找到數(shù)據(jù)塊，這些數(shù)據(jù)塊中存儲(chǔ)的才是文件數(shù)據(jù)信息；二次間接塊是存儲(chǔ)一次間接塊地址的數(shù)據(jù)塊；三次間接塊則是存儲(chǔ)二次間接塊地址的數(shù)據(jù)塊。3.4.2多級(jí)目錄結(jié)構(gòu)為了實(shí)現(xiàn)文件的按名存取，可將文件控制塊組織成目錄，以便于文件的按名檢索。為了更好地管理文件，例