2009碩士研究生入學(xué)考試輔導(dǎo)

操作系統(tǒng)原理

北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系

PekingUniversity

內(nèi)容提綱

■推薦參考書列表

■考試大綱概況

■考查內(nèi)容及要求

■知識(shí)點(diǎn)及復(fù)習(xí)要點(diǎn)

■樣題練習(xí)與講解

參考書（1/2）

■陳向群、楊芙清編著，操作系統(tǒng)教程

（第2版），北京大學(xué)出版社，2006

■湯子瀛等編著，計(jì)算機(jī)操作系統(tǒng)（第3,

版），西安電子科技大學(xué)出版社，2007

參考書（2/2）

AndrewS?Tanenbaum著，陳向群，馬洪兵

等譯，現(xiàn)代操作系統(tǒng)（第2版），機(jī)械工業(yè)出

版社，2005

］本課程考試大綱概況

■考查目標(biāo)

■了解操作系統(tǒng)在計(jì)算機(jī)系統(tǒng)中的作用、地位、

發(fā)展和特點(diǎn)。

■理解操作系統(tǒng)的基本概念、原理，掌握操作

系統(tǒng)設(shè)計(jì)方法與實(shí)現(xiàn)技術(shù)。

■能夠運(yùn)用所學(xué)的操作系統(tǒng)原理、方法與技術(shù)

分析問題和解決問題。

■操作系統(tǒng)34分

■單項(xiàng)選擇題18分（9小題，每小題2分）

■綜合應(yīng)用題16分（2小題，每小題8分）

復(fù)習(xí)方法建議

■圍繞大綱，系統(tǒng)地復(fù)習(xí)。既要建立系統(tǒng)的

概念原理體系，也要善于抓重點(diǎn)，把重點(diǎn)

學(xué)懂學(xué)透。

■抓住知識(shí)點(diǎn)，掌握正確的概念。

■適當(dāng)做題，但不要被大量的樣題擾亂

內(nèi)容提綱

?推薦參考書列表

■考試大綱概況

■考查內(nèi)容及要求

■知識(shí)點(diǎn)及復(fù)習(xí)要點(diǎn)

■樣題練習(xí)與講解

考查內(nèi)容及要求

?1概述-4文件管理

■1.1操作系統(tǒng)基本概念■4.1文件管理概述

■L2操作系統(tǒng)的分類■4.2文件系統(tǒng)的實(shí)現(xiàn)

■1.3操作系統(tǒng)的運(yùn)行環(huán)境-4.3磁盤組織與管理

-2進(jìn)程管理■5輸入輸出（I/O）概述

■2.1進(jìn)程與線程.5.1I/O管理概述

■2.2處理機(jī)調(diào)度■5.2I/O內(nèi)核子系統(tǒng)

■2.3進(jìn)程同步

■2.4死鎖

■3存儲(chǔ)管理

■3.1存儲(chǔ)管理基礎(chǔ)

■3.2虛擬頁式存儲(chǔ)管理方案

概述

操作系統(tǒng)的概念、特征、功能和提供的

服務(wù)

■掌握操作系統(tǒng)的定義，每個(gè)特征的含義，

操作系統(tǒng)功能和服務(wù)的主要內(nèi)容

■例如操作系統(tǒng)管理哪些資源，如何管理；

提供接口有什么，如何提供

■要求對(duì)操作系統(tǒng)的基本概念有清晰的理解,

能夠判斷給出的說法的正誤

概述

操作系統(tǒng)的發(fā)展與分類

■要求掌握操作系統(tǒng)的主要類型和發(fā)展歷史,

特別是批處理、分時(shí)、分布式、嵌入式等

有代表性的操作系統(tǒng)的特點(diǎn)

■能夠分辨說法的正誤

■能夠辨別任意兩種操作系統(tǒng)的區(qū)別與優(yōu)缺

占

八、、

概述

■操作系統(tǒng)的運(yùn)行環(huán)境

■掌握計(jì)算機(jī)系統(tǒng)中關(guān)鍵的硬件特征及其與操作

系統(tǒng)的關(guān)系

■特別是處理器的特權(quán)級(jí)和特權(quán)指令、主要狀態(tài)

寄存器的含義和功能，中斷機(jī)制

■能夠判斷說法的正誤

考查內(nèi)容

-1概述-4文件管理

■1.1操作系統(tǒng)基本概-4.1文件管理概述

念■4.2文件系統(tǒng)的實(shí)現(xiàn)

■；2操作系統(tǒng)的分類

-4.3磁盤組織與管理

-1.3操作系統(tǒng)的運(yùn)行■5輸入輸出(I/O)概述

環(huán)境■5.1I/O管理概述

■2進(jìn)程管理-5.2I/O內(nèi)核子系統(tǒng)

-2.1進(jìn)程與線程

-2.2處理機(jī)調(diào)度

.2.3進(jìn)程同步

■2.4死鎖

■3存儲(chǔ)管理

-3.1存儲(chǔ)管理基礎(chǔ)

-3.2虛擬頁式存儲(chǔ)管

例方窣

進(jìn)程管理

進(jìn)程與線程

■掌握進(jìn)程概念，進(jìn)程的狀態(tài)與轉(zhuǎn)換，進(jìn)程控制,

進(jìn)程組織，進(jìn)程通信（共享內(nèi)存，消息傳遞，

管道），線程概念與多線程模型

■特別是

■并發(fā)環(huán)境下的特點(diǎn)，引入進(jìn)程的意義

■與進(jìn)程狀態(tài)相關(guān)的原理，如轉(zhuǎn)換條件，等待與就緒

隊(duì)列，控制原語的功能

■三種進(jìn)程通信方法的特點(diǎn)，對(duì)比

■引入多線程的意義，進(jìn)程和其中多線程之間的關(guān)系

■能夠判斷說法的正誤

進(jìn)程管理

■處理機(jī)調(diào)度

■掌握調(diào)度概念，調(diào)度時(shí)機(jī)、切換與過程，基本準(zhǔn)則，

調(diào)度方式，典型調(diào)度算法

■先來先服務(wù)，短作業(yè)（短任務(wù)、短進(jìn)程、短線程）優(yōu)先，時(shí)

間片輪轉(zhuǎn)，優(yōu)先級(jí)，高響應(yīng)比優(yōu)先，多級(jí)反饋隊(duì)列

■特別是

■調(diào)度方式：搶占■非搶占（剝奪■非剝奪）

.各種調(diào)度算法：調(diào)度的執(zhí)行序列，算法的優(yōu)缺點(diǎn)

■能夠識(shí)別說法的正誤

■能夠按照要求的調(diào)度算法給出調(diào)度結(jié)果，計(jì)算調(diào)度算

法的平均響應(yīng)時(shí)間等參數(shù)

■這部分內(nèi)容的出題率近100%,重中之重

進(jìn)程管理

■F程同步

-掌握進(jìn)程同步的基本概念，實(shí)現(xiàn)臨界區(qū)互斥的基本方

