Elsa CHOI

Elsa CHOI

02326-操作系統

6 minute read

Published:

簡介

第一章 操作系統概論

  • 操作系統是一種複雜的系統軟件，是不同程序代碼、數據結構、數據初始化文件的集合，可執行

  • 操作系統

  • window:
    • 內核、硬件抽象層、執行體、系統進程和系統線程
  • Unix
    • 內核、硬件、系統調用接口和UNIX命令和庫
  • Linux
    • 系統資源、內核、Shell、用戶應用程序和文件系統
  • Android
    • Android應用程序
    • Android應用框架
    • C,C++本地庫和Android運行時環境
    • Lunix內核

操作系統分類

  • 批處理操作系統:
    • 優點:成批處理、資源利用率高和作業吞吐率高
    • 缺點：不能直接與計算機無交互，不適合調試程序
  • 分時系統
    • 多路性、交互性、獨佔性和及時性
    • 硬實時系統和軟實時系統
  • 實時操作系統
    • 實時時鐘管理，高可靠性和過載防護
  • 嵌入式操作系統
    • 高可靠性、實時性、佔有資源少、智能化能源管理、易於連接和低成本。
  • 網絡操作系統
    • 為計算機網絡的操作系統
    • 集中式和分佈式
  • 分布式操作系統
    • 大量計算機通過網絡連結在一起，可以獲得極高的運算能力和廣泛的數據分享
    • 特點:
      • 同一個操作系統
      • 實現資源的深度共享
      • 透明性
      • 自治性
      • 助記:(同身共投資)
    • 優點：
      • 較低成本獲得較高的運算性能
      • 可靠性
      • 機群是分布式系統的一種

操作系統設計

  • 設計複雜度高
  • 正確性難以保證

  • 研制周期長

  • 操作系統設計過程
    • 功能設計
    • 算法設計
    • 結構設計
    • 助記(能結算)
  • 操作系統的設計目標
    • 可靠性
    • 高效性
    • 易維護性
    • 可移植性
    • 安全性
    • 簡明性
    • 易記(靠高位已安檢)

操作系統的結構

  • 整體式結構
    • 優點:
      • 結構緊密
      • 接口簡單直接
      • 系統效率高
    • 缺點:
      • 獨立性差,系統結構不清晰
      • 數據基本上為全程量處理,相當複雜的事
      • 可適應性比較差
  • 層次式結構
    • 優點:
      • 結構清晰
      • 不構成循環
      • 操作增加一層不影響其他層次
      • 易於調試、易於修改、擴充、維護和保證正確性
  • 微內核結構:
    • 將操作系統分成用於實現操作系統最基本功能的內核和提供各種服務的服務進程兩個部分。
    • 優點:可靠、靈活和適宜分布式處理的計算環境
    • 缺點:效率考慮, 用戶只能通過微內核𡧟互通信, 不能提供好的效率
  • 助記: 曾為整體

第二章 操作系統運行環境

處理器

  • 處理器一般由運算器、控制器、一系列的寄存器和高速緩存
  • 運算器實現指令的算術和邏輯
  • 寄存器的類型
    • 程序計數器(PC): 取出的指令地址
    • 指令寄存器(IR): 包含了最近取出的指令
    • 程序狀態字(PSW): 記錄了處理器的運模式信息
      • CPU的工作狀態代碼:指明當前處理器的工作狀態是管態還是目態
      • 條件碼: 反映指令執行後的結果特徵
      • 中斷屏蔽:指出是否允許中斷
      • 助記: C跳斷
  • 指令執行的基本過程（單選、填空）
    • 取指令
    • 指令寄存器
    • 程序計數器+1
  • 指令執行的基本過程（單選）
    • 訪問存儲器指令:它們負責處理器和存儲器之間的數據傳送
    • I/O指令:它們負責處理器和 I/O模塊之間的數據傳送和命令發送；
    • 算術邏輯指令:有時又稱為數據處理指令，用以執行有關數據的算術和邏輯操作
    • 控制轉移指令:這種指令可以指定一個新的指令的執行起點
    • 處理器控制指令:這種指令用於修改處理器狀態，改變處理器工作方式等。
  • 特權指令: 只能由操作系統使用
  • 非特權指令: 操作系統和普通用戶都能使用
  • 管態: 操作系統管理程序運行的狀態, 具有較高的特權級別, 又稱內核態、特權態
  • 目態: 用戶程序運行時的狀態, 具有較低的特權級別, 又稱為用戶態和普通態
  • 目態到管態: 通過中斷,程序狀態字標志為管態
  • 管態到目態: 修改程序狀態字(PSW)實現
  • 系統啟動時，處理器的初始狀態為管態

