北林操作系統(tǒng)2015級教材用書：《操作系統(tǒng)實用教程》第三版 任愛華帜讲，王雷

我的復(fù)習(xí).jpg

概念題：

實時操作系統(tǒng)：指操作系統(tǒng)能及時(或即時)響應(yīng)外部事件的請求缨该，和實施任務(wù)相結(jié)合能在規(guī)定的時間內(nèi)完成對該事件的處理，并控制所有實時任務(wù)協(xié)調(diào)一致地運行。

可分為實時處理系統(tǒng)和實時控制系統(tǒng)兩類晰韵。

主要特點：專用性強惹挟，種類多，用途各異气筋，人工干預(yù)少拆内；基本特征是事件驅(qū)動設(shè)計。

分布式操作系統(tǒng)：通過通信網(wǎng)絡(luò)將物理上分布的具有自治功能的計算機系統(tǒng)互連起來宠默，實現(xiàn)信息交換和資源共享麸恍，協(xié)作完成任務(wù)。處理和控制的分散（相對于集中式系統(tǒng)）是其主要特點搀矫。

分布式系統(tǒng)是以計算機網(wǎng)絡(luò)為基礎(chǔ)的抹沪，它的基本特征是處理上的分布，即功能和任務(wù)的分布瓤球。

分布式操作系統(tǒng)的所有系統(tǒng)任務(wù)可在系統(tǒng)中任何處理機上運行融欧，自動實現(xiàn)全系統(tǒng)范圍內(nèi)的任務(wù)分配并自動調(diào)度各處理機的工作負(fù)載。

分布式操作系統(tǒng)特點: 系統(tǒng)狀態(tài)的不精確性卦羡；控制機構(gòu)的復(fù)雜性噪馏；通信開銷引起性能的下降；

嵌入式系統(tǒng)：用于控制绿饵、監(jiān)視或者輔助操作機器和設(shè)備的裝置欠肾。它一般由嵌入式微處理器、外圍硬件設(shè)備拟赊、嵌入式操作系統(tǒng)以及用戶的應(yīng)用程序等四個部分組成,軟硬件可裁剪刺桃。

嵌入式操作系統(tǒng)：運行在嵌入式智能芯片環(huán)境中，對整個智能芯片以及它所操作要门、控制的各種部件裝置等等資源進行統(tǒng)一協(xié)調(diào)虏肾、調(diào)度、指揮和控制的系統(tǒng)軟件欢搜。

原語：由若干條機器指令構(gòu)成的用于完成特定功能的一段程序封豪。

進程：具有獨立功能的程序關(guān)于某個數(shù)據(jù)集合上的一次運行活動，是系統(tǒng)進行資源分配和調(diào)度的獨立單位炒瘟。進程的組成（程序+進程控制塊+數(shù)據(jù)）

線程：是進程的一個實體吹埠，是CPU調(diào)度的基本單位。（不擁有系統(tǒng)資源，它與同屬同一個進程的其他線程共享進程所擁有的全部資源缘琅。）

死鎖：如果一個進程集合中的每個進程都在等待只能由該集合中的其他一個進程才能引發(fā)的事件粘都，則稱這一組進程或系統(tǒng)此時發(fā)生了死鎖。

資源：需要排他性使用的對象稱為資源刷袍。分為可搶占式和不可搶占式翩隧。

虛擬存儲：虛擬存儲器的基本思想是把作業(yè)地址空間和實際主存的存儲空間，視為兩個不同的概念呻纹。一個計算機系統(tǒng)采用一定技術(shù)為程序員提供了一個足夠大的地址空間堆生，而完全不必考慮實際主存的大小。

內(nèi)存交換：多個程序并發(fā)執(zhí)行雷酪，將暫時不能執(zhí)行的程序送到外存中淑仆，從而獲得內(nèi)存空間來裝入新程序，或讀入達(dá)就緒狀態(tài)的進程哥力。交換單位為整個進程的地址空間蔗怠。

顛簸（抖動）在虛存中，頁面在內(nèi)存與外存之間頻繁調(diào)度吩跋，以至于調(diào)度頁面所需時間比進程實際運行的時間還多寞射，此時系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰钞澳。這種現(xiàn)象稱為顛簸或抖動怠惶。

文件：是指具有符號名的數(shù)據(jù)信息的集合。

目錄：文件系統(tǒng)層次結(jié)構(gòu)的一個非終結(jié)節(jié)點轧粟，一個目錄通常包含有許多目錄項，每個目錄項可以是一個文件或目錄（文件控制塊或目錄的有序集合）脓魏。

用戶態(tài)和系統(tǒng)態(tài)：系統(tǒng)程序工作的狀態(tài)稱為管態(tài)或系統(tǒng)態(tài)兰吟；用戶工作的狀態(tài)稱為算態(tài)或用戶態(tài)。

系統(tǒng)調(diào)用：指系統(tǒng)為用戶程序調(diào)用操作系統(tǒng)核心實現(xiàn)系統(tǒng)功能的過程茂翔。

邏輯地址混蔼、物理地址和地址映射：

1.邏輯地址（相對地址，虛地址）：用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼珊燎，目標(biāo)代碼通常采用相對地址的形式惭嚣。其首地址為0，其余指令中的地址都相對于首地址來編址悔政。不能用邏輯地址在內(nèi)存中讀取信息晚吞。

2.物理地址（絕對地址，實地址）：內(nèi)存中存儲單元的地址谋国。物理地址可直接尋址槽地。

3.地址映射：將用戶程序中的邏輯地址轉(zhuǎn)換為運行時由機器直接尋址的物理地址。當(dāng)程序裝入內(nèi)存時, 操作系統(tǒng)要為該程序分配一個合適的內(nèi)存空間，由于程序的邏輯地址與分配到內(nèi)存物理地址不一致, 而CPU執(zhí)行指令時捌蚊，是按物理地址進行的集畅，所以要進行地址轉(zhuǎn)換。

