計算機作業系統（第四版）複習材料-完全

計算機作業系統（第四版）複習材料-完全版

計算機作業系統（第四版）複習材料-第一章 作業系統引論

計算機作業系統（第四版）複習材料-第二章 程序的描述與控制

計算機作業系統（第四版）複習材料-第三章 處理機排程與死鎖

計算機作業系統（第四版）複習材料-第四章 存儲器管理

計算機作業系統（第四版）複習材料-第五章 虛拟存儲器

計算機作業系統（第四版）複習材料-第六章 輸入輸出系統

計算機作業系統（第四版）複習材料-第七章 檔案管理

計算機作業系統（第四版）複習材料-第八章 磁盤存儲器的管理

計算機作業系統（第四版）複習材料-簡述題

文章目錄

• 第一章 作業系統引論
• • 什麼是作業系統
  • 作業系統的目标和作用
  • 作業系統的發展過程
  • 作業系統的基本特征
  • 作業系統的主要功能
  • • 處理機管理
    • 存儲器管理
    • 裝置管理
    • 檔案管理
    • 使用者接口
  • 作業系統的結構設計
  • • 作業系統的結構設計發展
    • 常見的OS總體結構風格
• 第二章 程序的描述與控制
• • 現代OS中程序和線程的概念
  • 前驅圖和程式執行
  • 程序的描述
  • • 程序的定義
    • 程序的特征
    • 程序和程式的差別
    • 程序的狀态模型
    • 如何區分阻塞Or挂起？
    • 程序控制塊PCB
  • 程序控制
  • • 作業系統核心的功能
    • 程序的層次結構
    • 引起程序建立的事件
    • 程序建立流程
    • 引起程序結束的事件
    • 程序的終止過程
    • 程序的阻塞與喚醒
    • 程序的挂起與激活
  • 線程相關
  • 程序同步
  • • 定義
    • 機制
    • 制約關系
    • 臨界資源
    • 同步機制規則
    • 硬體機制
    • 信号量機制
    • 管程機制
  • 經典程序同步的同步問題
  • • 生産者消費者問題
    • 哲學家進餐問題
    • 讀者寫者問題
  • 程序通信
• 第三章 處理機排程與死鎖
• • 處理機排程的層次和排程算法的目标
  • • 按照層次劃分
    • 按OS類型劃分
    • 排程算法的共同目标
    • 批處理系統的目标
    • 分時系統的目标
    • 實時系統的目标
  • 作業排程（進階排程）
  • • 作業與作業步
    • 作業運作的三階段和三狀态
    • FCFS（先來先服務）
    • SJF（最短作業優先）
    • PSA（優先級排程算法）
    • HRRN（高響應比優先算法）
  • 程序排程（低級排程）
  • • 程序排程任務
    • 程序排程機制
    • 程序排程方式
    • SRT（最短剩餘時間優先）
    • RR（時間輪轉排程算法）
    • MFQ（多級回報隊列排程算法）
  • 實時排程
  • • 實作實時排程的基本條件
    • 實時排程算法的分類
    • EDF（最早截止時間優先算法）
    • LLF（最低松弛度優先算法）
    • 優先級倒置
  • 死鎖概述
  • • 死鎖定義
    • 死鎖産生原因
    • 死鎖産生的條件
    • 處理死鎖的方法
    • 避免死鎖（銀行家算法）
    • 死鎖的檢測與解除
    • 死鎖的解除
• 第四章 存儲器管理
• • 存儲器的層次結構
  • 程式的裝入和連結
  • • 如何從源程式變為在記憶體中可執行的程式
    • 程式的裝入方式
    • 程式的連結方式
  • 存儲管理技術-分區（連續）
  • • 固定分區
    • 動态分區
  • 存儲管理技術-分頁（離散）
  • • 簡單分頁
    • 位址變換機構
    • 通路記憶體的有效時間
    • 虛拟存儲分頁
  • 存儲管理技術-分段（離散）
  • • 簡單分段
    • 段頁式
    • 虛拟存儲分段
• 第五章 虛拟存儲器
• • 引入
  • • 正常存儲管理的問題
    • 解決方案：
    • 局部性原理
  • 虛拟存儲器的定義和特征
  • • 虛拟存儲器的基本原理
    • 虛拟存儲器的定義
    • 虛拟存儲器的特征
    • 虛拟存儲器的實作方法
    • 請求分頁
    • 請求分段
    • 缺頁率
    • 抖動
    • 頁面置換算法
    • 通路記憶體的有效時間EAT（了解）
• 第六章 輸入輸出系統
• • I/O系統的功能、模型和接口
  • • I/O系統的任務和基本功能
    • I/O軟體的層次結構
    • I/O系統的上下接口
    • I/O系統的分層
  • I/O裝置和裝置控制器
  • • I/O裝置的類型
    • 裝置控制器
    • 記憶體映像I/O
    • I/O通道
  • 中斷機構和中斷處理程式
  • • 中斷簡介
    • 對多源中斷的處理方式
    • 中斷處理程式
  • 裝置驅動程式
  • • 裝置驅動程式簡介
    • 裝置驅動程式功能
    • 裝置驅動程式特點
    • 裝置處理方式
    • 裝置驅動程式的處理過程
    • 對 I/O 裝置的控制方式
  • 與裝置無關的I/O軟體（了解思想）
  • • 引入
    • 裝置配置設定的資料結構
    • 邏輯裝置表 LUT(Logical Unit Table)
    • 裝置配置設定時應考慮的因素
  • 使用者層I/O軟體
  • 緩沖區管理
  • 磁盤存儲器的性能和排程
  • • 提高磁盤I/O速度的主要途徑
    • 磁盤結構
    • 資料的組織
    • 磁盤通路時間
    • 磁盤排程算法
• 第七章 檔案管理
• • 檔案和檔案系統
  • • 檔案
    • 檔案類型
    • 檔案系統
  • 檔案的邏輯結構
  • • 引入
    • 檔案邏輯結構的類型
  • 檔案目錄
  • • 引入
    • 對檔案目錄的管理要求
    • 檔案控制塊FCB
    • 索引結點（平均啟動磁盤的次數）
  • 檔案共享
  • • 檔案共享的方法
  • 檔案保護
  • • 影響檔案安全性的主要因素
    • 確定檔案系統安全性的措施
    • 通路控制技術
    • 通路控制表和通路權限表
• 第八章 磁盤存儲器的管理
• • 外存的組織方式
  • • 連續組織方式（順序配置設定）
    • 連結組織方式
    • • FAT檔案系統
      • NTFS 檔案系統
    • 索引組織方式
  • 檔案存儲空間的管理
  • • 存儲空間的管理方法
  • 其餘不再總結
  • 簡述作業系統的四個基本特征
  • 微核心OS的優點和缺點是什麼？
  • 請描述多級回報隊列排程算法的排程機制
  • 産生死鎖的四個必要條件是什麼？
  • 試述快表技術是如何實作的
  • 分頁存儲管理和分段存儲管理有何差別
  • 裝置管理的目标和功能是什麼
  • 檔案的實體結構有哪幾種

第一章 作業系統引論