存儲系統

  • 中央處理器能直接訪問的唯一的存儲空間是內存儲器（主存）。
  • 存儲器的類型
    • 讀寫型的存儲器，這種類型的存儲器常被稱為隨機訪問存儲器(RAM)
    • 只讀型的存儲器(ROM)
  • 計算機存儲系統的設計主要考慮三個問題:
    • 容量
    • 速度
    • 成本
  • 時鐘部件
    • 在多道程序運行的環境中，時鐘可以為系統發現一個陷入死循環（由編程錯誤引起）的作業，從而防止機時的浪費
    • 在分時系統中，用時鐘間隔來實現各個作業按時間片輪轉運行。
    • 在實時系統中，按要求的時間間隔輸出正確的時間信號給相關的實時控制設備
    • 定時喚醒要求按照事先給定的時間執行的各個外部事件
    • 記錄用戶使用各種設備的時間和記錄某外部事件發生的時間間隔

中斷機制

  • 中斷的概念（簡答）
    • 所謂中斷是指處理器對系統中或系統外發生的異步事件的響應。
    • 中斷是所有要打斷處理器的正常工作次序，並要求其去處理某一事件的一種常用手段。
graph TB
 id1[中斷源]
 id2[CPU]
 id3[正在執行的程序]
 id4[中斷處程序]
 id1--中斷請求-->id2
 id2-->id3
 id2--中斷響應-->id4 
 id4--中斷返回-->id3
  • 一個計算機系統提供的中斷源的有序集合一般被稱為中斷字
  • Intel的x86微處理器能處理256種不同的中斷.
  • 能充分發揮處理器的使用效率
  • 提高系統的實時能力

  • 中斷是由外部事件引發的，而異常則是由正在執行的指令引發的，

  • 硬件中斷裝置和中斷處理程序
  • 中斷是由外部事件引發的
    • 時鐘中斷
    • 輸入輸出中斷
    • 控制台中斷
    • 硬件固障中斷
  • 異常是由正在執行的指令引發的
    • 程序性中斷:
      • 多數是程指令出錯、指令越權或者指令尋址越界而引發的系統保護。
    • 訪管指令異常
      • 目的：要求操作系統提供系統服務

中斷系統

  • 中斷系統是現代計算機系統的核心機制之一，它不是單純的硬件或者軟件的概念，而是硬件和軟件相互配合、相互滲透而使得計算機系統得以充分發揮能力的計算模式。
  • 組成：（填空、簡答）
    • 中斷系統的硬件中斷裝置和軟件中斷處理程序。
  • 硬件中斷裝置負責捕獲中斷源發出的中斷請求，並以一定的方式響應中斷源
  • 然後將處理器的控制權移交給特定的中斷處理程序。

  • 中斷處理程序則針對對中斷事件的性質而執行相應的一系列操作。

  • 中斷請求和接收:觸發器的值為1時, 表示收到中斷信號
  • 中斷請求的接收
    • 它們是通過在計算機硬件的中斷邏輯線路和中斷寄存器實現的。
  • 中斷響應:
    • 保存中斷點的程序執行上文下文環境: 程序狀態字PSW, 程序計數器PC的下一條指令位置和一些寄存器的值
    • 查詢中斷向量表和中斷處理程序的入口地址
  • 中斷處理
    • 結束後處理器檢測到中處返回指令, 上下文環境從系統堆棧中恢復,處理器由管態恢復到目態
    • 其中包括檢查I/O相關的狀態信息，操縱I/O設備或者在設備和內存之間傳送數據等。
  • 在中斷處理程序結束工作之後（簡單了解）
    • 處理器會檢測到一條中斷返回指令，
    • 處理器會把原先被中斷的程序的上下文環境從系統堆棧中恢復
    • 處理器狀態也從管態恢復成被中斷時的目態。
    • 整個中斷處理結束
    • 處理器開始一個新的指令周期，繼續執行原來被中斷的程序
  • 中斷請求響應的工作過程是：（簡答）
    • 處理器接收中斷信號；
    • 保護現場，將中斷斷點的程序狀態字PSW和程序計數器PC值存入系統堆棧：
    • 分析中斷向量，取得中斷處理程序的入口地址；
    • 將處理器的PC值置為中斷處理程序的入口地址；
    • 調用中斷處理程序。
  • 幾種典型中斷的處理
    • I/O中斷:I/O中斷通常可分成兩大類：I/O操作正常結束以及I/O異常。
    • 時鐘中斷（單選、填空）:維護軟件時鐘,處理器調度，控制系統定時任務，實時處理
    • 硬件故障中斷（單選、填空）:硬件故障一般是由硬件的問題引起的，排除此類故障通常需要人工的干預，例如復位硬件或者更換設備等。需要做的工作是保存現場，使用一定的手段警告管理員並提供一些輔助的診斷信息。
    • 程序性中斷（簡單了解）:
      • 第一類為程序性中斷，只能由操作系統完成。
      • 第二類為程序性中斷，可以由程序自己完成。
    • 系統服務請求（自願性中斷）（單選）:系統服務請求一般由處理器提供的專用指令（又稱訪管格令）來激發
    • 助記：熟食應城西