內(nèi)存緊縮(compaction)：將各個占用分區(qū)向內(nèi)存一端移動缅糟。使各個空閑分區(qū)聚集在另一端挺智，然后將各個空閑分區(qū)合并成為一個空閑分區(qū)。

臨界區(qū)和臨界資源:一次僅供一個進程使用的資源窗宦。在進程中涉及到臨界資源的程序段叫臨界區(qū).

物理轉(zhuǎn)儲和邏輯轉(zhuǎn)儲

①　物理轉(zhuǎn)儲：從磁盤的第0塊開始逃贝，將全部磁盤塊按順序輸出到存儲設(shè)備上，直到最后一塊復(fù)制完畢迫摔。

②　邏輯轉(zhuǎn)儲：從一個或幾個指定的目錄開始沐扳，并遞歸的轉(zhuǎn)儲其自給定基準(zhǔn)日期后，有所更改的全部文件和目錄句占。

簡答題：

1沪摄、程序、進程纱烘、線程的基本概念及區(qū)別

進程：具有獨立功能的程序關(guān)于某個數(shù)據(jù)集合上的一次運行活動杨拐，是系統(tǒng)進行資源分配和調(diào)度的獨立單位。

線程：是進程的一個實體擂啥，是CPU調(diào)度的基本單位哄陶。（不擁有系統(tǒng)資源，它與同屬同一個進程的其他線程共享進程所擁有的全部資源）

程序：程序是一組指令的有序集合哺壶。

進程與程序的區(qū)別：

1屋吨、進程-動態(tài)，程序-靜態(tài)：作為程序的執(zhí)行山宾，進程通常不可在計算機之間遷移至扰；作為有序代碼集合，程序?qū)?yīng)的文件是靜態(tài)资锰、和可復(fù)制的敢课。

2、進程與程序的組成不同：進程的組成包括程序绷杜、數(shù)據(jù)和進程控制塊（即進程狀態(tài)信息）直秆。

3、進程能真實描述并發(fā)執(zhí)行鞭盟，程序不能：進程是獨立調(diào)度并能和其他進程并行執(zhí)行的單位圾结。

4、進程可以創(chuàng)建其它進程懊缺，而程序不能疫稿；

5培他、進程是暫時的，程序是永久的：進程是一個狀態(tài)變化的過程遗座，程序可長久保存舀凛。

6、進程與程序的對應(yīng)關(guān)系：通過多次執(zhí)行途蒋，一個程序可對應(yīng)多個進程猛遍；通過調(diào)用關(guān)系，一個進程可包括多個程序号坡。

進程和線程的比較

1懊烤、 進程是資源分配的基本單位。線程與資源分配無關(guān)宽堆，它只屬于某一個進程腌紧，并與進程內(nèi)其他線程一起共享進程的資源。

2畜隶、進程發(fā)生調(diào)度時壁肋，不同的進程擁有不同的虛擬地址空間，而同一進程內(nèi)的不同線程共享同一地址空間籽慢。

3浸遗、進程包含了PCB，用戶地址空間和堆棧箱亿。線程只由相關(guān)的堆棧（用戶棧和系統(tǒng)棧）跛锌、寄存器和線程控制表TCB組成。

4届惋、進程切換時將涉及到有關(guān)資源指針的保存以及地址空間的變化等問題髓帽。線程切換時，由于同一進程

內(nèi)的線程共享資源和地址空間盼樟，將不涉及上述內(nèi)容的保存氢卡，故減少了操作系統(tǒng)的開銷時間。

5晨缴、進程的調(diào)度與切換都是由操作系統(tǒng)內(nèi)核完成，而線程則既可由操作系統(tǒng)內(nèi)核完成峡捡，也可由用戶程序進行击碗。

2、進程的組成们拙，基本狀態(tài)稍途，三狀態(tài)模型，五狀態(tài)模型

進程的組成【代碼+PCB（進程控制塊砚婆、進程狀態(tài)信息）+數(shù)據(jù)】

代碼—程序械拍；資源句柄—分配的資源突勇；寄存器—執(zhí)行狀態(tài)；堆椏缆牵—運行場景甲馋；數(shù)據(jù)—特定的數(shù)據(jù)集合

基本狀態(tài)：就緒態(tài)、運行態(tài)迄损、阻塞態(tài)

（運行定躏、就緒和阻塞三狀態(tài)模型就是對暫停狀態(tài)的細(xì)化）

就緒態(tài)（Ready）：一個進程已經(jīng)具備運行條件，當(dāng)調(diào)度給其CPU時芹敌，立即可以運行痊远；

運行態(tài)（Running）：執(zhí)行狀態(tài)：

阻塞態(tài)（Blocked）：指進程因等待某種事件的發(fā)生而暫時不能運行的狀態(tài)。

其他狀態(tài)：創(chuàng)建態(tài)氏捞、結(jié)束態(tài)

進程的三種基本狀態(tài)及其轉(zhuǎn)換.png

進程的五種基本狀態(tài)及其轉(zhuǎn)換.png

含進程控制原語的五狀態(tài)模型.png

3碧聪、臨界資源、臨界區(qū)液茎、臨界區(qū)訪問原則

臨界資源:一次僅供一個進程使用的資源逞姿。

臨界區(qū):在進程中涉及到臨界資源的程序段。

臨界區(qū)的訪問原則：

空閑讓進：當(dāng)無進程在臨界區(qū)時豁护，任何有權(quán)使用臨界區(qū)的進程可進入

忙則等待：不允許兩個以上的進程同時進入臨界區(qū)

多中擇一：當(dāng)沒有進程在臨界區(qū)哼凯，而同時有多個進程要求進入臨界區(qū)，只能讓其中之一進入臨界區(qū)楚里，其他進程必須等待