什麼是作業系統

1. 定義

   作業系統是一組能有效地組織和管理計算機硬體和軟體資源，合理地對各類作業進行排程，以及友善使用者使用的程式的集合。（作業系統是一類程式的集合）

2. 從外部看OS

• 使用者環境觀點（計算機使用者的觀點）
• 虛拟機器觀點（應用程式員的觀點）

1. 從内部看OS

• 資源管理觀點（OS開發者觀點一）
• 作業組織觀點（OS開發者觀點二）

  

作業系統的目标和作用

1. 目标

• 有效性
• 友善性
• 可擴充性
• 開放性

1. 作用

• OS作為使用者與計算機硬體系統之間的接口
• OS作為計算機系統資源的管理者（四大管理：程序管理、存儲管理、裝置管理、檔案管理）
• OS實作了對計算機資源的抽象

作業系統的發展過程

1. 人工操作方式
2. 脫機輸入輸出方式
3. 單道批處理系統（自動性、順序性、單道性）
4. 多道批處理系統（排程性、無序性、多道性）
5. 分時系統（多路性、獨立性、及時性、互動性）
6. 實時系統（實時性和可靠性、多路性、獨立性、互動性）
7. 通用作業系統

• 微機作業系統

1. 單使用者單任務作業系統（CP/M、MS-DOS）
2. 單使用者多任務作業系統（Windows98以及以前版本的Windows）
3. 多使用者多任務作業系統 （UNIX、Windows XP以及以後版本的Windows）

• 網絡作業系統

1. 其他作業系統（MPS…）

作業系統的基本特征

1. 現代OS的兩個基本特征（慕課版）

• 任務1共行

從宏觀上來看，任務共行是指系統中有多個任務同時運作

從微觀上來看，任務共行是指單處理器系統中的任務并發或多處理系統中的任務并行

• 資源共享

從宏觀上看，資源共享是指多個任務可以同時使用系統中的軟硬體資源

從微觀上看，資源共享是指多個任務可以交替互斥地使用系統中的某個資源

1. 作業系統的基本特征（所學習版）

• 并發性（最重要）
• 共享性
• 虛拟性
• 異步性

并發性和共享性是作業系統的兩個最基本特征，二者互為存在條件。

作業系統的主要功能

處理機管理

1. 程序控制
2. 程序同步
3. 程序通信
4. 程序排程

存儲器管理

1. 記憶體配置設定
2. 記憶體保護
3. 位址映射
4. 記憶體擴充

裝置管理

1. 緩沖管理
2. 裝置配置設定
3. 裝置處理
4. 虛拟裝置

檔案管理

1. 檔案存儲空間的管理
2. 目錄管理
3. 檔案的讀寫管理
4. 檔案的共享與保護

使用者接口

1. 使用者接口
2. 程式接口

作業系統的結構設計

作業系統的結構設計發展

1. 無結構
2. 子產品化
3. 分層式
4. 微核心

常見的OS總體結構風格

大多數現代OS其總體結構包含兩類子系統：1.使用者接口子系統；2.基礎平台子系統；它們之間具有單向性。

1. 常見的基礎平台子系統結構風格

• 分層結構風格
• 分級結構風格
• 分塊結構風格
• 單模式2結構風格
• 多模式結構風格

1. 雙模式基礎平台子系統

• 核外子系統（User Mode）
• 核内子系統（Kernel Mode）

第二章 程序的描述與控制

現代OS中程序和線程的概念

程序：是資源配置設定的和獨立運作的基本機關。

線程：是系統排程的基本機關。

前驅圖和程式執行

1. 前驅圖

   有向無循環圖（DAG ）。描述一個程式的各部分（程式段或語句）間的依賴關系，或者是一個大的計算的各個子任務間的因果（前後）

   關系。前趨圖中的每個結點可以表示一條語句、一個程式段或一個程序，結點間的有向邊表示兩個結點之間存在的偏序關系或前趨關系“→ ”。沒有前趨的結點稱為初始結點，沒有後繼的結點稱為終止結點。此外，每個結點還具有一個權值，用于表示該結點所含有的程式量或結點的執行時間。

2. 程式順序執行

• 順序性
• 封閉性
• 可再現性

1. 程式并發執行

• 異步性
• 失去封閉性
• 不可再現性

  

程序的描述

程序的定義

程序是程式在一個資料集合上的運作過程，是系統進行資源配置設定和排程的一個獨立機關。

擴：程序實體：程式段+資料段+PCB

程序的特征

• 動态性
• 并發性
• 獨立性
• 異步性

程序和程式的差別

程式是指令的有序集合，是靜态的，其存在是無生命周期的，而程序由程式段、資料段、PCB組成，是動态的，有生命周期的。

程序的狀态模型

1. 二狀态模型

   Running

   Not-Running

2. 三狀态模型

   Running

   Ready

   Block

3. 五狀态模型

   Running

   Ready

   Block

   New

   Exit

4. 七狀态模型

   Running

   Ready

   Block

   Ready，Suspend

   Block，Suspend

   New

   Exit

挂起需要用到Swapping技術；

如何區分阻塞Or挂起？

• 程序是否等待事件，阻塞與否
• 程序是否被換出記憶體，挂起與否

程序控制塊PCB

1. 定義：

   是作業系統為了管理和控制程序的運作，而為每一個程序定義的一個資料結構，它記錄了系統管理程序所需的全部資訊。

2. 位置：

   常駐記憶體，存放在作業系統中專門開辟的PCB區内。

3. 作用：

   a. 作為獨立運作基本機關的标志，程序存在的唯一标志，系統根據PCB而感覺相關程序的存在。

   b. 能實作間斷性運作方式。保護現場

   c. 提供程序管理所需要的資訊

   d. 提供程序排程所需要的資訊

   e. 實作與其他程序的同步和通信

4. 内容：

   a. 程序辨別符

   b. 處理機狀态

   c. 程序排程資訊

   d. 程序控制資訊

程序控制

作業系統核心的功能

1. 支撐功能

• 中斷處理
• 時鐘管理
• 原語3操作

1. 資源管理功能

• 程序管理
• 存儲器管理
• 裝置管理

程序的層次結構

• 子程序可繼承父程序的所有資源
• 子程序撤銷時要把資源歸還給父程序
• 父程序撤銷時也必須撤銷所有子程序

引起程序建立的事件

使用者登入、作業排程、提供服務、應用請求

程序建立流程

• 為程序配置設定一個唯一辨別号
• 為程序配置設定空間
• 初始化PCB
• 建立連結
• 建立或擴充其他資料結構

引起程序結束的事件

正常、異常、外界幹預

程序的終止過程

• 根據PID找到PCB，讀出該程序的狀态
• 若該程序為執行狀态，則終止其執行，排程新程序執行
• 若該程序有子孫程序，則立即終止其所有子孫程序
• 将該程序的全部資源，或歸還其父程序，或歸還系統
• 将被終止程序的PCB從所在隊列中移出，等待其他程式來搜集資訊

程序的阻塞與喚醒

阻塞是主動的，喚醒是被動的

程序的挂起與激活