法（軟件和硬件實(shí)現(xiàn)方法），信號(hào)量，管程，經(jīng)典同

步問題（生產(chǎn)者■消費(fèi)者問題，讀者■寫者問題，哲學(xué)家

進(jìn)餐問題）

-特別是

■深刻理解同步互斥的含義

■準(zhǔn)確理解信號(hào)量、PV原語的含義、功能

■解決同步互斥問題的基本思路和方法

-能夠?qū)σ粋€(gè)問題進(jìn)行判斷屬于哪類問題（同步互斥）

-能夠用PV原語解決問題，要求清晰地定義信號(hào)量、其

含義，并給出初值；編寫程序邏輯正確，不死鎖

■這部分內(nèi)容的出題率近100%,重中之重

進(jìn)程管理

死鎖

■掌握死鎖的概念，處理策略，預(yù)防，避免，用銀行家

算法判別系統(tǒng)安全狀態(tài)，死鎖檢測(cè)和解除

■特別是

■死鎖基本概念中涉及到的概念，如資源分類等

■用銀行家算法判別系統(tǒng)安全狀態(tài)

■四種處理策略的概念和相關(guān)的方法

■能夠識(shí)別說法的正誤

■能夠用銀行家算法解決判別系統(tǒng)安全狀態(tài)的問題

考查內(nèi)容

-1概述-4文件管理

■1.1操作系統(tǒng)基本概-4.1文件管理概述

念■4.2文件系統(tǒng)的實(shí)現(xiàn)

■；2操作系統(tǒng)的分類

-4.3磁盤組織與管理

-1.3操作系統(tǒng)的運(yùn)行■5輸入輸出(I/O)概述

環(huán)境■5.1I/O管理概述

-2進(jìn)程管理-5.2I/O內(nèi)核子系統(tǒng)

-2.1進(jìn)程與線程

-2.2處理機(jī)調(diào)度

■2.3進(jìn)程同步

■2.4死鎖

-3存儲(chǔ)管理

-3.1存儲(chǔ)管理基礎(chǔ)

-3.2虛擬頁式存儲(chǔ)管

鋰方窣

存儲(chǔ)管理

■存儲(chǔ)管理基礎(chǔ)

■掌握內(nèi)存管理概念，程序裝入與鏈接，邏輯地址與物

理地址空間，內(nèi)存保護(hù)，交換與覆蓋，連續(xù)分配管理

方式，單一連續(xù)分配，分區(qū)分配，非連續(xù)分配管理方

式，分頁管理方式，分段管理方式，段頁式管理方式

■特別是

■地址空間及地址轉(zhuǎn)換的概念和過程

■各種內(nèi)存管理的特點(diǎn)和基本思想，實(shí)現(xiàn)過程，利用的硬件

分區(qū)管理，分頁管理

■交換與覆蓋，保護(hù)，鏈接

■能夠判別說法的正誤

■能夠按照某種管理方法來解決回收、分配中的問題

-能夠按照內(nèi)存管理方式分析地址變換過程如

存儲(chǔ)管理

虛擬頁式存儲(chǔ)管理方案

-掌握虛擬內(nèi)存基本概念，請(qǐng)求分頁管理，頁面置

換算法（OPT,FIFO,LRU,時(shí)鐘置換算法），

頁面分配策略，抖動(dòng)，工作集，請(qǐng)求分段管理方

式，請(qǐng)求段頁式管理方式

-特別是

-虛擬內(nèi)存概念及其相關(guān)概念，如局部性原理，工作集等

■頁面置換算法，請(qǐng)求分頁管理

-能夠識(shí)別說法的正誤

-能夠根據(jù)要求分析給定頁面訪問序列下的缺頁次

數(shù)、嵌頁率，料藥問題

-這部分內(nèi)容的出題率很高

考查內(nèi)容

-1概述-4文件管理

■1.1操作系統(tǒng)基本概■4.1文件管理概述

念■4.2文件系統(tǒng)的實(shí)現(xiàn)

■；2操作系統(tǒng)的分類

-4.3磁盤組織與管理

-1.3操作系統(tǒng)的運(yùn)行■5輸入輸出(I/O)概述

環(huán)境■5.1I/O管理概述

-2進(jìn)程管理-5.2I/O內(nèi)核子系統(tǒng)

-2.1進(jìn)程與線程

-2.2處理機(jī)調(diào)度

■2.3進(jìn)程同步

■2.4死鎖

■3存儲(chǔ)管理

-3.1存儲(chǔ)管理基礎(chǔ)

-3.2虛擬頁式存儲(chǔ)管

例方窣

文件管理

■文件管理概述

-掌握文件概念，文件結(jié)構(gòu)（順序文件，索引文件,

索引順序文件），目錄結(jié)構(gòu)（文件控制塊和索引

節(jié)點(diǎn)，單級(jí)目錄結(jié)構(gòu)和兩級(jí)目錄結(jié)構(gòu)，樹形目錄

結(jié)構(gòu)，圖形目錄結(jié)構(gòu)），文件共享（共享動(dòng)機(jī)，

共享方式，共享語義），文件保護(hù)（訪問類型，

訪問控制）

-特別是

■不同文件結(jié)構(gòu)的特點(diǎn)，不同目錄結(jié)構(gòu)的特點(diǎn)

-文件共享和保護(hù)的概念

-能夠識(shí)別說法的正誤，對(duì)基本概念進(jìn)行辨識(shí)和定

義

文件管理

■文件系統(tǒng)的實(shí)現(xiàn)

■掌握文件系統(tǒng)層次結(jié)構(gòu)，目錄實(shí)現(xiàn)，文件實(shí)

現(xiàn)

■特別是

■目錄實(shí)現(xiàn)的過程和特點(diǎn)，如按名存取，目錄項(xiàng)分解,

相對(duì)路徑，絕對(duì)路徑

■文件操作的概念和實(shí)現(xiàn)過程

■能夠?qū)δ夸泴?shí)現(xiàn)和文件實(shí)現(xiàn)中某個(gè)操作的功

能、結(jié)果、實(shí)現(xiàn)方法進(jìn)行選擇和辨識(shí)

文件管理

磁盤組織與管理

■掌握磁盤的結(jié)構(gòu)，磁盤調(diào)度算法，磁盤的管理

■特別是

■幾種磁盤調(diào)度算法（綜合磁臂，磁頭，扇區(qū)三個(gè)因素）

■磁盤的組織結(jié)構(gòu)，優(yōu)化方法

■能夠根據(jù)要求計(jì)算給定磁盤訪問序列的調(diào)度結(jié)果，分

析磁盤存取時(shí)間

-能夠結(jié)合文件結(jié)構(gòu)和目錄結(jié)構(gòu)分析磁盤訪問次數(shù)

■能夠根據(jù)給定參數(shù)分析磁盤空間利用率、磁盤塊訪問

時(shí)間，給出優(yōu)化方案和結(jié)果

考查內(nèi)容

-1概述-4文件管理

