定義

周轉時間=等待時間+處理時間

響應時間=周轉時間/處理時間=1+等待時間/處理時間

進程調度

批處理系統

先來先服務

最短作業優先

最短剩余時間優先

最高響應比優先

交互式系統

輪轉調度

最高優先級調度

多級反饋隊列調度

最短進程優先

保證調度

彩票調度

公平分享調度

進程互斥

軟件實現

屏蔽中斷

鎖變量

嚴格輪換(單標志法)

由于需要嚴格輪換，所以無法滿足當臨界區空閑且有進程想進入時，能夠及時進入臨界區。

Peterson算法

interested[2]、turn

Dekker算法

硬件實現

中斷屏蔽(開關中斷指令)

TSL指令(TestAndSetLock指令)

把內存地址中的信息拷貝到寄存器中，并在地址中存儲一個非零的值，指令結束之前，該內存地址不允許被訪問

XCHG指令

交換寄存器和內存地址中的值，指令結束之前，該內存地址不允許被訪問

LDREX、STREX指令

信號量

信號量只能初始化、P操作、V操作，使用原語操作，不可中斷。

P、V操作

P操作：占用資源

V操作：釋放資源

信號量機制實現進程互斥

信號量機制實現進程同步

使得兩個進程能夠按照一定的順序執行

信號量機制實現前驅關系

進程同步的擴展

生成者-消費者問題

！！！！！實現互斥的P操作一定要在實現同步的P操作之后！！！！！

多生產者-多消費者問題

！！！！！如果緩沖區大于1，必須設置一個互斥信號量mutex來保證互斥訪問緩沖區！！！！！

吸煙者問題

讀者-寫者問題

哲學家進餐問題

信號量vs管程

死鎖

產生條件：互斥使用、 占有且等待、不可搶占、循環等待

發生死鎖，一定有循環等待；但有循環等待，不一定發生死鎖

死鎖建模

二元組G=(V,E)

處理死鎖的策略

忽略

假裝不存在死鎖

預防死鎖

破壞產生死鎖的四個條件

破壞互斥使用：把獨占資源變為共享資源，SPOOLing技術。但很多情況下，并不能這樣。不實用。

破壞不可搶占：當一個進程申請的資源被其他進程占用時，可以通過操作系統搶占這一資源。不實用。

破壞占有且等待：采用靜態分配方法，一次性申請全部需要的資源。不實用。

破壞循環等待：采用順序資源分配法，給資源編號，每次申請只能申請更大的資源。不實用。

避免死鎖

銀行家算法尋找一條資源分配順序的路線

E表示全部資源量，P表示已分配資源量，A表示剩余資源量

檢測與恢復

**一、**死鎖檢測 可利用死鎖模型檢測、或矩陣檢測 很想避免死鎖中的銀行家算法

**二、**解除死鎖 資源剝奪法、撤銷進程法、進程回退法（進程優先級、已執行時間、剩余時間、已使用資源量、交互式or批處理式）

內存管理

無存儲抽象

①程序中的地址就是真實的內存地址。

②切換程序(進程)的時候整個程序(進程)在內存—硬盤之間切換。

③一段時間內內存中只有一個程序。

④保護機制：把內存劃分為若干區域，每個區域設置訪問權限，進程擁有自己的訪問權限，只能訪問權限相對應的內存。

地址空間

進程看到的是虛擬的地址，進程的地址空間相互獨立且足夠大，不是最終的物理地址，需要經過一個虛擬地址到物理地址的轉換。

動態重定位

基址寄存器和界限寄存器

缺點：訪問內存都需要進行加法和比較運算；內存空間可能是瓶頸。

交換技術

空閑內存管理(連續)

固定分區分配

優點：最簡單的存儲分配

缺點：利用率低，會產生內碎片

動態分配—位圖

動態分配—鏈表

首次適配、下次適配、最佳適配、最差適配、快速適配

伙伴系統

slab機制

虛擬內存(非連續)

覆蓋

缺點：程序員必須自行分割程序：費時且容易出錯

分頁式存儲管理

基本概念

頁表

頁表位于內存中

硬件支持—MMU