有限等待：任何進入臨界區(qū)的要求應(yīng)在有限的時間內(nèi)得到滿足

讓權(quán)等待：處于等待狀態(tài)的進程應(yīng)放棄占用CPU断部，以使其他進程有機會得到CPU的使用權(quán).

4、四種數(shù)據(jù)傳送控制方式的工作過程：

程序直接控制方式：

外圍設(shè)備接收到CPU的start命令班缎，開始準(zhǔn)備接收或發(fā)送數(shù)據(jù)蝴光；

此過程中CPU始終等待設(shè)備，反復(fù)檢測設(shè)備的狀態(tài)达址；

設(shè)備標(biāo)志位觸發(fā)器置“done”時蔑祟，CPU才執(zhí)行下條指令開始數(shù)據(jù)傳送；

程序直接控制方式.png

中斷方式：

外圍設(shè)備接收到CPU的start命令沉唠，準(zhǔn)備數(shù)據(jù)并將其置入緩沖寄存器疆虚；

此過程中CPU調(diào)度其他進程執(zhí)行；

數(shù)據(jù)緩沖寄存區(qū)滿后满葛，設(shè)備控制器發(fā)中斷請求径簿，CPU進行中斷處理；

中斷方式.png

DMA方式：

1嘀韧、進程要求輸入數(shù)據(jù)時CPU把準(zhǔn)備存放輸入數(shù)據(jù)的內(nèi)存始址及要傳輸字節(jié)數(shù)分別送入DMA控制器中的內(nèi)存地址寄存器和字節(jié)計數(shù)器篇亭；另外，將中斷允許位和啟動位置1锄贷，從而啟動設(shè)備译蒂，開始數(shù)據(jù)輸入曼月。
2、當(dāng)前進程進入阻塞狀態(tài)柔昼， 調(diào)度程序調(diào)度其它進程執(zhí)行哑芹。
3、輸入設(shè)備不斷地挪用CPU工作周期岳锁， 將數(shù)據(jù)從內(nèi)部緩沖區(qū)源源不斷地送入內(nèi)存绩衷，直至所要求的字節(jié)數(shù)全部傳送完畢。
4激率、DMA控制器在傳輸完成時發(fā)出中斷信號咳燕， CPU接到中斷信號，進行中斷處理乒躺。

5招盲、中斷處理結(jié)束后， CPU返回被中斷的進程或去運行重新被調(diào)度的進程嘉冒。

DMA.png

通道控制方式

1曹货、 CPU：執(zhí)行用戶程序，當(dāng)遇到I/O請求時讳推，可根據(jù)該請求生成通道程序放入內(nèi)存顶籽，并將該通道程序的首地址放入CAW中；之后執(zhí)行“啟動I/O”指令银觅，啟動通道工作礼饱。
2、通道：接收到“啟動I/O”指令后究驴，從CAW中取出通道程序的首地址镊绪，并根據(jù)首地址取出第一條指令放入CCW中，同時向CPU發(fā)回答信號洒忧，使CPU可繼續(xù)執(zhí)行其他程序蝴韭，而通道則開始執(zhí)行通道程序，完成傳輸工作熙侍。
3榄鉴、當(dāng)通道傳輸完成最后一條指令時，向CPU發(fā)I/O中斷蛉抓，并且通道停止工作牢硅。CPU接收中斷信號，從CSW中取得有關(guān)信息芝雪，決定下一步做什么。

5综苔、頁式惩系、段式位岔、段頁式的工作原理及區(qū)別

頁式管理的基本原理

把用戶程序劃分成大小相等的頁，從0開始編制頁號堡牡，頁內(nèi)地址是相對于0編址進程抒抬。虛擬地址為頁號P與頁內(nèi)地址W組成。內(nèi)存空間也按頁的大小劃分為大小相等的內(nèi)存塊晤柄，以頁為單位進行分配擦剑，并按作業(yè)的頁數(shù)多少來分配。邏輯上相鄰的頁芥颈，物理上不一定相鄰惠勒，通過頁表把作業(yè)的各個頁面與頁框?qū)?yīng)起來。

段式管理的基本原理

按程序自身的邏輯關(guān)系劃分為若干程序段爬坑，每個程序段都有一個段名纠屋，且有一個段號。段號從0開始盾计，每一段也從0開始編址售担，段內(nèi)地址是連續(xù)的。虛擬地址為段號P與段內(nèi)地址W組成署辉。內(nèi)存空間被動態(tài)的劃分為若干個長度不相同的物理段族铆，以段為單位分配內(nèi)存，每一個段在內(nèi)存中占據(jù)連續(xù)空間（內(nèi)存隨機分割哭尝，需要多少分配多少）哥攘，但各段之間可以不連續(xù)存放。

段頁式管理的基本原理

按程序的邏輯關(guān)系劃分為段刚夺，并有各自的段號s献丑，對于段s中的程序或數(shù)據(jù)，則按照一定的大小將其劃分為不同的頁侠姑。虛擬地址由段號s创橄，頁號p，和頁內(nèi)地址w三個部分組成莽红。將存儲空間分成大小固定的頁妥畏，一個段中的程序或數(shù)據(jù)在內(nèi)存中可以分開存放與不相鄰的頁。

分頁與分段的主要區(qū)別：

1安吁、段是信息的邏輯單位醉蚁，它是根據(jù)用戶的需要劃分的，因此段對用戶是可見的鬼店；頁是信息的物理單位网棍，是為了管理主存的方便而劃分的，對用戶是透明的妇智。
2氏身、頁的大小固定不變惑畴，由系統(tǒng)決定。段的大小是不固定的陷虎，它由其完成的功能決定杠袱。
3、段式向用戶提供的是二維地址空間页眯，頁式向用戶提供的是一維地址空間凌唬，其頁號和頁內(nèi)偏移是機器硬件的功能。
4骗灶、由于段是信息的邏輯單位，因此便于存貯保護和信息的共享耙旦，頁的保護和共享受到限制脱羡。