挂起是由程序自己或其父程序調 Suspend 原語完成。激活是由父程序或使用者程序請求激活指定程序，系統利用 Active 原語将指定程序激活。

線程相關

1. 當引入線程後，線程是系統排程的基本機關，程序是資源配置設定的基本機關，而不再是一個可執行的實體。
2. 程序與線程的存在方式

   

3. 程序與線程的比較

   

程序同步

定義

是指對多個相關程序在執行次序上進行協調，他的目的是使系統中諸程序之間能有效地共享資源和互相合作，進而使程式的執行具有可再現性。

機制

硬體機制、信号量機制、管程機制

制約關系

• 直接制約關系（程序同步）
• 間接制約關系（程序互斥）

  

臨界資源

臨界資源是一次隻允許一個程序使用的資源，需要程序采用互斥方式通路；通路臨界資源的那一段代碼叫做臨界區（CS區）。

同步機制規則

• 空閑讓進
• 忙則等待
• 有限等待
• 讓權等待

硬體機制

• 關中斷
• TS指令

• Swap指令

  不符讓權等待（造成了忙等）

信号量機制

操作：P、V操作

原語：wait、signal（必須成對存在）

類别：資源信号量、互斥信号量

資源信号量：申請/歸還資源，可以初始化為一個正整數（>=0 表示可用資源數 <0表示被阻塞的程序數）

互斥信号量：申請/釋放使用權，常初始化為1

注意事項：兩個wait操作相鄰的話，順序很重要！同步wait必須在互斥wait前面！wait，signal成對出現，當為互斥操作時，處于同一程序，否則不在同一程序；使用PV不當，會産生死鎖；

管程機制

定義：一個資料結構和在該資料結構上能被并發程序所執行的一組操作，這組操作能使程序同步和改變管程中的資料。

管程規定每次隻準許一個程序執行，進而實作了程序互斥，保證了管程共享變量的資料完整性。

經典程序同步的同步問題

生産者消費者問題

資源信号量：full=0、empty=n（分别表示滿緩沖區的數目、空緩沖區的數目）

互斥資源量：mutex=1

核心算法表示：

哲學家進餐問題

互斥資源量：五個

可能會出現死鎖，改進如下：

讀者寫者問題

1. 讀者優先：

   共享變量：readcount，目前讀者個數，初值為0

   互斥信号量：Rmutex=1（讀互斥）、Wmutex=1（寫互斥）

   

   

2. 寫者優先

   共享變量：readcount，目前讀者個數，初值為0

   互斥信号量：Rmutex=1（讀互斥）、Wmutex=1（寫互斥）、S=1（讀寫互斥）

   

程序通信

1. 共享存儲器系統
2. 消息傳遞系統

• 直接通信方式：消息緩沖通信
• 間接通信方式：信箱通信方式

1. 管道通信（共享檔案通信）
2. 客戶機-伺服器系統

第三章 處理機排程與死鎖

處理機排程的層次和排程算法的目标

按照層次劃分

進階排程 外《----》内

中級排程 外《----》内 但PCB在内

低級排程 記憶體之中

按OS類型劃分

批處理排程、分時排程、實時排程、多處理機排程

排程算法的共同目标

• 資源使用率

C P U 利 用 率 = C P U 有 效 工 作 時 間 / 有 效 時 間 + 空 閑 等 待 時 間 CPU使用率=CPU有效工作時間/有效時間+空閑等待時間 CPU使用率=CPU有效工作時間/有效時間+空閑等待時間

• 公平性（防止程序饑餓）
• 平衡性（CPU型程序和I/O型程序）
• 政策強制執行（搶占）

批處理系統的目标

• 平均周轉時間

周轉時間：駐外存等待排程時間+駐記憶體等待排程時間+執行時間+阻塞時間=結束時間-到達時間

平均周轉時間= 1 n ∑ i = 0 n T i \frac{1} {n} \displaystyle \sum^{n}_{i=0} T_i n1​i=0∑n​Ti​

平均周轉時間可以衡量不同排程算法對相同作業流的排程性能。

帶權周轉時間= 1 n ∑ i = 0 n T i T s \frac{1} {n} \displaystyle \sum^{n}_{i=0} \frac{T_i} {T_s} n1​i=0∑n​Ts​Ti​​

帶權周轉時間越小越好

• 系統吞吐量
• 處理機使用率高

分時系統的目标

• 響應時間快
• 均衡性

實時系統的目标

• 截止時間保障
• 可預測性

作業排程（進階排程）

作業與作業步

Job是指，計算機使用者在一次上機過程中要求計算機系統為其所做的工作的集合；作業中的每項相對獨立的工作稱為作業步；

一個典型的作業可分為三個作業步：1.編譯作業步 2.連結裝配作業步 3.運作作業步

作業運作的三階段和三狀态

• 收容階段 後備狀态
• 運作階段 執行狀态
• 完成階段 停止狀态

FCFS（先來先服務）

基本思想：按程序（作業）進入就緒（後備）隊列的先後次序來配置設定處理機（為其建立程序）。

排程方式：非剝奪

優點：簡單、有利于CPU繁忙型作業

缺點：I/O不利、短作業不利

SJF（最短作業優先）

基本思想：從後備作業中選擇一個或若幹個估計運作時間最短的作業，将他們調入記憶體運作

排程方式：非剝奪

優點：有效降低作業的平均等待時間、提高了吞吐量

缺點：長作業不利、不考慮緊迫性、作業執行時間、剩餘時間僅為估計

PSA（優先級排程算法）

• 靜态優先級
• 動态優先級

HRRN（高響應比優先算法）

基本思想： 既考慮了作業的等待時間，也考慮了作業的運作時間，是一種動态優先級排程算法。

優先權=等待時間+要求服務時間/要求服務時間

程序排程（低級排程）

程序排程任務

1. 儲存處理機的現場資訊
2. 按某種算法選取程序
3. 把處理器配置設定給程序

程序排程機制

1. 排隊器
2. 分派器
3. 上下文切換器

程序排程方式

1. 非搶占式

   優點：簡單、系統開銷小

   缺點：不适用于分時系統和實時系統

2. 搶占式

   搶占原則：優先權原則、短程序優先原則、時間片原則

SRT（最短剩餘時間優先）

基本思想：它總是選擇預期剩餘時間最短的程序。隻要新程序就緒，且有更短的剩餘時間，排程程式就可能搶占目前正在運作的程序

方式：搶占式

優點：搶占

缺點：必須記錄過去的服務時間，進而增加了開銷。

RR（時間輪轉排程算法）

基本思想：系統将所有就緒程序按FCFS的原則，排成一個隊列依次排程，把 CPU 配置設定給隊首程序，并令其執行一個時間片，通常為

10-100ms。時間片用完後，系統的計時器發出時鐘中斷，該程序将被剝奪 CPU并插入就緒隊列末尾。

優點：非常公平

程序切換時機：

1. 若一個時間片尚未用完程序便已經完成，就立即再排程就緒隊列中隊首程序運作，并啟動一個新的時間片。