加速分頁過程TLB

多級頁表

倒排頁表

頁面置換算法

最佳算法、先進先出、第二次機會、時鐘算法、最近未使用、最近最少使用、最不經常使用、老化算法、工作集、工作集時鐘

時鐘算法

改進型時鐘算法

最近最少使用(LRU)

最不常用算法與老化算法

工作集算法

工作集時鐘頁面置換算法

分段存儲管理方式

段表

分頁、分段對比

段頁式管理方式

分頁、分段的優缺點

基本思路

段表、頁表

文件管理

文件有哪些屬性？

文件名、標識符、類型、位置、大小、創建時間、上次修改時間、所有者、保護信息(權限)

文件結構

文件存放

順序文件

順序文件的缺點是增加或刪除一個記錄比較困難

索引文件

索引順序文件

多級索引順序文件

文件目錄

單級目錄結構

兩級目錄結構

層次目錄結構

無環圖目錄結構

索引結點

文件的物理結構

連續分配

優點：讀寫速度最快

缺點：不靈活，利用率低

鏈接分配

隱式鏈接

顯式鏈接

文件分配表FAT

索引分配與i結點

文件存儲空間管理—空閑塊管理

空閑表法

空閑鏈表法

位示圖法

文件基本操作

創建文件

刪除文件

打開文件

關閉文件

讀文件

寫文件

文件共享

系統中只有**“一份”**文件數據，某個用戶修改了文件數據，其他用戶也可以看到文件的變化，注意與復制的區分

基于索引結點的共享方式(硬鏈接)

基于符號鏈的共享方式(軟連接) 快捷方式

對比

硬鏈接無需額外的開銷，只需要在i結點中添加計數器，計數有多少個鏈接，而符號鏈接即軟鏈接需要額外的開銷來存儲共享文件的路徑名。

軟鏈接只要簡單地提供一個機器的網絡地址以及文件在該機器上的駐留的路徑，就可以鏈接全球任何地方的機器上的文件，而硬鏈接不能這樣。

文件保護

口令保護

加密保護

例如異或加密等，系統中保存的是解密后的密文

優點：保密性強，不需要在系統中存儲“密碼”

缺點：加密/解密需要花費一定時間

訪問控制

磁盤調度算法

一次磁盤讀/寫操作的時間：尋道時間、延遲時間(轉動時間)、傳輸時間

先來先服務

根據進程請求訪問磁盤的先后順序進行調度

最短尋道時間優先

掃描算法/電梯算法

LOOK調度算法

循環掃描算法

C-LOOK調度算法

I/O管理

I/O控制器

I/O控制方式

程序直接控制

讀操作(數據流向)：IO–>CPU–>內存

寫操作(數據流向)：內存–>CPU–>IO

優點：實現簡單

缺點：只能串行工作，CPU長期處于“忙等”狀態

中斷驅動方式

優點：與“程序直接控制方式”相比，在“中斷驅動方式”中，I/O控制器會通過中斷信號主動報告I/O已完成，CPU不再需要不停地輪詢。

缺點：每個字在I/O設備與內存之間的傳輸，都需要經過CPU。而頻繁的中斷處理會消耗比較多的CPU時間。

DMA方式(直接存儲器存取)

CPU干預的頻率進一步降低

通道控制方式

層次結構

設備獨立性軟件：①向上層提供統一的調用接口；②設備的保護；③差錯處理；④設備的分配與回收；

? ⑤數據緩沖區管理；⑥建立邏輯到物理的設備名的映射關系；

中斷處理程序：

核心子系統

假脫機技術SPOOLing

設備的分配和回收

設備的固有屬性：獨占設備、共享設備、虛擬設備

安全分配方式：為進程分配一個設備后就將進程阻塞，本次I/O完成后才喚醒進程 缺點：只能串行工作

不安全分配方式：與安全分配方式相反 缺點：可能發生死鎖

靜態分配

進程運行前為其分配全部所需資源，運行結束后歸還資源

動態分配

進行運行過程中動態申請設備資源

設備分配表DCT

控制器控制表COCT

總結

以上是生活随笔為你收集整理的[现代操作系统] 考前突击的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。