中斷優先級、中斷屏蔽與中斷嵌套

  • 現代的微處理器都提供有多級中斷系統，在多級中斷系統中，硬件決定了各個中斷的優先級別。
  • 作用：
    • 對各類中斷信號依據其緊急程度和重要性劃分級別。
    • 解決如果有重要程度相當的多個中斷信號同時到達時，如何選擇首個被處理的中斷信號的問題
  • 在同一中斷級中的多個設備接口中同時都有中斷請求時，一般有兩種辦法可以采用：固定的優先數,輪轉法
  • 中斷屏蔽
    • PWS中的中斷屏蔽位決定，這些屏蔽位標識了被屏蔽的中斷類或者中斷。
    • 機器故障中斷不可屏蔽，上如內存奇偶校驗錯，以及掉電等使得機器無法繼續操作一類的故障。
  • 多級中斷
    • 對中斷信號依據其緊程度和重要性劃分級別
    • 掉電有非常高的級別
    • PSW有中斷屏蔽字, 主機是否允許響應或禁止某些中斷
    • 中斷嵌套

系統調用

  • 用戶在程序中調用操作系統所提供的一些子功能,
  • 系統轉入特權方式(管態)
  • 系統調用和函數調用分別
    • 運行在不同的系統狀態
    • 狀態的轉換
    • 返回問題
    • 嵌套調用
  • 系統調用分類
    • 進程控制類系統調用
    • 文件操作類
    • 進程通訊
    • 設備管理
    • 信息維護
    • 助記：通信需要文件設備進程控制
  • 系統調用的處理過程
    • p.72
    • 操作系統內必須有事先編制好的、實現這些功能的子程序或過程
    • 硬件中斷理的中斷處理機構
    • 陷入(TRAP)或訪管指令
    • 每個系統調用都對應一個事先給定的功能號
    • 系統調用功能的子程序編造入口地址表
    • 二種
      • 陷入指令自帶參數
      • 有關寄存器來傳遞參數(UNIX)
      • 內存開辟堆棧區傳遞參數

第三章 進程與線程

程序的順序執行

  • 我們把一個具有獨立功能的程序獨佔處理器直到得到最終結果的過程稱為程序的順序執行。
  • 程序的順序執行的特點
    • 順序性
    • 封閉性:計算結果只取決於程序自身
    • 確定性:與運行速度無
    • 可再現性:與不同時間執行無關

並發與並行

  • 並行執行:兩個或以上程在計算機系統中，同時處於已開始執行且尚未結束的狀態。
  • 並行:微觀與宏觀都是同時
  • 並發:微觀是順序執行, 宏觀是同時
  • 程序的並發執行的特征
    • 在執行期間並發程序相互制約
    • 程序與計算不再一一對應
    • 並發程序的執行結果不可再現
    • 程序的並行執行與程序的並發執行

多道程序

  • 在現代計算機系統中，為了提高系統中各種資源的利用效率，縮短程序執行的周轉時間，廣泛采用了多道程序技術，使多種硬件資源能並行工作。
  • P.80
  • 吞吐量:單位時間內系統所處理的進程的道數
  • 多道程序設計環境的特徵
    • 獨立性:與其他程序多無關
    • 隨機性:執行開始時間和數據輸入時間都是隨機
    • 資源共享性
  • 多道程序的缺點
    • 時間延長:對實時要求的程序不合適
    • 系統效率提高有一定限度

進程

  • P.81
  • 進程是具有一定獨立功能的程序在某個數據集合上的一次運行活動,進程:系統進行資源分配和調度的一個獨立單位
  • 從操作系統角度來看，可將進程分為系統進程和用戶進程兩類。
  • 進程與程序的聯系和區別(問答)
    • 聯系：
      • 程序是構成進程的組成部分之一，一個進程的運行目標是執行它所對應的程序，如果沒有程序，進程就失去了其存在的意義。從靜態的角度看，進程是由程序、數據和進程控制塊（PCB）三部分組成的。（進程-程序+數據+進程控制塊（ PCB））
    • 區別：
      • 程序是靜態的，而進程是動態的。
      • 進程是程序的一個執行過程。程序的存在是永久的（這裡不討論人為刪除程序等行為）。而進程是為了程序的一次執行行暫時存在的。進程有生命周期，有誕生，亦有消亡
  • 進程的特徵:
    • 並發性
    • 動態性
    • 獨立性
    • 交往性
    • 異步性
    • 結構性

可再入程序

  • 可再入程序:被多個用戶同時調用的程序,與數據區分離

進程的隊列

  • 三狀態進程的隊列
    • 就緒
    • 等待，也稱阻塞或封鎖
    • 運行
    graph TB