段頁式是存儲：

每個程序建立一張段表，為每個段又必須建立一張頁表免都；

由于在段頁式管理中锉罐，頁表不再是屬于進程，而是屬于某個段的绕娘，因此脓规，段表中應(yīng)有專項指出該段所對應(yīng)頁表的起始地址等信息。

6险领、P/V操作的基本概念及基本工作機制

P(S)：表示申請一個資源 侨舆；

V(S)：表示釋放一個資源；

P绢陌、V操作的基本概念：P挨下、V操作均為原語操作，執(zhí)行必須是連續(xù)的脐湾，在執(zhí)行過程中不允許被中斷臭笆。

P、V操作目的：避免在執(zhí)行臨界區(qū)操作時會有其它的進程也進入臨界區(qū)，即實現(xiàn)并發(fā)進程間的互斥操作

****P操作：
（1）sem減1耗啦；
（2）若sem減1后仍大于等于0凿菩，則進程繼續(xù)執(zhí)行；
（3）若結(jié)果小于0，則該進程睡眠似将，進入等待隊列在验。

****V操作：
（1）s值加1；
（2）若相加結(jié)果大于0块饺，進程繼續(xù)執(zhí)行授艰；
（3）否則淮腾，喚醒一個等待隊列中的進程，然后本進程繼續(xù)執(zhí)行圆凰。

p.png

v.png

關(guān)于P、V操作：成對使用P和V原語：遺漏P原語則不能保證互斥訪問驶沼，遺漏V原語則不能在使用臨界資源之后將其釋放（給其他等待的進程）回怜；

P翔试、V原語不能次序錯誤垦缅、重復(fù)或遺漏壁涎。

當(dāng)為互斥操作時，它們同處于同一進程

當(dāng)為同步操作時浮还，則不在同一進程中出現(xiàn)

如果P(S1)和P(S2)兩個操作在一起担汤，那么P操作的順序至關(guān)重要,一個同步P操作與一個互斥P操作在一起時同步P操作在互斥P操作前漫试。而兩個V操作無關(guān)緊要。

信號量的使用：

必須置一次且只能置一次初值播掷；
初值不能為負(fù)數(shù)歧匈；
只能執(zhí)行P件炉、V操作
S>0表示有S個資源可用
S=0表示無資源可用
S<0則| S |表示S等待隊列中的進程個數(shù)

(信號量sem：是一個整數(shù)斟冕，在sem大于等于零時，代表可供并發(fā)資源使用的

資源實體數(shù)秀撇，但sem小于零時則表示正在等待使用臨界區(qū)的進程數(shù)棠绘。sem代表

資源的實體弄唧。)

優(yōu)點：簡單且表達(dá)能力強，用P.V操作可解決任何同步互斥問題

缺點：不夠安全敦跌；P.V操作使用不當(dāng)會出現(xiàn)死鎖；

遇到復(fù)雜同步互斥問題時實現(xiàn)復(fù)雜

看PV操作實例的代碼＞宓选患整！

7各谚、連續(xù)昌渤、隨機膀息、串聯(lián)的文件保存方式

文件的保存方式：

連續(xù)文件（順序結(jié)構(gòu)）

文件的信息存放在若干連續(xù)的物理塊中潜支。

優(yōu)點：簡單毁腿；支持順序存取和隨機存瑞啊；順序存取速度快臣嚣；所需的磁盤尋道次數(shù)和尋道時間最少

缺點：文件不能動態(tài)增長硅则；不利于文件插入和刪除；外部碎片問題

串聯(lián)文件（鏈接結(jié)構(gòu)）

文件的信息存放在若干連續(xù)的物理塊中大审，通過指針鏈接徒扶，前一個物理塊指向下一個物理塊。

優(yōu)點： 提高空間利用率溶浴；有利于文件動態(tài)擴充士败；有利于文件插入和刪除谅将；不存在外部碎片問題

缺點：不適于隨機存取隅熙；存取速度慢囚戚；更多的尋道次數(shù)和尋道時間匾二；可靠性問題察藐，如指針出錯；鏈接指針占用一定的空間

隨機文件（索引結(jié)構(gòu)）

一個文件的信息存放在若干不連續(xù)物理塊中浸须，系統(tǒng)為每個文件建立一個索引表，并將這些塊的塊號存放在索引表中顺囊。

優(yōu)點：
1.即能順序存取，又能隨機存取
2. 有利于文件動態(tài)擴充
3.有利于文件插入和刪除
4.? 不存在外部碎片問題

缺點：
1.較多的尋道次數(shù)和尋道時間午乓；
2.索引表本身帶來了系統(tǒng)開銷；

8蒸其、操作系統(tǒng)的各項基本功能以及操作系統(tǒng)的發(fā)展階段

操作系統(tǒng)的功能 :處理機管理摸袁、存儲管理蜂大、設(shè)備管理奶浦、文件管理、用戶接口耳高。

功能一泌枪、處理機管理
進程控制：創(chuàng)建、撤銷修壕、改變進程的狀態(tài)
進程調(diào)度：作業(yè)和進程的運行切換慈鸠，以充分利用處理機資源和提高系統(tǒng)性能；
進程同步：協(xié)調(diào)并發(fā)進程之間的推進步驟督笆，以協(xié)調(diào)資源共享娃肿；
進程通信：進程之間傳送數(shù)據(jù)咸作，以協(xié)調(diào)進程間的協(xié)作；

功能二桐智、存儲管理：
目標(biāo)：提高利用率说庭、方便用戶使用姿搜、提供足夠的存儲空間舅柜、方便進程并發(fā)運行致份。
存儲分配與存儲無關(guān)性：地址重定位（地址映射）
存儲保護：保證進程間互不干擾、相互保密滔蝉；
存儲擴充：提高主存利用率锰提、擴大進程的主存空間边坤；

