第一章 操作系統(tǒng)引論

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

操作系統(tǒng)是一組能有效地組織和管理計(jì)算機(jī)硬件和軟件資源，
合理地對(duì)各類作業(yè)進(jìn)行調(diào)度，以及方便用戶使用的程序的集合

操作系統(tǒng)的目標(biāo)

==方便性==氛魁、==有效性==、可擴(kuò)充性氓扛、開放性

有效性: 提高系統(tǒng)資源的利用率右蒲、提高系統(tǒng)的吞吐量

引入OS的目的

為多道程序的運(yùn)行提供良好的運(yùn)行環(huán)境，以保證多道程序能有條不紊地着裹、高效地運(yùn)行领猾，
并能最大程度地提高系統(tǒng)中各種資源的利用率米同。方便用戶的使用

操作系統(tǒng)的作用

1. OS作為用戶和計(jì)算機(jī)硬件系統(tǒng)之間的接口

• 用戶有三種方式使用計(jì)算機(jī): 命令方式、系統(tǒng)調(diào)用方式摔竿、圖標(biāo)-窗口方式

2. OS作為計(jì)算機(jī)系統(tǒng)資源的管理者

• 處理機(jī)管理: 用于分配和控制處理機(jī)
• 存儲(chǔ)器管理: 負(fù)責(zé)內(nèi)存的分配與回收
• I/O設(shè)備管理: 負(fù)責(zé)I/O設(shè)備的分配(回收)與操縱
• 文件管理: 用于實(shí)現(xiàn)對(duì)文件的存取面粮、共享和保護(hù)

3. OS實(shí)現(xiàn)了對(duì)計(jì)算機(jī)資源的抽象

推動(dòng)操作系統(tǒng)發(fā)展的主要?jiǎng)恿?/h2>

• 不斷提高計(jì)算機(jī)資源利用率
• 方便用戶
• 器件的不斷更新?lián)Q代
• 計(jì)算機(jī)體系結(jié)構(gòu)的不斷發(fā)展
• 不斷提出新的應(yīng)用需求

操作系統(tǒng)的發(fā)展過程

人工方式

缺點(diǎn): 用戶獨(dú)占全機(jī)、CPU等待人工操作

脫機(jī)輸入/輸出方式

事先將裝有用戶程序和數(shù)據(jù)的紙帶裝入紙帶輸入機(jī)继低，在一臺(tái)外圍機(jī)的控制下熬苍，把紙帶上的數(shù)據(jù)輸入到磁帶上。
CPU在需要時(shí)袁翁，從磁帶上高速地調(diào)入內(nèi)存柴底。

優(yōu)點(diǎn): 減少了CPU的空閑時(shí)間、提高了I/O速度

單道批處理系統(tǒng)

• 在系統(tǒng)運(yùn)行過程中粱胜，內(nèi)存中只有一個(gè)用戶作業(yè)存在柄驻；
• 把一批作業(yè)脫機(jī)輸入到磁帶上；
• 系統(tǒng)配上監(jiān)督程序焙压；
• 在監(jiān)督程序的控制下使這批作業(yè)能一個(gè)接一個(gè)的連續(xù)得到處理鸿脓；
• 處理機(jī)使用權(quán)在監(jiān)督程序和用戶程序間轉(zhuǎn)換。

特征: 自動(dòng)性涯曲、順序性野哭、單道性

缺點(diǎn): 系統(tǒng)中的資源得不到充分的利用。因?yàn)樵趦?nèi)存中僅有一道程序幻件，每逢該程序在運(yùn)行中發(fā)出I/O請(qǐng)求后拨黔，
CPU便處于等待狀態(tài)，必須在其I/O完成后才繼續(xù)運(yùn)行

多道批處理系統(tǒng)

過程: 作業(yè)先存放在外存上并排成一個(gè)隊(duì)列绰沥，稱為“后備隊(duì)列”篱蝇；然后，由作業(yè)調(diào)度程序按一定的算法
從后備隊(duì)列中選擇若干個(gè)作業(yè)調(diào)入內(nèi)存揪利，使它們共享CPU和系統(tǒng)中的各種資源态兴。

優(yōu)缺點(diǎn):

• 資源利用率高
• 系統(tǒng)吞吐量大
• 可提高內(nèi)存和I/O設(shè)備利用率
• 平均周轉(zhuǎn)時(shí)間長
• 無交互能力

多道批處理系統(tǒng)需要解決的問題:

• 處理機(jī)爭用問題
• 內(nèi)存分配和保護(hù)問題
• I/O設(shè)備分配問題
• 文件的組織和管理問題
• 作業(yè)管理問題
• 用戶與系統(tǒng)的接口問題

image

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

分時(shí)系統(tǒng)是指，在一臺(tái)主機(jī)上連接了多個(gè)配有顯示器和鍵盤的終端并由此所組成的系統(tǒng)疟位，\

該系統(tǒng)允許多個(gè)用戶同時(shí)通過自己的終端瞻润，以交互方式使用計(jì)算機(jī)，共享主機(jī)中的資源

分時(shí)系統(tǒng)實(shí)現(xiàn)中的關(guān)鍵問題:

1. 及時(shí)接收
2. 及時(shí)處理

為實(shí)現(xiàn)人——機(jī)交互甜刻，采用下面的運(yùn)行方式:

• 作業(yè)直接進(jìn)入內(nèi)存
• 采用==時(shí)間片==輪轉(zhuǎn)的運(yùn)行方式绍撞。

image

影響響應(yīng)時(shí)間的因素:

• 終端數(shù)目多少
• 調(diào)度算法（時(shí)間片的選取）
• 信息交換量和信息交換速度
• 機(jī)器處理能力
• 請(qǐng)求服務(wù)的時(shí)間長短及服務(wù)請(qǐng)求的分布

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

實(shí)時(shí)系統(tǒng)是指系統(tǒng)能及時(shí)響應(yīng)外部事件的請(qǐng)求得院，在規(guī)定的時(shí)間內(nèi)完成對(duì)該事件的處理傻铣，并控制所有實(shí)時(shí)任務(wù)協(xié)調(diào)一致地運(yùn)行

實(shí)時(shí)系統(tǒng)的類型:

• 工業(yè)(武器)控制系統(tǒng)
• 信息查詢系統(tǒng)
• 多媒體系統(tǒng)
• 嵌入式系統(tǒng)

實(shí)時(shí)任務(wù)的類型:

• 周期性實(shí)時(shí)任務(wù)和非周期性實(shí)時(shí)任務(wù)
• 硬實(shí)時(shí)任務(wù)和軟實(shí)時(shí)任務(wù)

實(shí)時(shí)系統(tǒng)與分時(shí)系統(tǒng)特征的比較

image

微機(jī)操作系統(tǒng)

單用戶單任務(wù)操作系統(tǒng)

只允許一個(gè)用戶上機(jī)，且只允許用戶程序作為一個(gè)任務(wù)運(yùn)行

單用戶多任務(wù)操作系統(tǒng)

只允許一個(gè)用戶上機(jī)祥绞，但允許用戶把程序分為若干個(gè)任務(wù)非洲，使它們并發(fā)執(zhí)行

多用戶多任務(wù)操作系統(tǒng)

允許多個(gè)用戶通過各自的終端鸭限，使用同一臺(tái)機(jī)器共享主機(jī)系統(tǒng)中的各種資源，
而每個(gè)用戶程序又可進(jìn)一步分為幾個(gè)任務(wù)两踏，使它們能并發(fā)執(zhí)行黔州，
從而可進(jìn)一步提高資源利用率和系統(tǒng)吞吐量

操作系統(tǒng)的基本特性

并發(fā)

==并行性==: 兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生

==并發(fā)性==: 兩個(gè)或多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生

程序的并發(fā)執(zhí)行秸架，有效地改善了系統(tǒng)資源的利用率和提高了系統(tǒng)的吞吐量番甩，
但它使系統(tǒng)復(fù)雜化猜憎，操作系統(tǒng)必須具有控制和管理各種并發(fā)活動(dòng)的能力。

==進(jìn)程==: 在系統(tǒng)中能獨(dú)立運(yùn)行并作為資源分配的基本單位帕识，它是由一組機(jī)器指令泛粹、數(shù)據(jù)和堆棧等組成的，是一個(gè)能獨(dú)立運(yùn)行的活動(dòng)實(shí)體肮疗。多個(gè)進(jìn)程之間可以并發(fā)執(zhí)行和交換信息晶姊。

共享

資源共享指系統(tǒng)中的資源可供內(nèi)存中多個(gè)并發(fā)執(zhí)行的進(jìn)程共同使用

==互斥共享方式==

臨界資源: 在一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程訪問的資源

==同時(shí)訪問方式==

==并發(fā)==和==共享==是多用戶(多任務(wù))OS的兩個(gè)最基本的特征

虛擬

通過某種技術(shù)將一個(gè)物理實(shí)體變?yōu)槿舾蓚€(gè)邏輯上的對(duì)應(yīng)物

==時(shí)分復(fù)用技術(shù)==: 利用某設(shè)備為一用戶服務(wù)的==空閑時(shí)間==，又轉(zhuǎn)去為其他用戶服務(wù)

虛擬處理機(jī)技術(shù)族吻、虛擬設(shè)備技術(shù)

==空分復(fù)用技術(shù)==: 利用存儲(chǔ)器的==空閑空間==分區(qū)域存放和運(yùn)行其它的多道程序

虛擬存儲(chǔ)技術(shù)

異步

進(jìn)程以不可預(yù)知的速度向前推進(jìn)

操作系統(tǒng)的主要功能

處理機(jī)管理功能

處理機(jī)的分配和運(yùn)行都是以==進(jìn)程==為基本單位的

處理機(jī)管理的主要功能有:
創(chuàng)建和撤銷進(jìn)程帽借，對(duì)諸進(jìn)程的運(yùn)行進(jìn)行協(xié)調(diào)珠增，
實(shí)現(xiàn)進(jìn)程之間的信息交換超歌，以及按照一定算法把處理機(jī)分配給進(jìn)程

==進(jìn)程控制==: 為作業(yè)創(chuàng)建進(jìn)程、撤銷(終止)已結(jié)束的進(jìn)程蒂教，
以及控制進(jìn)程在運(yùn)行過程中的狀態(tài)轉(zhuǎn)換

==進(jìn)程同步(信號(hào)量機(jī)制)==: 為多個(gè)進(jìn)程(含線程)的運(yùn)行進(jìn)行協(xié)調(diào)

協(xié)調(diào)方式: 進(jìn)程互斥方式巍举、進(jìn)程同步方式

進(jìn)程同步方式: 在相互合作去完成共同任務(wù)的諸進(jìn)程間，由同步機(jī)構(gòu)對(duì)它們的執(zhí)行次序加以協(xié)調(diào)

==進(jìn)程通信==: 實(shí)現(xiàn)相互合作進(jìn)程之間的信息交換

==調(diào)度==: 作業(yè)調(diào)度凝垛、進(jìn)程調(diào)度

存儲(chǔ)器管理功能

主要任務(wù): 為多道程序的運(yùn)行提供良好的環(huán)境懊悯，提高存儲(chǔ)器的利用率，
方便用戶使用梦皮，并能從邏輯上擴(kuò)充內(nèi)存

主要功能: 內(nèi)存分配和回收炭分、內(nèi)存保護(hù)、地址映射和內(nèi)存擴(kuò)充

1. ==內(nèi)存分配==:

主要任務(wù):

• 為每道程序分配內(nèi)存空間
• 提高存儲(chǔ)器的利用率
• 允許正在運(yùn)行的程序申請(qǐng)附加的內(nèi)存空間

==靜態(tài)分配方式==: 運(yùn)行期間不允許該作業(yè)再申請(qǐng)新的內(nèi)存空間

==動(dòng)態(tài)分配方式==: 可以在運(yùn)行過程中申請(qǐng)新的附加內(nèi)存空間

2. ==內(nèi)存保護(hù)==

內(nèi)存保護(hù)機(jī)制: 設(shè)置兩個(gè)界限寄存器剑肯，分別用于存放正在執(zhí)行程序的上界和下界

主要任務(wù):

• 確保每道用戶程序都僅在自己的內(nèi)存空間內(nèi)運(yùn)行捧毛，彼此互不干擾
• 絕不允許用戶程序訪問操作系統(tǒng)的程序和數(shù)據(jù)，也不允許用戶程序轉(zhuǎn)移到非共享的其它用戶程序中執(zhí)行

3. ==地址映射==

能夠?qū)⒌刂房臻g中的邏輯地址轉(zhuǎn)換=為內(nèi)存空間中與之對(duì)應(yīng)的物理地址

4. ==內(nèi)存擴(kuò)充==

請(qǐng)求調(diào)入功能

置換功能

設(shè)備管理功能

主要任務(wù):