2. 如果在一個時間片用完時程序尚未運作完畢，則剝奪 CPU，排程程式把它送往就緒隊列的末尾。

   響應時間T = 時間片q × 就緒隊列程序數n

   時間片的選擇：略大于一次典型的互動所需要的時間（在一個時間片内能完成80%左右的程序）

MFQ（多級回報隊列排程算法）

1. 基本思想

   

   

實時排程

實作實時排程的基本條件

1. 提供必要的排程資訊
2. 系統處理能力強
3. 采用搶占式的排程機制
4. 具有快速切換機制

實時排程算法的分類

1. 按實時任務性質

• 硬實時
• 軟實時

1. 按排程方式

• 非搶占
• 搶占

EDF（最早截止時間優先算法）

1. 非搶占式

   

2. 搶占式

   

LLF（最低松弛度優先算法）

基本思想：算法是根據任務緊急（或松弛）的程度，來确定任務的優先級。任務的緊急度越高，其優先級越高，并使之優先執行。

方式：搶占式

松弛度 = 必須完成時間 - 本身剩餘運作時間 - 目前時間

優先級倒置

1. 原因

   高優先級程序（或線程）被低優先級程序（或線程）延遲或阻塞。臨界資源

2. 解決方法

   

   

死鎖概述

死鎖定義

死鎖是指兩個或兩個以上的程序在執行過程中，因争奪資源而造成的一種互相等待的現象，若無外力作用，它們都将無法推進下去。此時稱系統處于死鎖狀态，這些永遠在互相等待的程序稱為死鎖程序。

擴：饑餓是指一個程序一直得不到資源4

死鎖産生原因

1. 競争不可搶占資源引起死鎖
2. 競争可消耗資源引起死鎖
3. 程序間推進順序不當引起死鎖

死鎖産生的條件

1. 互斥條件
2. 請求和保持條件
3. 不可剝奪條件

4. 環路等待條件

   前三個是必要條件、最後一個是前三個條件産生的結果

處理死鎖的方法

1. 鴕鳥方法
2. 預防死鎖（破壞四個條件中的一個或幾個）
3. 避免死鎖
4. 檢測死鎖
5. 解除死鎖

避免死鎖（銀行家算法）

1. 定義

   在資源的動态配置設定過程中, 采用某種政策防止系統進入不安全狀态5, 進而避免發生死鎖。（確定系統不進入不安全狀态）。

   并非所有不安全狀态都是死鎖狀态，隻要系統處于安全狀态，則可避免進入死鎖狀态。

1. 銀行家算法

   實質：設法保證系統動态配置設定資源後不進入不安全狀态，以避免可能産生的死鎖。

   前提條件：要求程序必須預先提出自己的最大資源請求數量，這一數量不能超過系統資源的總量，系統資源的總量是一定的。

   資料結構：

   

   

算法描述：

自然語言描述:

系統提出請求後，先判斷請求是否合法，如果合法，則嘗試修改，判斷修改後是否存在安全狀态，如果存在則确認修改。

如何判斷是否存在安全狀态：

目前系統可用資源配置設定給某個程序後，可以完成該程序，并釋放該程序資源。循環直至全部完成；

死鎖的檢測與解除

1. 資源配置設定圖

   

   重要結論：如果資源配置設定圖中不存在環路，則系統中不存在死鎖；反之，如果資源配置設定圖中存在環路，則系統中可能存在死鎖，也可能不存在死鎖。
2. 死鎖定理

   

死鎖的解除

• 資源剝奪法
• 撤銷程序法

第四章 存儲器管理

存儲器的層次結構

程式的裝入和連結

如何從源程式變為在記憶體中可執行的程式

1. 編譯
2. 連結
3. 裝入

   

程式的裝入方式

1. 絕對裝入方式
2. 可重定位6裝入方式

1. 動态運作時裝入方式

程式的連結方式

1. 靜态連結
2. 裝入時動态連結
3. 運作時動态連結

存儲管理技術-分區（連續）

固定分區

1. 定義

   系統初始啟動時将記憶體劃分為數目固定、尺寸固定的多個分區。這些分區的尺寸可以相等也可以不等。

2. 條件

   系統需建立一張分區說明表或使用表，以記錄分區号、分區大小、分區的起始位址及狀态（已配置設定或未配置設定）。

3. 流程

   當某個使用者程式要裝入記憶體時，通常将分區按大小進行排隊，由記憶體配置設定程式檢索分區說明表，從表中找出一個滿足要求的尚未配置設定的分區配置設定該程式，同時修改說明表中相應分區的狀态；若找不到大小足夠的分區，則拒絕為該程式配置設定記憶體。程式執行完畢，釋放占用的分區，管理程式修改說明表中相應分區的狀态為未配置設定，實作記憶體資源的回收。

4. 缺點

   作業的大小并不一定與某個分區大小相等，進而使一部分存儲空間被浪費，産生内零頭7，是以主存的使用率不高。分區尺寸固定,系統無法運作大程式；分區數目固定,使活動程序的數目受限。

動态分區

1. 定義

   動态分區配置設定是一種動态劃分存儲器的分區方法。記憶體不是預先劃分好的，作業裝入時，根據作業的需求和記憶體空間的使用情況來決定是否配置設定。

2. 條件

   系統需要建立空閑分區表（和空閑分區鍊），用來登記系統中的空閑分區（分區号、分區起始位址、分區大小及狀态）。以及需要特定的分區配置設定算法；

3. 流程

   

   

4. 缺點

   容易産生外零頭8，需要較好的比對算法支援。

1. 配置設定算法

   a.基于順序搜尋的動态分區配置設定算法

• 首次适應算法
• 循環首次适應算法
• 最佳适應算法

• 最壞适應算法

  b.基于索引搜尋的動态分區配置設定算法

• 快速适應算法
• 夥伴系統
• 雜湊演算法

1. 涉及到的寄存器（存儲保護）

• 基址寄存器
• 界限寄存器

1. 覆寫與對換

   覆寫可減少一個程序運作所需的空間。對換可讓整個程序暫存于外存中，讓出記憶體空間。

   覆寫是由程式員實作的，作業系統根據程式員提供的覆寫結構來完成程式段之間的覆寫。對換技術不要求程式員給出程式段之間的覆寫結構。

   覆寫技術主要在同一個作業或程序中進行。對換主要在作業或程序之間進行。

存儲管理技術-分頁（離散）

簡單分頁

1. 定義

   将一個使用者程序的位址空間（邏輯空間）劃分成若幹個大小相等的區域，稱為頁或頁面，各頁從 0 開始編号。記憶體空間也分成若幹個與頁大小相等的區域，稱為塊（實體塊）或頁框（frame），同樣從 0 開始編号。在為程序配置設定記憶體時以塊為機關，将程序中若幹頁裝入到多個不相鄰的塊中，最後一頁常裝不滿一塊而出現頁内碎片。在分頁存儲管理方式中，如果不具備頁面對換功能，不支援虛拟存儲器功能，這種存儲管理方式稱為純分頁或基本分頁存儲管理方式。

2. 條件

   需要建立頁表、以及需要寄存器的配合（硬體位址轉換）。

   邏輯位址：頁号＋頁内偏移

   實體位址：塊号＋塊内偏移