id1[運行狀態]
id2[就緒狀態]
id3[等待狀態]

id1--等待某個事件發生-->id3
id3--等待的事件已發生-->id2
id2--進程被調度程序選中-->id1
id1--時間片用完-->id2

  • 五狀態進程模型中的主要狀態轉換：

    graph LR
id1[創建狀態]
id2[就緒狀態]
id3[運行狀態]
id4[阻塞狀態]
id5[結束狀態]

id1--提交-->id2
id2--調度-->id3
id3--超時,被搶佔-->id2
id3--等待某個事件發生-->id4
id4--等待的事件已發生-->id2
id4--釋放-->id5
  • 七狀態
  • 掛起（Suspend）：把一個進程人內存轉到外存；
  • 可能有以下幾種情況。
    • 阻塞到阻塞掛起
    • 就緒到就緒掛起
    • 運行到就緒掛起
  • 激活（Activate）：把一個進程從外存轉到內存
  • 可能有以下幾種情況。
    • 就緒掛起到就緒
    • 阻塞掛起到阻基

進程控制塊(PCB)

  • PCB的內容
    • 進程控制塊的內容可以分成調度信息和現場信息兩大部分。
    • 調度信息（進程名、進程號、地址空間信息、優先級、當前狀態、資源清單、“家族”關系、消息隊列指針、進程隊列指針和當前打開文件）等。
  • PCB 組織
    • 線性
    • 索引
    • 鏈接:進程隊列可以用進程控制塊的鏈接來形成，常用鏈接的方式有單向鏈接和雙向鏈接

進程控制

  • 原語
    • 是由若干條指令所組成的一個指令序列，用來實現某個特定的操作功能。
    • 原語是操作系統核心由一組程序模塊所組成的、完成操作系統中基本功能）的一個組成部分
    • 原語必須在管態下執行，並且常駐內存。

    • 原語和系統調用都可以衱進程所調用，兩者的差別在於原語有不可中斷性，己是通過在其執行過程中關閉中斷實現的，而且原語往往是被系統進程所調用。

    • P.90

    • 創建原語

      graph LR
A[申請PCB區域]-->B[有關信息填入PCB]
B-->C[設進程狀態為就緒]
C-->D[把進程放進就緒隊列]

    • 撤銷原語

      graph LR
A[找撤銷進程的PCB]-->B[進程所在隊列消去]
B-->C[撤銷它的子進程]
C-->D[釋放佔用的資源]
D-->E[消去PCB]

    • 阻塞原語

      graph LR
A[中斷處理器運作]-->B[保存現場信息去PCB]
B-->C[進程狀態設為等待]
C-->D[將它放進等待隊列]

    • 喚醒原語

      graph LR