• 完成用戶進(jìn)程提出的I/O請(qǐng)求让网，為用戶進(jìn)程分配所需的I/O設(shè)備呀忧，并完成指定的I/O操作
• 提高CPU和I/O設(shè)備的利用率，提高I/O速度溃睹，方便用戶使用I/O設(shè)備

文件管理功能

主要任務(wù):

對(duì)用戶文件和系統(tǒng)文件進(jìn)行管理以方便用戶使用而账，并保證文件的安全性。

功能:

• 對(duì)文件存儲(chǔ)空間的管理
• 目錄管理
• 文件的讀/寫管理
• 文件的共享與保護(hù)

操作系統(tǒng)與用戶之間的接口

用戶接口: 用戶通過該接口向作業(yè)發(fā)出命令以控制作業(yè)的運(yùn)行

程序接口: 為用戶程序在執(zhí)行中訪問系統(tǒng)資源而設(shè)置的

第二章 進(jìn)程的描述與控制

程序順序執(zhí)行時(shí)的特征

順序性因篇、封閉性泞辐、可再現(xiàn)性

程序并發(fā)執(zhí)行

只有不存在前趨關(guān)系的程序之間才有可能并發(fā)執(zhí)行笔横，否則無法并發(fā)執(zhí)行

程序并發(fā)執(zhí)行時(shí)的特征: ==間斷性、失去封閉性咐吼、不可再現(xiàn)性==

image

進(jìn)程的定義

==進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過程狠裹，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立的基本單位==

==進(jìn)程控制塊==(PCB): 描述進(jìn)程的基本情況和活動(dòng)過程，進(jìn)而控制和管理進(jìn)程

==進(jìn)程實(shí)體==: 程序段汽烦、相關(guān)的數(shù)據(jù)段涛菠、PCB

==創(chuàng)建進(jìn)程==: 創(chuàng)建進(jìn)程實(shí)體中的PCB；==撤銷進(jìn)程==: 撤銷進(jìn)程的PCB

進(jìn)程的特征

• ==結(jié)構(gòu)特征==: 程序段撇吞、數(shù)據(jù)段俗冻、PCB
• ==動(dòng)態(tài)性==: 進(jìn)程的實(shí)質(zhì)是進(jìn)程實(shí)體的執(zhí)行過程。進(jìn)程實(shí)體有一定的生命期
• ==并發(fā)性==: 多個(gè)進(jìn)程實(shí)體同存于內(nèi)存中牍颈，且能在一段時(shí)間內(nèi)同時(shí)運(yùn)行迄薄。
  ==引入進(jìn)程的目的==正是為了使其進(jìn)程實(shí)體能和其它進(jìn)程實(shí)體并發(fā)執(zhí)行
• ==獨(dú)立性==: 進(jìn)程實(shí)體是一個(gè)能獨(dú)立運(yùn)行、獨(dú)立獲得資源和獨(dú)立接收調(diào)度的基本單位
• ==異步性==: 進(jìn)程是按異步方式運(yùn)行的煮岁，按各自獨(dú)立的讥蔽、不可預(yù)知的速度向前推進(jìn)

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

• 就緒狀態(tài): 得到了除CPU以外的所有必要資源
• 執(zhí)行狀態(tài): 已獲得處理機(jī)，程序正在被執(zhí)行
• 阻塞狀態(tài): 因等待某事件而暫時(shí)無法繼續(xù)執(zhí)行画机，從而放棄處理機(jī)冶伞，
  使程序執(zhí)行處于暫停狀態(tài)

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

image

基本狀態(tài)的轉(zhuǎn)換

image

==創(chuàng)建狀態(tài)==: 進(jìn)程已擁有了自己的PCB，但進(jìn)程自身還未進(jìn)入主存步氏，
即創(chuàng)建工作尚未完成响禽，進(jìn)程還不能被調(diào)度運(yùn)行，其所處的狀態(tài)荚醒。

==終止?fàn)顟B(tài)==：當(dāng)一個(gè)進(jìn)程到達(dá)了自然結(jié)束點(diǎn)芋类，或是出現(xiàn)了無法克服的錯(cuò)誤，
或是被操作系統(tǒng)所終結(jié)界阁，或是被其他有終止權(quán)的進(jìn)程所終結(jié)侯繁，它將進(jìn)入終止?fàn)顟B(tài)。

==掛起操作==

把一個(gè)進(jìn)程掛起使之處于靜止?fàn)顟B(tài)泡躯，以便研究它的執(zhí)行情況或?qū)λM(jìn)行修改

原因：

• 終端用戶請(qǐng)求
• 父進(jìn)程請(qǐng)求
• 負(fù)荷調(diào)節(jié)的需要
• 操作系統(tǒng)的需要

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

• 活動(dòng)就緒→靜止就緒
• 靜止就緒→活動(dòng)就緒
• 活動(dòng)阻塞→靜止阻塞
• 靜止阻塞→活動(dòng)阻塞
• 靜止阻塞→靜止就緒

進(jìn)程控制塊

==概念==: 進(jìn)程控制塊是進(jìn)程實(shí)體的重要組成部分贮竟，是操作系統(tǒng)中最重要的記錄型數(shù)據(jù)，在進(jìn)程控制塊PCB（Program Contral Block）中記錄了操作系統(tǒng)所需要的精续、用于描述進(jìn)程情況及控制進(jìn)程運(yùn)行所需要的全部信息

==作用==:

通過PCB坝锰，使得原來不能獨(dú)立運(yùn)行的程序（數(shù)據(jù)），成為一個(gè)可以獨(dú)立運(yùn)行的基本單位重付，一個(gè)能夠并發(fā)執(zhí)行的進(jìn)程顷级。進(jìn)程控制塊是進(jìn)程存在的唯一標(biāo)志。

==PCB中的信息==:

進(jìn)程標(biāo)識(shí)符: 用于唯一地標(biāo)識(shí)一個(gè)進(jìn)程

處理機(jī)狀態(tài): 保留進(jìn)程存放在處理器中的各種信息确垫，主要由處理器內(nèi)的各個(gè)寄存器的內(nèi)容組成弓颈。

進(jìn)程調(diào)度信息:進(jìn)程狀態(tài)帽芽、進(jìn)程優(yōu)秀級(jí)、阻塞原因等等翔冀。

進(jìn)程控制信息:程序和數(shù)據(jù)的地址导街、進(jìn)程同步和通信機(jī)制、資源清單纤子、鏈接指針

==PCB的組織方式==

線性方式

鏈接方式: 將具有相同狀態(tài)的PCB搬瑰，用其中的鏈接字，鏈接成一個(gè)隊(duì)列

索引方式: 根據(jù)進(jìn)程的狀態(tài)控硼，建立索引表

進(jìn)程控制

進(jìn)程控制是對(duì)系統(tǒng)中所有進(jìn)程從產(chǎn)生泽论、存在到消亡的全過程實(shí)行有效的管理和控制。
進(jìn)程控制一般是由操作系統(tǒng)的內(nèi)核來實(shí)現(xiàn)卡乾，內(nèi)核在執(zhí)行操作時(shí)翼悴，
往往是通過執(zhí)行各種原語操作來實(shí)現(xiàn)的

操作系統(tǒng)內(nèi)核

==內(nèi)核==: 加在硬件上的第一層軟件，通過執(zhí)行各種原語操作來實(shí)現(xiàn)各種控制和管理功能幔妨，具有創(chuàng)建鹦赎、撤消、進(jìn)程通信误堡、資源管理的功能

==內(nèi)核的基本功能==

支撐功能：中斷處理古话、時(shí)鐘管理、原語操作

資源管理功能：進(jìn)程管理埂伦、存貯管理煞额、設(shè)備管理

==原語==：是由若干條機(jī)器指令所構(gòu)成，用以完成特定功能的一段程序 沾谜。原語在執(zhí)行期間是不可分割的或不可中斷的。

創(chuàng)建原語胀莹、撤消原語基跑、阻塞原語、喚醒原語

進(jìn)程的創(chuàng)建

==進(jìn)程之間的關(guān)系==

• 父描焰、子進(jìn)程與祖先進(jìn)程: PCB中標(biāo)識(shí)
• 繼承/歸還資源: “父”創(chuàng)建“子”媳否、父撤子消

==引起創(chuàng)建進(jìn)程的事件==

• 用戶登錄 :在分時(shí)系統(tǒng)中，用戶在終端鍵入登錄命令
• 作業(yè)調(diào)度:在批處理系統(tǒng)中荆秦，當(dāng)作業(yè)調(diào)度程序按一定的算法調(diào)度到某作業(yè)
• 提供服務(wù):用戶程序提出某種請(qǐng)求后篱竭，系統(tǒng)將專門創(chuàng)建一個(gè)進(jìn)程來提供用戶所需要的服務(wù)
• 應(yīng)用請(qǐng)求:它自己創(chuàng)建一個(gè)新進(jìn)程，以便使新進(jìn)程以并發(fā)運(yùn)行方式完成特定任務(wù)

==進(jìn)程創(chuàng)建的過程==
（進(jìn)程創(chuàng)建原語Create()）

• 申請(qǐng)一個(gè)空白PCB,為新進(jìn)程申請(qǐng)獲得唯一的數(shù)字標(biāo)識(shí)符(PID)
• 為新進(jìn)程分配資源
• 初始化PCB
• 新進(jìn)程加入到就緒隊(duì)列

進(jìn)程的終止

==引起進(jìn)程終止的事件==

• 進(jìn)程正常結(jié)束
• 在進(jìn)程運(yùn)行期間步绸，由于出現(xiàn)某些錯(cuò)誤和故障而使得進(jìn)程被迫中止
• 進(jìn)程應(yīng)外界的請(qǐng)求而中止運(yùn)行

==進(jìn)程終止的過程==
（進(jìn)程終止原語Destroy()）

• 根據(jù)被終止進(jìn)程的標(biāo)識(shí)符掺逼，從PCB集合中檢索該進(jìn)程的PCB，讀出進(jìn)程狀態(tài)瓤介。
• 若該進(jìn)程處于執(zhí)行狀態(tài)吕喘，則立即終止該進(jìn)程的執(zhí)行赘那。
• 若該進(jìn)程有子孫進(jìn)程，還要將其子孫進(jìn)程終止氯质。
• 將該進(jìn)程所占用的資源回收募舟，歸還給其父進(jìn)程或操作系統(tǒng)。
• 將被終止進(jìn)程的PCB從所在隊(duì)列中移出闻察，并撤消該進(jìn)程的PCB拱礁。

進(jìn)程的阻塞與喚醒

==引起進(jìn)程阻塞的事件==

• 請(qǐng)求系統(tǒng)服務(wù)，要求不能立即滿足
• 啟動(dòng)某種操作辕漂，必須在操作完成后才能繼續(xù)
• 合作進(jìn)程提供的新數(shù)據(jù)尚未到達(dá)
• 無新工作可做

==進(jìn)程阻塞的過程==
（進(jìn)程阻塞原語Block()）

• 立即停止執(zhí)行
• 修改進(jìn)程控制塊中的相關(guān)信息
• 把進(jìn)程控制塊插入到阻塞隊(duì)列
• 轉(zhuǎn)調(diào)度程序重新調(diào)度

==引起進(jìn)程喚醒的事件==

• 請(qǐng)求系統(tǒng)服務(wù)得到滿足
• 啟動(dòng)某種操作完成
• 新數(shù)據(jù)已經(jīng)到達(dá)
• 有新工作可做

==進(jìn)程喚醒的過程==
（進(jìn)程喚醒原語Wakeup()）

• 從阻塞隊(duì)列中找到該進(jìn)程
• 修改該進(jìn)程控制塊的相關(guān)內(nèi)容
• 把進(jìn)程控制塊插入到就緒隊(duì)列

進(jìn)程的掛起與激活

==進(jìn)程掛起的方式==

• 把發(fā)出本原語的進(jìn)程自身掛起
• 掛起指定進(jìn)程名的進(jìn)程
• 把某進(jìn)程及其全部或部分子孫一起掛起

==進(jìn)程掛起的過程==
（進(jìn)程掛起原語Suspend()）

• 檢查被掛進(jìn)程的狀態(tài)觅彰，改為相應(yīng)的掛起狀態(tài)
• 把進(jìn)程的PCB復(fù)制到指定的區(qū)域
• 轉(zhuǎn)向調(diào)度程序重新調(diào)度

==進(jìn)程激活的過程==
（進(jìn)程激活原語Active()）

先將進(jìn)程從外存調(diào)入內(nèi)存，檢查該進(jìn)程的現(xiàn)行狀態(tài)钮热，
改為相應(yīng)的活動(dòng)狀態(tài)填抬。根據(jù)優(yōu)先級(jí)可能引起調(diào)度。

進(jìn)程同步

主要任務(wù)