3. 頁表

   a.為了便于在記憶體找到程序的每個頁面所對應塊，分頁系統中為每個程序配置一張頁表，程序邏輯位址空間中的每一頁，在頁表中都對應一個頁表項。頁表項的長度一般是由作業系統決定的。（具體頁表項中都包含什麼不再讨論）

   c.頁表存放在記憶體中，屬于程序的現場資訊。用途：①記錄程序的記憶體配置設定情況 ②實作程序運作時的動态重定位。

   d.通路一個資料需通路記憶體 2 次 (頁表一次，記憶體一次)。頁表的基址及長度由頁表寄存器給出。

4. 頁面的大小

   

5. 多級頁表

   為了解決大頁表問題。

   

6. 反置頁表

   是為每一個實體塊設定一個頁表項并按實體塊号排序，其中的内容是頁号 P 及隸屬程序标志符 pid。

位址變換機構

作用：将使用者位址空間中的邏輯位址變換為記憶體空間中的實體位址。實作邏輯位址向實體位址的轉換（頁号 ⇒ 塊号）。位址變換借助頁表來完成。

1. 基本位址變換機構

   

2. 具有快表的位址變換機構

   基本位址變換存在的問題：位址變換速度低（兩次通路記憶體）

   目的：為提高位址變換速度。

   定義：又稱為聯想寄存器、聯想存儲器 (Associative Memory) 、IBM-TLB(Translation Lookaside Buffer)。快表是一種特殊的高速緩沖存儲器（Cache），内容是頁表中的一部分或全部内容。

   流程：CPU 産生邏輯位址的頁号，首先在快表中尋找，若命中就找出其對應的實體塊；若未命中，再到頁表中找其對應的實體塊，并将之複制到快表。若快表中内容滿，則按某種算法淘汰某些頁。

   

通路記憶體的有效時間

虛拟存儲分頁

存儲管理技術-分段（離散）

引入的必要性：友善程式設計、資訊共享、資訊保護、動态增長、動态連結

簡單分段

1. 定義

   将使用者作業的邏輯位址空間劃分成若幹個大小不等的段（由使用者根據邏輯資訊的相對完整來劃分）。各段有段名（常用段号代替），首位址為 0。

2. 條件

   需要段表（記憶體中）。

3. 次元

   整個作業的位址空間由于是分成多個段，，因而是二維的，邏輯位址由段号和段内位址所組成。

段頁式

1. 引入：

   分頁活動源于系統管理實體記憶體的需要，在系統内部進行，由系統實施，使用者看不見。

   分段活動源于使用者進行子產品化程式設計的需要，在系統外部進行，由使用者實施，使用者是知道的。

   

2. 位址結構

   

3. 段表和頁表

   系統中設段表和頁表，均存放于記憶體中。讀一位元組的指令或資料須通路記憶體三次。為提高執行速度可增設高速緩沖寄存器。

   每個程序一張段表，每個段一張頁表。

   段表含段号、頁表始址和頁表長度。頁表含頁号和塊号。

4. 流程

   

虛拟存儲分段

第五章 虛拟存儲器

引入

正常存儲管理的問題

正常存儲管理方式的共同點：要求一個作業全部裝入記憶體後方能運作。可能出現的問題

1. 有的作業很大，所需記憶體空間大于記憶體總容量，使作業無法運作
2. 有大量作業要求運作，但記憶體容量不足以容納下所有作業，隻能讓一部分先運作，其它在外存等待。

解決方案：

1. 增加記憶體容量
2. 從邏輯上擴充記憶體容量：覆寫、對換、虛拟存儲技術

局部性原理

1. 時間局部性

   如果程式中的某條指令一旦執行，則不久以後該指令可能再次執行；如果某資料被通路過，則不久以後該資料可能再次被通路。産生時間局限性的典型原因，是由于在程式中存在着大量的循環操作。

2. 空間局部性

   一旦程式通路了某個存儲單元，在不久之後，其附近的存儲單元也将被通路，即程式在一段時間内所通路的位址，可能集中在一定的範圍之内，其典型情況便是程式的順序執行。

虛拟存儲器的定義和特征

虛拟存儲器的基本原理

虛拟存儲器的定義

虛拟存儲器，是指具有請求調入功能和置換功能，能從邏輯上對記憶體容量加以擴充的一種存儲器系統。

邏輯容量由記憶體容量和外存容量之和所決定。

運作速度接近于記憶體速度，成本接近于外存。

速度和容量：虛拟存儲量的擴大是以犧牲 CPU 工作時間以及内外存交換時間為代價。

虛拟存儲器的容量取決于主存與輔存的容量，最大容量是由計算機的位址結構決定。

虛拟存儲器的邏輯位址空間理論上不受實體存儲器的限制。如 32 位機器，虛拟存儲器的最大容量就是 4G，再大 CPU 無法直接通路。

虛拟存儲器的特征

1. 多次性（最重要的特征）
2. 對換性
3. 虛拟性

虛拟性以多次性和對換性為基礎，而多次性和對換性必須以離散配置設定為基礎。

虛拟存儲器的實作方法

1. 請求分頁（虛拟分頁）
2. 請求分段（虛拟分段）
3. 請求段頁式（虛拟段頁式）

請求分頁

1. 定義

   在分頁系統的基礎上，增加了請求調頁功能、頁面置換功能所形成的頁式虛拟存儲器系統。

它允許隻裝入若幹頁的使用者程式和資料，便可啟動運作，以後在硬體支援下通過調頁功能和置換頁功能，陸續将要運作的頁面調入記憶體，同時把暫不運作的頁面換到外存上，置換時以頁面為機關。

1. 條件

   硬體支援：請求分頁的頁表機制、缺頁中斷9機構和位址變換機構。

1. 流程

   

請求分段

1. 定義

   在分段系統的基礎上，增加了請求調段功能及分段置換功能，所形成的段式虛拟存儲器系統。

它允許隻裝入若幹段的使用者程式和資料，便可啟動運作，以後再硬體支援下通過請求調段功能和分段置換功能，陸續将要運作的段調入記憶體，同時把暫不運作的段換到外存上，置換時以段為機關

1. 條件

   硬體支援：請求分段的段表機制、缺段中斷機構和位址變換機構。

   軟體：請求調段功能和段置換功能的軟體。

缺頁率

抖動

1. 定義（詳細的請看書）

   剛被淘汰出記憶體的頁面，過後不久又要通路它，需要再次将其調入，而該頁調入記憶體後不久又再次被淘汰出記憶體，然後又要通路它，如此反複，使得系統把大部分時間用在了頁面的調進換出上，這種現象稱為抖動。

2. 預防方法

   a. 采取局部置換政策

   b. 在處理機排程中引入工作集政策（工作集不再解釋）

   c. 用L=S準則調節缺頁率

   d. 挂起若幹程序

頁面置換算法

1. 最佳置換算法（OPT）

   思路：選擇永遠不再需要的頁面或最長時間以後才需要通路的頁面予以淘汰。