功能三肮韧、設(shè)備管理：
目標(biāo)：方便設(shè)備使用弄企、提高CPU與I/O設(shè)備利用率；
設(shè)備無關(guān)性：提供統(tǒng)一的I/O設(shè)備接口约素；
設(shè)備分配與回收：在多用戶間共享I/O設(shè)備資源圣猎。
虛擬設(shè)備：設(shè)備由多個進程共享慢显，每個進程如同獨占荚藻。
設(shè)備的傳輸控制：利用設(shè)備驅(qū)動程序完成對設(shè)備的操作鞋喇。

功能四、文件管理：
目標(biāo)：解決軟件資源的存儲罐韩、共享散吵、保密和保護。
文件存儲空間管理：解決如何存放信息枚冗，以提高空間利用率。
目錄管理：解決信息檢索問題股囊，方便用戶按名存取稚疹。
文件的讀寫管理和存取控制：解決信息安全問題穆壕。
軟件管理：軟件的版本喇勋、相互依賴關(guān)系、安裝和拆除等。

功能五妙真、用戶接口：
目標(biāo)：提供一個友好的用戶訪問操作系統(tǒng)的接口练般。
系統(tǒng)命令：供用戶用于組織和控制自己的作業(yè)運行。
編程接口：供用戶程序和系統(tǒng)程序調(diào)用操作系統(tǒng)功能摄职。
圖形接口：窗口谷市、菜單和對話框

操作系統(tǒng)發(fā)展史：

（1）1946-50年代：無操作系統(tǒng)時代，工作環(huán)境 是電子管計算機
（2）50-60年代：單道批處理系統(tǒng)
（3）60年代中-70年代：多道批處理系統(tǒng)
（4）70年代中期至今：分時系統(tǒng)-個人計算機

9、文件系統(tǒng)的層次結(jié)構(gòu)

文件系統(tǒng)的層次結(jié)構(gòu).png

10、安全設(shè)計原則

①　應(yīng)該公開系統(tǒng)設(shè)計方案又跛。
②　默認(rèn)規(guī)則應(yīng)該是不能訪問感混。
③　檢查當(dāng)前權(quán)限。
④　給每個進程盡可能小的權(quán)限庭呜。
⑤　保護機制應(yīng)該簡單。
⑥　所選的安全方案應(yīng)該是心理上可接受的。
⑦　設(shè)計盡可能簡單拐纱。

11、文件備份的考慮問題和因素

處理兩個潛在問題：從意外的災(zāi)難中恢復(fù)咕宿，從愚蠢的操作中恢復(fù)。

考慮的因素：
備份整個文件系統(tǒng)還是僅一部分
增量轉(zhuǎn)儲結(jié)合周期性的全面的轉(zhuǎn)儲
備份前進行壓縮操作
對當(dāng)前活動的文件進行轉(zhuǎn)儲比較困難芽突，即備份時發(fā)生增刪修改等操作
要面臨許多非技術(shù)問題试浙，例如，人員的行為管理

12寞蚌、多媒體進程調(diào)度(詳見第八章)

①　調(diào)度同質(zhì)進程：固定數(shù)目的電影田巴，所有電影使用相同的幀率、視頻分辨率挟秤、數(shù)據(jù)率以及其他參數(shù)。所有進程同等，輪換調(diào)度，加上定時機制老保證每個進程以恰當(dāng)?shù)膸蕚鬏敗?/p>

②　一般實時調(diào)度：實際中燕雁，電影數(shù)目懂衩，壓縮后的幀大小分辨率等差異大法希。多個相互競爭的進程屋剑，其中若干進程或全部進程具有必須滿足的最終時限的調(diào)度成為實時調(diào)度。特點：最終時限使得存在搶先的特性。有時并不一定存在可調(diào)度的方案梅鹦。

③　速率單調(diào)調(diào)度：靜態(tài)的實時調(diào)度算法箍邮。滿足條件：每個周期性進程必須在其周期內(nèi)完成味滞。沒有進程依賴于任何其他進程。每一個進程再一次突發(fā)中需要相同的CPU時間量。任何非周期性進程都沒有最終時限镇饺。進程搶先即刻發(fā)生而沒有系統(tǒng)開銷。

④　最早最終時限優(yōu)先調(diào)度：一種動態(tài)算法，不考慮周期性父虑，不考慮每個CPU突發(fā)有相同的時間。只要一個進程需要CPU時間，它就宣布它的到來和最終時限勒极。調(diào)度程序維護一個可運行進程的列表，該列表按照最終時限排序邑贴。edf算法運行列表中的第一個進程秕狰。新進程就緒，檢查是否最終時限在當(dāng)前運行進程結(jié)束之前莉恼，如果是吱七，則新進程搶占CPU

13苍碟、死鎖的產(chǎn)生原因和必備條件

原因：系統(tǒng)資源不足；進程推進順序不合適彼城；

必要條件 ：

1. 互斥控制（資源獨占）
2. 非剝奪控制（不可剝奪）
3. 請求和保持（部分分配代嗤，占有申請）
4. 環(huán)路條件（循環(huán)等待）

14、多處理機系統(tǒng)的三種典型結(jié)構(gòu)（詳見第八章）

共享存儲器的多處理機；主從多處理機；對稱多處理機

15麻诀、邏輯地址挪丢、物理地址以及地址映射的基本過程

1. 邏輯地址（相對地址趋距，虛地址）：用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼城须，目標(biāo)代碼通常采用相對地址的形式。
   – 其首地址為0，其余指令中的地址都相對于首地址來編址饭庞。
   – 不能用邏輯地址在內(nèi)存中讀取信息。