對(duì)多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上進(jìn)行協(xié)調(diào)隧期，使并發(fā)執(zhí)行的諸進(jìn)程之間能按照一定的規(guī)則(或時(shí)序)共享系統(tǒng)資源飒责，并能很好地相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性

兩種形式的制約關(guān)系

間接相互制約關(guān)系——共享某種系統(tǒng)資源

直接相互制約關(guān)系——相互合作

臨界資源

一次僅允許一個(gè)進(jìn)程使用的資源仆潮，如打印機(jī)宏蛉、變量

臨界區(qū)

臨界區(qū)是每個(gè)進(jìn)程中訪問臨界資源的那段代碼

若能保證諸進(jìn)程互斥地進(jìn)入自己的臨界區(qū)，
便可實(shí)現(xiàn)諸進(jìn)程對(duì)臨界資源的互斥訪問

同步機(jī)制應(yīng)遵循的規(guī)則

image

信號(hào)量機(jī)制

==信號(hào)量==

用于表示==資源數(shù)目==或請(qǐng)求使用某一資源的==進(jìn)程個(gè)數(shù)==的整型量

S是與臨界區(qū)內(nèi)所使用的公用資源有關(guān)的信號(hào)量

S ≥0 可供并發(fā)進(jìn)程使用的資源數(shù)

S < 0 正在等待使用臨界區(qū)的進(jìn)程數(shù)

整型信號(hào)量

Wait和Signal是兩個(gè)原子操作性置，在執(zhí)行時(shí)是不可中斷的拾并。

整型信號(hào)量解決臨界區(qū)調(diào)度的==缺點(diǎn)==:
對(duì)不能進(jìn)入臨界區(qū)的進(jìn)程，采用忙式等待測試法鹏浅，浪費(fèi)CPU時(shí)間嗅义。因此未遵循“讓權(quán)等待”的準(zhǔn)則，使進(jìn)程處于“忙等”狀態(tài)隐砸。
在采取了“讓權(quán)等待”的策略后之碗，又會(huì)出現(xiàn)多個(gè)進(jìn)程等待訪問同一臨界資源的情況。

記錄型信號(hào)量

struct semaphore{
    int value;
    struct process_control_block *L;
}

wait(semaphore S)
{
    S.value--;
    if(S.value＜0)  block(S.L)
}
signal(semaphore S)
{
    S.value++;
    if(S.value≤0)   wakeup(S.L);
}

image

AND型信號(hào)量

AND同步機(jī)制的基本思想是：將進(jìn)程在整個(gè)運(yùn)行過程中需要的所有資源季希，一次性全部地分配給進(jìn)程褪那，待進(jìn)程使用完后再一起釋放。只要尚有一個(gè)資源未能分配給進(jìn)程式塌，其它所有可能為之分配的資源博敬，也不分配給他。亦即峰尝，對(duì)若干個(gè)臨界資源的分配偏窝，采取原子操作方式：要么全部分配到進(jìn)程，要么一個(gè)也不分配。

信號(hào)量集

在有些情況下囚枪，當(dāng)資源數(shù)量低于某一下限值派诬，不予以分配

Swait(S, t, d), S為信號(hào)量，t為下限值链沼，d為需求值

image

利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系

image

管程機(jī)制

管程: 代表共享資源的數(shù)據(jù)結(jié)構(gòu)以及由對(duì)該共享數(shù)據(jù)結(jié)構(gòu)實(shí)施操作的
一組過程所組成的資源管理程序共同構(gòu)成了一個(gè)操作系統(tǒng)的資源管理模塊

由四部分組成

• 管程的名稱
• 局部于管程的共享數(shù)據(jù)結(jié)構(gòu)說明
• 對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程
• 對(duì)內(nèi)部的共享數(shù)據(jù)初始化語句

image

注意:

局部變量只能被管程的過程訪問默赂；

進(jìn)程通過調(diào)用管程的過程進(jìn)入管程；

只能有一個(gè)進(jìn)程在管程中執(zhí)行

利用記錄型信號(hào)量解決生-消問題

int in = 0, out = 0;
item buffer[n];
semaphore mutex = 1, empty = n, full = 0;
void procuder() {
  do {
      procuder an item nextp;
      ...
      wait(empty);//判斷是否有空緩沖區(qū)括勺，表示空緩沖區(qū)-１缆八；
      wait(mutex);//數(shù)據(jù)緩沖區(qū)互斥訪問，關(guān)閉訪問疾捍；
      buffer[in] = nextp;
      in = (in+1) % n;
      signal(mutex);//打開訪問
      signal(full);//滿緩沖區(qū)加+1
  } while (true);
}

void consumer() {
   do {
       wait(full);//判斷是否有滿緩沖區(qū)奈辰，滿緩沖區(qū)-1
       wait(mutex);//數(shù)據(jù)緩沖區(qū)互斥訪問，關(guān)閉訪問乱豆；
       nextc = buffer[out];
       out = (out+1) % n;
       signal(mutex);//打開訪問
       siganl(empty);//空緩沖區(qū)+1
       consumer the item in nextc;
       ....
   } while (true);
}

void main() {
  cobegin
    producer(); consumer();
  coend
}

每次只允許一個(gè)進(jìn)程進(jìn)入緩沖池進(jìn)行操作

mutex為互斥信號(hào)量奖恰，實(shí)現(xiàn)諸進(jìn)程對(duì)緩沖池的互斥訪問，初值為1宛裕，取值為0瑟啃、1

empty,full為資源信號(hào)量，為正時(shí)分別表示==空緩沖區(qū)==和==滿緩沖區(qū)==的數(shù)量揩尸；
為負(fù)時(shí)蛹屿，其絕對(duì)值為相應(yīng)阻塞進(jìn)程的數(shù)目。
初值為n岩榆，0错负。可為負(fù)

應(yīng)先執(zhí)行對(duì)資源信號(hào)量的wait操作勇边，然后再執(zhí)行對(duì)互斥信號(hào)量的wait操作犹撒，否則會(huì)造成死鎖

由buffer組成的緩沖池是被組織成循環(huán)緩沖的

wait兩個(gè)操作不能互換。例如：當(dāng) mutex=1, E=0, F=n時(shí)粥诫，則對(duì)生產(chǎn)者進(jìn)程：wait(mutex)成功油航，wait(E)失敗怀浆；對(duì)消費(fèi)者進(jìn)程：wait(F)成功，wait(mutex)失敗怕享，形成死鎖

signal操作的次序無關(guān)緊要

互斥和資源信號(hào)量的原語必須成對(duì)出現(xiàn)

wait(empty) 
    empty >= 0  則數(shù)據(jù)送入緩沖區(qū)
    empty < 0   被阻塞  （滿）
signal(empty)   
    empty > 0       
    empty <= 0  釋放一個(gè)空緩沖區(qū)执赡，喚醒一個(gè)阻塞的生產(chǎn)者進(jìn)程
    
    
wait(full)  
    full >= 0   則從緩沖區(qū)取走數(shù)據(jù)
    full < 0    被阻塞  （空）
signal(full)    
    full > 0        
    full <= 0   數(shù)據(jù)裝入緩沖區(qū)，喚醒一個(gè)
                阻塞的消費(fèi)者進(jìn)程

image

讀者-寫者問題

算法描述：

設(shè)置兩個(gè)互斥信號(hào)量：

（1）wmutex函筋，實(shí)現(xiàn)Reader與Writer進(jìn)程間在讀或?qū)憰r(shí)的互斥沙合。

（2）rmutex,用于使讀者互斥地訪問共享變量readcount。

readcount表示正在讀的進(jìn)程數(shù)目跌帐，只要有一個(gè)Reader進(jìn)程在讀首懈，便不允許Writer進(jìn)程去寫绊率。因此，僅當(dāng)readcount=0, 表示尚無Reader進(jìn)程在讀時(shí)究履，Reader進(jìn)程才需要執(zhí)行Wait(wmutex)操作滤否。若wait(wmutex)操作成功，Reader進(jìn)程便可去讀最仑，相應(yīng)地藐俺，做readcount+1操作。同理泥彤，僅當(dāng)Reader進(jìn)程在執(zhí)行了readcount減1操作后其值為0時(shí)欲芹，才須執(zhí)行signal(wmutex)操作，以便讓W(xué)riter進(jìn)程寫

讀者進(jìn)來: 讀者函數(shù)首先申請(qǐng)將rmutex吟吝，鎖住讀信號(hào)量菱父，判斷readcount是否為0，為0則申請(qǐng)wmutex剑逃，不讓寫者進(jìn)來浙宜，再釋放掉rmutex，到此炕贵，可以讓其他讀者進(jìn)來梆奈，但是寫者都進(jìn)不來

讀者離開: 先申請(qǐng)rmutex，鎖住称开，不讓新的讀者進(jìn)來亩钟，執(zhí)行readcount--，移出已進(jìn)來的讀者鳖轰，判斷readcount是否為0清酥，為0，也就是所有讀者出去了蕴侣，釋放wmutex焰轻，這個(gè)時(shí)候，寫者和讀者都可以進(jìn)來了

使用信號(hào)量機(jī)制時(shí)易犯的錯(cuò)誤

==錯(cuò)誤1==：在利用互斥信號(hào)量mutex實(shí)現(xiàn)進(jìn)程互斥時(shí)昆雀，如果將wait(s)與signai(s)顛倒辱志，即

signal(mutex);
critical section
wait(mutex);  

在這種情況下，可能會(huì)有幾個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)狞膘，因而同時(shí)去訪問臨界資源揩懒。對(duì)于這樣的錯(cuò)誤僅在幾個(gè)進(jìn)程同時(shí)活躍在臨界區(qū)內(nèi)時(shí)，才可能發(fā)現(xiàn)挽封，而這種情況又并非總是可在發(fā)現(xiàn)的已球。

==錯(cuò)誤2==: 在實(shí)現(xiàn)進(jìn)程互斥時(shí)，如果程序中的signal(mutex)被誤寫為wait(mutex),即

wait(mutex);
critical section
wait(mutex);

此時(shí)的mutex將被出錯(cuò)的進(jìn)程連續(xù)兩次地執(zhí)行wait操作，因而變成-1智亮，這樣將會(huì)使任何其它進(jìn)程都不能進(jìn)入臨界區(qū)忆某；從而也不會(huì)再有進(jìn)程執(zhí)行signal(mutex)操作，去喚醒出錯(cuò)的進(jìn)程阔蛉。在這種情況下弃舒，將發(fā)生死鎖。

==錯(cuò)誤3==:
在實(shí)現(xiàn)進(jìn)程互斥時(shí)馍忽，如果在程序中遺漏了wait(mutex)操作棒坏，將會(huì)使多個(gè)進(jìn)程同時(shí)活躍在臨界區(qū)验游；而如果遺漏了signal(mutex)操作珠移，則將會(huì)使其它進(jìn)程無法再進(jìn)入臨界區(qū)但两；而如果已有進(jìn)程因不能進(jìn)入臨界區(qū)而阻塞敌完，則該進(jìn)程將永遠(yuǎn)不會(huì)被喚醒嵌灰。

線程

==定義==: 作為調(diào)度和分派的基本單位

==線程與進(jìn)程的比較==

• 調(diào)度：進(jìn)程不再是調(diào)度的基本單位划咐。
• 并 發(fā) 性：進(jìn)程之間可以并發(fā)纽帖，線程之間也可以并發(fā)執(zhí)行椒舵。
• 擁有資源：線程幾乎不占資源央串，同一進(jìn)程的線程共享進(jìn)程的資源磨澡。
• 獨(dú)立性：同一進(jìn)程中的不同線程之間的獨(dú)立性要低很多。
• 系統(tǒng)開銷：線程的創(chuàng)建质和、撤消與切換的系統(tǒng)開銷小的多稳摄。
• 支持多處理機(jī)系統(tǒng)

==線程的運(yùn)行狀態(tài)==

• 執(zhí)行狀態(tài): 表示線程已獲得處理機(jī)而正在運(yùn)行
• 就緒狀態(tài): 指線程已具備了各種執(zhí)行條件，只須獲得CPU便可立即執(zhí)行
• 阻塞狀態(tài): 指線程在執(zhí)行中因某事件受阻而處于暫停狀態(tài)

==線程控制塊TCB==

線程標(biāo)志符和一組狀態(tài)參數(shù)：寄存器狀態(tài)饲宿，堆棧厦酬，線程運(yùn)行狀態(tài)，優(yōu)先級(jí)瘫想，線程專有存儲(chǔ)器仗阅，信號(hào)屏蔽

==多線程OS中的進(jìn)程屬性==

• 進(jìn)程是一個(gè)可擁有資源的基本單位；
• 多線程可以并發(fā)執(zhí)行国夜；
• 進(jìn)程已不是可執(zhí)行實(shí)體

==線程的實(shí)現(xiàn)方式==

1. 內(nèi)核支持線程