■1.1操作系統(tǒng)基本概-4.1文件管理概述

念■4.2文件系統(tǒng)的實(shí)現(xiàn)

■；2操作系統(tǒng)的分類

-4.3磁盤組織與管理

-1.3操作系統(tǒng)的運(yùn)行■5輸入輸出(I/O)概述

環(huán)境■5.1I/O管理概述

-2進(jìn)程管理-5.2I/O內(nèi)核子系統(tǒng)

-2.1進(jìn)程與線程

-2.2處理機(jī)調(diào)度

■2.3進(jìn)程同步

■2.4死鎖

■3存儲(chǔ)管理

-3.1存儲(chǔ)管理基礎(chǔ)

-3.2虛擬頁式存儲(chǔ)管

例方窣

輸入輸出(I/O)概述

■I/O管理概述

■掌握I/O設(shè)備概念，I/O管理目標(biāo)，I/O管理功

能，I/O應(yīng)用接口，I/O控制方式

■特別是

■設(shè)備分類

■不同I/O控制方式的特點(diǎn)，如中斷，DMA,通道

■能夠辨識(shí)說法的正誤

■能夠選擇或判斷I/O處理過程和操作

輸入輸出(I/O)概述

■I/O內(nèi)核子系統(tǒng)

■掌握I/O調(diào)度概念，高速緩存與緩沖區(qū)，設(shè)

備分配與回收，假脫機(jī)技術(shù)(SPOOLing),出

錯(cuò)處理

■特別是

■假脫機(jī)技術(shù)的概念和原理

-緩沖區(qū)概念和管理操作

■能夠辨識(shí)說法的正誤

■能夠選擇或判斷某個(gè)過程或操作

內(nèi)容提綱

I

■推薦參考書列表

■考試大綱概況

■考查內(nèi)容及要求

■知識(shí)點(diǎn)及復(fù)習(xí)要點(diǎn)

■樣題練習(xí)與講解

知識(shí)點(diǎn)及復(fù)習(xí)要點(diǎn)

■概述?

■進(jìn)程線程

■內(nèi)存管理

■文件管理

■設(shè)備管理

操作系統(tǒng)的定義

操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)中的一個(gè)系統(tǒng)軟件，是一些程序模

塊的集合——

■它們能以盡量有效、合理的方式組織和管理計(jì)算機(jī)的軟

硬件資源

■合理的組織計(jì)算機(jī)的工作流程，控制程序的執(zhí)行并向用

戶提供各種服務(wù)功能

■使得用戶能夠靈活、方便、有效的使用計(jì)算機(jī)，使整個(gè)

計(jì)算機(jī)系統(tǒng)能高效地運(yùn)行

操作系統(tǒng)的特征

并發(fā)（concurrency）：處理多個(gè)同時(shí)性活動(dòng)的能力

共享（sharing）：操作系統(tǒng)與多個(gè)用戶的程序共同使

用計(jì)算機(jī)系統(tǒng)中的資源（共享有限的系統(tǒng)資源）

虛擬（Virtual）：一個(gè)物理實(shí)體映射為若干個(gè)對(duì)應(yīng)的

邏輯實(shí)體一一分時(shí)或分空間。虛擬是操作系統(tǒng)管理系

統(tǒng)資源的重要手段，可提高資源利用率

隨機(jī)性：操作系統(tǒng)必須隨時(shí)對(duì)以不可預(yù)測(cè)次序發(fā)生的

事件進(jìn)行響應(yīng)

不確定性：由共享和并發(fā)引起

操作系統(tǒng)的功能和提供的服務(wù)

■進(jìn)程（線程）管理

■協(xié)調(diào)多道程序，處理機(jī)分配調(diào)度策略、分配實(shí)施和回收

■存儲(chǔ)管理

■分配回收，擴(kuò)充，共享，保護(hù)

■文件管理

■文件的存儲(chǔ)、檢索，修改，共享、保密和保護(hù)

■設(shè)備管理

■I/O操作，外部設(shè)備的分配、啟動(dòng)和故障處理，提供一個(gè)

良好的界面

■用戶接口

■向用戶提供使用手段，系統(tǒng)調(diào)用，命令方式

4操作系統(tǒng)的分類

■批處理操作系統(tǒng)（多道批處理）

■分時(shí)系統(tǒng)

■實(shí)時(shí)操作系統(tǒng)■

■個(gè)人計(jì)算機(jī)操作系統(tǒng)

■網(wǎng)絡(luò)操作系統(tǒng)

■分布式操作系統(tǒng)J

■嵌入式操作系統(tǒng)

批處理操作系統(tǒng)特點(diǎn)

■多道

內(nèi)存中同時(shí)存放幾個(gè)作業(yè)

某個(gè)作業(yè)占用CPU,若由于某種原因暫時(shí)

不用CPU,則系統(tǒng)讓第二個(gè)作業(yè)占用CPU

.成批處理

用戶自己不能干預(yù)自己作業(yè)的運(yùn)行，一旦發(fā)現(xiàn)

作業(yè)錯(cuò)誤不能及時(shí)改正，并延長(zhǎng)開發(fā)軟件時(shí)間，

所以適用于成熟的程序

批處理操作系統(tǒng)優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：作業(yè)流程自動(dòng)化-資源利用率高

吞吐量大---

單位時(shí)間內(nèi)完成的工作總量大

缺點(diǎn)：用戶交互性差，調(diào)試程序困難

（無交互手段：整個(gè)作業(yè)完成后或中間出錯(cuò)

時(shí)，才與用戶交互，不利于調(diào)試和修改）

作業(yè)平均周轉(zhuǎn)時(shí)間長(zhǎng)

短作業(yè)的周轉(zhuǎn)時(shí)間顯著增長(zhǎng)

分時(shí)操作系統(tǒng)特點(diǎn)

■多路性

-同時(shí)有多個(gè)用戶使用一臺(tái)計(jì)算機(jī)

■宏觀上：是多個(gè)人同時(shí)使用一個(gè)CPU

■微觀上：多個(gè)人在不同時(shí)刻輪流使用CPU

■交互性

-用戶根據(jù)系統(tǒng)響應(yīng)結(jié)果進(jìn)一步

-提出新請(qǐng)求（用戶直接干預(yù)每一步）

■“獨(dú)占”性

-用戶感覺不到計(jì)算機(jī)為其他人服務(wù)

■OS提供虛機(jī)器，各個(gè)用戶的虛機(jī)器互不干擾

■及時(shí)性

-系統(tǒng)對(duì)用戶提出的請(qǐng)求及時(shí)響應(yīng)

I實(shí)時(shí)操作系統(tǒng)

■指使計(jì)算機(jī)能及時(shí)響應(yīng)外部事件的請(qǐng)求，

在規(guī)定的嚴(yán)格時(shí)間內(nèi)完成對(duì)該事件的處理,

并控制所有實(shí)時(shí)設(shè)備和實(shí)時(shí)任務(wù)協(xié)調(diào)一致