2. 物理地址（絕對地址菇绵，實地址）：內(nèi)存中存儲單元的地址望几。物理地址可直接尋址慌随。

3. 地址映射：將用戶程序中的邏輯地址轉(zhuǎn)換為運行時由機器直接尋址的物理地址捎谨。
   – 當(dāng)程序裝入內(nèi)存時, 操作系統(tǒng)要為該程序分配一個合適的內(nèi)存空間，由于程序的邏輯地址與分配到內(nèi)存物理地址不一致, 而CPU執(zhí)行指令時御毅，是按物理地址進行的今豆，所以要進行地址轉(zhuǎn)換嫌拣。

地址映射.png

16、與實驗有關(guān)的經(jīng)典同步/互斥問題

同步：進程之間的一種通信方式呆躲，有時序上的制約關(guān)系异逐，或者說是進程之間為了協(xié)同工作而存在的一種等待關(guān)系。

互斥：進程之間對臨界資源的一種競爭關(guān)系插掂，排他性地對資源的訪問方式灰瞻。

(生產(chǎn)者與消費者/ 讀者與寫者)

17、各種經(jīng)典的調(diào)度算法

①　FCFS先來先服務(wù)
②　SJF短作業(yè)優(yōu)先
③　HRF高響應(yīng)比優(yōu)先
④　HPF高優(yōu)先級優(yōu)先
⑤　資源均衡型調(diào)度

18辅甥、中斷執(zhí)行的過程

中斷執(zhí)行的過程.png

19酝润、系統(tǒng)調(diào)用與普通調(diào)用的區(qū)別：

相同點：
? 改變指令流程
? 重復(fù)執(zhí)行和公用
? 改變指令流程后需要返回原處同

不同點：
? 系統(tǒng)調(diào)用是動態(tài)調(diào)用，而CALL調(diào)用方式是靜態(tài)調(diào)用璃弄；
? 執(zhí)行狀態(tài)不同
? 內(nèi)部實現(xiàn)過程不同
? 與進程調(diào)度的關(guān)系不同：
? 嵌套或遞歸調(diào)用

計算題
【例1】下表給出作業(yè)l要销，2，3的提交時間和運行時間夏块。采用先來先服務(wù)調(diào)度算法和短作業(yè)優(yōu)先調(diào)度算法疏咐，試問作業(yè)調(diào)度次序和平均周轉(zhuǎn)時間各為多少？（時間單位：小時脐供，以十進制進行計算凳鬓。）

解：采用先來先服務(wù)調(diào)度策略，則調(diào)度次序為l患民、2缩举、3。

平均周轉(zhuǎn)時間T＝（8＋11.6＋12）/3＝10.53

采用短作業(yè)優(yōu)先調(diào)度策略，則調(diào)度次序為l仅孩、3托猩、2。

平均周轉(zhuǎn)時間T＝（8＋8＋12.6）/3＝9.53

【例2】在一個單道的程序設(shè)計系統(tǒng)中辽慕，有3個作業(yè)J1京腥、J2、J3溅蛉，它們到達(dá)輸入井的時間分別為8：50公浪、9：00、9：30船侧，它們需要執(zhí)行的時間分別為1.5小時欠气、0.4小時、1小時镜撩。系統(tǒng)在10：00按響應(yīng)比高者優(yōu)先算法對它們進行調(diào)度预柒，請回答：

（1）作業(yè)被選中執(zhí)行的次序是什么？ （2）作業(yè)被選中時的響應(yīng)比分別是多少袁梗？
分析： 響應(yīng)比＝作業(yè)周轉(zhuǎn)時間/作業(yè)運行時間 ＝1＋作業(yè)等待時間/作業(yè)運行時間

系統(tǒng)在10：00宜鸯，計算作業(yè)的響應(yīng)比：

以J1為例，它的作業(yè)計算時間是1.5小時遮怜，即90分鐘淋袖；J1從8：50到達(dá)輸入井，在10：00時刻锯梁，J1的等待時間為70分鐘即碗，因此作業(yè)J1的響應(yīng)比為：

1＋70分鐘/90分鐘=1.77
同理，J2：1＋60分鐘/24分鐘=3.5 J3：1＋30分鐘/60分鐘=1.5
因此按照響應(yīng)比高者優(yōu)先算法涝桅，優(yōu)先調(diào)度J2拜姿。
在10：24烙样，J2完成冯遂。這時計算J1、J3的響應(yīng)比：
J1：1＋（70＋24）分鐘/90分鐘=2.04 J3：1＋（30＋24）分鐘/60分鐘=1.9
按照響應(yīng)比高者優(yōu)先算法谒获，優(yōu)先調(diào)度J1蛤肌。
在11：54，J1完成批狱，系統(tǒng)調(diào)度J3裸准，J3的響應(yīng)比為

1＋（30＋24＋90）分鐘/60分鐘=3.4

因此，作業(yè)被選中執(zhí)行的次序是J2赔硫、J1炒俱、J3。
三個作業(yè)被選中時的響應(yīng)比分別是：J1，2.04权悟；J2砸王，3.5；J3峦阁，3.4谦铃。

解：（1）作業(yè)被選中執(zhí)行的次序是J2、J1榔昔、J3驹闰。
（2）三個作業(yè)被選中時的響應(yīng)比分別是：J1，1.04撒会；J2嘹朗，2.5；J3茧彤，2.4骡显。

【例3】設(shè)有進程A、B曾掂、C惫谤、D依次進入就緒隊列（相隔一個時間單位），它們的優(yōu)先級（優(yōu)先數(shù)大的優(yōu)先級較高）如下表所示：

求采用“先來先服務(wù)”珠洗、“靜態(tài)優(yōu)先數(shù)法”調(diào)度算法（注：優(yōu)先數(shù)大的優(yōu)先級高）溜歪，選中進程的執(zhí)行次序。