A[將PCB狀態設為就緒]-->B[在等待隊列消去]
B-->C[放進就緒隊列]
  • UNIX操作系統的進程創建操作fork(簡單了解，可能出簡答題)
    • 為子進程分配一個空閒的proc結構（即進程描述符）。
    • 賦予子進程唯一的標識PID。
    • 以一次一頁的方式復制父進程用戶地址空間。
    • 獲得子進程繼承的共享資源的指針，如打開的文件和當前工作目錄等。
    • 子進程就緒，加入調度隊列
    • 對子進程返回標識符0；向父進程返回子進程的PID。
  • fork函數執行的特點是：只被調用一次，卻會返回兩次
  • exec函數：為子進程運行不同於父進程的代碼提供了一條途徑
  • 信號(Signal）函數是UNIX處理異步事件的經英方法。信號可以說是進程控制的一部分。

線程

  • 可以調度和分派的基本單位
  • 用戶級線程:在用戶空間管理線程,每個線程有其專用的線程表
  • 內核級線程:沒有線程表,內核中有用來紀錄系統中所有線程的線程表,保存了每個線程寄存器、狀態和其他信息
  • 屬性
    • P.95
    • 唯一標識符和一張線程描述表
    • 不同線程可執行相同程序
    • 同一進程中的線程共享進程的內存地址空間
    • 多個線程可以井發
    • 創建後開始它的生命周期
  • 設立線程好處
    • 花費少
    • 切換線程速度快
    • 同一進程的不同線程通訊方便
    • 獨立執行:增強井行能力

線程實現機制

  • 第一種實現方式是用戶級線程 User-Level Threads ），這種線程不依賴於內核。
    • 用戶級線程只存在於用戶態中，對它的創建、撤銷和切換不會通過系統調用來實現，因而這種線程與內核無關。相應地，內核也並不知道有用戶級線程的存在，八內核角度考慮，就是按正常的方式管理，即單線程進程。
    • 優點：用戶級線程包可以在不支持線程的操作系統上實現。 函數庫實現線程）
  • 內核級線程
    • 第二種實現方式是內核級線程（Kernel-Supported Threads），這種線程依賴於內核。
    • 內核級線程依賴於內核，即無論是在用戶進程中的線程，還是系統進程中的線程，它們的創建、撤銷和切換都由內核實現。
    • 在內核中保留了一個線程控制塊，系統根據該控制塊而感知該線程的存在並對線程進行控制。
  • 用戶級線程和內核級線程比較
    • 用戶級線程的切換通常是發生在一個應用進程的諸線程之間
    • 系統調用
      • 用戶進程調用系統調用，用戶狀態一>核心狀態，用戶進程封鎖，返回系統調用時喚醒
      • 內核級線程：調度以線程為單位，只封鎖該線程，調度其他線程執行
    • 線程執行時間
      • 用戶級線程的系統，調度是以進程為單位進行的。
      • 核心級線程，其調度是以線程為單位進行的，
  • Pthread線程包
    • UNIX系統
    • pthread線程=1標只符+n寄存器+n性

內核

  • 系統運行的各種基本操作和基礎功能的一組程序模塊集中安排, 形成操作系統的核心
  • 內核是線程和進程賴以活動的基礎
  • 功能
    • 中斷處理程序
    • 進程互斥和同步
    • 進程調度、控制和通信
    • 存儲管理基本操作
    • 時鐘管理

進程調度

  • 進程調度即處理器調度。
  • 進程調度的任務是控制、協調進程對處理器的競爭，按照一定的調度算法，使某一就緒進程獲得CPu的控制權，轉換成運行狀態。
  • 交互式用戶環境中，搶佔是心須的。
  • 實時系統中，非搶佔式
  • 響應比=（等待+運行）/運行
  • 最短剩余时间优先算法:调度程序总是选择具刺余运行时间最短的那个进程运

第四章 進程同步與互斥

  • P.117
  • 有空讓進
  • 無空等待
  • 有限等待
  • 讓權等待

PV操作

P(S)
{
  S=S-1
}

V(S)
{
  S=S+1
}
  • 完成了P(S)後$S<0$,進程設為等待狀態
  • 完成了V(S)後$S\geq 0$,進程設為就緒狀態
  • 當$S>0$,s值的大小表示某類可用資源的數量，表示有s個數量的資源可分配
  • 當$S<0$,$\vert S\vert$表示等待隊列中等待隊列中進程的數目
  • 每一次P操作，就分配一個資源
  • 每一次V操作，就進程釋放一個資源
  • 一些例子，看書：P.120

管程

  • 因p,v有以下缺點，所以有管程
    • 程序易讀性差
    • 不利於修改和維護，局部性差
    • 正確性難以保證
  • 管程由管程名稱、共享數據的說明、對數據進行操作的一組過程和對共享數據賦初值
  • 管程三個主要特性
    • 模塊化
    • 抽象數據類型
    • 信息隱藏
  • 任一時刻管程只能有一個活躍進程
  • 解決緩沖區阻塞
    • 引入條件變量
    • wait
    • signal

進程通訊

  • 共享內存
  • 消息機制
  • 管道通信
    • 信箱說明：可存信件數，已有信件數
    • 信箱體
  • 所謂管道， 就是連接兩個進程之間的一個打開共享文件
  • 管道通訊的同步和互斥都由操作系統自動進行，對用戶是透明
  • 傳送數據量大的優點，但通信速度較慢

第五章 死鎖

  • 死鎖產生的原因
    • 競爭資源
    • 多道程序運行時, 進程推進順序不合理
  • 死鎖產生的必要條件
    • 互斥條件
    • 不可剝奪條件:破壞-阻塞前釋放資源
    • 請求和保持條件:破壞-每個進程執行申請全部資源
    • 循環等待條件:破壞-進程沒有佔用資源時才允許它去申請資源
  • 解決死鎖
    • P.140
    • 預防死鎖:嚴格防止死鎖產生的必要條件
    • 避免死鎖:資源分配時,采用某種方法防止系統進入不安全狀態,銀行家算法
    • 檢測與解除死鎖
    • 忽略死鎖

死鎖的檢測與解除

  • 檢測死鎖的特質是確定是否存在循環等待條件
  • 檢測算法
    • 每個進程和資源指定唯一編號
    • 設置一張資源分配狀態表
    • 進程等待分配表
  • 解除有兩大類
    • 剝奪資源
      • 使用掛起/激活機制掛起一些進程, 剝奪他們佔有的資源給死鎖進程
    • 撤銷進程
      • 撤銷死銷進程, 將它們佔有的資源分配給另一些死鎖進程

資源分配圖

  • 死鎖定理
    • 沒有環路, 表示沒有死鎖
    • 有環路, 可能存在死鎖
    • 環路中資源類中只包括一個資源, 則死鎖

第六章 存儲管理

  • 由快到慢
    • 寄存器
    • 高速緩存
    • 內存
    • 本地外存
    • 遠程存儲
  • 內存分配方式
    • 靜態:目標模塊裝入內存時確定井分配的，並在程序運行中不允許再申請或移動,即分配工作在程運行一次性完成
    • 動態:目標模塊裝入內存時確定井分配的，並在程序運行中允許再申請空間或移動,即分配工作可以在程序運行前及運行時過程中逐步完成
  • 存儲共享:提高內存利用率。包括代碼共享和數據共享, 代碼共享必須是純代碼
  • 存儲保護
    • 地址越界保護
    • 權限保護

  • 內存擴充容量

  • 地址轉換
    • 存儲器以字節為單位,每個字節都有地址一一對應
    • 以絕對地址對應的內存空間稱為物理地址空間
    • 用戶可以存儲地址為”0”的內存空間,稱為邏輯地址空間
  • 地址重定位:內存裝入程序時,程序中的指令和數據地址轉換成絕對地址
    • 靜態重定位:程序開始執行前集中完成轉換，在程序執行時無須進行地址轉換工作
    • 動態重定位:內存在裝入程序時,不進行地址轉換,執行每一條指令時,才轉換
      • 基址寄存器和地址轉換線路

分區管理

  • 固定分區:一旦劃分了,系統運行期間不再重新劃分
  • 可變分區:裝入程序時劃分內存分區,使好等於需求量
    • 實現需要基址寄存器和限長寄存器
  • 緊縮技術:不足連續整塊分配要求，但空閒的碎塊加起來可以,采用緊縮技術
    • 增加系統的開銷:修改內存分配表和進程控制塊
    • 移動是有條件的:某個進程與外部交換信息,就不能移動
  • 可變分區分配策略
    • 最優適應算法:順序查找,第一個合適的內存長度就分配
    • 最壞適應算法:查找合適的內存長度並且最少空閒區就分配
  • 可變分區的優點
    • 分區存儲算法簡單,實現起來相對容易,內存額外開銷少,存儲保護措施簡單
  • 缺點
    • 內存使用仍不充份,碎片問題嚴重
    • 不能提供虛存或擴充
    • 要求程序一次全部裝入內存

覆蓋與交換技術

  • 覆蓋
    • 覆蓋是由一個程序的若干程序段,共幾個程序的某些部分共享某一存儲空間
    • 是由編譯程序支持
  • 交換
    • 進程從內存移到磁盤,再移回內存作為交換
    • 多用於分時系統
    • 打破了一個程序一旦進入內存便一直運行到結束的限制
    • 對用戶是透明的

虛擬頁式存儲管理

  • 硬件支持
    • 系統有容量足夠大的外存
    • 系統有一定容量的內存
    • 虛-實地址映射機制
    • 支持頁式管理部件:存儲管理部件
    • 邏輯地址:虛擬頁號和頁內地址
  • 位示圖
    • 一列有32位
    • 0為可分配
    • 1為已佔用
    • 位示圖是將”物理頁面號”分成二維矩陣,若$\text{字長}$是每一列的長度,$\text{字號}$是第幾列,則
\[\text{物理頁面號}=\text{字長}\times\text{字號}+\text{位號}\]
  • 轉換過程
    • 始址寄存器和頁表長度寄存器
\[\text{物理地址}=\text{物理頁面號}\times\text{塊長}+\text{頁內地址}\]

頁表項

  • 物理頁面號:頁面在內存時所對應的物理頁面號
  • 有效位:在內存還是在磁盤
  • 訪問位:有否訪問過
  • 修改位:內存是否修改

  • 保護位:是否能讀寫

  • 頁表種類
    • 多級頁表
    • 散列頁表
    • 反置頁表

TLB

graph LR
P["頁號P|頁內地址D"]
P---L{P<頁表長度寄存器的值L}
L--YES-->C["P'=B(頁表基址) + P"]
C--查找-->T[TLB]
T--組成-->G["P'|D"]
P-->G

缺頁過程

  • 查頁表的有效位, 看是否在內存
  • 若為0,保留現場,中斷裝置通過交換PSW讓中斷系統佔用處理器
  • 操作系統處理缺頁異常,尋找一個空閒的頁面
  • 若有空閒,把磁盤讀入,修改頁表及存分配表,表示該頁已在內存
  • 若無空閒,某種算法將內存某頁調出,把內存空間用來儲存現在需要的頁面
  • 恢復現場,重新執行被中斷的指令
graph TD
A{判斷是否在內存}-- YES -->B[繼續運行程序]
A-- NO -->C[缺頁中斷,該頁標志為0,保留現場]
C-->D{找內存空閒頁}
D-- YES -->E[裝入內存]
E-->F[修改頁表和內存分配頁]
D-- NO -->G[根據算法置換內外存]
F-->H[恢復現場]
G-->H

頁面調度策略

  • 調入策略
    • 請求調頁:只調入需要
    • 預調頁:一次調入相鄰的頁面
  • 置頁策略:找物理位置的最佳策略
  • 置換策略
    • 固定分配局部置換
    • 可變分配全局置換
    • 可變分配局部置換
    • 固定:分配固定的頁數的內存空間,運行期間不再改變
    • 局部:是一次分配一個進程
    • 全局:一次分配全部進程

頁面置換算法

  • 抖動/顛簸:剛被調出的頁面又立即要用, 因而又把它裝入,裝入不久又要被調出,反反復復
    • 由缺頁率高而引起,
  • OPT理想頁面置換算法:淘汰最晚才用到的頁面
  • FIFO先進先出置換算法:用指針,先進先淘汰,不理會先進的頁面是否常用
  • 第二次機會置換算法:FIFO且多加一位1或0,並將時間定義為變0的時間,放在鏈表最後(即最近發生),1的話變0,0就直接置換
  • Clock時鐘頁面置換算法:第二次一樣, 只是將鏈表變成環形鏈表,指針指向最先進的頁面

  • LRU最近最少使用頁面置換算法:淘汰最久沒有使用過的頁面

  • 缺頁率: $A$訪問頁面總次數;$F$缺頁次數
\[f=\frac{F}{A}\]
  • 影響缺頁因素
    • 分配給程序的物理頁數
      • 頁數越多,缺頁率越低
      • 若需共$n$頁的程序,分配$\frac{n}{2}$頁是最高效。
    • 頁面大小:
      • 頁越大,缺頁率越低
    • 程序編制方法:
      • P.197例子熟用
      • 若將每一行的元素進同一頁,以下的需要$(128\times128-1)$次換頁
        VAR A:ARRAY[1..128,1..128] OF integer;
FOR j:=1 TO 128 DO
FOR i:=1 TO 128 DO
    A[i,j]=0
      • 若將每一行的元素進同一頁,以下的需要$(128-1)$次換頁
        VAR A:ARRAY[1..128,1..128] OF integer;
FOR i:=1 TO 128 DO
FOR j:=1 TO 128 DO
    A[i,j]=0
      • 頁面調度算法
        • FIFO是OPT的3倍,但OPT是理想算法

虛擬頁式管理的優缺點

  • 優:
    • 不需連續存放,解決碎片問題,提高內存利用率
  • 缺:
    • 頁面浪費,程序代碼不同, 但頁面相同,總有一些空間得不到利用
  • 引入虛擬頁式管理的目的
    • 內存和外存統一管理,把訪問率非常高的頁面放入內存.減少內外存交換的次數
  • 抖動/顛簸
    • 由缺頁率高而引起
    • 采用工作集模型,可解決: $t-\Delta$到$t$所訪問頁面的集合
    • 統計工作集大小一般由硬件完成,開銷較大

第七章 文件管理

  • 存儲介質
    • 磁帶:順序
    • 磁盤: 想像成三維(柱面號(磁道號),磁頭號(盤面號),扇區號)
      • 尋道時間:找磁道
      • 旋轉時間:找扇區
      • 信息傳輸時間
    • 光盤
    • 閃存
  • 文件存取方法:順序存取和隨機存取
  • 文件的分類
    • 用途分類:系統文件、庫函數文件和用戶文件
    • 組織形式分類:普通文件、目錄文件和特殊文件
    • UNIX:普通文件、目錄文件和特殊文件

邏輯結構和物理結構

  • P.202
  • 邏輯結構
    • 流式文件:有序字符的集合,基本單位是字符
    • 記錄文件:有序記錄的集合,基本單位是記錄
      • 分定長和不定長
  • 物理結構
    • 順序
    • 鏈接:FAT
      • 優:存儲碎片解決,有利文件插入和刪除,提高利用率
      • 缺:存取慢,不適隨機存取文件,對指針依靠性強
    • 索引
      • 索引表鏈接
      • 多級索引:UNIX
      • 優:鏈的優點,適合順序和隨機存儲
      • 缺:多次尋道次數和時間,增加存儲空間的開銷

文件目錄

  • 文件控制塊(PCB)

  • 文件物理結構
    • 鏈接
    • 索引
  • 文件邏輯結構
    • 流式
    • 記錄式
  • 物理位置
    • 記錄了與文件在存儲介質中的物理位置有關的信息
  • 一級目錄結構
  • 二級目錄結構
    • 第一級為主文件目錄, 第二級為用戶文件目錄
    • 解決了文件重名問題, 可以實現用戶間的文件分享, 查找時間也降低了
    • 增加了系統的開銷
    • 解決同用戶間的文件共享問題
  • 多級目錄
    • 層次清楚
    • 解決了文件重名問題
    • 查找搜索快
    • Unix是三級

目錄項和目錄文件

  • 文件控制塊做成定長數據結構的一個紀錄,存儲在目錄文件中, 稱目錄項
  • FAT目錄項就是文件控制塊
  • 目錄項:文件名,文件號,其他信息
    • 符號目錄項:文件名,文件號
    • 基本目錄項:文件號, 其他信息

文件存儲空間管理

  • 位示圖
  • 空閒塊表
  • 空閒塊鏈表
  • 空閒塊成組鏈接法

文件共享、保護和保密

  • 文件存取控制
    • 建立副本
    • 定時轉儲
    • 規定文件的存取權限
  • 存取控制矩陣

  • 二級存取控制

  • 文件保密
    • 隱蔽文件目錄
    • 設置口令
    • 使用密碼
    • 病毒防范

第八章 I/O設備管理

  • I/O 管理任務:
    • CPU 與I/O設備性能不匹配的反差
    • 主要通過緩沖技術、中斷技術和虛擬技術
  • I/O設備分類
    • 按使用特性分類
      • 輸入設備
      • 輸出設備
      • 交互設備
      • 存儲設備
    • 信息組織方式分類
      • 塊設備
      • 字符設備
    • 按共享性分類
      • 獨佔:打印機、磁帶驅動
      • 共享:磁盤
      • 虛擬設備
        • 一類設備模擬另一類設備, 被模擬的稱虛擬設備
        • 共享模擬獨佔
        • 高速模擬低速

I/O硬件和軟件組成

  • 硬件組成(由裡到外)
    • 處理器和內存
    • 總線
    • 接口(適配器)
    • 外圍設備控制器
      • 控制寄存器
      • 狀態
      • 數據
      • 為一個寄存器分配唯一地址
        • 內存映射編址
        • I/O獨立編址
      • 操作系統並不直接與設備本身打交道,而是與設備控器打交道
    • 外圍設備
  • 軟件組成
    1. 用戶層軟件
    2. 設備獨立層軟件:承上啟下作用
    3. 設備驅動層軟件
    4. 中斷處理層軟件
    5. 硬件
  • 設備的獨立性
    • 除了直接與設備打交道的底層軟件外, 其他部份的軟件並不依賴硬件。I/O軟件獨立於設備﹐就可以提高設備管理軟件的設計效率，當I/O更新時, 沒有必要重新編寫全部I/O軟件。

I/O設備控制方式

  • 程序控制方式:
    • 忙-等方式
    • 輪詢方式
    • 循環測試
  • 中斷控制方式
  • DMA控制方式
    • 直接內存訪問, 由硬件執行I/O數據交換的工作方式
    • 三個階段
      • 傳送前預處理、數據傳送、傳送後處理
    • 高速傳送成組的數據,優點是操作由硬件電路實現,傳輸速度快,處理器在初始化和結束時參數,對數據傳送基本上不干預
  • 通道
    • P.250
    • 是一個特殊功能的處理器,有自己的指令和程序,可以實現對外圍設備的統一管理和外圍設備與內存之間的數據傳送
    • 引入通道的目的是為了進一步減少數據輸入輸出對整個系統運行效率的影響
    • 增加了處理器與通道操作的並行能力
    • 選擇通道:獨佔,高速
    • 數組多路通道:
      • 只為該設備服務,當設備在執行尋址等控制性動作時,暫時斷開與這個設備的連接, 掛起通道程序, 去為其他設備服務
      • 以數據塊為單位,通道利制率高, 但控制複雜
    • 字節多路通道:
      • 簡單共享通道, 分時基礎上多台低速和中速設備服務
      • 各設備與通道之間的數據傳送是以字節為單位交替進行, 各設備輪流佔用一個很短時間片
  • 通道具有如下功能
    • 接受處理器的指令
    • 從內存讀取屬於該通道的指令
    • 組織外圍設備和內存之間的數據傳送
    • 從外圍設備得到設備的狀態信息
    • 將外圍設備的中斷請求和通道本身的中斷請求

設備分配與回收

  • 數據結構
    • 系統設備表
    • 設備控制表
    • 控制控制表
    • 通道控制表
  • 分配原則
    • 靜態
    • 動態
  • 獨佔備的分備
    • 設備的絕對號:”絕對號”
    • 設備的相對號:”設備類、相對號”

磁盤調度策略

  • 尋找時間:磁頭在移動臂帶動下移動到指定柱面所花的時間
  • 延遲時間:指定扇區旋轉到磁頭下所花的時間
  • 傳送時間:由磁頭進行讀寫完成信息傳送所花的時間
  • $t$每個柱面上的磁道數、$s$每個盤面上的扇區數;第$i$柱面、第$j$磁頭和$k$扇區所對應的塊$b$
\[b=k+s\times(j+i\times t)\]

緩沖技術

  • I/O設備和處理器之間可以並行工作
  • 緩沖池

虛擬設備技術-SPOOLing

  • 系統包括
    • 程序模塊
    • 輸出模塊
    • 作業調度程序

You May Also Enjoy