最佳置換算法是一種理想化的算法，性能最好，實際上這種算法無法實作，因為頁面通路的未來順序很難精确預測，但可用該算法評價其它算法的優劣。

1. 先進先出置換算法（FIFO）

   思路：選擇先進入記憶體的頁面予以淘汰。

Belady奇異現象，是指采用頁面置換FIFO算法時，如果對一個程序未配置設定它所要求的全部頁面，有時就會出現配置設定的頁面數增多，但缺頁率反而提高的異常現象，這是一個違反直覺的現象。

1. 最近最久未使用算法（LRU）

   思路：選擇最近一段時間最長時間沒有被通路過的頁面予以淘汰。

：如果某個頁面被通路了，則它可能馬上還要通路。如果很長時間未被通路，則它在最近一段時間也不會被通路。該算法的性能接近于最佳算法，但實作起來較困難。因為要找出最近最久未使用的頁面，必須為每一頁設定相關記錄項，用于記錄頁面的通路情況，并且每通路一次頁面都須更新該資訊。這将使系統的開銷加大，是以在實際系統中往往使用該算法的近似算法。

條件：實作開銷很大，必須有硬體支援。（寄存器、棧、）

1. 最近最少使用置換算法（LFU）

   思路：選擇在最近時期使用最少的頁面為淘汰頁。

每當程序通路某頁面時，将該頁面對應寄存器的最高位 (Rn−1) 置 1，系統定期 (如 100ms) 将寄存器右移一位并将最高位補 0。在一段時間内，ΣRi 最小的頁面就是最近最少使用的頁面。

1. 最近未使用算法 (Not Recently Used，NRU，又稱Clock置換算法)

   思路：

   

   流程：

   

2. 比較

   

通路記憶體的有效時間EAT（了解）

第六章 輸入輸出系統

輸入輸出系統是作業系統對計算機系統中除 CPU 和記憶體之外的外部裝置進行管理、對資料傳輸進行控制的子產品，是作業系統資源管理中最複雜、最多樣化的部分。

I/O系統的功能、模型和接口

I/O 系統：用于實作資料輸入、輸出及資料存儲的系統。

I/O系統的任務和基本功能

1. 任務

• 對 I/O 裝置進行控制，完成使用者提出的輸入/輸出要求。
• 根據裝置請求的情況，按照一定的算法實作對 I/O 裝置的合理配置設定。
• 提高裝置使用率以及裝置與 CPU 的并行操作程度。

1. 基本功能

• 隐藏實體裝置的細節（向上提供抽象的指令）
• 實作與裝置的無關性（提高可移植性；即插即用）
• 提高處理機和 I/O 裝置的使用率（并行）
• 對 I/O 裝置進行控制（驅動程式）
• 確定對裝置的正确共享
• 其他功能（錯誤處理、緩沖管理等）

I/O軟體的層次結構

1. 使用者層I/O軟體
2. 裝置獨立性軟體
3. 裝置驅動程式
4. 中斷處理程式

   

I/O系統的上下接口

1. I/O系統接口（上層，提供服務）

• 塊裝置接口
• 流裝置接口
• 網絡通信接口

1. 軟體、硬體（SW/HW）接口（底層硬體）

I/O系統的分層

1. 中斷處理程式

   用于儲存被中斷程序的 CPU 環境，轉入相應的中斷處理程式進行處理，處理完後恢複現場，并傳回到被中斷的程序。

2. 裝置驅動程式

   用來具體實作系統對裝置發出的操作指令，驅動 I/O 裝置工作。

3. 裝置獨立性軟體

   使 I/O 軟體獨立于具體的實體裝置。

I/O裝置和裝置控制器

I/O裝置的類型

1. 按裝置的從屬關系分類

   系統裝置、 使用者裝置

2. 按使用特性

   儲存設備、I/O裝置

3. 按傳輸速率

   低速、中速、高速

4. 按使用方式/共享屬性

   獨享/獨占裝置、共享裝置、虛拟裝置

裝置控制器

1. 定義

   裝置控制器是處于 CPU 與 I/O 裝置之間的接口。裝置控制器是一個可編址裝置。當它僅控制一個裝置時，它隻有一個唯一的裝置位址，連接配接多個裝置時，則含有多個裝置位址。

2. 功能

• 接收和識别指令（控制寄存器）
• 實作資料交換（資料寄存器）
• 了解裝置狀态（狀态寄存器）
• 識别裝置位址（位址譯碼器）
• 資料緩沖（緩沖器）
• 差錯控制

1. 組成

   裝置控制器與處理機的接口（資料線、位址線、控制線）、裝置控制器與裝置的接口、I/O邏輯、寄存器

記憶體映像I/O

驅動程式把抽象的 I/O 指令通過驅動程式變成具體的指令和參數，裝入裝置控制器的寄存器中，由控制器執行。這一項工作可由兩種方法完成

1. 利用特定的I/O指令
2. 記憶體映像I/O

I/O通道

通道是一種特殊的專門執行 I/O 指令的處理機，與 CPU 共享記憶體，可以有自己的總線。通道包含通道指令（空操作，讀操作，寫操作，控制，轉移操作），并可執行用這些指令編寫的通道程式。

1. 引入目的

解脫 CPU 對 I/O 的組織、管理。

CPU 隻需發送 I/O 指令給通道，通道通過調用記憶體中的相應通道程式完成任務，僅當通道完成了規定的 I/O 任務後，才向 CPU 發中斷信号。

1. 通道與一般處理機的差異

   執行的指令主要局限于與 I/O 操作有關的指令、通道沒有自己的記憶體（與 CPU 共享記憶體）。

2. 通道類型

   位元組多路通道、數組選擇通道、數組多路通道

   

3. 瓶頸問題

   

   

中斷機構和中斷處理程式

中斷簡介

1. 中斷

   CPU 對外部某個事件作出的一種響應。某個事件發生時，系統中止現運作程式的執行，引出處理事件程式對相應事件進行處理，處理完畢後傳回斷點繼續執行。

2. 陷入

   由 CPU 内部事件引起的中斷。如非法指令、位址越界等。（内中斷）

3. 中斷處理程式

   對中斷事件進行處理的程式。如時鐘中斷處理、列印機完成中斷處理、列印機缺紙中斷處理等。

4. 中斷向量表

   表項為中斷處理程式的入口位址。當裝置發出中斷請求信号後，根據中斷号查中斷向量表，取得該裝置中斷處理程式的入口位址。

對多源中斷的處理方式

1. 屏蔽中斷
2. 嵌套中斷（優先級）

   

中斷處理程式

1. 處理過程

   

   

裝置驅動程式

裝置驅動程式簡介

裝置驅動程式通常又稱為裝置處理程式，它是 I/O 程序與裝置控制器之間的通信程式，它常以程序的形式存在。

一個裝置驅動程式通常由若幹子程式組成，每個子程式實施一種或一組實體操作。如讀、寫子程式、裝置初始化、關閉裝置、控制和配置裝置子程式等。通過這些子程式向上層提供了與硬體無關的接口。

每一類裝置都需要配置一種驅動程式。

裝置驅動程式功能