解：采用先來先服務(wù)調(diào)度算法许蓖，按照進程進入就緒隊列的先后次序占有CPU蝴猪，其執(zhí)行次序是A-B-C-D。
采用靜態(tài)優(yōu)先數(shù)法膊爪，進程A最先就緒自阱，在0時刻先占有CPU運行，隨后1時刻進程B進入就緒隊列米酬，2時刻進程C進入就緒隊列沛豌，3時刻進程D進入就緒隊列。由于采用靜態(tài)優(yōu)先數(shù)法赃额，不容許隨時間的推移改變進程的優(yōu)先級加派，所以當(dāng)進程A運行結(jié)束時，系統(tǒng)的就緒隊列中有B跳芳、C芍锦、D三個進程，而進程C優(yōu)先級最高飞盆，于是選中C娄琉；這樣分析下去次乓，進程的執(zhí)行次序是A-C-D-B。

【例4】在一分頁存儲管理系統(tǒng)中,邏輯地址長度為16位,頁面大小為4096字節(jié),現(xiàn)有一邏輯地址為2F6AH,且第0, 1, 2頁依次存放在物理塊5, 10 ,11中,問相應(yīng)的物理地址為多少?

解:由題目所給給條件可知,本頁式系統(tǒng)的邏輯地址結(jié)構(gòu)為:

頁號P,頁內(nèi)位移W

邏輯地址2F6AH的二進制表示如下:

由此可知邏輯地址2F6AH的頁號為2,該頁存放在第11號物理塊中,用十六進制表示志號為B,所以物理地址為BF6AH.

【例5】（南開大學(xué)1994年試題）在采用頁式存儲管理的系統(tǒng)中孽水，默作業(yè)J的邏輯地址空間為4頁（每頁2048字節(jié)）檬输，且已知該作業(yè)的頁面映象表（即頁表）如下：

試借助地址變換圖（即要求畫出地址變換圖）求出有效邏輯地址4865所對應(yīng)的物理地址。

解：在本題中匈棘，一頁大小為2048字節(jié)丧慈，則邏輯得志4865的頁號機頁內(nèi)位移:為：

頁號： 4865/2048=2

頁內(nèi)位移 4865-2048x2=769

然后，通過頁表查知物理塊號為6主卫，將物理塊號與邏輯地址中的頁內(nèi)位移拼接逃默，形成物理地址，即：6*2048+769=13057

【例6】考慮一個由8個頁面簇搅，每頁有1024個字節(jié)組成的邏輯空間完域，把它裝入到有32個物理塊的存儲器中，問： （1）邏輯地址需要多少二進制位表示瘩将？ （2）物理地址需要多少二進制位表示吟税？

分析 在分頁存儲管理中，邏輯地址結(jié)構(gòu)如下圖所示姿现。

它由兩個部分組成：前一部分表示該地址所在頁面的頁號p肠仪；后一部分表示頁內(nèi)地址（頁內(nèi)位移）d。頁號的地址位數(shù)決定了頁的多少备典，假設(shè)頁號有20位异旧，則地址空間中最多可容納的頁面數(shù)為220，即1MB個頁面提佣。頁內(nèi)地址位數(shù)確定了每頁的大小吮蛹，若頁內(nèi)地址為12位，則每頁大小為212拌屏，即2KB潮针。

同理，物理地址中塊號的地址位數(shù)決定了塊的數(shù)量倚喂。由于頁式存儲管理內(nèi)存空間塊的大小與頁面大小相同每篷，所以物理地址中塊內(nèi)地址與邏輯地址中的頁內(nèi)地址位數(shù)相同。

解 因為頁面數(shù)為8=23务唐，故需要3位二進制數(shù)表示雳攘。每頁有1024個字節(jié)带兜， 1024=210枫笛，于是頁內(nèi)地址需要10位二進制數(shù)表示。32個物理塊刚照，需要5位二進制數(shù)表示（32=25）刑巧。
（1）頁的邏輯地址由頁號和頁內(nèi)地址組成，所以需要3+10=13位二進制數(shù)表示。
（2）頁的物理地址由塊號和頁內(nèi)地址的拼接啊楚，所以需要5+10=15位二進制數(shù)表示吠冤。

【例7】若在一分頁存儲管理系統(tǒng)中，某作業(yè)的頁表如下所示恭理。已知頁面大小為1024字節(jié)拯辙，試將邏輯地址1011，2148颜价，4000涯保，5012轉(zhuǎn)化為相應(yīng)的物理地址。

分析 頁式存儲管理的地址結(jié)構(gòu)是一維的周伦，即邏輯地址（或物理地址）只用一個數(shù)值即可表示夕春。若給定邏輯地址A，頁面的大小為L专挪，則頁號p和頁內(nèi)地址d可按照下式求得： p=int [A/L] d=A mod L

其中及志，int是取整函數(shù)（取數(shù)值的整數(shù)部分），mod是取余函數(shù)（取數(shù)值的余數(shù)部分）寨腔。

物理地址的計算公式為：
物理地址＝塊的大兴俪蕖（即頁的大小L）x 塊號f＋頁內(nèi)地址d

解: 本題中，為了描述方便迫卢，設(shè)頁號為p锌畸，頁內(nèi)位移為d，則：
（1）對于邏輯地址1011靖避，p＝int（1011/1024）＝0潭枣，d＝1011 mod 1024＝1011。查頁表第0頁在第2塊幻捏，所以物理地址為1024*2＋1011＝3059盆犁。
（2）對于邏輯地址2148，p＝int（2148/1024）＝2篡九，d＝2148 mod 1024＝100谐岁。查頁表第2頁在第1塊，所以物理地址為1024＋100＝1124榛臼。
（3）對于邏輯地址4000伊佃，p＝int（4000/1024）＝3，d＝4000 mod 1024＝928沛善。查頁表第3頁在第6塊航揉，所以物理地址為1024*6＋928＝7072。
（4）對于邏輯地址5012金刁，p＝int（5012/1024）＝4帅涂，d＝5012 mod 1024＝916议薪。因頁號超過頁表長度，該邏輯地址非法媳友。