地工作的操作系統(tǒng)

■硬實(shí)時(shí)系統(tǒng)

■,某個(gè)動(dòng)作絕對(duì)必須在規(guī)定的時(shí)刻或時(shí)間范圍

完成

■軟實(shí)時(shí)系統(tǒng)

■接受偶爾違反最終時(shí)限

實(shí)時(shí)操作系統(tǒng)

q時(shí)系統(tǒng)與批處理系統(tǒng)和分時(shí)系統(tǒng)的區(qū)別

■專用系統(tǒng)：許多實(shí)時(shí)系統(tǒng)是專用系統(tǒng)，而批處

理與分時(shí)系統(tǒng)通常是通用系統(tǒng)

■實(shí)時(shí)控制：實(shí)時(shí)系統(tǒng)用于控制實(shí)時(shí)過程，要求

對(duì)外部事件的迅速響應(yīng)，具有較強(qiáng)的中斷處理

機(jī)構(gòu)

■高可靠性：實(shí)時(shí)系統(tǒng)用于控制重要過程，要求

高度可靠，具有較高冗余（如雙機(jī)系統(tǒng)）

■事件驅(qū)動(dòng)和隊(duì)列驅(qū)動(dòng)：實(shí)時(shí)系統(tǒng)的工作方式：

接受外部消息，分析消息，調(diào)用相應(yīng)處理程序

進(jìn)行處理。

分布式操作系統(tǒng)

分布式系統(tǒng):處理和控制的分散（相對(duì)于集中

式系統(tǒng)）

分布式系統(tǒng)是以計(jì)算機(jī)網(wǎng)絡(luò)為基礎(chǔ)的9它的基

本特征是處理上的分布，即功能和任務(wù)的分布

分布式操作系統(tǒng)的所有系統(tǒng)任務(wù)可在系統(tǒng)中任

何處理機(jī)上運(yùn)行，自動(dòng)實(shí)現(xiàn)全系統(tǒng)范圍內(nèi)的任

務(wù)分配并自動(dòng)調(diào)度各處理機(jī)的工作負(fù)載

r.分布式操作系統(tǒng)

W--------------------------------------------

特征：

1.是一個(gè)統(tǒng)一的操作系統(tǒng)

若干個(gè)計(jì)算機(jī)可相互協(xié)作共同完成一項(xiàng)任務(wù)

2.資源進(jìn)一步共享

3.透明性：

資源共享，分布對(duì)用戶來講是不知道的

4.自治性：

處于分布式系統(tǒng)的多個(gè)主機(jī)處于平等地位，無主

從關(guān)系

5.處理能力增強(qiáng)、速度更快、可靠性增強(qiáng)

網(wǎng)絡(luò)和分布式的比較

耦合程度

分布式系統(tǒng)是緊密耦合系統(tǒng)，分布式OS是在各機(jī)上

統(tǒng)一建立的，直接管理CPU、存儲(chǔ)器和外設(shè)；統(tǒng)一進(jìn)行

全系統(tǒng)的管理；網(wǎng)絡(luò)通常容許異種OS互連，各機(jī)上各

種服務(wù)程序需按不同網(wǎng)絡(luò)協(xié)議互操作

并行性

分布式OS可以將一個(gè)進(jìn)程分散在各機(jī)上并行執(zhí)行”

進(jìn)程遷移“；網(wǎng)絡(luò)則各機(jī)上的進(jìn)程獨(dú)立

透明性

用戶是否知道或指定資源在哪個(gè)機(jī)器上

分布式系統(tǒng)的網(wǎng)絡(luò)資源調(diào)度對(duì)用戶透明，用戶不了

解所占有資源的位置；網(wǎng)絡(luò)操作系統(tǒng)中對(duì)網(wǎng)絡(luò)資源的使

用要由用戶明確指定

健壯性

分布式系統(tǒng)要求更強(qiáng)的容錯(cuò)能力（工作時(shí)系統(tǒng)重構(gòu)）

嵌入式操作系統(tǒng)

■耿入式系統(tǒng)

■以應(yīng)用為中心、以計(jì)算機(jī)技術(shù)為基礎(chǔ)、軟件硬件

可裁剪、適用于應(yīng)用系統(tǒng)對(duì)功能、可靠性、成本、

體積、功耗嚴(yán)格要求的專用計(jì)算機(jī)系統(tǒng)

■限制條件：大小、內(nèi)存、能源1

■嵌入式操作系統(tǒng)r

■安裝在有限的內(nèi)存里（ROM）

■運(yùn)行在嵌入式系統(tǒng)環(huán)境中，對(duì)整個(gè)嵌入式系統(tǒng)以

及它所操作、控制的各種部件裝置等等資源進(jìn)行

統(tǒng)一協(xié)調(diào)、調(diào)度、指揮和控制的系統(tǒng)軟件

處理器的特權(quán)指令和非特權(quán)指令

特權(quán)指令：只能由操作系統(tǒng)使用的指令

■使用多道程序設(shè)計(jì)技術(shù)的計(jì)算機(jī)指令系統(tǒng)必須要區(qū)

分為特權(quán)指令和非特權(quán)指令

■特權(quán)指令一般引起處理器狀態(tài)的切換

-處理器通過特殊的機(jī)制將處理器狀態(tài)切換到操作系統(tǒng)運(yùn)行

的特權(quán)狀態(tài)（管態(tài)）

■然后將處理權(quán)移交給操作系統(tǒng)中的一段特殊代碼，這一個(gè)

過程稱為陷入

］處理器的狀態(tài)

根據(jù)運(yùn)行程序?qū)Y源和機(jī)器指令的使用權(quán)限

將處理器設(shè)置為不同狀態(tài)一一程序狀態(tài)字PSW

多數(shù)系統(tǒng)將處理器工作狀態(tài)劃分為管態(tài)和目態(tài)

管態(tài)：操作系統(tǒng)管理程序運(yùn)行的狀態(tài)，較高的特權(quán)

級(jí)別，又稱為特權(quán)態(tài)（特態(tài)）、核心態(tài)、系統(tǒng)態(tài)

目態(tài)：用戶程序運(yùn)行時(shí)的狀態(tài)，較低的特權(quán)級(jí)別，

又稱為普通態(tài)（普態(tài)）、用戶態(tài)

具體處理器將CPU狀態(tài)劃分為兩種、三種或四種

存儲(chǔ)訪問局部性原理

提高存儲(chǔ)系統(tǒng)性能的關(guān)鍵：程序存儲(chǔ)訪問局部性原理

■程序執(zhí)行時(shí)，有很多的循環(huán)和子程序調(diào)用，一旦進(jìn)入

這樣的程序段，就會(huì)重復(fù)存取相同的指令集合

■對(duì)數(shù)據(jù)存取也有局部性，在較短的時(shí)間內(nèi)，穩(wěn)定地保

持在一個(gè)存儲(chǔ)器的局部區(qū)域

處理器主要和存儲(chǔ)器的局部打交道