1. 将接收到的抽象要求轉換為具體要求
2. 檢查使用者 I/O 請求的合法性、I/O 裝置狀态、傳遞有關參數、設定裝置的工作方式。
3. 發出 I/O 指令。
4. 及時響應由控制器或通道發來的中斷請求，并進行相應處理。

裝置驅動程式特點

1. 裝置驅動程式是實作在與裝置無關軟體與裝置控制器之間的一個通信和轉換程式。把抽象的指令轉為具體的 I/O 操作。
2. 與 I/O 裝置的特性緊密相關。
3. 與 I/O 控制方式緊密相關（中斷驅動、DMA）。
4. 與硬體緊密相關，因而其中一部分程式必須用彙編語言編寫。很多驅動程式的基本部分已經固化在 ROM 中。
5. 驅動程式應允許可重入。

裝置處理方式

1. 作業系統為每一類裝置設定一個程序，專門執行這類裝置的 I/O 操作。
2. 在整個系統中設定一個程序，執行所有的 I/O 操作。
3. 不設定專門的裝置處理程序，而為各類裝置設定相應的裝置驅動程式，供使用者程序或系統程序調用。這類方式目前使用最多。

裝置驅動程式的處理過程

對 I/O 裝置的控制方式

1. 采用輪詢的可程式設計I/O方式（程式直接控制）
2. 采用中斷的可程式設計I/O方式
3. 直接存儲器通路方式（DMA）
4. I/O通信方式

   

   

與裝置無關的I/O軟體（了解思想）

引入

裝置獨立性的概念：為提高 OS 的可适應性和可擴充性，将應用程式獨立于具體使用的實體裝置。

驅動程式是一個與硬體緊密相關的軟體。為了實作裝置獨立性，必須再在驅動程式之上設定一層軟體，稱為裝置獨立性軟體（與裝置無關的軟體）。

與裝置無關的軟體是I/O系統的最高層軟體

裝置配置設定的資料結構

邏輯裝置表 LUT(Logical Unit Table)

每個表目中包含三項：邏輯裝置名、實體裝置名和裝置驅動程式的入口位址。

裝置配置設定時應考慮的因素

裝置的使用性質/固有屬性、裝置配置設定算法、裝置配置設定的安全性、

使用者層I/O軟體

庫函數10、假脫機技術（可以參考列印店裡面多電腦共享列印機）

緩沖區管理

為了緩解解 CPU 與 I/O 傳輸速度不比對的沖突。有兩種實作方法（硬體緩沖區、軟緩沖區又稱記憶體緩沖區）

磁盤存儲器的性能和排程

提高磁盤I/O速度的主要途徑

1. 選擇性能好的磁盤
2. 采用好的磁盤排程算法
3. 設定磁盤高速緩存
4. 其他方法（提前讀、延遲寫、虛拟盤）
5. 采用高度可靠、快速的磁盤系統：獨立磁盤備援陣列

磁盤結構

磁盤的 0 磁道在最外圈，記錄了分區表，主引導記錄等一些重要資訊。

資料的組織

1. 磁盤實體塊的位址（磁頭号、柱面号、扇區号）

2. 存儲容量

   存儲容量＝磁頭（盤面）數 × 磁道（柱面）數 × 每道扇區數 × 每扇區位元組數

   

磁盤通路時間

磁盤排程算法

1. 先來先服務FCFS
2. 最短尋道時間優先SSTF（磁臂黏着、磁道歧視）
3. 掃描 (SCAN)/電梯 (LOOK) 算法（不掃描到頭！）
4. 循環掃描 (CSCAN) 算法

5. N-STEP-SCAN 排程算法和 FSCAN 排程算法

   N-STEP-SCAN 排程算法将磁盤請求隊列分成若幹個長度為 N 的子隊列，磁盤排程将按 FCFS 算法依次處理這些子隊列，而每一子隊列按SCAN 算法處理。

第七章 檔案管理

檔案和檔案系統

檔案

1. 定義

   檔案是由建立者所定義的、具有符号名的相關資訊集合。

   檔案是檔案系統中最大的一個資料機關，它描述了一個對象集。

檔案是一個抽象機制，它提供了一種把資訊儲存在存儲媒體上，而且便于以後存取的方法，使用者不必關心實作細節。

檔案必須有檔案名，所有檔案的資訊都儲存在目錄中。

檔案可分為有結構檔案和無結構檔案兩種。有結構檔案是由若幹個相關記錄組成，無結構檔案被看成一個字元流。

1. 表示範圍

   源程式、二進制代碼、文本文檔、資料、表格、聲音、圖像和視訊等。

2. 檔案屬性

   名字、辨別符、類型、位置、大小、保護、時間日期和使用者辨別等。

檔案類型

檔案系統

1. 定義

   檔案系統是指 OS 中負責操縱和管理檔案的軟體集合。

   檔案系統 = 檔案管理程式 + 它所管理的全部檔案（檔案和目錄的集合）。

2. 檔案系統管理的對象

   檔案、目錄、實體儲存空間

3. 檔案系統的接口

   指令接口、程式接口

4. 對檔案的操作（系統調用）

   

   

檔案的邏輯結構

引入

1. 檔案的邏輯結構（檔案組織）

   從使用者觀點出發所觀察到的檔案組織形式，是使用者可以直接處理的資料及其結構，它獨立于實體特性。

   順序檔案、索引檔案、索引順序檔案

2. 檔案的實體結構（檔案的存儲結構）

   是指檔案在外存上的存儲組織形式，使用者是看不見的，檔案的實體結構不但與存儲媒體的存儲性能有關，而且還與所采取的外存配置設定方式有關。

   順序檔案、連結檔案、索引檔案

檔案邏輯結構的類型

檔案目錄

引入

用于檢索檔案的目錄稱為檔案目錄，它是由目錄項所構成的有序序列。

對檔案目錄的管理要求

1. 實作“按名存取”
2. 提高對目錄的檢索速度
3. 檔案共享（多個使用者共享一個檔案，隻需要在外存保留一個檔案）
4. 允許檔案重名（不同檔案使用同一個名字）

檔案控制塊FCB

從檔案管理角度看，檔案由檔案控制塊 FCB 和檔案體（檔案本身）兩部分組成。

檔案控制塊是作業系統為管理檔案而設定的資料結構，存放了檔案的有關說明資訊，是檔案存在的标志。

1. 組成

   

2. 檔案目錄、目錄項、目錄檔案

   

索引結點（平均啟動磁盤的次數）

樹型結構、目錄建立這些不再總結

檔案共享

檔案共享的方法

各方法不再介紹

檔案保護

影響檔案安全性的主要因素

人為、系統、自然

確定檔案系統安全性的措施

1. 存取控制機制 人為因素
2. 系統容錯技術 系統因素
3. 後備系統 系統、自然因素

通路控制技術

1. 保護域

   保護域是程序對一組對象的通路權的集合。程序僅在保護域内執行操作，保護域規定了程序所能通路的對象和能執行的操作。

2. 通路權

   為了對系統中的對象（包括硬體對象和軟體對象）加以保護，由系統來控制程序對對象的通路。我們把一個程序能對某對象 (Object) 執行操作的權力稱為通路權(AccessRight)。每個通路權可以用一個有序對（對象名，權集）來表示。