【例8】某虛擬存儲器的用戶編程空間共32個頁面斯议，每頁為1KB，內(nèi)存為16KB醇锚。假定某時刻一用戶頁表中已調(diào)入內(nèi)存的頁面的頁號和物理塊號的對照表如下：

問：邏輯地址0A5C（H）所對應(yīng)的物理地址是什么哼御？

分析 頁式存儲管理的邏輯地址分為兩部分：頁號和頁內(nèi)地址。

由已知條件“用戶編程空間共32個頁面”焊唬，可知頁號部分占5位艇搀；由“每頁為1KB”，1K=210求晶，可知內(nèi)頁地址占10位焰雕。由“內(nèi)存為16KB”，可知有16塊芳杏，塊號為4位矩屁。

邏輯地址0A5C（H）所對應(yīng)的二進制表示形式是：000 1010 0101 1100 ，根據(jù)上面的分析爵赵，下劃線部分為頁內(nèi)地址吝秕，編碼 “000 10” 為頁號，表示該邏輯地址對應(yīng)的頁號為2空幻。查頁表烁峭，得到物理塊號是4（十進制），即物理塊地址為：01 00 秕铛，拼接塊內(nèi)地址10 0101 1100约郁，得01 0010 0101 1100，即125C（H）但两。

解 邏輯地址0A5C（H）所對應(yīng)的物理地址是125C（H）鬓梅。

【例9】 設(shè)一計算機系統(tǒng)有輸入機一臺、打印機兩臺谨湘，現(xiàn)有二道程序同時投入運行绽快，且程序 A 先開始運行，程序 B 后運行紧阔。程序 A 的運行軌跡為：計算 50ms坊罢，打印信息 100ms，再計 算 50ms ,打印信息 100ms ,結(jié)束擅耽。程序 B 運行的軌跡為：計算 50ms活孩，輸入數(shù)據(jù) 80ms，再 計算 100ms秫筏，結(jié)束诱鞠。要求： (1) 用圖畫出這二道程序并發(fā)執(zhí)行時的工作情況。 (2) 說明在二道程序運行時这敬，CPU 有無空閑等待？若有，在哪段時間內(nèi)等待枫弟？為什 么會空閑等待糊秆？ (3) 程序 A、B 運行時有無等待現(xiàn)象冷蚂？在什么時候會發(fā)生等待現(xiàn)象缭保？

多道.png

【例10】 LRU 和 FIFO （看PPT吧。蝙茶。）

頁面置換算法

1.先進先出置換算法

2.最近最久未用置換算法(LRU)

3.近似的LRU算法（NRU算法）

FIFO_1.png

LRU.png

在一個請求分頁系統(tǒng)中,假如一個作業(yè)的頁面走向為：1艺骂，2，3隆夯，6钳恕，4，7蹄衷，3忧额，2，1愧口，4睦番，7，5耍属，6托嚣，5，2厚骗，1注益。當(dāng)分配給該作業(yè)的物理塊數(shù)為4時,分別采用最佳置換算法、LRU和FIFO頁面置換算法,計算訪問過程中所發(fā)生的缺頁次數(shù)和缺頁率溯捆。

置換

程序題
P/V 操作:

// 請復(fù)習(xí)生產(chǎn)者和消費者的實驗 ３笊Α！提揍！
procedure P(var s:samephore);  
{  
    s.value=s.value-1;  
    if (s.value<0)   
    asleep(s.queue);  
}  
procedure V(var s:samephore);  
{  
    s.value=s.value+1;  
    if (s.value<=0)   
    wakeup(s.queue);  
} 
/* 
asleep(s.queue）：執(zhí)行此操作的進程的PCB進入s.queue尾部啤月，進程變成等待狀態(tài)
wakeup(s.queue）：將s.queue頭進程喚醒插入就緒隊列
s.value初值為1時，可以用來實現(xiàn)進程的互斥劳跃。
*/

例題
設(shè)公共汽車上谎仲，司機和售票員的活動分別如下：
司機的活動：啟動車輛：正常行車；到站停車刨仑。
售票員的活動：關(guān)車門郑诺；售票夹姥；開車門。
在汽車不斷地到站辙诞、停車辙售、行駛過程中，這兩個活動有什么同步關(guān)系飞涂？用信號量和P旦部、V操作實現(xiàn)它們的同步。

分析

答：在汽車行駛過程中较店，司機活動與售票員活動之間的同步關(guān)系為：售票員關(guān)車門后士八，向司機發(fā)開車信號，司機接到開車信號后啟動車輛梁呈，在汽車正常行駛過程中售票員售票婚度，到站時司機停車，售票員在車停后開門讓乘客上下車官卡。因此陕见，司機啟動車輛的動作必須與售票員關(guān)車門的動作取得同步；售票員開車門的動作也必須與司機停車取得同步味抖。
應(yīng)設(shè)置兩個信號量：s1评甜、s2；s1表示是否允許司機啟動汽車(其初值為0)仔涩；s2表示是否允許售票員開門(其初值為0)忍坷。
用P、V原語描述如下：

var  s1,s2：semaphore;
s1 = 0; s2 = 0;
cobegin
{
    driver();
    busman();
}
coend


driver ()
  begin
    while (1)    
    {
         P(s1);
         啟動車輛;
         正常行車;
         到站停車;
         V(s2);
    }
  end 

busman()
  begin
    while (1)        
    {
         關(guān)車門;
         V(s1);
         售票;
         P(s2);
         開車門;
         上下乘客;
    }
  end