在經(jīng)過一段時(shí)間以后，使用的代碼和數(shù)據(jù)集合會(huì)改變

磁盤

控制器

總線

物理地址

MMU：內(nèi)存管理單元

中斷的概念

■CPU對(duì)系統(tǒng)發(fā)生的某個(gè)事件作出的一種反應(yīng)

■CPU暫停正在執(zhí)行的程序，保留現(xiàn)場(chǎng)后自動(dòng)轉(zhuǎn)去執(zhí)

行相應(yīng)事件的處理程序，處理完成后返回?cái)帱c(diǎn)，繼

續(xù)執(zhí)行被打斷的程序

特點(diǎn)：

引入中斷的目的

■解決主機(jī)與外設(shè)的并行1）中斷是隨機(jī)的

工作問題2）中斷是可恢復(fù)的

■實(shí)現(xiàn)實(shí)時(shí)控制3）中斷是自動(dòng)處理的

中斷的概念

「I/O中斷

「中斷（外中斷）

Y時(shí)鐘中斷

I硬件故障

廣義中斷V"系統(tǒng)調(diào)用

缺頁異常

異常（內(nèi)中斷）斷點(diǎn)指令

例外其他程序性異常

I（如算術(shù)溢出等）

中斷（狹義）與異常的區(qū)別：

中斷：與正執(zhí)行指令無關(guān)，可以屏蔽

異常：與正執(zhí)行指令有關(guān)，不可屏蔽

.中斷類型

■強(qiáng)迫性中斷

■正在運(yùn)行的程序所不期望的，由于某種硬件故障或外部請(qǐng)

求引起的

?輸入/輸出（I/O）中斷：主要來自外部設(shè)備通道

?程序性中斷：運(yùn)行程序中本身的中斷，如溢出，缺頁中斷地址越界）

■時(shí)鐘中斷

■控制臺(tái)中斷

■自愿性中斷

■用戶在程序中有意識(shí)安排的中斷，用戶在編制程序時(shí)因?yàn)?/p>

要求操作系統(tǒng)提供服務(wù)，有意使用“訪管”指令或系統(tǒng)調(diào)

用，使中斷發(fā)生

■系統(tǒng)調(diào)用

■斷點(diǎn)調(diào)試

知識(shí)點(diǎn)及復(fù)習(xí)要點(diǎn)

■概述1

■進(jìn)程線程管理

■內(nèi)存管理

■文件管理

■設(shè)備管理

發(fā)程序

并發(fā)環(huán)境:

一定時(shí)間內(nèi)，物理機(jī)器上有兩個(gè)或兩個(gè)以

上的程序同時(shí)處于開始運(yùn)行但尚未結(jié)束的

狀態(tài)，并且次序不是事先確定的

ABAB

BA

BA

并發(fā)程序

CPUIDEVIICP【J,DEV2?CPU

A1O152O

—3040t(s)

-DEV1

B1----------H_CEU---------JEV2|CPUIDEV2?

1020253040

在順序環(huán)境下，A先執(zhí)行，B再執(zhí)行

CPU利用率=40/80=50%

DEVI利用率=15/80=18.75%

DEV2禾用率=25/80=31.25%

并發(fā)程序

ACPUDEVIICPUDEV2CPU

1_11一十

1111111L

1)15253()：!54045

BDEVICPUDEV2CPUDEV2

在并發(fā)環(huán)境下CPU利用=40/45=89%

DEV1并發(fā)環(huán)境下利用==15/45=33%

DEV2并發(fā)環(huán)境下利用=25/45=56%

進(jìn)程的概念

■定義

進(jìn)程是具有獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合

上的一次運(yùn)行活動(dòng)，是系統(tǒng)進(jìn)行資源分配和調(diào)

度的獨(dú)立單位，又稱任務(wù)(Task)

進(jìn)程狀態(tài)轉(zhuǎn)換

狀態(tài)轉(zhuǎn)換：

在進(jìn)程運(yùn)行過程中，由于進(jìn)程自身進(jìn)展情況及

外界環(huán)境的變化，這三種基本狀態(tài)可以依據(jù)一

定的條件相互轉(zhuǎn)換

①就緒—運(yùn)行

②運(yùn)行—就緒

③運(yùn)行一等待

④等待一就緒

、■進(jìn)程轉(zhuǎn)換原因

二

■就緒-->運(yùn)行

-調(diào)度程序選擇一個(gè)新的進(jìn)程運(yùn)行

■運(yùn)行-->就緒

■運(yùn)行進(jìn)程用完了時(shí)間片

?一個(gè)高優(yōu)先級(jí)進(jìn)程處于就緒狀態(tài)，中斷正在運(yùn)行的進(jìn)程

■運(yùn)行-->等待

■當(dāng)一個(gè)進(jìn)程必須等待時(shí)

?os尚未完成服務(wù)（系統(tǒng)調(diào)用）

■對(duì)一資源的訪問尚不能進(jìn)行（同步互斥）

?初始化I/O且必須等待結(jié)果（I/O）

■等待某一進(jìn)程提供輸入（IPC）

■等待一〉就緒

.當(dāng)所等待的事件發(fā)生時(shí)

進(jìn)程的其他狀態(tài)

■創(chuàng)建狀態(tài)

-OS已完成為創(chuàng)建一進(jìn)程所必要的工作

■已構(gòu)造了進(jìn)程標(biāo)識(shí)符

■已創(chuàng)建了管理進(jìn)程所需的表格

■但還沒有允許執(zhí)行該進(jìn)程（尚未同意）

-因?yàn)橘Y源有限

■終止?fàn)顟B(tài)

■不再有執(zhí)行資格，占有的資源將要被釋放

■掛起（suspend）狀態(tài)

■進(jìn)程沒有占用內(nèi)存空間，處在掛起狀態(tài)的進(jìn)程映像在

磁盤上調(diào)節(jié)負(fù)載，對(duì)換）

調(diào)度的基本準(zhǔn)則

■一般原則：

■公平：保證每個(gè)進(jìn)程得到合理的CPU時(shí)間

■高效：CPU保持忙碌狀態(tài)，CPU利用率高

■針對(duì)某類操作系統(tǒng)確定原則：

■響應(yīng)時(shí)間：交互式系統(tǒng)，越短越好

■周轉(zhuǎn)時(shí)間：使批處理用戶等待時(shí)間盡可能短

■吞吐量：批處理系統(tǒng)情況下，單位時(shí)間內(nèi)處

理的進(jìn)程個(gè)數(shù)盡可能多

進(jìn)程調(diào)度方式

兩種占用CPU的方式：

可剝奪式（可搶占式Preemptive）：

當(dāng)有比正在運(yùn)行的進(jìn)程優(yōu)先級(jí)更高的進(jìn)程就

緒時(shí)，系統(tǒng)可強(qiáng)行剝奪正在運(yùn)行進(jìn)程的CPU,提

供給具有更高優(yōu)先級(jí)的進(jìn)程使用

不可剝奪式（不可搶占式Non-preemptive）：