• 線程的創(chuàng)建减噪、撤消、線程之間的切換车吹，都需要在內(nèi)核的支持下來實(shí)現(xiàn)筹裕；
• 線程控制塊（TCB）
• 調(diào)度以線程為單位

2. 用戶級(jí)線程

• 僅存在于用戶進(jìn)程空間中，線程的創(chuàng)建窄驹、撤消饶碘、線程之間的同步與通信都無須利用系統(tǒng)調(diào)用（內(nèi)核）來實(shí)現(xiàn)；
• 系統(tǒng)內(nèi)的線程可以“成百上千”
• 調(diào)度以進(jìn)程為單位

==線程的實(shí)現(xiàn)==

1. 內(nèi)核支持線程的實(shí)現(xiàn)

• 進(jìn)程的任務(wù)數(shù)據(jù)區(qū)（Per Task Data Area）
• 線程控制塊（TCB）
• 與進(jìn)程管理類似

2. 用戶級(jí)線程的實(shí)現(xiàn)——利用中間系統(tǒng)

• 運(yùn)行時(shí)系統(tǒng)（Runtime System）是用于管理和控制線程的函數(shù)（過程）的集合馒吴。他們使用戶級(jí)線程與內(nèi)核無關(guān)。
• 內(nèi)核控制線程（又稱輕型進(jìn)程LWP），用戶級(jí)線程通過LWP獲得內(nèi)何服務(wù)饮戳。

==線程的創(chuàng)建和終止==

• 應(yīng)用程序啟動(dòng)時(shí)豪治，僅有一個(gè)線程——初始化線程
• 初始化線程調(diào)用線程創(chuàng)建函數(shù)去創(chuàng)建若干個(gè)線程
• 終止線程的方式：線程完成工作后自愿退出；線程在運(yùn)行中出現(xiàn)錯(cuò)誤或由于某種原因而被其它線程強(qiáng)行終止
• 被終止未釋放資源的線程可以被需要的線程調(diào)用扯罐，使它重新恢復(fù)運(yùn)行

第三章 處理機(jī)調(diào)度與死鎖

調(diào)度的實(shí)質(zhì)是一種資源分配负拟，處理機(jī)調(diào)度是對(duì)處理機(jī)資源進(jìn)行分配

處理機(jī)調(diào)度的層次

高級(jí)調(diào)度

又稱長程調(diào)度或==作業(yè)==調(diào)度。調(diào)度對(duì)象是==作業(yè)==歹河。運(yùn)行頻率最低

==主要功能==是根據(jù)某種算法掩浙，決定將外存上處于后備隊(duì)列中的哪幾個(gè)作業(yè)調(diào)入內(nèi)存，
為它們創(chuàng)建進(jìn)程秸歧、分配必要的資源厨姚，并將它們放入就緒隊(duì)列

主要用于多道批處理系統(tǒng)中，而在分時(shí)和實(shí)時(shí)系統(tǒng)中不設(shè)置高級(jí)調(diào)度

低級(jí)調(diào)度

又稱為==進(jìn)程==調(diào)度或短程調(diào)度键菱。調(diào)度對(duì)象是==進(jìn)程==(或內(nèi)核級(jí)線程)谬墙。運(yùn)行頻率最高

==主要功能==是根據(jù)某種算法，決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)经备，
然后再由分派程序把處理機(jī)分配給該進(jìn)程

多道批處理拭抬、分時(shí)、實(shí)時(shí)系統(tǒng)

中級(jí)調(diào)度

又稱為==內(nèi)存==調(diào)度

主要==目的==是為了提高內(nèi)存利用率和系統(tǒng)吞吐量

==功能==: 將處于外存交換區(qū)中的就緒狀態(tài)或等待狀態(tài)的進(jìn)程調(diào)入內(nèi)存侵蒙，
或把處于內(nèi)存就緒狀態(tài)或內(nèi)存等待狀態(tài)的進(jìn)程交換到外存交換區(qū)中造虎。

實(shí)際上就是存儲(chǔ)器管理中的對(duì)換功能

處理機(jī)調(diào)度算法的目標(biāo)

共同目標(biāo)

• 資源利用率

  CPU的利用率=
  CPU有效工作時(shí)間/（ CPU有效工作時(shí)間+CPU空閑等待時(shí)間）

• 公平性

• 平衡性

• 策略強(qiáng)制執(zhí)行

批處理系統(tǒng)的目標(biāo)

• 平均周轉(zhuǎn)時(shí)間短

• 系統(tǒng)吞吐量高

  吞吐量：單位時(shí)間內(nèi)完成的作業(yè)數(shù)，與作業(yè)的平均長度具有密切關(guān)系纷闺。

• 處理機(jī)利用率高

image

分時(shí)系統(tǒng)的目標(biāo)

• 響應(yīng)時(shí)間快

  響應(yīng)時(shí)間：從用戶通過鍵盤提交一個(gè)請(qǐng)求開始至系統(tǒng)首次產(chǎn)生響應(yīng)為止算凿。

• 均衡性

實(shí)時(shí)系統(tǒng)的目標(biāo)

• 截止時(shí)間的保證

  截止時(shí)間：某任務(wù)開始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間急但。

• 可預(yù)測性

作業(yè)與作業(yè)調(diào)度

批處理系統(tǒng)中的作業(yè)

==作業(yè)==: 包含了通常的程序和數(shù)據(jù)澎媒，還配有一份作業(yè)說明書

在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的

==作業(yè)步==: 對(duì)作業(yè)的加工步驟

==作業(yè)控制塊==(JCB): 作業(yè)在系統(tǒng)中存在的標(biāo)志波桩，其中保存了系統(tǒng)對(duì)作業(yè)進(jìn)行管理和調(diào)度所需的全部信息

在作業(yè)運(yùn)行期間戒努，系統(tǒng)按照J(rèn)CB中的信息和作業(yè)說明書對(duì)作業(yè)進(jìn)行控制

作業(yè)運(yùn)行的三個(gè)階段和三種狀態(tài)

• 收容階段：后備狀態(tài)
• 運(yùn)行階段：運(yùn)行狀態(tài)
• 完成階段：完成狀態(tài)

image

作業(yè)調(diào)度的主要任務(wù)

根據(jù)JCB中的信息，檢查系統(tǒng)中的資源能否滿足作業(yè)對(duì)資源的需求镐躲，以及按照一定的算法储玫，從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程萤皂、分配必要的資源撒穷。然后再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上等待調(diào)度

執(zhí)行作業(yè)調(diào)度時(shí)，需要解決

1.==一次接納多少作業(yè)==裆熙，即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行

2.==接納哪些作業(yè)==端礼，即哪些作業(yè)調(diào)入內(nèi)存禽笑，取決于所采用的算法。比如先來先服務(wù)調(diào)度算法蛤奥；或者是短作業(yè)優(yōu)先調(diào)度算法佳镜；還有基于作業(yè)優(yōu)先權(quán)的調(diào)度算法，響應(yīng)比高者優(yōu)先調(diào)度算法等

作業(yè)調(diào)度算法

先來先服務(wù)算法(FCFS)

• 可用于作業(yè)調(diào)度和進(jìn)程調(diào)度凡桥。
• 按照作業(yè)（進(jìn)程）進(jìn)入后備隊(duì)列（就緒隊(duì)列）的先后次序來挑選作業(yè)（進(jìn)程）蟀伸，先進(jìn)入先被挑選。
• 算法容易實(shí)現(xiàn)缅刽，效率不高啊掏，只顧及作業(yè)（進(jìn)程）等候時(shí)間，沒考慮作業(yè)（進(jìn)程）要求服務(wù)時(shí)間的長短衰猛。
• 有利于長作業(yè)（進(jìn)程）迟蜜，不利于短作業(yè)（進(jìn)程）。有利于CPU繁忙型作業(yè)腕侄，不利于I/O繁忙型作業(yè)

image

短作業(yè)優(yōu)先調(diào)度算法(SJF)

image

image

優(yōu)點(diǎn)：

• 降低作業(yè)的平均等待時(shí)間小泉，提高系統(tǒng)吞吐量。

優(yōu)先級(jí)調(diào)度算法(PSA)

基于作業(yè)的==緊迫程度==冕杠，由外部賦予作業(yè)相應(yīng)的優(yōu)先級(jí)微姊，調(diào)度算法是根據(jù)優(yōu)先級(jí)進(jìn)行調(diào)度的

高響應(yīng)比優(yōu)先調(diào)度算法

image

image

重要例題

image

image

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

進(jìn)程調(diào)度的任務(wù)

• 保存處理機(jī)的現(xiàn)場信息
• 按某種算法選取進(jìn)程
• 把處理器分配給進(jìn)程

進(jìn)程調(diào)度機(jī)制

• 排隊(duì)器：將就緒進(jìn)程插入到相應(yīng)的就緒隊(duì)列中。
• 分派器：依據(jù)進(jìn)程調(diào)度程序所選定的進(jìn)程分预，將其從就緒隊(duì)列中取出兢交。
• 上下文切換器：保存當(dāng)前進(jìn)程的上下文；新選進(jìn)出的CPU現(xiàn)場信息恢復(fù)笼痹。

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

非搶占方式

一旦把處理機(jī)分配給某個(gè)進(jìn)程后配喳，讓該進(jìn)程一直執(zhí)行，
直到該進(jìn)程完成或者發(fā)生某事件而阻塞

引起進(jìn)程調(diào)度的因素：

• 正在執(zhí)行的進(jìn)程執(zhí)行完畢
• 執(zhí)行中的進(jìn)程因?yàn)樘岢鯥/O請(qǐng)求而暫停執(zhí)行
• 進(jìn)程通信或同步過程中執(zhí)行了原語操作

==優(yōu)點(diǎn)==：實(shí)現(xiàn)簡單凳干、系統(tǒng)開銷小晴裹，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。

==缺點(diǎn)==：難以滿足緊急任務(wù)的要求救赐，不適宜要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)

搶占方式

允許調(diào)度程序根據(jù)某種原則涧团，暫停正在執(zhí)行的進(jìn)程，將處理機(jī)重新分配給其他進(jìn)程

image

輪轉(zhuǎn)調(diào)度算法

image

時(shí)間片 Q=R / Nmax

R：響應(yīng)時(shí)間 Nmax： 最大進(jìn)程數(shù)

image

好題

優(yōu)先級(jí)調(diào)度算法

==優(yōu)先級(jí)調(diào)度算法的類型==

• 非搶占式優(yōu)先級(jí)調(diào)度算法
• 搶占式優(yōu)先級(jí)調(diào)度算法

==優(yōu)先級(jí)的類型==

• ==靜態(tài)優(yōu)先級(jí)==

靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的经磅，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變泌绣。

確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個(gè)方面：

（1）進(jìn)程類型
（2）進(jìn)程對(duì)資源的需求
（3）用戶要求

• ==動(dòng)態(tài)優(yōu)先級(jí)==

動(dòng)態(tài)優(yōu)先權(quán)是指，在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)预厌，是可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變的阿迈，以便獲得更好的調(diào)度性能。

進(jìn)程優(yōu)先權(quán)改變?cè)颍?/p>

（1）進(jìn)程等待時(shí)間
（2）進(jìn)程占用CPU時(shí)間

多級(jí)反饋隊(duì)列調(diào)度算法

• 設(shè)置多個(gè)就緒隊(duì)列轧叽，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)苗沧，優(yōu)先級(jí)越高的隊(duì)列中刊棕，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就越小
• 新進(jìn)程進(jìn)入內(nèi)存后，放入第一隊(duì)列末尾崎页，按FCFS原則等待調(diào)度鞠绰，如果在一個(gè)時(shí)間片結(jié)束時(shí)沒完成，將該進(jìn)程轉(zhuǎn)入第二隊(duì)列末尾重新等待調(diào)度執(zhí)行……
• 僅當(dāng)?shù)谝魂?duì)列空閑時(shí)飒焦，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行
• 如果處理機(jī)正在為某隊(duì)列的進(jìn)程服務(wù)，又有新進(jìn)程插入到較高優(yōu)先級(jí)的隊(duì)列中屿笼，則新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)

算法性能：

• 較好的性能牺荠，能夠照顧到用戶的利益
• 短作業(yè)、長作業(yè)都能得到比較滿意的處理

實(shí)時(shí)調(diào)度

實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件

1. 提供必要的信息

• 就緒時(shí)間
• 開始截止時(shí)間和完成截止時(shí)間
• 處理時(shí)間
• 資源要求
• 優(yōu)先級(jí)

2. 系統(tǒng)處理能力強(qiáng)
3. 采用搶占式調(diào)度機(jī)制
4. 具有快速切換機(jī)制

實(shí)時(shí)調(diào)度算法的分類

1. 非搶占式調(diào)度算法
2. 搶占式調(diào)度算法