3. 切換權

   程序在保護域之間切換的權力，稱為切換權 (switch)。程序擁有切換權時，可把程序從一個保護域切換到另一保護域，以實作程序和域之間的動态聯系。

4. 拷貝權

   拷貝權指程序在某個域中對某對象擁有的通路權可通過拷貝将通路權擴充到同一列（即同一對象）的其它域中。

   限制拷貝：拷貝後拷貝權*不能擴散。

5. 所有權

   除了可以利用拷貝權把通路權進行有控制的擴散以外，系統還需要能删除某些控制權，我們可以利用所有權實作這些操作。

6. 控制權

   拷貝權和所有權都是用于改變矩陣内同一列的通路權。控制權則可用于改變矩陣内同一行 (域)中的通路權，即用于改變在某個域中運作程序對不同對象的通路權

通路控制表和通路權限表

通路控制表：把通路矩陣按列（對象）劃分，為每一列建立一張通路控制表 ACL。通路控制表可用于定義整個系統的預設的通路權集。

通路權限表：把通路矩陣按行（域）劃分，每行形成一張通路權限表。

第八章 磁盤存儲器的管理

外存的組織方式

連續組織方式（順序配置設定）

連續組織方式為每一個檔案配置設定一片連續的磁盤塊。例如，第一個盤塊的位址為 b，則第二個盤塊的位址為 b+1，第三個盤塊的位址為 b+2。通常它們都位于一條磁道上，在進行讀/寫時不必移動磁頭，僅當通路到磁道的最後一個盤塊後才需要移到下一條磁道。這樣所形成的檔案結構稱為順序檔案結構，此時的實體檔案稱為順序檔案。

連結組織方式

離散配置設定

1. 隐式連結
2. 顯式連結

FAT檔案系統

FAT：File Allocation Table 檔案配置設定表。

FAT 檔案系統支援把一個實體磁盤分成 4 個邏輯磁盤（卷、分區），一個卷也可以由多個實體磁盤組成（RAID）。

NTFS 檔案系統

NTFS 檔案系統：New Technology File System 新技術檔案系統，是目前的主流檔案系統。

索引組織方式

1. 單級索引配置設定
2. 多級索引配置設定
3. 混合索引配置設定

檔案存儲空間的管理

存儲空間的管理方法

1. 空閑表法和空閑鍊法
2. 位示圖法
3. 成組連結法

其餘不再總結

簡述作業系統的四個基本特征

1. 并發性

在宏觀上，多個程式同時運作

在微觀上，多道處理機系統中，多個程式同時運作，單道處理機系統中，程式交替運作。

1. 共享性

指系統中的資源可供記憶體中多個并發執行的程序共同使用。（互斥、同時）

1. 虛拟性

通過某種技術将一個實體實體變為若幹邏輯上對應物。時空複用、空分複用

1. 異步性

程序以不可預知的速度向前推進，此即為程式的異步性。

微核心OS的優點和缺點是什麼？

1. 優點

提高了系統的可擴充性

提高了系統的可靠性

可移植性好

适用于分布式系統

融入了面向對象技術

1. 缺點

運作效率低：消息傳遞比直接調用效率要低

請描述多級回報隊列排程算法的排程機制

産生死鎖的四個必要條件是什麼？

1. 互斥條件
2. 請求和保持條件
3. 不可剝奪條件
4. 環路等待條件

試述快表技術是如何實作的

又稱為聯想寄存器，目的是提高位址變換速度；快表是一種特殊的高速緩沖存儲器（Cache），内容是頁表中的一部分或全部内容。CPU 産生邏輯位址的頁号，首先在快表中尋找，若命中就找出其對應的實體塊；若未命中，再到頁表中找其對應的實體塊，并将之複制到快表。若快表中内容滿，則按某種算法淘汰某些頁。

分頁存儲管理和分段存儲管理有何差別

頁和段都有存儲保護機制。但存取權限不同：段有讀、寫和執行三種權限；而頁隻有讀和寫兩種權限。

裝置管理的目标和功能是什麼

裝置管理的目标：1、向使用者提供外部裝置的友善、統一的接口，按照使用者的要求和裝置的類型，控制裝置工作，完成使用者的輸入輸入請求。2、充分利用中斷技術、通道技術和緩沖技術，提高CPU與裝置、裝置與裝置之間的并行工作能力，以充分利用裝置資源，提高外部裝置的使用效率。3、裝置管理就是要保證在多道程式環境下，當多個程序競争使用裝置時，按照一定的政策配置設定和管理裝置，以使系統能有條不紊地工作。

裝置管理的功能：1、裝置配置設定和回收；2、管理輸入輸入緩沖區；3、裝置驅動，實作實體I/O操作；4、外部裝置中斷處理；5、虛拟裝置及其實作。

檔案的實體結構有哪幾種

1. 順序檔案
2. 連結檔案

3. 索引檔案

   計算題複習：https://blog.csdn.net/qq_42759593/article/details/111871761

1. 所謂任務（Task）是指，計算機在某個資源集合上所做的一次相對獨立的計算過程。 ↩︎
2. 所謂模式，簡單地說，就是程式在運作過程中使用的、由硬體體系結構提供的CPU特權模式。 ↩︎
3. 由若幹條指令組成的，用于完成一定功能的一個過程。是一個不可分割的基本機關，執行過程中不許中斷。 ↩︎
4. 資源分類 可重用資源和消耗性資源、可搶占資源和不可搶占資源 ↩︎
5. 安全狀态指在某一時刻，系統能按某種程序順序 (p1,p2,…，pn) 來為每個程序 Pi 配置設定其資源，直到滿足每個程序對資源的最大需求，使每個程序都可順利地完成，則稱此時的系統狀态為安全狀态，稱序列 (p1,p2,…，pn) 為安全序列。若某一時刻系統中不存在這樣一個安全序列，則稱此時的系統狀态為不安全狀态。 ↩︎
6. 重定位：由于一個作業裝入到與其位址空間不一緻的存儲空間所引起的，需對其有關位址部分進行調整的過程就稱為重定位（實質是一個位址變換過程/位址映射過程）。分為靜态、動态兩種方式；靜：軟體實作，動：軟硬（寄存器支援）結合。 ↩︎
7. 内零頭是指配置設定給作業的存儲空間中未被利用的部分。 ↩︎
8. 外零頭是指系統中無法利用的小存儲塊。 ↩︎

9. 在請求分頁系統中，當通路的頁不在記憶體，便産生一個缺頁中斷。缺頁中斷是在指令執行期間産生和進行中斷信号（要通路的指令或資料不在記憶體）。一條指令在執行期間，可能産生多次缺頁中斷。

   軟體：請求調頁功能和頁置換功能的軟體。 ↩︎

10. 系統調用（System Call）是作業系統核心提供的一組功能強大的函數，在核心态下運作。系統調用是使用者程式取得 OS 服務的唯一途徑。庫函數是系統調用的一種封裝和擴充，工作在使用者态。 ↩︎