某一進(jìn)程被調(diào)度運(yùn)行后，除非由于它自身的

原因不能運(yùn)行，否則一直運(yùn)行下去

進(jìn)程調(diào)度的時(shí)機(jī)

當(dāng)一個(gè)進(jìn)程運(yùn)行完畢，或由于某種錯(cuò)誤而終止運(yùn)行

當(dāng)一個(gè)進(jìn)程在運(yùn)行中處于等待狀態(tài)（等待I/O）

時(shí)間片用完

當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒（可搶占式）

如：新創(chuàng)建一個(gè)進(jìn)程；一個(gè)等待進(jìn)程變成就緒

在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語操作

（P操作，阻塞原語，喚醒原語）

進(jìn)程中斷/異常/系統(tǒng)調(diào)用返回到用戶態(tài)時(shí)

進(jìn)程切換

■『個(gè)進(jìn)程讓出處理器，由另一個(gè)進(jìn)程占用處理器的過程

-進(jìn)程的切換使系統(tǒng)中的各進(jìn)程均有機(jī)會(huì)占用CPU

■進(jìn)程的切換是由進(jìn)程狀態(tài)的變化引起的，而進(jìn)程狀態(tài)的變化又

與出現(xiàn)中斷事件有關(guān)

■當(dāng)有中斷事件發(fā)生時(shí)，當(dāng)前運(yùn)行的進(jìn)程被中斷，中斷響應(yīng)后由

操作系統(tǒng)處理出現(xiàn)的中斷事件。中斷處理后，某些進(jìn)程的狀態(tài)

會(huì)發(fā)生變化，也可能又創(chuàng)建了一些新的進(jìn)程。因此，要進(jìn)行隊(duì)

列的調(diào)整。然后，進(jìn)程調(diào)度根據(jù)預(yù)定的調(diào)度算法從就緒隊(duì)列選

一個(gè)進(jìn)程占用CPU。這個(gè)占用CPU運(yùn)行的進(jìn)程可能仍是被中斷的

進(jìn)程，也可能是另一個(gè)進(jìn)程

,何時(shí)切換進(jìn)程?

■只要OS取得對(duì)CPU的控制，進(jìn)程切換就可

能發(fā)生，如：

■系統(tǒng)調(diào)用

■來自程序的顯式請(qǐng)求（如：打開文件），該進(jìn)程通

常會(huì)被阻塞

■異常

■最末一條指令導(dǎo)致出錯(cuò)，會(huì)引起進(jìn)程變?yōu)橥顺鰻顟B(tài)

■中斷

■外部因素影響當(dāng)前指令的執(zhí)行，控制被轉(zhuǎn)移至中斷

處理程序

進(jìn)程切換的過程

■保存處理器的上下文，包括程序計(jì)數(shù)器和其它寄存器

■用新狀態(tài)和其它相關(guān)信息更新正在運(yùn)行進(jìn)程的PCB

-把原來的進(jìn)程移至合適的隊(duì)列—就緒、阻塞‘

■選擇另一個(gè)要執(zhí)行的進(jìn)程.

■更新被選中進(jìn)程的PCB”

■從被選中進(jìn)程中重裝入CPU上下文

線程的引入

■進(jìn)程的缺點(diǎn)

■時(shí)間、空間開銷大，限制了并發(fā)度的提高

■線程?

■也稱輕量級(jí)進(jìn)程

■進(jìn)程中的一個(gè)運(yùn)行實(shí)體，是一個(gè)CPU調(diào)度單位

■一個(gè)進(jìn)程中的線程共享進(jìn)程的資源（內(nèi)存、文件等）

進(jìn)程與線程

■引入線程的好處

■創(chuàng)建和終止一個(gè)線程花費(fèi)時(shí)間少

■兩個(gè)線程的切換花費(fèi)時(shí)間少

■如果機(jī)器設(shè)有“存儲(chǔ)I,恢復(fù)］所有寄存器”指令，則

整個(gè)切換過程用幾條指令即可完成）

■線程之間相互通信無須調(diào)用內(nèi)核

■同一進(jìn)程內(nèi)的線程共享內(nèi)存和文件

■適合多處理機(jī)系統(tǒng)

4線程模型

二線程和進(jìn)程的關(guān)系

■單線程進(jìn)程

■多線程進(jìn)程

多線程進(jìn)程模型

單線程進(jìn)程模型

用

線程

戶控制塊

棧PCB

核

用

戶

心

棧

棧

用戶地址空間用戶

地址

空間

核

心

線程控制塊棧

包含了寄存器映像，線程優(yōu)先數(shù)和線程狀態(tài)信息

線程模型（2/3）

單線程進(jìn)程模型

PCB

用戶地址空間

線程控制塊

包含了寄存器映像，線程優(yōu)先數(shù)和線程

狀態(tài)信息

線程模型（3/3）

多線程進(jìn)程模型

線程

控制塊

PCB

用

戶

用戶棧

地址

空間核

心

棧

、■進(jìn)程的同步與互斥

■進(jìn)程的同步

■指系統(tǒng)中多個(gè)進(jìn)程中發(fā)生的事件存在某種時(shí)序關(guān)系，

需要相互合作，共同完成一項(xiàng)任務(wù)。

■進(jìn)程的同步

■由于各進(jìn)程要求共享資源，而有些資源需要互斥使用,

因此各進(jìn)程間競(jìng)爭(zhēng)使用這些資源，進(jìn)程的這種關(guān)系為

進(jìn)程的互斥

■臨界資源

■系統(tǒng)中某些資源一次只允許一個(gè)進(jìn)程使用，稱這樣的

資源為臨界資源或互斥資源

■臨界區(qū)

■在進(jìn)程中涉及到臨界資源的程序段

.實(shí)現(xiàn)臨界區(qū)互斥的方法

■軟件解法

■定義變量，進(jìn)入臨界區(qū)前和退出后執(zhí)行相應(yīng)函數(shù)Paterson算法

■需要忙等待(busywaiting)

■實(shí)現(xiàn)過于復(fù)雜，需要高的編程技巧

■硬件解法：

■提供專門的硬件指令，允許對(duì)一個(gè)字的內(nèi)容進(jìn)行檢測(cè)和修正，或交

換兩個(gè)字的內(nèi)容

■“測(cè)試并設(shè)置”(TS)指令，“交換”指令，“開關(guān)中斷”指令

■目的：解決共享變量的完整性和正確性

■簡(jiǎn)單、有效，特別適用于多處理機(jī)

■缺點(diǎn)：(1)忙等待；(2)“饑餓”現(xiàn)象

信號(hào)量：seaphore

■是一個(gè)數(shù)據(jù)結(jié)構(gòu)】)信號(hào)量的物理含義：

■定義如下：S>0表示有s個(gè)資源可用

strucsemaphores=o表示無資源可用

SVO則IS|表示S等待隊(duì)列中的進(jìn)程