• 基于時(shí)鐘中斷的搶占式優(yōu)先級(jí)調(diào)度算法
• 立即搶占的優(yōu)先級(jí)調(diào)度算法

最早截止時(shí)間優(yōu)先算法(EDF)

見書P100~101

• 根據(jù)開始截止時(shí)間來確定任務(wù)的優(yōu)先級(jí)
• 截止時(shí)間早的排在就緒隊(duì)列前面
• 總是選擇就緒隊(duì)列中的第一個(gè)任務(wù)
• 可用于搶占式調(diào)度和非搶占式調(diào)度

最低松弛度優(yōu)先算法(LLF)

見書P101~102

• 根據(jù)任務(wù)緊急（或松弛）的程度來確定優(yōu)先級(jí)
• 緊急程度愈高（松弛程度愈低）優(yōu)先級(jí)愈高驴一，愈先執(zhí)行
• 主要用于搶占式調(diào)度
• ==松弛度=必須完成時(shí)間-其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間==

一任務(wù)在400 ms時(shí)必須完成休雌，它本身需要運(yùn)行 150 ms，則其松弛程度為 250 ms肝断。

優(yōu)先級(jí)倒置

原因: 進(jìn)程之間有無資源爭搶

解決方法:

• 處理機(jī)不允許被搶占
• 動(dòng)態(tài)優(yōu)先級(jí)繼承

死鎖

資源問題

• 可重用性資源：IO設(shè)備杈曲、打印機(jī)等
• 可消耗性資源（臨時(shí)資源）：進(jìn)程間通信的消息等
• 可搶占性資源（可剝奪資源）：CPU、內(nèi)存
• 不可搶占性資源（非可剝奪資源）：磁帶機(jī)胸懈、打印機(jī)

定義

如果一組進(jìn)程中的每一個(gè)進(jìn)程都在等待僅由該組進(jìn)程中的其他進(jìn)程才能引發(fā)的事件担扑，那么該組進(jìn)程是死鎖的

原因

• ==競爭不可搶占性資源引起進(jìn)程死鎖==
• ==競爭可消耗資源引起進(jìn)程死鎖==
• 進(jìn)程推進(jìn)順序不當(dāng)
• PV操作使用不當(dāng)

產(chǎn)生死鎖的必要條件

• 互斥條件：進(jìn)程互斥使用資源
• 請(qǐng)求和保持條件：申請(qǐng)新資源時(shí)不釋放已占有資源
• 不剝奪條件：一個(gè)進(jìn)程不能搶奪其他進(jìn)程占有的資源
• 環(huán)路等待條件：存在一組進(jìn)程循環(huán)等待資源的環(huán)形鏈

處理死鎖的基本方法

• 預(yù)防死鎖：通過設(shè)置某些限制條件來破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)，來預(yù)防發(fā)生死鎖
• 避免死鎖：在動(dòng)態(tài)分配資源的過程中趣钱，用某種方法防止系統(tǒng)進(jìn)入不安全狀態(tài)涌献，從而避免發(fā)生死鎖
• 檢測死鎖：通過設(shè)置檢測機(jī)制，及時(shí)檢測出死鎖的發(fā)生首有，確定有關(guān)的進(jìn)程和資源
• 解除死鎖：與檢測死鎖配套使用燕垃，常用的方法是撤銷或掛起一些進(jìn)程，收回資源井联，分配給處于阻塞狀態(tài)的進(jìn)程卜壕，使之轉(zhuǎn)為就緒狀態(tài)，可以繼續(xù)運(yùn)行

預(yù)防死鎖

破壞“請(qǐng)求和保持”條件

1. 第一種協(xié)議：資源靜態(tài)分配法

   一個(gè)進(jìn)程必須在執(zhí)行前就申請(qǐng)它所要的全部資源烙常，并且直到它所要的資源都得到滿足后才開始執(zhí)行

2. 第二種協(xié)議：資源靜態(tài)分配法

   允許進(jìn)程只獲得運(yùn)行初期所需的資源轴捎，便開始運(yùn)行。這些資源使用完畢并全部釋放军掂，再申請(qǐng)新的所需資源轮蜕。

破壞“不可搶占”條件

采用剝奪控制

當(dāng)進(jìn)程在申請(qǐng)資源未獲準(zhǔn)許時(shí),先主動(dòng)釋放已占有的資源,然后才去等待，以后再一起向系統(tǒng)提出申請(qǐng)

一般只適用于可剝奪性資源蝗锥，如CPU跃洛、存儲(chǔ)區(qū)

破壞“循環(huán)等待”條件

資源順序分配法

對(duì)系統(tǒng)的全部資源編號(hào)，并規(guī)定進(jìn)程申請(qǐng)資源時(shí)只能按升序進(jìn)行

避免死鎖

系統(tǒng)安全狀態(tài)

• 安全狀態(tài)是指系統(tǒng)能按某種順序?yàn)槊總€(gè)進(jìn)程分配其所需的資源终议，使每個(gè)進(jìn)程執(zhí)行完畢
• 安全序列：進(jìn)程安全執(zhí)行完的順序汇竭。
• 如果系統(tǒng)無法找到這樣一個(gè)安全序列葱蝗，則稱系統(tǒng)處于不安全狀態(tài)。
• 避免死鎖的本質(zhì)在于：當(dāng)進(jìn)行資源分配時(shí)细燎，如何避免進(jìn)入不安全狀態(tài)

銀行家算法

• （1）如果Requesti[j]≤Need[i,j]两曼，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)玻驻。

• （2）如果Requesti[j]≤Available[j]悼凑，便轉(zhuǎn)向步驟(3)；否則璧瞬， 表示尚無足夠資源户辫，Pi須等待。

• （3）系統(tǒng)試探著把資源分配給進(jìn)程Pi嗤锉，并執(zhí)行：

   Available[j]=Available[j]-Requesti[j];
   
   Allocation[i,j]=Allocation[i,j]+Requesti[j];
   
  Need[i,j]=Need[i,j]-Requesti[j];
  

-（4）系統(tǒng)執(zhí)行安全性算法渔欢，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)瘟忱。若安全奥额，才正式將資源分配給進(jìn)程Pi，以完成本次分配访诱；否則垫挨， 將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)盐数，讓進(jìn)程Pi等待棒拂。

優(yōu)點(diǎn)：
資源利用率比靜態(tài)資源分配法高，又避免死鎖玫氢。

缺點(diǎn)：
對(duì)資源分配過于保守帚屉；計(jì)算太多，并且需知道對(duì)資源的最大需求量漾峡，不太實(shí)際

安全性算法

(1) 設(shè)置工作向量Work和布爾型向量Finish 攻旦，并初始化: Work=Available; Finish[i]=false;

(2)尋找能滿足下述條件的進(jìn)程：①Finish[i]=false;② Need[i,j]≤Work[j];若找到，執(zhí)行 (3)生逸，否則牢屋，執(zhí)行 (4)。

(3) 執(zhí)行：
Work[j]=Work[i]+Allocation[i,j];
Finish[i]=true;
go to step 2;

(4) 如果所有進(jìn)程的Finish［i］=true都滿足槽袄， 則表示系統(tǒng)處于安全狀態(tài)烙无；否則，系統(tǒng)處于不安全狀態(tài)遍尺。

死鎖定理

系統(tǒng)為死鎖狀態(tài)的充分條件是：當(dāng)且僅當(dāng)該狀態(tài)的資源分配圖是不可完全簡化的截酷。該充分條件稱為死鎖定理。

死鎖的解除

• 剝奪資源
• 終止(或撤銷)進(jìn)程

第四章 存儲(chǔ)器管理

管理對(duì)象: ==內(nèi)存==

存儲(chǔ)器的多層結(jié)構(gòu)

寄存器乾戏、高速緩存迂苛、主存儲(chǔ)器三热、磁盤緩存 屬于操作系統(tǒng)存儲(chǔ)管理的管轄范疇

以上，掉電后存儲(chǔ)信息丟失

固定磁盤三幻、可移動(dòng)存儲(chǔ)介質(zhì) 屬于設(shè)備管理的管轄范疇

存儲(chǔ)信息長期保存

可執(zhí)行存儲(chǔ)器: 寄存器就漾、主存儲(chǔ)器

寄存器: 存放處理機(jī)運(yùn)行時(shí)的數(shù)據(jù)，以加速存儲(chǔ)器的訪問速度

高速緩存: 用于備份主存中較常用的數(shù)據(jù)念搬，以減少處理機(jī)對(duì)主存儲(chǔ)器的訪問次數(shù)

主存儲(chǔ)器(內(nèi)存,主存): 用于保存進(jìn)程運(yùn)行時(shí)的程序和數(shù)據(jù)

磁盤緩存: 用于暫時(shí)存放頻繁使用的一部分磁盤數(shù)據(jù)和信息

一些基本概念

邏輯地址(相對(duì)地址抑堡，虛地址)

用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對(duì)地址的形式锁蠕，其首地址為0夷野，其余指令中的地址都相對(duì)于首地址而編址。不能用邏輯地址在內(nèi)存中讀取信息荣倾。

物理地址(絕對(duì)地址，實(shí)地址)

內(nèi)存中存儲(chǔ)單元的地址骑丸，可直接尋址

地址空間

• 程序用來訪問信息所用地址單元的集合
• 邏輯（相對(duì)）地址的集合
• 由編譯程序生成

存儲(chǔ)空間

• 主存中物理單元的集合
• 物理（絕對(duì)）地址的集合
• 由裝配程序等生成

定位(存儲(chǔ)分配)

為具體的程序和數(shù)據(jù)等分配存儲(chǔ)單元或存儲(chǔ)區(qū)工作舌仍。

映射

把邏輯地址轉(zhuǎn)換為相應(yīng)的物理地址的過程。

程序的裝入

對(duì)用戶程序的處理步驟

image

1. 編譯通危，由編譯程序?qū)τ脩粼闯绦蜻M(jìn)行編譯铸豁，形成若干個(gè)目標(biāo)模塊
2. 鏈接，由鏈接程序?qū)⒕幾g后形成的一組目標(biāo)模塊以及它們所需要的庫函數(shù)鏈接在一起菊碟，形成一個(gè)完整的裝入模塊
3. 裝入节芥，由裝入程序?qū)⒀b入模塊裝入內(nèi)存

絕對(duì)裝入方式

• 編譯程序產(chǎn)生絕對(duì)地址的目標(biāo)代碼，即代碼的邏輯地址和物理地址相同
• 裝入程序按照裝入模塊中的地址逆害，將程序和數(shù)據(jù)裝入內(nèi)存头镊，不進(jìn)行地址的修改
• 只適用于單道程序環(huán)境

可重定位裝入方式

目標(biāo)模塊的起始地址從0開始，程序中其他地址相對(duì)于起始地址計(jì)算魄幕，裝入程序根據(jù)內(nèi)存的當(dāng)前情況相艇，將裝入模塊裝入內(nèi)存的適當(dāng)位置

==重定位==：在裝入時(shí)對(duì)目標(biāo)程序中指令和數(shù)據(jù)地址的修改過程〈吭桑或者說：把作業(yè)地址空間中使用的邏輯地址變換成內(nèi)存空間中的物理地址的過程坛芽。又稱地址映射。

地址變換在裝入時(shí)一次完成翼抠，以后不再改變咙轩，==故稱為靜態(tài)重定位==

==優(yōu)點(diǎn)==：無需增加硬件地址變換機(jī)構(gòu)；實(shí)現(xiàn)簡單阴颖；適用于多道程序環(huán)境

==缺點(diǎn)==：不允許程序運(yùn)行時(shí)在內(nèi)存中移動(dòng)位置活喊；程序在存儲(chǔ)空間中只能連續(xù)分配；多個(gè)用戶難以共享存于內(nèi)存中的同一程序膘盖。

動(dòng)態(tài)運(yùn)行時(shí)的裝入方式

• 裝入程序把裝入模塊裝入內(nèi)存后胧弛，不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址尤误，
  而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。
• 裝入內(nèi)存后的所有地址都仍是相對(duì)地址结缚。
• 允許程序在內(nèi)存中移動(dòng)损晤；
• 需要重定位寄存器的支持
• 優(yōu)點(diǎn)：可對(duì)內(nèi)存進(jìn)行非連續(xù)分配；提供了實(shí)現(xiàn)虛存的基礎(chǔ)红竭；有利于程序段的共享

程序的鏈接

靜態(tài)鏈接方式

在程序運(yùn)行之前尤勋，先將各目標(biāo)模塊以及所需的庫函數(shù)，鏈接成一個(gè)完整的裝配模塊茵宪，==以后不拆開==最冰。

在將這幾個(gè)目標(biāo)模塊裝配成一個(gè)裝入模塊時(shí)，須解決以下兩個(gè)問題：

(1) 對(duì)相對(duì)地址進(jìn)行修改稀火。 (2) 變換外部調(diào)用符號(hào)

裝入時(shí)動(dòng)態(tài)鏈接

將用戶源程序編譯后所得到的一組目標(biāo)模塊暖哨，在裝入內(nèi)存時(shí)，采用==邊裝入邊鏈接==的鏈接方式

==優(yōu)點(diǎn)==：便于修改和更新凰狞；便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享篇裁。

==缺點(diǎn)==：程序每次要運(yùn)行的模塊可能不相同，但無法知道本次要運(yùn)行哪些模塊赡若，故只能將所有可能要運(yùn)行的模塊都全部裝入內(nèi)存并鏈接达布。

運(yùn)行時(shí)動(dòng)態(tài)鏈接

對(duì)某些目標(biāo)模塊的鏈接，在程序執(zhí)行中需要該模塊時(shí)逾冬，才對(duì)它進(jìn)行的鏈接黍聂。

==優(yōu)點(diǎn)==：凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上身腻，這樣不僅可加快程序的裝入過程产还，而且可節(jié)省大量的內(nèi)存空間。

連續(xù)分配存儲(chǔ)管理方式

該方式為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間霸株，即程序中代碼或數(shù)據(jù)的邏輯地址相鄰雕沉，體現(xiàn)在內(nèi)存空間分配時(shí)物理地址的相鄰

單一連續(xù)分配

• 最簡單的一種存儲(chǔ)管理方式，但只能用于單用戶去件、單任務(wù)的操作系統(tǒng)中坡椒。
• 內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用尤溜，通常是放在內(nèi)存的低址部分倔叼；
  用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間， 提供給用戶使用宫莱。
• 優(yōu)點(diǎn)：管理簡單丈攒，不要求專用的硬件支持；為防止破壞OS ，設(shè)置界限寄存器巡验；易于實(shí)現(xiàn)怖竭。
• 缺點(diǎn)：存儲(chǔ)器利用率低速侈；信息不共享胁黑；CPU 利用率低涩盾，周轉(zhuǎn)時(shí)間長

固定分區(qū)分配

• 運(yùn)行多道程序的存儲(chǔ)管理方式。
• 內(nèi)存用戶被劃分為若干個(gè)固定大小的區(qū)域捕捂，每個(gè)分區(qū)中只裝入一道作業(yè)瑟枫。
• 內(nèi)存利用率低。
• 允許幾道作業(yè)并發(fā)指攒。
• ==劃分分區(qū)的方法==：
  分區(qū)大小相等慷妙；分區(qū)大小不等。

內(nèi)存分配:

==分區(qū)使用表==：各表項(xiàng)包括每個(gè)分區(qū)的起始地址允悦，大小和狀態(tài)膝擂。

用戶程序需要裝入時(shí)，內(nèi)存分配程序檢索該表隙弛，找出一個(gè)能滿足要求尚未分配的分區(qū)猿挚，分配給該程序，并將其表項(xiàng)中的狀態(tài)置為“已分配”驶鹉。

若未找到大小足夠的分區(qū)，則拒絕為用戶程序分配內(nèi)存铣墨。

動(dòng)態(tài)分區(qū)分配

按作業(yè)的實(shí)際大小來劃分分區(qū)室埋，且分區(qū)個(gè)數(shù)也是隨機(jī)的,實(shí)現(xiàn)多個(gè)作業(yè)對(duì)內(nèi)存的共享，進(jìn)一步提高內(nèi)存資源利用率

動(dòng)態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)

• 空閑分區(qū)表伊约，一個(gè)空閑分區(qū)占一個(gè)表目姚淆，表目包括：分區(qū)序號(hào)、分區(qū)始址屡律、分區(qū)大小
• 空閑分區(qū)鏈腌逢。

動(dòng)態(tài)分區(qū)分配操作

分配內(nèi)存

image

回收內(nèi)存

image

基于順序搜索的動(dòng)態(tài)分區(qū)分配算法

順序搜索是指依次搜索空閑分區(qū)鏈上的空閑分區(qū)，去尋找一個(gè)其大小能滿足要求的分區(qū)

首次適應(yīng)算法

把主存中所有空閑區(qū)按其==物理地址遞增==的次序排列超埋。

在為作業(yè)分配存儲(chǔ)空間時(shí)搏讶，從低址空閑區(qū)開始查找,直到找到第一個(gè)能滿足要求的空閑區(qū)后，從中劃出與請(qǐng)求的大小相等的存儲(chǔ)空間分配給作業(yè)霍殴，余下的空閑區(qū)仍留在空閑鏈中媒惕；

優(yōu)先利用內(nèi)存中低址部分的空閑分區(qū)，保留了高址部分的大空閑區(qū)来庭；==低址部分不斷被分割妒蔚，形成很多難以利用的碎片。==

循環(huán)首次適應(yīng)算法

該算法是首次適應(yīng)算法的變形，在為作業(yè)分配存儲(chǔ)空間時(shí)肴盏，是==從上次所分配的空閑區(qū)的下一個(gè)空閑區(qū)開始查找科盛，直到找到第一個(gè)能滿足要求的空閑區(qū)==，從中劃出一塊與請(qǐng)求的大小相等的一塊存儲(chǔ)區(qū)分配給作業(yè)菜皂。若到最后一個(gè)空閑區(qū)的大小仍不能滿足要求時(shí)贞绵，應(yīng)再從第一個(gè)空閑區(qū)開始查找；

需設(shè)置查詢指針幌墓；

使空閑分區(qū)分布均勻但壮，但是缺乏大的空閑區(qū)；

最佳適應(yīng)算法

“最佳”的含義是指每次為作業(yè)分配主存時(shí)常侣，總是把既能滿足要求蜡饵，又是最小的空閑區(qū)分配給作業(yè)，以免由于“大材小用”而浪費(fèi)主存胳施。為了加速查找溯祸，==該算法要求將所有的空閑區(qū)按其大小遞增次序排列==；

第一個(gè)找到能滿足要求的空閑區(qū)一定使最佳的舞肆；每次分割的剩余部分都是最小的焦辅，因此在存儲(chǔ)器中會(huì)留下很多難以利用的小碎片

最壞適應(yīng)算法

在掃描整個(gè)空閑分區(qū)表或鏈表時(shí)，總是挑選一個(gè)最大的空閑區(qū)椿胯，從中分割一部分存儲(chǔ)空間給作業(yè)使用筷登，以至于存儲(chǔ)器缺乏大的空閑分區(qū)

優(yōu)點(diǎn): 使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的可能性最小哩盲，對(duì)中前方、小作業(yè)有利；查找效率最高

基于索引搜索的動(dòng)態(tài)分區(qū)分配算法

==快速適應(yīng)算法廉油、伙伴系統(tǒng)惠险、哈希算法==

image

動(dòng)態(tài)可重定位分區(qū)分配

==緊湊==

==通過移動(dòng)內(nèi)存中作業(yè)的位置，把原來多個(gè)分散的小分區(qū)拼接成一個(gè)大分區(qū)==

動(dòng)態(tài)重定位的實(shí)現(xiàn)

• 每次“緊湊”后必須對(duì)移動(dòng)了的程序或數(shù)據(jù)進(jìn)行重定位
• 地址變換過程是在程序執(zhí)行期間抒线，隨著對(duì)每條指令或數(shù)據(jù)的訪問自動(dòng)進(jìn)行的班巩，稱為動(dòng)態(tài)重定位。
• 硬件地址變換機(jī)構(gòu)的支持——重定位寄存器
• 內(nèi)存地址＝相對(duì)地址＋重定位寄存器中的地址
• 移動(dòng)程序時(shí)只需修改重定位寄存器中的地址

對(duì)換

定義

把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)換出到外存上嘶炭，以便騰出足夠的內(nèi)存空間抱慌，再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)換入內(nèi)存

對(duì)換是改善內(nèi)存利用率的有效措施，它可以直接提高處理機(jī)的利用率和系統(tǒng)的吞吐量

對(duì)換分類

整體對(duì)換: 進(jìn)程對(duì)換
部分對(duì)換: 頁面對(duì)換旱物、分段對(duì)換

進(jìn)程對(duì)換,OS必須實(shí)現(xiàn)三方面的功能

對(duì)換空間的管理

1. 對(duì)換空間管理的主要目標(biāo)

   在具有對(duì)換功能的OS中遥缕，通常把磁盤空間分為文件區(qū)和對(duì)換區(qū)

   1. 對(duì)文件區(qū)管理的主要目標(biāo)

      提高文件存儲(chǔ)空間的利用率，提高對(duì)文件的訪問速度

      采取==離散分配==方式

   2. 對(duì)對(duì)換空間管理的主要目標(biāo)

      提高進(jìn)程換入和換出的速度宵呛，然后才是提高文件存儲(chǔ)空間的利用率

      采取==連續(xù)分配==方式

進(jìn)程的換出與換入

1. 換出過程

   選擇處于阻塞狀態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程单匣，
   換出后收回內(nèi)存空間，修改進(jìn)程的PCB相關(guān)信息

2. 換入過程

   找出“就緒”狀態(tài)并已經(jīng)換出的進(jìn)程，將其中換出時(shí)間最久的進(jìn)程作為換入進(jìn)程户秤，將其換入

直到已無可換入的進(jìn)程和無可換出的進(jìn)程

離散分配

連續(xù)分配方式的缺點(diǎn)

形成許多“碎片”码秉；“緊湊”開銷大。

離散分配的種類

根據(jù)在離散分配時(shí)所分配地址空間的基本單位的不同

1. 分頁存儲(chǔ)管理方式

在該方式中鸡号，將用戶程序的地址空間分為若干個(gè)固定大小的區(qū)域转砖，稱為“==頁==”或者“==頁面==”。大小為1KB鲸伴。相應(yīng)地府蔗，也將內(nèi)存空間分為若干個(gè)物理塊或頁框，==頁和塊的大小相同==汞窗。這樣可將用戶程序的任一頁放入任一物理塊中姓赤，實(shí)現(xiàn)了==離散分配==

2. 分段存儲(chǔ)管理方式

該方式把用戶程序的地址空間分為若干個(gè)大小不同的段，每段可定義一組相對(duì)完整的信息仲吏。

3. 段頁式存儲(chǔ)管理方式

分頁存儲(chǔ)管理方式

頁(頁面)

把每個(gè)作業(yè)(進(jìn)程)==邏輯地址空間==劃分成若干大小相等的片.第0頁不铆、第1頁

(物理)塊或頁框(frame)

把==內(nèi)存空間==分成與頁面相同大小的若干個(gè)存儲(chǔ)塊。 0＃塊裹唆、1＃塊

頁內(nèi)碎片

由于進(jìn)程的最后一頁經(jīng)常裝不滿一塊而形成了不可利用的碎片誓斥。

頁面大小

• 太小，可使內(nèi)存碎片減小许帐，有利于提高內(nèi)存利用率劳坑；會(huì)使每個(gè)進(jìn)程占用較多的頁面，從而導(dǎo)致進(jìn)程的頁表過長成畦，占用大量內(nèi)存泡垃； 此外，還會(huì)降低頁面換進(jìn)換出的效率羡鸥。
• 較大，可以減少頁表的長度忠寻，提高頁面換進(jìn)換出的速度惧浴，但卻又會(huì)使頁內(nèi)碎片增大。
• 頁面的大小應(yīng)選擇得適中奕剃，且頁面大小應(yīng)是2的冪衷旅，通常為1 KB~8 KB。

地址結(jié)構(gòu)(頁號(hào)纵朋、頁內(nèi)地址)

image

頁表(頁面映象表)

==頁表的作用是實(shí)現(xiàn)從頁號(hào)到物理塊號(hào)的地址映射==

由頁號(hào)和塊號(hào)組成柿顶，指出邏輯地址中頁號(hào)與主存中物理塊號(hào)的對(duì)應(yīng)關(guān)系

==頁號(hào)==---作業(yè)地址空間的頁序號(hào)

==塊號(hào)==---內(nèi)存空間的頁面序號(hào)

地址轉(zhuǎn)換機(jī)構(gòu)

基本任務(wù)

借助于頁表,實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換,實(shí)際上就是將邏輯地址中的頁號(hào)轉(zhuǎn)換為內(nèi)存中的物理塊號(hào)

image

image

image

image

image

image

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

(1) 頁是信息的物理單位，由于系統(tǒng)管理的需要操软。段則是信息的邏輯單位嘁锯，它含有一組其意義相對(duì)完整的信息。分段的目的是為了能更好地滿足用戶的需要。

(2) 頁的大小固定且由系統(tǒng)決定家乘，而段的長度卻不固定蝗羊，它由其完成的功能決定。

(3) 分頁的作業(yè)地址空間是一維的而分段的作業(yè)地址空間則是二維的仁锯，程序員在標(biāo)識(shí)一個(gè)地址時(shí)耀找，需給出段名和段內(nèi)地址。