(個(gè)數(shù)

intvalue;

pointer_PCBqueue;P(S)：表示申請(qǐng)一個(gè)資源

)"V(S)：表示釋放一個(gè)資源

信號(hào)量的初值應(yīng)該大于等于0

■信號(hào)量說明：

semaphores;

P操作和V操作

I)V(s)

(

s.value=s.value-1;s.value=s.value+1;

if(s.value<0)if(s.value<=0)

((,

該進(jìn)程狀態(tài)置為等待狀態(tài)

將該進(jìn)程插入等待隊(duì)列末尾喚醒等待隊(duì)列中等待的進(jìn)程

重新調(diào)度改變?yōu)榫途w態(tài)，并將其插入就緒隊(duì)列

■P.V操作必須成對(duì)出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作

■當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程

■當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn)

■如果P(S1)和P(S2)兩個(gè)操作在一起，那么P操作的順序至關(guān)重要，一個(gè)同

步P操作與一個(gè)互斥P操作在一起時(shí)同步P操作在互斥P操作前

■而兩個(gè)V操作的順序無關(guān)緊要

空典的生產(chǎn)者一消費(fèi)者問題(同步為主)

■P進(jìn)程不能往“滿”的緩沖區(qū)中放產(chǎn)品，

設(shè)置信號(hào)量為S1

■Q進(jìn)程不能從“空”的緩沖區(qū)中取產(chǎn)品,

設(shè)置信號(hào)量S2

■S1初值為1,S2初值為0

注意：

while(true){while(true){

■私有信號(hào)量用于控制生產(chǎn)一個(gè)產(chǎn)品；P(s2);

進(jìn)程執(zhí)行順序

P(s1);從緩沖區(qū)取產(chǎn)品;

■可以擴(kuò)展理解為：

送產(chǎn)品到緩沖區(qū);V(s1);

控制進(jìn)程執(zhí)行的次數(shù)

V(s2);消費(fèi)產(chǎn)品；

■生產(chǎn)者比消費(fèi)者多1

次，消費(fèi)者比生產(chǎn)者)；

多。次

多個(gè)緩沖區(qū)的生產(chǎn)者和消費(fèi)者（帶互斥的同步）

■S1初值為工，S2初值為0

-mutextl用于生產(chǎn)者互斥寫緩沖區(qū)，

初值為工

■mutext2用于消費(fèi)者互斥讀緩沖區(qū)，初

值為工

10,

i=0;j=o；

while(true){while(true){

注意：生產(chǎn)產(chǎn)品；P(S2);

■生產(chǎn)者消費(fèi)者問題可P(S。；P(mutex2);

以擴(kuò)展為倉庫問題，P(mutex1);從Buffer。］取產(chǎn)品;

往Buffer［i］放產(chǎn)品;

商店賣貨問題，零件j=(j+1)%n;

裝配問題。i=(i+1)%n;V(mutex2);

V(mutex1);V(Si);

■數(shù)量限制引申為進(jìn)程V(S2);消費(fèi)產(chǎn)品；

的執(zhí)行次數(shù)限制，當(dāng)}；

作私有信號(hào)量的初值

商店賣食品問題

某商店有兩種食品A和B,最大數(shù)量各為m個(gè)。該商店

將A、B兩種食品搭配出售，每次各取一個(gè)。為避免食

品變質(zhì)，遵循先到食品先出售的原則，有兩個(gè)食品公司

分別不斷地供應(yīng)A、B兩種食品(每次一個(gè))。為保證正常

銷售，當(dāng)某種食品的數(shù)量比另一種的數(shù)量超過k(kvm)

個(gè)時(shí)，暫停對(duì)數(shù)量大的食品進(jìn)貨，補(bǔ)充數(shù)量少的食品。

-(1)問共需設(shè)置幾個(gè)進(jìn)程？

■(2)試用P、V操作解決上述問題中的同步和互斥關(guān)系。

商店賣食品問題

■這是一個(gè)三進(jìn)程同步互斥問題，互相之間的制約可以看成是執(zhí)行

次數(shù)的約束

■食品A和商店c之間同步，Sac=m,sca=O;

■食品B和商店c之間同步，Sbc=m,scb=O;

■食品A和食品B直接同步，Sab=k,sba=k;

■三者之間的對(duì)貨架操作互斥，定義mutex=1；

B：

(

P(sac);P(sbc);P(sca);

P(sab);P(sba);P(scb);

p(mutex)；p(mutex)；p(mutex)；

store(A);store(B);take_A&B;

v(sca);v(scb);v(sac);

v(sba);v(sab);v(sbc);

v(mutext);v(mutext);v(mutext);

1；_____1；_____1；______

讀者寫者問題（互斥為主）

問題描述：

有兩組并發(fā)進(jìn)程：讀者和寫者，共享一組數(shù)據(jù)區(qū)

要求：

允許多個(gè)讀者同時(shí)執(zhí)行讀操作

不允許讀者、寫者同時(shí)操作

不允許多個(gè)寫者同時(shí)操作

第一類讀寫者問題：讀者優(yōu)先

■如果讀者到：

-1）無讀者、寫者，新讀者可以讀

-2）有寫者等，但有其它讀者正在讀，則新讀者也可以讀

?3）有寫者寫，新讀者等

■如果寫者到：

-1）無讀者，新寫者可以寫

-2）有讀者，新寫者等待

-3）有其它寫者，新寫者等待

第一類讀者寫者問題的解法

讀者：寫者:

(

P(mutex);

readcount++;

if(readcount==1)P(w);

P(w);寫

V(mutex);

讀V(w);

P(mutex);

readcount｝；

if(readcount==0)

V(w);

V(mutex);

)；

第二類讀者寫者問題一寫者優(yōu)先

Integerrcount=0zwcount=0;

1）多個(gè)讀者可以同Semaphoremutexl=mutex2=w=r=l;

時(shí)進(jìn)行讀

讀者：

2）寫者必須互斥寫者：

(

（只允許一個(gè)寫(

P(r)；P(w);

P(mutex1);

者寫，也不能讀P(mutex2)

者寫者同時(shí)進(jìn)行）rcount++;

if(rcount==1)P(w);wcount++;

3）寫者優(yōu)先于讀者V(mutex1);If(wcount==1)P(r);

（一旦有寫者，V(r);V(mutex2);

則后續(xù)讀者必須讀寫

等待，喚醒時(shí)優(yōu)P(mutex1);P(mutex2);

rcountwcount

先考慮寫者）

if(rcount==0)V(w);If(wcount==0)V(r);

注意：V(mutex1);V(mutex2);

｝；

■讀寫者問題可以改為為V(w);

過橋問題，巴拿馬運(yùn)河｝；

問題等

■單向互斥或雙向互斥

巴拿馬運(yùn)河問題

巴拿馬運(yùn)河建在太平洋和大西洋之間。由于太平洋和大

西洋水面高度不同，有巨大落差，所以運(yùn)河中修建有T

(T>=2)級(jí)船閘，并且只能允許單向通行。船閘依次

編號(hào)為1,2,……，To由大西洋來的船需經(jīng)由船閘T,

T-1,……，2,1通過運(yùn)河到太平洋；由太平洋來的船

需經(jīng)由船閘1,2,……，T-1,T通過運(yùn)河到大西洋。

試用P,V操作正確解決大西洋和太平洋的船只通航問

題。

巴拿馬運(yùn)河問題

記錄由太平洋往大西洋航行的船只，PtoAcnt=0

記錄此船閘正由大西洋往太平洋航行的船只AtoPcnt=0

對(duì)PtoAcount互斥，Mutex1=1

對(duì)AtoPcount互斥，Mutex2=1

太平洋往大西洋方向的信號(hào)量

大西洋往太平洋方向的信號(hào)量E=1

PtoA：AtoP：

(｛

P(W);P(E)；

P(mutex1);P(mutex2);

PtoAcount++;AtoPcount++;

if(PtoAcount==1)P(E);if(AtoPcount==1)P(W);

V(mutex1);V(mutex2);

過閘過閘

P(mutex1);P(mutex2);

PtoAcountAtoPcount

if(PtoAcount==0)V(E);if(AtoPcount==0)V(W);

V(mutex1);V(mutex2);

｝；｝；

哲學(xué)家就餐問題（互斥為主）

問題描述:

■有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前

有一只空盤子，每?jī)扇酥g放一只筷子

■每個(gè)哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉

■為了吃通心粉，每個(gè)哲學(xué)家必須拿到兩只筷子,并且每個(gè)人只能

直接從自己的左邊或右邊去取筷子

解法1:

為防止死鎖發(fā)生可采取的措施：

#defineN5

-最多允許4個(gè)哲學(xué)家同時(shí)坐在桌子周圍

voidphilosopher(inti){

-僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí)，

while(true){才允許他拿筷子（4）

思考；-給所有哲學(xué)家編號(hào)，奇數(shù)號(hào)的哲學(xué)家必須首

取fork。］;Work［(i+1)%5］；先拿左邊的筷子，偶數(shù)號(hào)的哲學(xué)家則反之

進(jìn)食；為了避免死鎖，把哲學(xué)家分為三種狀態(tài)，思

放fork。］;放fork［(i+1)%5］；考，饑餓，進(jìn)食，并且一次拿到兩只筷子，

否則不拿

)

)

voidphilosopher(inti)

{while(true)

哲學(xué)家就餐問題解法（2）(

思考；

■#defineN5P(&mutex);

>#defineTHINKING0state[i]=HUNGRY;

?#defineHUNGRY1test(i);

>#defineEATING2V(&mutex);

■#typedefintsemaphore;P(&s[i])；

拿左筷子；拿右筷子；

■intstate[N];

進(jìn)食；

■semaphoremutex=1;放左筷子；放右筷子;

■semaphores[N];叫&mutex)

voidtest(inti)state[i]=THINKING；

{test([i-1]%5);

if(state[i]==HUNGRY)test([i+1]%5);

&&(state[(i-1)%5]!=EATING)V(&mutex);

&&(state[(i+1)%5]!=EATING))

()

state[i]=EATING;state[i]=THINKING

V(&s[i]);

s[i]=0

}

}

理發(fā)師問題（多進(jìn)程同步）

■題目：

■理發(fā)店里有一位理發(fā)師，一把理發(fā)椅和N把供等候理

發(fā)的顧客坐的椅子

■如果沒有顧客，則理發(fā)師便在理發(fā)椅上睡覺。當(dāng)一個(gè)

顧客到來時(shí)，他必須先喚醒理發(fā)師

■如果顧客到來時(shí)理發(fā)師正在理發(fā)，則如果有空椅子,

可坐下來等；否則離開

理發(fā)師問題

■定義

■理發(fā)師的私有信號(hào)量：等待理發(fā)的顧客c=0；

■顧客的私有信號(hào)量：等待顧客的理發(fā)師b=0;

■等待椅子的顧客數(shù)waiting=O；互斥訪問waiting變

量的mutex=1；

Customer：Barber：注意：

(

P(mutex);P(c)；■理發(fā)師問題可以改為

if(waiting<N){P(mutex);牙醫(yī)問題，網(wǎng)球場(chǎng)問

waiting++;waiting-題，學(xué)生上機(jī)問題，

V(c);v(b);銀行柜員

V(mutex1);V(mutex);

P(b)；理發(fā)■可以采用計(jì)數(shù)器加互

理發(fā)；｝；斥信號(hào)量方法實(shí)現(xiàn)

}

else■也可以用私有信號(hào)量

V(mutex1);控制執(zhí)行順序

}；

閱覽室問題

假定一個(gè)閱覽室最多可容納100人,讀者進(jìn)入

和離開閱覽室時(shí)都必須在閱覽室門口的一個(gè)登

記表上進(jìn)行登記(進(jìn)入時(shí)登記，離開時(shí)去掉登

記項(xiàng))，而且每次只允許一人登記或去掉登記,

問：

(1)應(yīng)編寫幾個(gè)程序完成此項(xiàng)工作，程序的

主要?jiǎng)幼魇切┦裁?？?yīng)設(shè)置幾個(gè)進(jìn)程？進(jìn)程與

程序間的對(duì)應(yīng)關(guān)系如何？

(2)用P,V操作寫出這些進(jìn)程的同步通信

關(guān)系。

閱覽室問題

定義登記過程的互斥信號(hào)量mutex=1

閱覽室可進(jìn)人數(shù)信號(hào)量mc=100；

所有學(xué)生進(jìn)程共用一個(gè)程序

Student：

(

P(mc);

P(mutex);

登記；

V(mutex);

閱讀；

P(mutex);

去除登記;

V(mutex);

V(mc);

L_________

網(wǎng)球場(chǎng)問題

■某高校有m個(gè)網(wǎng)球場(chǎng)，n個(gè)學(xué)生預(yù)約打網(wǎng)

球，有k個(gè)裁判。每?jī)蓚€(gè)學(xué)生組成一隊(duì)，

占用一個(gè)網(wǎng)球場(chǎng)練習(xí)，并安排一個(gè)裁判進(jìn)

行判分（沒有安排時(shí)，裁判休息）。

■請(qǐng)用PV操作完成網(wǎng)球場(chǎng)的分配和學(xué)生練

習(xí)過程

網(wǎng)球場(chǎng)問題

■用私有信號(hào)量實(shí)現(xiàn)多個(gè)進(jìn)程之間的同步，引入場(chǎng)地管理進(jìn)程，完成分配場(chǎng)

地和安排裁判的功能

-定義私有信號(hào)量，分別是

■想打球?qū)W生數(shù)student=O;場(chǎng)地?cái)?shù)site=m,裁判數(shù)judge=k；

?學(xué)生允許進(jìn)場(chǎng)信號(hào)量enter=O；學(xué)生打球結(jié)束信號(hào)量finish=O；安排教練信號(hào)

量call；

Student：monitor：