(4)由于段是信息的邏輯單位业崖，因此便于存貯保護(hù)和信息的共享野芒，頁的保護(hù)和共享受到限制。

分段存儲(chǔ)管理方式

==可重入代碼==：又稱為“純代碼”双炕，是一種允許多個(gè)進(jìn)程同時(shí)訪問的代碼狞悲。可重入代碼是一種不允許任何進(jìn)程對(duì)它進(jìn)行修改的代碼雄家。

分段系統(tǒng)中效诅，實(shí)現(xiàn)代碼的共享比在分頁系統(tǒng)中容易。

例如：不同進(jìn)程共享代碼長為160KB的文本編輯器趟济。

段頁式存儲(chǔ)管理方式

引入

分頁和分段管理方式各有其優(yōu)缺點(diǎn)乱投，分頁系統(tǒng)能有效提高內(nèi)存的利用率，而分段則能更好地滿足用戶的需要顷编，因此可以將兩者結(jié)合成一種新的存儲(chǔ)管理方式系統(tǒng)稱為“段頁式系統(tǒng)”戚炫。

原理

先將程序分成若干個(gè)段，再把每個(gè)段分成若干個(gè)頁媳纬，并為每一個(gè)段賦予一個(gè)段名双肤。

第五章 虛擬存儲(chǔ)器

第六章 輸入輸出系統(tǒng)

I/O系統(tǒng)管理的主要對(duì)象是I/O設(shè)備和相應(yīng)的設(shè)備控制器

主要任務(wù): 完成用戶提出的I/O請(qǐng)求，提高I/O速率钮惠，以及提高設(shè)備的利用率茅糜，并能為更高層的進(jìn)程方便地使用這些設(shè)備提供手段

I/O系統(tǒng)的基本功能

• 隱藏物理設(shè)備的細(xì)節(jié)

  僅向上層進(jìn)程提供少量的、抽象的讀/寫命令

• 與設(shè)備的無關(guān)性

• 提高處理機(jī)和I/O設(shè)備的利用率

• 對(duì)I/O設(shè)備進(jìn)行控制

• 確保對(duì)設(shè)備的正確共享

• 錯(cuò)誤處理

I/O設(shè)備的四種控制方式:

• 采用輪詢的可編程I/O方式

• 采用中斷的可編程I/O方式

• 直接存儲(chǔ)器的訪問方式

  (傳輸數(shù)據(jù)的基本單位:數(shù)據(jù)塊素挽，提高系統(tǒng)的利用率)

• I/O通道方式

I/O系統(tǒng)的層次結(jié)構(gòu)和模型

層次結(jié)構(gòu)

image

I/O系統(tǒng)中各種模塊之間的層次視圖

image

image

I/O系統(tǒng)接口

• 塊設(shè)備接口: 以塊為單位傳輸
• 流設(shè)備接口：字符設(shè)備接口
• 網(wǎng)絡(luò)通信接口

I/O設(shè)備的類型

• 按傳輸速率分類：
  低速設(shè)備蔑赘、中速設(shè)備、高速設(shè)備
• 按信息交換的單位分類：
  塊設(shè)備预明、字符設(shè)備
• 按設(shè)備的共享屬性分類：
  獨(dú)占設(shè)備缩赛、共享設(shè)備、虛擬設(shè)備

設(shè)備控制器

I/O設(shè)備與CPU之間的接口

image

定義和概念

==設(shè)備控制器是CPU和設(shè)備之間的一個(gè)接口,它接收從CPU發(fā)來的命令,控制I/O設(shè)備操作,實(shí)現(xiàn)主存和設(shè)備之間的數(shù)據(jù)傳輸撰糠。==

控制器接受一條命令后酥馍，CPU可以轉(zhuǎn)向其它工作，而設(shè)備控制器自行完成具體的I/O操作阅酪；當(dāng)命令執(zhí)行完畢后旨袒，控制器發(fā)出一個(gè)中斷信號(hào)汁针，以便OS重新獲得CPU的控制權(quán)并檢查執(zhí)行結(jié)果

設(shè)備控制器是一個(gè)可編址設(shè)備,當(dāng)它連接多臺(tái)設(shè)備時(shí),則應(yīng)具有多個(gè)設(shè)備地址

設(shè)備控制器的基本功能

• 接收和識(shí)別命令
• 數(shù)據(jù)交換
• 標(biāo)識(shí)和報(bào)告設(shè)備的狀態(tài)
• 地址識(shí)別
• 數(shù)據(jù)緩沖
• 差錯(cuò)控制

設(shè)備控制器的組成

image

I/O通道

==定義==：通道是獨(dú)立于CPU的專門負(fù)責(zé)數(shù)據(jù)輸入/輸出傳輸工作的處理機(jī)，對(duì)外部設(shè)備實(shí)現(xiàn)統(tǒng)一管理峦失，代替CPU對(duì)輸入/輸出操作進(jìn)行控制扇丛，從而使輸入，輸出操作可與CPU并行操作尉辑。

==引入通道的目的==：為了使CPU從I/O事務(wù)中解脫出來帆精，同時(shí)為了提高CPU與設(shè)備，設(shè)備與設(shè)備之間的并行工作能力

==通過執(zhí)行通道程序來控制I/O操作==

==指令類型單一隧魄，與CPU共享內(nèi)存==

通道類型

字節(jié)多路通道

• 字節(jié)多路通道以字節(jié)為單位傳輸信息卓练，它可以分時(shí)地執(zhí)行多個(gè)通道程序。當(dāng)一個(gè)通道程序控制某臺(tái)設(shè)備傳送一個(gè)字節(jié)后购啄，通道硬件就控制轉(zhuǎn)去執(zhí)行另一個(gè)通道程序襟企，控制另一臺(tái)設(shè)備傳送信息，使所有的通道輪轉(zhuǎn)一周
• 主要連接以字節(jié)為單位的低速I/O設(shè)備狮含。如打印機(jī)顽悼，終端。
• 以字節(jié)為單位交叉?zhèn)鬏敿钙?dāng)一臺(tái)傳送一個(gè)字節(jié)后蔚龙，立即轉(zhuǎn)去為另一臺(tái)傳送字節(jié)

數(shù)組選擇通道（Block Selector Channel）

• 選擇通道是以成組方式工作的，即每次傳送一批數(shù)據(jù)映胁，故傳送速度很高木羹。選擇通道在一段時(shí)間內(nèi)只能執(zhí)行一個(gè)通道程序，只允許一臺(tái)設(shè)備進(jìn)行數(shù)據(jù)傳輸
• 當(dāng)這臺(tái)設(shè)備數(shù)據(jù)傳輸完成后解孙，再選擇與通道連接的另一臺(tái)設(shè)備坑填，執(zhí)行它的相應(yīng)的通道程序
• 主要連接磁盤，磁帶等高速I/O設(shè)備

數(shù)組多路通道（Block Multiplexor Channel）

• 它結(jié)合了選擇通道傳送速度高和字節(jié)多路通道能進(jìn)行分時(shí)并行操作的優(yōu)點(diǎn)弛姜。它先為一臺(tái)設(shè)備執(zhí)行一條通道指令脐瑰，然后自動(dòng)轉(zhuǎn)接，為另一臺(tái)設(shè)備執(zhí)行一條通道指令廷臼；主要連接高速設(shè)備
• 這樣蚪黑，對(duì)于連接多臺(tái)磁盤機(jī)的數(shù)組多路通道，它可以啟動(dòng)它們同時(shí)執(zhí)行移臂定位操作中剩，然后，按序交叉地傳輸一批批數(shù)據(jù)抒寂。數(shù)據(jù)多路通道實(shí)際上是對(duì)通道程序采用多道程序設(shè)計(jì)的硬件實(shí)現(xiàn)

“瓶頸”問題

解決問題的方法是增加設(shè)備到主機(jī)的通路而不增加通道：即把一個(gè)設(shè)備連接到多個(gè)控制器上结啼，一個(gè)控制器連接到多個(gè)通道上

中斷機(jī)構(gòu)和中斷處理程序

中斷和陷入

image

中斷向量表和中斷優(yōu)先級(jí)

image

對(duì)多中斷源的處理方式

屏蔽（禁止）中斷、嵌套中斷

中斷處理程序

當(dāng)一個(gè)進(jìn)程請(qǐng)求I/O操作時(shí)屈芜，該進(jìn)程將被掛起郊愧，直到I/O設(shè)備完成I/O操作后朴译，設(shè)備控制器便向CPU發(fā)送一個(gè)中斷請(qǐng)求，CPU響應(yīng)后便轉(zhuǎn)向中斷處理程序属铁，中斷處理程序執(zhí)行相應(yīng)的處理眠寿，處理完后解除相應(yīng)進(jìn)程的阻塞狀態(tài)

處理過程

• 測定是否有未響應(yīng)的中斷信號(hào)
• 保護(hù)被中斷進(jìn)程的CPU環(huán)境
• 轉(zhuǎn)入相應(yīng)的設(shè)備處理程序
• 中斷處理
• 恢復(fù)CPU的現(xiàn)場并退出中斷

設(shè)備驅(qū)動(dòng)程序

定義、主要任務(wù)

• 設(shè)備驅(qū)動(dòng)程序:是I/O進(jìn)程與設(shè)備控制器之間的通信程序
• 主要任務(wù): 接收上層軟件發(fā)來的抽象I/O要求焦蘑，再把它轉(zhuǎn)換為具體要求后盯拱，發(fā)送給設(shè)備控制器，啟動(dòng)設(shè)備區(qū)執(zhí)行例嘱；反之狡逢，它也將由設(shè)備控制器發(fā)來的信號(hào)傳送給上層軟件
• 設(shè)備驅(qū)動(dòng)程序包括與設(shè)備相關(guān)的代碼，它的工作是：把用戶提交的邏輯I/O請(qǐng)求轉(zhuǎn)化為物理I/O操作的啟動(dòng)和執(zhí)行拼卵，如設(shè)備名轉(zhuǎn)化為端口地址奢浑、邏輯記錄轉(zhuǎn)化為物理記錄、邏輯操作轉(zhuǎn)化為物理操作等

設(shè)備驅(qū)動(dòng)程序的功能

• 將接收到的抽象要求轉(zhuǎn)換為具體要求腋腮；
• 檢查用戶I/O請(qǐng)求的合法性雀彼，了解I/O設(shè)備的狀態(tài)，傳遞有關(guān)參數(shù)即寡，設(shè)置設(shè)備的工作方式徊哑；
• 發(fā)出I/O命令，啟動(dòng)分配到的I／O設(shè)備嘿悬，完成指定的I／O操作实柠；
• 及時(shí)響應(yīng)由控制器或通道發(fā)來的中斷請(qǐng)求，并根據(jù)其中斷類型調(diào)用相應(yīng)的中斷處理程序進(jìn)行處理善涨；
• 對(duì)于設(shè)置有通道的計(jì)算機(jī)系統(tǒng)窒盐，驅(qū)動(dòng)程序還應(yīng)能夠根據(jù)用戶的I/O請(qǐng)求，自動(dòng)地構(gòu)成通道程序

設(shè)備驅(qū)動(dòng)程序的特點(diǎn)

• 驅(qū)動(dòng)程序主要是指在請(qǐng)求I/O的進(jìn)程與設(shè)備控制器之間的一個(gè)通信和轉(zhuǎn)換程序钢拧。
• 驅(qū)動(dòng)程序與設(shè)備控制器和I/O設(shè)備的硬件特性緊密相關(guān)蟹漓， 因而對(duì)不同類型的設(shè)備應(yīng)配置不同的驅(qū)動(dòng)程序。
• 驅(qū)動(dòng)程序與I/O設(shè)備所采用的I/O控制方式緊密相關(guān)源内。
• 由于驅(qū)動(dòng)程序與硬件緊密相關(guān)葡粒， 因而其中的一部分必須用匯編語言書寫。

設(shè)備處理方式

• 為每一類設(shè)備設(shè)置一個(gè)進(jìn)程膜钓，專門用于執(zhí)行這類設(shè)備的I/O操作 .
• 在整個(gè)系統(tǒng)中設(shè)置一個(gè)I/O進(jìn)程嗽交，專門用于執(zhí)行系統(tǒng)中所有各類設(shè)備的I/O操作。
• 不設(shè)置專門的設(shè)備處理進(jìn)程颂斜，而只為各類設(shè)備設(shè)置相應(yīng)的設(shè)備處理程序(模塊)夫壁， 供用戶進(jìn)程或系統(tǒng)進(jìn)程調(diào)用。

設(shè)備驅(qū)動(dòng)程序的處理過程

• 將抽象要求轉(zhuǎn)換為具體要求
• 檢查I/O請(qǐng)求的合法性
• 讀出和檢查設(shè)備的狀態(tài)
• 傳送必要的參數(shù)
• 工作方式的設(shè)置
• 啟動(dòng)I/O設(shè)備

==I/O設(shè)備的控制方式==

宗旨

盡量減少主機(jī)對(duì)I/O控制的干預(yù)沃疮，把主機(jī)從繁雜的I/O控制事務(wù)中解脫出來盒让，以便更多地去完成數(shù)據(jù)處理任務(wù)

使用輪詢的可編程I/O方式

• 在這種方式下梅肤，輸入輸出指令或詢問指令測試一臺(tái)設(shè)備的忙閑標(biāo)志位，決定主存儲(chǔ)器和外圍設(shè)備是否交換一個(gè)字符或一個(gè)字
• 一旦CPU啟動(dòng)I/O設(shè)備邑茄，便不斷查詢I/O設(shè)備的準(zhǔn)備情況姨蝴，終止原程序的執(zhí)行，浪費(fèi)CPU時(shí)間肺缕；
• I/O準(zhǔn)備就緒后左医，CPU參與數(shù)據(jù)傳送工作，而不能執(zhí)行原程序搓谆，
• CPU和I/O設(shè)備串行工作炒辉，使主機(jī)不能充分發(fā)揮效率，外圍設(shè)備也不能得到合理使用泉手，整個(gè)系統(tǒng)效率很低黔寇。

使用中斷的可編程I/O方式

• CPU啟動(dòng)I/O設(shè)備后，不必查詢I/O設(shè)備是否就緒斩萌，繼續(xù)執(zhí)行現(xiàn)行程序缝裤。
• 設(shè)備控制器按照命令要求去控制指定的I/O設(shè)備，當(dāng)數(shù)據(jù)準(zhǔn)備好后颊郎，即進(jìn)入數(shù)據(jù)寄存器后憋飞，控制器通過控制線向CPU發(fā)送中斷信號(hào)
• I/O操作直接由CPU控制，每傳送一個(gè)字符或字姆吭，要發(fā)生一次中斷榛做，仍然消耗大量CPU時(shí)間
• 不必忙式查詢I/O準(zhǔn)備情況，CPU和I/O設(shè)備可實(shí)現(xiàn)部分并行内狸，與程序查詢的串行工作方式相比检眯，使CPU資源得到較充分利用

==直接存儲(chǔ)器(DMA)訪問方式==

如果I/O設(shè)備能直接與主存交換數(shù)據(jù)而不占用CPU，CPU的利用率還可提高昆淡，這就出現(xiàn)了直接存儲(chǔ)器存取DMA方式

==特點(diǎn)==:

• 數(shù)據(jù)傳輸?shù)幕締挝皇菙?shù)據(jù)塊锰瘸，在主機(jī)與I/O設(shè)備之間每次至少傳遞一個(gè)數(shù)據(jù)塊；
• 所傳送的數(shù)據(jù)塊是從設(shè)備直接送入內(nèi)存昂灵；
• 在傳送一個(gè)或多個(gè)數(shù)據(jù)塊的開始和結(jié)束才需CPU干預(yù)避凝，傳送過程是在控制器的控制下完成

image

==DMA控制器的組成==

• 主機(jī)與DMA控制器的接口
• DMA控制器與塊設(shè)備的接口
• I/O控制邏輯

==DMA工作流程==

image

I/O通道控制方式

I/O通道控制方式的引入

• 為獲得CPU和外圍設(shè)備間更高的并行工作能力，也為了讓種類繁多眨补，物理特性各異的外圍設(shè)備能以標(biāo)準(zhǔn)的接口連接到系統(tǒng)中管削，計(jì)算機(jī)系統(tǒng)引入了自成獨(dú)立體系的通道結(jié)構(gòu)
• 由通道管理和控制I/O操作，減少了外圍設(shè)備和CPU的邏輯聯(lián)系撑螺。把CPU從瑣碎的I/O操作中解放出來

==與DMA方式的區(qū)別==

• 通道控制方式與DMA方式相類似含思，也是一種內(nèi)存和設(shè)備直接進(jìn)行數(shù)據(jù)交換的方式。與DMA方式不同的是实蓬，在通道控制方式中茸俭，數(shù)據(jù)傳送方向、存放數(shù)據(jù)的內(nèi)存始址及傳送的數(shù)據(jù)塊長度均由一個(gè)專門負(fù)責(zé)輸入/輸出的硬件——通道來控制安皱。
• 另外调鬓，DMA方式每臺(tái)設(shè)備至少需要一個(gè)DMA控制器，而通道控制方式中酌伊，一個(gè)通道可控制多臺(tái)設(shè)備與內(nèi)存進(jìn)行數(shù)據(jù)交換

==通道程序==

• 操作碼腾窝。
• 內(nèi)存地址。
• 計(jì)數(shù)居砖。
• 通道程序結(jié)束位P虹脯。
• 記錄結(jié)束標(biāo)志R。

與設(shè)備無關(guān)的I/O軟件

設(shè)備獨(dú)立性的概念

• 也稱為設(shè)備無關(guān)性奏候。 其基本含義是： 應(yīng)用程序獨(dú)立于具體使用的物理設(shè)備循集。
• 引入了邏輯設(shè)備和物理設(shè)備這兩個(gè)概念
• 在應(yīng)用程序中， 使用邏輯設(shè)備名稱來請(qǐng)求使用某類設(shè)備蔗草；而系統(tǒng)在實(shí)際執(zhí)行時(shí)咒彤， 還必須使用物理設(shè)備名稱。
• 系統(tǒng)須具有將邏輯設(shè)備名稱轉(zhuǎn)換為某物理設(shè)備名稱的功能

設(shè)備獨(dú)立性的好處

• 設(shè)備分配時(shí)的靈活性
• 易于實(shí)現(xiàn)I/O重定向

與設(shè)備無關(guān)的軟件

• 設(shè)備驅(qū)動(dòng)程序的統(tǒng)一接口
• 緩沖管理
• 差錯(cuò)控制
• 對(duì)獨(dú)立設(shè)備的分配與回收
• 獨(dú)立于設(shè)備的邏輯數(shù)據(jù)塊

為什么要引入設(shè)備獨(dú)立性咒精？如何實(shí)現(xiàn)設(shè)備獨(dú)立性镶柱？

引入設(shè)備獨(dú)立性，可使應(yīng)用程序獨(dú)立于具體的物理設(shè)備模叙，是設(shè)備分配具有靈活性歇拆。另外容易實(shí)現(xiàn)I/O重定向。
為了實(shí)現(xiàn)設(shè)備獨(dú)立性范咨，必須在設(shè)備驅(qū)動(dòng)程序之上設(shè)置一層設(shè)備獨(dú)立性軟件故觅，用來執(zhí)行所有I/O設(shè)備的公用操作，并向用戶層軟件提供統(tǒng)一接口湖蜕。關(guān)鍵是系統(tǒng)中必須設(shè)置一張邏輯設(shè)備表LUT用來進(jìn)行邏輯設(shè)備到物理設(shè)備的映射逻卖，其中每個(gè)表目中包含了邏輯設(shè)備名、物理設(shè)備名和設(shè)備驅(qū)動(dòng)程序入口地址三項(xiàng)昭抒；當(dāng)應(yīng)用程序用邏輯設(shè)備名請(qǐng)求分配I/O設(shè)備時(shí)评也，系統(tǒng)必須為它分配相應(yīng)的物理設(shè)備，并在LUT中建立一個(gè)表目灭返，以后進(jìn)程利用該邏輯設(shè)備名請(qǐng)求I/O操作時(shí)盗迟，便可從LUT中得到物理設(shè)備名和驅(qū)動(dòng)程序入口地址腻菇。

設(shè)備分配

設(shè)備分配程序

物理設(shè)備名->SDT(系統(tǒng)設(shè)備表)->DCT(設(shè)備控制表)->
COCT(控制器控制表)->CHCT(通道控制表)->LUT(邏輯設(shè)備表)

設(shè)備分配時(shí)應(yīng)考慮的因素

1. 設(shè)備的固有屬性

• 獨(dú)享設(shè)備厌漂。
• 共享設(shè)備。
• 虛擬設(shè)備盾碗。

2. 設(shè)備分配算法

• 先來先服務(wù)怎静。
• 優(yōu)先級(jí)高者優(yōu)先邮弹。

3. 設(shè)備分配中的安全性

• 安全分配方式
• 不安全分配方式

獨(dú)占設(shè)備的分配程序

基本的設(shè)備分配程序

• 分配設(shè)備
• 分配控制器
• 分配通道

設(shè)備分配程序的改進(jìn)

• 增加設(shè)備的獨(dú)立性
• 考慮多通路情況

邏輯設(shè)備名到物理設(shè)備名映射的實(shí)現(xiàn)

為了實(shí)現(xiàn)設(shè)備的獨(dú)立性黔衡，系統(tǒng)必須設(shè)置一張邏輯設(shè)備表(LUT)，
用于將應(yīng)用程序中所使用的邏輯設(shè)備名映射為物理設(shè)備名腌乡。

LUT的設(shè)置問題:

• 第一種方式是在整個(gè)系統(tǒng)中只設(shè)置一張LUT盟劫。
• 第二種方式是為每個(gè)用戶設(shè)置一張LUT。

SPOOLing技術(shù)——假脫機(jī)系統(tǒng)

SPOOLing：即同時(shí)聯(lián)機(jī)外圍操作与纽，又稱脫機(jī)操作侣签。在多道程序環(huán)境下，可利用多道程序中的一道程序急迂，來模擬脫機(jī)的輸入輸出功能影所。即在聯(lián)機(jī)條件下，將數(shù)據(jù)從輸入設(shè)備傳送到磁盤僚碎，或從磁盤傳送到輸出設(shè)備猴娩。

組成: 輸入井和輸出井、輸入緩沖區(qū)和輸出緩沖區(qū)听盖、輸入進(jìn)程和輸出進(jìn)程胀溺、井管理程序

SPOOLing系統(tǒng)特點(diǎn)：提高了I/O的速度、將獨(dú)占設(shè)備改造成共享設(shè)備皆看、實(shí)現(xiàn)了虛擬設(shè)備功能仓坞。

共享打印機(jī)——SPOOLing技術(shù)的典型實(shí)例

打印機(jī)屬于獨(dú)享設(shè)備。 用SPOOLing技術(shù)轉(zhuǎn)換為共享設(shè)備腰吟，提高設(shè)備的利用效率无埃。
用戶請(qǐng)求打印后：
1.輸出進(jìn)程在輸出井中申請(qǐng)一個(gè)空閑磁盤塊區(qū)， 并將要打印的數(shù)據(jù)送入其中毛雇。
2.輸出進(jìn)程申請(qǐng)并填寫一張空白的用戶請(qǐng)求打印表嫉称，再將該表掛到請(qǐng)求打印隊(duì)列上
3. 打印機(jī)空閑時(shí)，首取第一張請(qǐng)求表灵疮，將數(shù)據(jù)從輸出井傳送到內(nèi)存緩沖區(qū)织阅，進(jìn)行打印

磁盤存儲(chǔ)器的性能和調(diào)度

磁盤的類型

• 固定頭磁盤:
  每條磁道上都有一讀/寫磁頭，所有的磁頭都被裝在一剛性磁臂中震捣±竺蓿可以并行讀/寫。
• 移動(dòng)頭磁盤:
  每一個(gè)盤面僅配有一個(gè)磁頭蒿赢，也被裝入磁臂中润樱。僅能以串行方式讀/寫

磁盤訪問時(shí)間

image

磁盤調(diào)度

目標(biāo): 使磁盤的平均尋道時(shí)間最短

先來先服務(wù)算法

原理: 根據(jù)進(jìn)程請(qǐng)求訪問磁盤的先后次序進(jìn)行調(diào)度

優(yōu)點(diǎn): 公平，簡單羡棵，每個(gè)進(jìn)程的請(qǐng)求都能依次地得到處理壹若，不會(huì)出現(xiàn)某一進(jìn)程的請(qǐng)求長期得不到滿足的情況

缺點(diǎn): 平均尋道時(shí)間較長

最短尋道時(shí)間優(yōu)先算法

原理：選擇有距當(dāng)前磁頭所在磁道最近的訪問磁道的進(jìn)程。

優(yōu)點(diǎn): 比FCFS有更好的尋道性能

缺點(diǎn): 可能導(dǎo)致某個(gè)進(jìn)程發(fā)生饑餓現(xiàn)象

image

SCAN算法——電梯調(diào)度算法

原理：選擇與當(dāng)前磁頭移動(dòng)方向一致且距離最近的進(jìn)程。

優(yōu)點(diǎn)：尋道性能較好避免出現(xiàn)“饑餓”現(xiàn)象

循環(huán)掃描(CSCAN)算法

規(guī)定磁頭單向移動(dòng)店展。

image

image