計算機操作系統(tǒng)課件(湯子瀛)完整版.ppt

計算機操作系統(tǒng)原理,-湯子瀛,第一章 操作系統(tǒng)引論,1.1 操作系統(tǒng)的目標和作用 1.2 操作系統(tǒng)的發(fā)展過程 1.3 操作系統(tǒng)的基本特性 1.4 操作系統(tǒng)的主要功能 1.5 操作系統(tǒng)的結(jié)構(gòu)設(shè)計,1.1 操作系統(tǒng)的目標和作用,1.1.1 操作系統(tǒng)的目標,目前存在著多種類型的OS，不同類型的OS，其目標各有所側(cè)重。通常在計算機硬件上配置的OS，其目標有以下幾點： 1. 方便性 2. 有效性 3. 可擴充性 4. 開放性,1.1.2 操作系統(tǒng)的作用,1.OS作為用戶與計算機硬件系統(tǒng)之間的接口 OS作為用戶與計算機硬件系統(tǒng)之間接口的含義是：OS處于用戶與計算機硬件系統(tǒng)之間，用戶通過OS來使用計算機系統(tǒng)。或者說，用戶在OS幫助下，能夠方便、快捷、安全、可靠地操縱計算機硬件和運行自己的程序。應(yīng)注意，OS是一個系統(tǒng)軟件，因而這種接口是軟件接口。,圖 1-1 OS作為接口的示意圖,(1) 命令方式。這是指由OS提供了一組聯(lián)機命令(語言)， 用戶可通過鍵盤輸入有關(guān)命令，來直接操縱計算機系統(tǒng)。 (2) 系統(tǒng)調(diào)用方式。OS提供了一組系統(tǒng)調(diào)用，用戶可在自己的應(yīng)用程序中通過相應(yīng)的系統(tǒng)調(diào)用，來操縱計算機。 (3) 圖形、窗口方式。用戶通過屏幕上的窗口和圖標來操縱計算機系統(tǒng)和運行自己的程序。,2. OS作為計算機系統(tǒng)資源的管理者 在一個計算機系統(tǒng)中，通常都含有各種各樣的硬件和軟件資源。歸納起來可將資源分為四類：處理器、存儲器、 I/O設(shè)備以及信息(數(shù)據(jù)和程序)。相應(yīng)地，OS的主要功能也正是針對這四類資源進行有效的管理，即：處理機管理， 用于分配和控制處理機；存儲器管理，主要負責內(nèi)存的分配與回收；I/O設(shè)備管理，負責I/O設(shè)備的分配與操縱；文件管理，負責文件的存取、共享和保護。可見，OS確是計算機系統(tǒng)資源的管理者。事實上，當今世界上廣為流行的一個關(guān)于OS作用的觀點，正是把OS作為計算機系統(tǒng)的資源管理者。,3. OS用作擴充機器 對于一臺完全無軟件的計算機系統(tǒng)(即裸機)，即使其功能再強，也必定是難于使用的。如果我們在裸機上覆蓋上一層I/O設(shè)備管理軟件，用戶便可利用它所提供的I/O命令，來進行數(shù)據(jù)輸入和打印輸出。此時用戶所看到的機器， 將是一臺比裸機功能更強、使用更方便的機器。通常把覆蓋了軟件的機器稱為擴充機器或虛機器。如果我們又在第一層軟件上再覆蓋上一層文件管理軟件，則用戶可利用該軟件提供的文件存取命令，來進行文件的存取。此時，用戶所看到的是臺功能更強的虛機器。如果我們又在文件管理軟件上再覆蓋一層面向用戶的窗口軟件，則用戶便可在窗口環(huán)境下方便地使用計算機，形成一臺功能更強的虛機器。,1.1.3 推動操作系統(tǒng)發(fā)展的主要動力,不斷提高計算機資源利用率 2. 方便用戶 3. 器件的不斷更新?lián)Q代 4. 計算機體系結(jié)構(gòu)的不斷發(fā)展,1.2 操作系統(tǒng)的發(fā)展過程,1.2.1 無操作系統(tǒng)的計算機系統(tǒng),1. 人工操作方式 從第一臺計算機誕生(1945年)到50年代中期的計算機，屬于第一代，這時還未出現(xiàn)OS。這時的計算機操作是由用戶(即程序員)采用人工操作方式直接使用計算機硬件系統(tǒng)，即由程序員將事先已穿孔(對應(yīng)于程序和數(shù)據(jù))的紙帶(或卡片)裝入紙帶輸入機(或卡片輸入機)，再啟動它們將程序和數(shù)據(jù)輸入計算機， 然后啟動計算機運行。當程序運行完畢并取走計算結(jié)果后， 才讓下一個用戶上機。這種人工操作方式有以下兩方面的缺點： (1) 用戶獨占全機。 (2) CPU等待人工操作。,2. 脫機輸入/輸出(Off-Line I/O)方式,這種脫機I/O方式的主要優(yōu)點如下： 減少了CPU的空閑時間。 (2) 提高I/O速度。,圖 1-2 脫機I/O示意圖,1.2.2 單道批處理系統(tǒng),1. 單道批處理系統(tǒng)(Simple Batch Processing System)的處理過程,圖 1-3 單道批處理系統(tǒng)的處理流程,2. 單道批處理系統(tǒng)的特征 單道批處理系統(tǒng)是最早出現(xiàn)的一種OS，嚴格地說，它只能算作是OS的前身而并非是現(xiàn)在人們所理解的OS。盡管如此，該系統(tǒng)比起人工操作方式的系統(tǒng)已有很大進步。 該系統(tǒng)的主要特征如下： (1) 自動性。 (2) 順序性。 (3) 單道性。,1.2.3 多道批處理系統(tǒng),1. 多道程序設(shè)計的基本概念 在單道批處理系統(tǒng)中，內(nèi)存中僅有一道作業(yè)，它無法充分利用系統(tǒng)中的所有資源，致使系統(tǒng)性能較差。為了進一步提高資源的利用率和系統(tǒng)吞吐量，在60年代中期又引入了多道程序設(shè)計技術(shù)，由此而形成了多道批處理系統(tǒng)(Multiprogrammed Batch Processing System)。在該系統(tǒng)中， 用戶所提交的作業(yè)都先存放在外存上并排成一個隊列，稱為“后備隊列”；然后，由作業(yè)調(diào)度程序按一定的算法從后備隊列中選擇若干個作業(yè)調(diào)入內(nèi)存，使它們共享CPU和系統(tǒng)中的各種資源。,在OS中引入多道程序設(shè)計技術(shù)可帶來以下好處： 提高CPU的利用率。,當內(nèi)存中僅有一道程序時，每逢該程序在運行中發(fā)出I/O請求后，CPU空閑，必須在其I/O完成后才繼續(xù)運行；尤其因I/O設(shè)備的低速性，更使CPU的利用率顯著降低。圖 1-4(a)示出了單道程序的運行情況，從圖可以看出：在t2t3、 t6t7時間間隔內(nèi)CPU空閑。在引入多道程序設(shè)計技術(shù)后， 由于同時在內(nèi)存中裝有若干道程序，并使它們交替地運行， 這樣，當正在運行的程序因I/O而暫停執(zhí)行時，系統(tǒng)可調(diào)度另一道程序運行，從而保持了CPU處于忙碌狀態(tài)。,圖 1-4 單道和多道程序運行情況,(2) 可提高內(nèi)存和I/O設(shè)備利用率。為了能運行較大的作業(yè)，通常內(nèi)存都具有較大容量，但由于80%以上的作業(yè)都屬于中小型，因此在單道程序環(huán)境下，也必定造成內(nèi)存的浪費。類似地，對于系統(tǒng)中所配置的多種類型的I/O設(shè)備， 在單道程序環(huán)境下也不能充分利用。如果允許在內(nèi)存中裝入多道程序， 并允許它們并發(fā)執(zhí)行，則無疑會大大提高內(nèi)存和I/O設(shè)備的利用率。 (3) 增加系統(tǒng)吞吐量。在保持CPU、I/O設(shè)備不斷忙碌的同時，也必然會大幅度地提高系統(tǒng)的吞吐量，從而降低作業(yè)加工所需的費用。,2. 多道批處理系統(tǒng)的特征,多道性。 (2) 無序性。 (3) 調(diào)度性。,3. 多道批處理系統(tǒng)的優(yōu)缺點,資源利用率高。 (2) 系統(tǒng)吞吐量大。 (3) 平均周轉(zhuǎn)時間長。 (4) 無交互能力。,4. 多道批處理系統(tǒng)需要解決的問題,處理機管理問題。 (2) 內(nèi)存管理問題。 (3) I/O設(shè)備管理問題。 (4) 文件管理問題。 (5) 作業(yè)管理問題。,1.2.4 分時系統(tǒng),1. 分時系統(tǒng)(Time-Sharing System)的產(chǎn)生 如果說， 推動多道批處理系統(tǒng)形成和發(fā)展的主要動力，是提高資源利用率和系統(tǒng)吞吐量，那么，推動分時系統(tǒng)形成和發(fā)展的主要動力，則是用戶的需求?；蛘哒f， 分時系統(tǒng)是為了滿足用戶需求所形成的一種新型OS。它與多道批處理系統(tǒng)之間，有著截然不同的性能差別。用戶的需求具體表現(xiàn)在以下幾個方面： (1) 人機交互。 (2) 共享主機。 (3) 便于用戶上機。,2. 分時系統(tǒng)實現(xiàn)中的關(guān)鍵問題,為實現(xiàn)分時系統(tǒng)，其中，最關(guān)鍵的問題是如何使用戶能與自己的作業(yè)進行交互，即當用戶在自己的終端上鍵入命令時， 系統(tǒng)應(yīng)能及時接收并及時處理該命令，再將結(jié)果返回給用戶。 此后， 用戶可繼續(xù)鍵入下一條命令，此即人機交互。應(yīng)強調(diào)指出，即使有多個用戶同時通過自己的鍵盤鍵入命令，系統(tǒng)也應(yīng)能全部地及時接收并處理,(1) 及時接收。,(2) 及時處理。,3. 分時系統(tǒng)的特征,多路性。 (2) 獨立性。 (3) 及時性。 (4) 交互性。,1.2.5 實時系統(tǒng),所謂“實時”，是表示“及時”，而實時系統(tǒng)(Real-Time System)是指系統(tǒng)能及時(或即時)響應(yīng)外部事件的請求，在規(guī)定的時間內(nèi)完成對該事件的處理，并控制所有實時任務(wù)協(xié)調(diào)一致地運行。,1. 應(yīng)用需求,實時控制。 (2) 實時信息處理。,2. 實時任務(wù),1) 按任務(wù)執(zhí)行時是否呈現(xiàn)周期性來劃分 周期性實時任務(wù)。 (2) 非周期性實時任務(wù)。,外部設(shè)備所發(fā)出的激勵信號并無明顯的周期性，但都必須聯(lián)系著一個截止時間(Deadline)。它又可分為： 開始截止時間任務(wù)在某時間以前必須開始執(zhí)行； 完成截止時間任務(wù)在某時間以前必須完成。,2) 根據(jù)對截止時間的要求來劃分 (1) 硬實時任務(wù)(hard real-time task)。系統(tǒng)必須滿足任務(wù)對截止時間的要求，否則可能出現(xiàn)難以預(yù)測的結(jié)果。 (2) 軟實時任務(wù)(Soft real-time task)。它也聯(lián)系著一個截止時間， 但并不嚴格，若偶爾錯過了任務(wù)的截止時間， 對系統(tǒng)產(chǎn)生的影響也不會太大。,3. 實時系統(tǒng)與分時系統(tǒng)特征的比較 多路性。 (2) 獨立性。 (3) 及時性。 (4) 交互性。 (5) 可靠性。,1.3 操作系統(tǒng)的基本特性,1.3.1 并發(fā)(Concurrence),并行性和并發(fā)性是既相似又有區(qū)別的兩個概念，并行性是指兩個或多個事件在同一時刻發(fā)生；而并發(fā)性是指兩個或多個事件在同一時間間隔內(nèi)發(fā)生。在多道程序環(huán)境下，并發(fā)性是指在一段時間內(nèi)，宏觀上有多個程序在同時運行，但在單處理機系統(tǒng)中，每一時刻卻僅能有一道程序執(zhí)行，故微觀上這些程序只能是分時地交替執(zhí)行。倘若在計算機系統(tǒng)中有多個處理機，則這些可以并發(fā)執(zhí)行的程序便可被分配到多個處理機上，實現(xiàn)并行執(zhí)行，即利用每個處理機來處理一個可并發(fā)執(zhí)行的程序，這樣，多個程序便可同時執(zhí)行。,1.3.2 共享(Sharing) 在操作系統(tǒng)環(huán)境下，所謂共享是指系統(tǒng)中的資源可供內(nèi)存中多個并發(fā)執(zhí)行的進程(線程)共同使用。由于資源屬性的不同，進程對資源共享的方式也不同，目前主要有以下兩種資源共享方式。,1. 互斥共享方式 系統(tǒng)中的某些資源，如打印機、磁帶機，雖然它們可以提供給多個進程(線程)使用，但為使所打印或記錄的結(jié)果不致造成混淆，應(yīng)規(guī)定在一段時間內(nèi)只允許一個進程(線程)訪問該資源。為此，當一個進程A要訪問某資源時，必須先提出請求， 如果此時該資源空閑，系統(tǒng)便可將之分配給請求進程A使用， 此后若再有其它進程也要訪問該資源時(只要A未用完)則必須等待。 僅當A進程訪問完并釋放該資源后， 才允許另一進程對該資源進行訪問。我們把這種資源共享方式稱為互斥式共享，而把在一段時間內(nèi)只允許一個進程訪問的資源稱為臨界資源或獨占資源。 計算機系統(tǒng)中的大多數(shù)物理設(shè)備，以及某些軟件中所用的棧、變量和表格，都屬于臨界資源，它們要求被互斥地共享。,2. 同時訪問方式 系統(tǒng)中還有另一類資源，允許在一段時間內(nèi)由多個進程“同時”對它們進行訪問。這里所謂的“同時”往往是宏觀上的，而在微觀上，這些進程可能是交替地對該資源進行訪問。典型的可供多個進程“同時”訪問的資源是磁盤設(shè)備，一些用重入碼編寫的文件，也可以被“同時”共享，即若干個用戶同時訪問該文件。 并發(fā)和共享是操作系統(tǒng)的兩個最基本的特征，它們又是互為存在的條件。一方面，資源共享是以程序(進程)的并發(fā)執(zhí)行為條件的，若系統(tǒng)不允許程序并發(fā)執(zhí)行，自然不存在資源共享問題；另一方面，若系統(tǒng)不能對資源共享實施有效管理， 協(xié)調(diào)好諸進程對共享資源的訪問，也必然影響到程序并發(fā)執(zhí)行的程度，甚至根本無法并發(fā)執(zhí)行。,1.3.3 虛擬(Virtual) 操作系統(tǒng)中的所謂“虛擬”，是指通過某種技術(shù)把一個物理實體變?yōu)槿舾蓚€邏輯上的對應(yīng)物。物理實體(前者)是實的， 即實際存在的；而后者是虛的，是用戶感覺上的東西。相應(yīng)地，用于實現(xiàn)虛擬的技術(shù)，稱為虛擬技術(shù)。在OS中利用了多種虛擬技術(shù)，分別用來實現(xiàn)虛擬處理機、虛擬內(nèi)存、 虛擬外部設(shè)備和虛擬信道等。,在虛擬處理機技術(shù)中，是通過多道程序設(shè)計技術(shù)，讓多道程序并發(fā)執(zhí)行的方法，來分時使用一臺處理機的。此時， 雖然只有一臺處理機，但它能同時為多個用戶服務(wù)，使每個終端用戶都認為是有一個CPU在專門為他服務(wù)。亦即， 利用多道程序設(shè)計技術(shù)，把一臺物理上的CPU虛擬為多臺邏輯上的CPU，也稱為虛擬處理機，我們把用戶所感覺到的CPU稱為虛擬處理器。,類似地，可以通過虛擬存儲器技術(shù)，將一臺機器的物理存儲器變?yōu)樘摂M存儲器，以便從邏輯上來擴充存儲器的容量。此時，雖然物理內(nèi)存的容量可能不大(如32 MB)， 但它可以運行比它大得多的用戶程序(如128 MB)。這使用戶所感覺到的內(nèi)存容量比實際內(nèi)存容量大得多，認為該機器的內(nèi)存至少也有128 MB。當然這時用戶所感覺到的內(nèi)存容量是虛的。我們把用戶所感覺到的存儲器稱為虛擬存儲器。,我們還可以通過虛擬設(shè)備技術(shù)，將一臺物理I/O設(shè)備虛擬為多臺邏輯上的I/O設(shè)備，并允許每個用戶占用一臺邏輯上的I/O設(shè)備，這樣便可使原來僅允許在一段時間內(nèi)由一個用戶訪問的設(shè)備(即臨界資源)，變?yōu)樵谝欢螘r間內(nèi)允許多個用戶同時訪問的共享設(shè)備。例如，原來的打印機屬于臨界資源，而通過虛擬設(shè)備技術(shù)，可以把它變?yōu)槎嗯_邏輯上的打印機，供多個用戶“同時”打印。此外，也可以把一條物理信道虛擬為多條邏輯信道(虛信道)。在操作系統(tǒng)中，虛擬的實現(xiàn)主要是通過分時使用的方法。顯然，如果n是某物理設(shè)備所對應(yīng)的虛擬的邏輯設(shè)備數(shù)，則虛擬設(shè)備的平均速度必然是物理設(shè)備速度的1/n。,1.3.4 異步性(Asynchronism),在多道程序環(huán)境下，允許多個進程并發(fā)執(zhí)行， 但只有進程在獲得所需的資源后方能執(zhí)行。在單處理機環(huán)境下，由于系統(tǒng)中只有一個處理機，因而每次只允許一個進程執(zhí)行，其余進程只能等待。當正在執(zhí)行的進程提出某種資源要求時，如打印請求，而此時打印機正在為其它某進程打印，由于打印機屬于臨界資源，因此正在執(zhí)行的進程必須等待，且放棄處理機，直到打印機空閑，并再次把處理機分配給該進程時，該進程方能繼續(xù)執(zhí)行?？梢姡捎谫Y源等因素的限制，使進程的執(zhí)行通常都不是“一氣呵成”，而是以“停停走走”的方式運行。,內(nèi)存中的每個進程在何時能獲得處理機運行，何時又因提出某種資源請求而暫停，以及進程以怎樣的速度向前推進，每道程序總共需多少時間才能完成，等等，都是不可預(yù)知的。由于各用戶程序性能的不同，比如，有的側(cè)重于計算而較少需要I/O；而又有的程序其計算少而I/O多，這樣，很可能是先進入內(nèi)存的作業(yè)后完成； 而后進入內(nèi)存的作業(yè)先完成?；蛘哒f，進程是以人們不可預(yù)知的速度向前推進，此即進程的異步性。盡管如此，但只要運行環(huán)境相同，作業(yè)經(jīng)多次運行，都會獲得完全相同的結(jié)果。因此，異步運行方式是允許的，是操作系統(tǒng)的一個重要特征。,1.4 操作系統(tǒng)的主要功能,1.4.1 處理機管理功能,1. 進程控制 在傳統(tǒng)的多道程序環(huán)境下，要使作業(yè)運行，必須先為它創(chuàng)建一個或幾個進程，并為之分配必要的資源。當進程運行結(jié)束時，立即撤消該進程，以便能及時回收該進程所占用的各類資源。進程控制的主要功能是為作業(yè)創(chuàng)建進程、撤消已結(jié)束的進程，以及控制進程在運行過程中的狀態(tài)轉(zhuǎn)換。 在現(xiàn)代OS中，進程控制還應(yīng)具有為一個進程創(chuàng)建若干個線程的功能和撤消(終止)已完成任務(wù)的線程的功能。,2. 進程同步 為使多個進程能有條不紊地運行，系統(tǒng)中必須設(shè)置進程同步機制。進程同步的主要任務(wù)是為多個進程(含線程)的運行進行協(xié)調(diào)。有兩種協(xié)調(diào)方式： 進程互斥方式， 這是指諸進程(線程)在對臨界資源進行訪問時， 應(yīng)采用互斥方式； 進程同步方式，指在相互合作去完成共同任務(wù)的諸進程(線程)間，由同步機構(gòu)對它們的執(zhí)行次序加以協(xié)調(diào)。 為了實現(xiàn)進程同步，系統(tǒng)中必須設(shè)置進程同步機制。最簡單的用于實現(xiàn)進程互斥的機制，是為每一個臨界資源配置一把鎖W，當鎖打開時，進程(線程)可以對該臨界資源進行訪問；而當鎖關(guān)上時，則禁止進程(線程)訪問該臨界資源。,3. 進程通信 在多道程序環(huán)境下，為了加速應(yīng)用程序的運行，應(yīng)在系統(tǒng)中建立多個進程，并且再為一個進程建立若干個線程，由這些進程(線程)相互合作去完成一個共同的任務(wù)。而在這些進程(線程)之間，又往往需要交換信息。例如，有三個相互合作的進程， 它們是輸入進程、計算進程和打印進程。輸入進程負責將所輸入的數(shù)據(jù)傳送給計算進程；計算進程利用輸入數(shù)據(jù)進行計算， 并把計算結(jié)果傳送給打印進程；最后，由打印進程把計算結(jié)果打印出來。進程通信的任務(wù)就是用來實現(xiàn)在相互合作的進程之間的信息交換。 當相互合作的進程(線程)處于同一計算機系統(tǒng)時，通常在它們之前是采用直接通信方式，即由源進程利用發(fā)送命令直接將消息(message)掛到目標進程的消息隊列上，以后由目標進程利用接收命令從其消息隊列中取出消息。,4. 調(diào)度 在后備隊列上等待的每個作業(yè)，通常都要經(jīng)過調(diào)度才能執(zhí)行。在傳統(tǒng)的操作系統(tǒng)中，包括作業(yè)調(diào)度和進程調(diào)度兩步。作業(yè)調(diào)度的基本任務(wù)，是從后備隊列中按照一定的算法，選擇出若干個作業(yè)，為它們分配其必需的資源(首先是分配內(nèi)存)。 在將它們調(diào)入內(nèi)存后，便分別為它們建立進程，使它們都成為可能獲得處理機的就緒進程，并按照一定的算法將它們插入就緒隊列。而進程調(diào)度的任務(wù)，則是從進程的就緒隊列中選出一新進程，把處理機分配給它，并為它設(shè)置運行現(xiàn)場， 使進程投入執(zhí)行。值得提出的是，在多線程OS中，通常是把線程作為獨立運行和分配處理機的基本單位，為此，須把就緒線程排成一個隊列，每次調(diào)度時，是從就緒線程隊列中選出一個線程，把處理機分配給它。,1.4.2 存儲器管理功能,1. 內(nèi)存分配,OS在實現(xiàn)內(nèi)存分配時，可采取靜態(tài)和動態(tài)兩種方式。在靜態(tài)分配方式中，每個作業(yè)的內(nèi)存空間是在作業(yè)裝入時確定的；在作業(yè)裝入后的整個運行期間， 不允許該作業(yè)再申請新的內(nèi)存空間，也不允許作業(yè)在內(nèi)存中“移動”； 在動態(tài)分配方式中，每個作業(yè)所要求的基本內(nèi)存空間， 也是在裝入時確定的，但允許作業(yè)在運行過程中，繼續(xù)申請新的附加內(nèi)存空間，以適應(yīng)程序和數(shù)據(jù)的動態(tài)增漲，也允許作業(yè)在內(nèi)存中“移動”。,為了實現(xiàn)內(nèi)存分配，在內(nèi)存分配的機制中應(yīng)具有這樣的結(jié)構(gòu)和功能： 內(nèi)存分配數(shù)據(jù)結(jié)構(gòu)， 該結(jié)構(gòu)用于記錄內(nèi)存空間的使用情況， 作為內(nèi)存分配的依據(jù)； 內(nèi)存分配功能，系統(tǒng)按照一定的內(nèi)存分配算法， 為用戶程序分配內(nèi)存空間； 內(nèi)存回收功能，系統(tǒng)對于用戶不再需要的內(nèi)存，通過用戶的釋放請求，去完成系統(tǒng)的回收功能。,2. 內(nèi)存保護 內(nèi)存保護的主要任務(wù)，是確保每道用戶程序都只在自己的內(nèi)存空間內(nèi)運行，彼此互不干擾。 為了確保每道程序都只在自己的內(nèi)存區(qū)中運行，必須設(shè)置內(nèi)存保護機制。一種比較簡單的內(nèi)存保護機制，是設(shè)置兩個界限寄存器，分別用于存放正在執(zhí)行程序的上界和下界。系統(tǒng)須對每條指令所要訪問的地址進行檢查，如果發(fā)生越界，便發(fā)出越界中斷請求，以停止該程序的執(zhí)行。如果這種檢查完全用軟件實現(xiàn)，則每執(zhí)行一條指令，便須增加若干條指令去進行越界檢查，這將顯著降低程序的運行速度。因此，越界檢查都由硬件實現(xiàn)。當然， 對發(fā)生越界后的處理， 還須與軟件配合來完成。,3. 地址映射 一個應(yīng)用程序(源程序)經(jīng)編譯后，通常會形成若干個目標程序；這些目標程序再經(jīng)過鏈接便形成了可裝入程序。這些程序的地址都是從“0”開始的，程序中的其它地址都是相對于起始地址計算的； 由這些地址所形成的地址范圍稱為“地址空間”， 其中的地址稱為“邏輯地址”或“相對地址”。此外，由內(nèi)存中的一系列單元所限定的地址范圍稱為“內(nèi)存空間”， 其中的地址稱為“物理地址”。 在多道程序環(huán)境下，每道程序不可能都從“0”地址開始裝入(內(nèi)存)， 這就致使地址空間內(nèi)的邏輯地址和內(nèi)存空間中的物理地址不相一致。使程序能正確運行，存儲器管理必須提供地址映射功能，以將地址空間中的邏輯地址轉(zhuǎn)換為內(nèi)存空間中與之對應(yīng)的物理地址。該功能應(yīng)在硬件的支持下完成。,4. 內(nèi)存擴充 存儲器管理中的內(nèi)存擴充任務(wù)，并非是去擴大物理內(nèi)存的容量，而是借助于虛擬存儲技術(shù)，從邏輯上去擴充內(nèi)存容量，使用戶所感覺到的內(nèi)存容量比實際內(nèi)存容量大得多； 或者是讓更多的用戶程序能并發(fā)運行。這樣，既滿足了用戶的需要，改善了系統(tǒng)的性能，又基本上不增加硬件投資。 為了能在邏輯上擴充內(nèi)存，系統(tǒng)必須具有內(nèi)存擴充機制， 用于實現(xiàn)下述各功能： (1) 請求調(diào)入功能。 (2) 置換功能。,1.4.3 設(shè)備管理功能 設(shè)備管理用于管理計算機系統(tǒng)中所有的外圍設(shè)備， 而設(shè)備管理的主要任務(wù)是，完成用戶進程提出的I/O請求； 為用戶進程分配其所需的I/O設(shè)備；提高CPU和I/O設(shè)備的利用率；提高I/O速度；方便用戶使用I/O設(shè)備。為實現(xiàn)上述任務(wù)，設(shè)備管理應(yīng)具有緩沖管理、設(shè)備分配和設(shè)備處理，以及虛擬設(shè)備等功能。,1. 緩沖管理 CPU運行的高速性和I/O低速性間的矛盾自計算機誕生時起便已存在。 而隨著CPU速度迅速、大幅度的提高，使得此矛盾更為突出，嚴重降低了CPU的利用率。如果在I/O設(shè)備和CPU之間引入緩沖，則可有效地緩和CPU和I/O設(shè)備速度不匹配的矛盾，提高CPU的利用率，進而提高系統(tǒng)吞吐量。 因此，在現(xiàn)代計算機系統(tǒng)中， 都毫無例外地在內(nèi)存中設(shè)置了緩沖區(qū)，而且還可通過增加緩沖區(qū)容量的方法，來改善系統(tǒng)的性能。 最常見的緩沖區(qū)機制有單緩沖機制、能實現(xiàn)雙向同時傳送數(shù)據(jù)的雙緩沖機制，以及能供多個設(shè)備同時使用的公用緩沖池機制。,2. 設(shè)備分配 設(shè)備分配的基本任務(wù)，是根據(jù)用戶進程的I/O請求、系統(tǒng)的現(xiàn)有資源情況以及按照某種設(shè)備分配策略，為之分配其所需的設(shè)備。如果在I/O設(shè)備和CPU之間，還存在著設(shè)備控制器和I/O通道時，還須為分配出去的設(shè)備分配相應(yīng)的控制器和通道。 為了實現(xiàn)設(shè)備分配，系統(tǒng)中應(yīng)設(shè)置設(shè)備控制表、控制器控制表等數(shù)據(jù)結(jié)構(gòu)，用于記錄設(shè)備及控制器的標識符和狀態(tài)。據(jù)這些表格可以了解指定設(shè)備當前是否可用，是否忙碌，以供進行設(shè)備分配時參考。在進行設(shè)備分配時，應(yīng)針對不同的設(shè)備類型而采用不同的設(shè)備分配方式。對于獨占設(shè)備(臨界資源)的分配，還應(yīng)考慮到該設(shè)備被分配出去后，系統(tǒng)是否安全。 設(shè)備使用完后，還應(yīng)立即由系統(tǒng)回收。,3. 設(shè)備處理 設(shè)備處理程序又稱為設(shè)備驅(qū)動程序。其基本任務(wù)是用于實現(xiàn)CPU和設(shè)備控制器之間的通信，即由CPU向設(shè)備控制器發(fā)出I/O命令，要求它完成指定的I/O操作；反之由CPU接收從控制器發(fā)來的中斷請求，并給予迅速的響應(yīng)和相應(yīng)的處理。 處理過程是：設(shè)備處理程序首先檢查I/O請求的合法性，了解設(shè)備狀態(tài)是否是空閑的，了解有關(guān)的傳遞參數(shù)及設(shè)置設(shè)備的工作方式。然后，便向設(shè)備控制器發(fā)出I/O命令，啟動I/O設(shè)備去完成指定的I/O操作。設(shè)備驅(qū)動程序還應(yīng)能及時響應(yīng)由控制器發(fā)來的中斷請求，并根據(jù)該中斷請求的類型，調(diào)用相應(yīng)的中斷處理程序進行處理。對于設(shè)置了通道的計算機系統(tǒng)， 設(shè)備處理程序還應(yīng)能根據(jù)用戶的I/O請求，自動地構(gòu)成通道程序。,1.4.4 文件管理功能,1. 文件存儲空間的管理 由文件系統(tǒng)對諸多文件及文件的存儲空間，實施統(tǒng)一的管理。其主要任務(wù)是為每個文件分配必要的外存空間，提高外存的利用率，并能有助于提高文件系統(tǒng)的運行速度。 為此，系統(tǒng)應(yīng)設(shè)置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用于記錄文件存儲空間的使用情況，以供分配存儲空間時參考；系統(tǒng)還應(yīng)具有對存儲空間進行分配和回收的功能。為了提高存儲空間的利用率，對存儲空間的分配，通常是采用離散分配方式，以減少外存零頭，并以盤塊為基本分配單位。盤塊的大小通常為512 B8 KB。,2. 目錄管理 為了使用戶能方便地在外存上找到自己所需的文件，通常由系統(tǒng)為每個文件建立一個目錄項。目錄項包括文件名、文件屬性、文件在磁盤上的物理位置等。由若干個目錄項又可構(gòu)成一個目錄文件。目錄管理的主要任務(wù)， 是為每個文件建立其目錄項，并對眾多的目錄項加以有效的組織，以實現(xiàn)方便的按名存取。即用戶只須提供文件名， 即可對該文件進行存取。其次，目錄管理還應(yīng)能實現(xiàn)文件共享，這樣，只須在外存上保留一份該共享文件的副本。此外，還應(yīng)能提供快速的目錄查詢手段，以提高對文件的檢索速度。,3. 文件的讀/寫管理和保護 (1) 文件的讀/寫管理。該功能是根據(jù)用戶的請求，從外存中讀取數(shù)據(jù)；或?qū)?shù)據(jù)寫入外存。在進行文件讀(寫)時，系統(tǒng)先根據(jù)用戶給出的文件名，去檢索文件目錄，從中獲得文件在外存中的位置。然后，利用文件讀(寫)指針，對文件進行讀(寫)。一旦讀(寫)完成，便修改讀(寫)指針，為下一次讀(寫)做好準備。由于讀和寫操作不會同時進行，故可合用一個讀/寫指針。 (2) 文件保護。 防止未經(jīng)核準的用戶存取文件； 防止冒名頂替存取文件； 防止以不正確的方式使用文件。,1.4.5 用戶接口,1. 命令接口,(1) 聯(lián)機用戶接口。這是為聯(lián)機用戶提供的，它由一組鍵盤操作命令及命令解釋程序所組成。當用戶在終端或控制臺上每鍵入一條命令后，系統(tǒng)便立即轉(zhuǎn)入命令解釋程序，對該命令加以解釋并執(zhí)行該命令。在完成指定功能后，控制又返回到終端或控制臺上，等待用戶鍵入下一條命令。這樣，用戶可通過先后鍵入不同命令的方式，來實現(xiàn)對作業(yè)的控制，直至作業(yè)完成。,(2) 脫機用戶接口。該接口是為批處理作業(yè)的用戶提供的，故也稱為批處理用戶接口。該接口由一組作業(yè)控制語言JCL組成。批處理作業(yè)的用戶不能直接與自己的作業(yè)交互作用，只能委托系統(tǒng)代替用戶對作業(yè)進行控制和干預(yù)。這里的作業(yè)控制語言JCL便是提供給批處理作業(yè)用戶的、為實現(xiàn)所需功能而委托系統(tǒng)代為控制的一種語言。用戶用JCL把需要對作業(yè)進行的控制和干預(yù)，事先寫在作業(yè)說明書上，然后將作業(yè)連同作業(yè)說明書一起提供給系統(tǒng)。當系統(tǒng)調(diào)度到該作業(yè)運行時，又調(diào)用命令解釋程序，對作業(yè)說明書上的命令，逐條地解釋執(zhí)行。如果作業(yè)在執(zhí)行過程中出現(xiàn)異常現(xiàn)象，系統(tǒng)也將根據(jù)作業(yè)說明書上的指示進行干預(yù)。這樣，作業(yè)一直在作業(yè)說明書的控制下運行，直至遇到作業(yè)結(jié)束語句時，系統(tǒng)才停止該作業(yè)的運行。,2. 程序接口 該接口是為用戶程序在執(zhí)行中訪問系統(tǒng)資源而設(shè)置的，是用戶程序取得操作系統(tǒng)服務(wù)的惟一途徑。它是由一組系統(tǒng)調(diào)用組成，每一個系統(tǒng)調(diào)用都是一個能完成特定功能的子程序，每當應(yīng)用程序要求OS提供某種服務(wù)(功能)時，便調(diào)用具有相應(yīng)功能的系統(tǒng)調(diào)用。早期的系統(tǒng)調(diào)用都是用匯編語言提供的，只有在用匯編語言書寫的程序中，才能直接使用系統(tǒng)調(diào)用；但在高級語言以及C語言中，往往提供了與各系統(tǒng)調(diào)用一一對應(yīng)的庫函數(shù)，這樣，應(yīng)用程序便可通過調(diào)用對應(yīng)的庫函數(shù)來使用系統(tǒng)調(diào)用。但在近幾年所推出的操作系統(tǒng)中，如UNIX、OS/2版本中，其系統(tǒng)調(diào)用本身已經(jīng)采用C語言編寫，并以函數(shù)形式提供，故在用C語言編制的程序中， 可直接使用系統(tǒng)調(diào)用。,3. 圖形接口 用戶雖然可以通過聯(lián)機用戶接口來取得OS的服務(wù)，但這時要求用戶能熟記各種命令的名字和格式，并嚴格按照規(guī)定的格式輸入命令，這既不方便又花時間，于是，圖形用戶接口便應(yīng)運而生。圖形用戶接口采用了圖形化的操作界面， 用非常容易識別的各種圖標(icon)來將系統(tǒng)的各項功能、各種應(yīng)用程序和文件，直觀、逼真地表示出來。用戶可用鼠標或通過菜單和對話框，來完成對應(yīng)用程序和文件的操作。此時用戶已完全不必像使用命令接口那樣去記住命令名及格式，從而把用戶從繁瑣且單調(diào)的操作中解脫出來。,1.5 操作系統(tǒng)的結(jié)構(gòu)設(shè)計,1.5.1 軟件工程的基本概念,1. 軟件的含義 所謂軟件，是指當計算機運行時，能提供所要求的功能和性能的指令和程序的集合，該程序能夠正確地處理信息的數(shù)據(jù)結(jié)構(gòu)；作為規(guī)范軟件，還應(yīng)具有描述程序功能需求以及程序如何操作使用的文檔。如果說，硬件是物理部件， 那么，軟件則是一種邏輯部件，它具有與硬件完全不同的特點。,2. 軟件工程的含義 軟件工程是指運用系統(tǒng)的、規(guī)范的和可定量的方法，來開發(fā)、運行和維護軟件；或者說，是采用工程的概念、 原理、 技術(shù)和方法，來開發(fā)與維護軟件， 其目的是為了解決在軟件開發(fā)中所出現(xiàn)的編程隨意、軟件質(zhì)量不可保證以及維護困難等問題。,1.5.2 傳統(tǒng)的操作系統(tǒng)結(jié)構(gòu) 操作系統(tǒng)是一個十分復(fù)雜的大型軟件。為了控制該軟件的復(fù)雜性，在開發(fā)OS時，先后引入了分解、模塊化、 抽象和隱蔽等方法。開發(fā)方法的不斷發(fā)展，促進了OS結(jié)構(gòu)的更新?lián)Q代。這里，我們把第一代至第三代的OS結(jié)構(gòu)， 稱為傳統(tǒng)的OS結(jié)構(gòu)，而把微內(nèi)核的OS結(jié)構(gòu)稱為現(xiàn)代OS結(jié)構(gòu)。,1. 無結(jié)構(gòu)操作系統(tǒng) 在早期開發(fā)操作系統(tǒng)時，設(shè)計者只是把他的注意力放在功能的實現(xiàn)和獲得高的效率上，缺乏首尾一致的設(shè)計思想。 此時的OS是為數(shù)眾多的一組過程的集合，各過程之間可以相互調(diào)用，在操作系統(tǒng)內(nèi)部不存在任何結(jié)構(gòu)，因此，這種OS是無結(jié)構(gòu)的，也有人把它稱為整體系統(tǒng)結(jié)構(gòu)。 此時程序設(shè)計的技巧，只是如何編制緊湊的程序，以便于有效地利用內(nèi)存、對GOTO語句的使用不加任何限制，所設(shè)計出的操作系統(tǒng)既龐大又雜亂，缺乏清晰的程序結(jié)構(gòu)。這一方面會使所編制出的程序錯誤很多，給調(diào)試工作帶來很多困難；另一方面也使程序難以閱讀和理解，增加了維護人員的負擔。,2. 模塊化OS結(jié)構(gòu) 1) 模塊化結(jié)構(gòu) 模塊化程序設(shè)計技術(shù)，是最早(20世紀60年代)出現(xiàn)的一種程序設(shè)計技術(shù)。該技術(shù)是基于“分解”和“模塊化”原則來控制大型軟件的復(fù)雜度的。為使OS具有較清晰的結(jié)構(gòu)，OS不再是由眾多的過程直接構(gòu)成，而是將OS按其功能劃分為若干個具有一定獨立性和大小的模塊。每個模塊具有某方面的管理功能，如進程管理模塊、存儲器管理模塊、I/O設(shè)備管理模塊和文件管理模塊等，并規(guī)定好各模塊間的接口， 使各模塊之間能通過該接口實現(xiàn)交互，然后再進一步將各模塊細分為若干個具有一定管理功能的子模塊，如把進程管理模塊又分為進程控制、 進程同步、 進程通信和進程調(diào)度等子模塊， 同樣也要規(guī)定各子模塊之間的接口。若子模塊較大時，再進一步將它細分。圖 1-5 示出了由模塊、子模塊等組成的模塊化OS結(jié)構(gòu)。,圖 1-5 模塊化操作系統(tǒng)結(jié)構(gòu),2) 模塊化OS的優(yōu)缺點 提高了OS設(shè)計的正確性、 可理解性和可維護性。 (2) 增強了OS的可適應(yīng)性。 (3) 加速了OS的開發(fā)過程。,模塊化結(jié)構(gòu)設(shè)計的缺點有二。首先，在開始設(shè)計OS時，對模塊的劃分及對接口的規(guī)定并不精確， 而且還可能存在錯誤，因而很難保證按此規(guī)定所設(shè)計出的模塊會完全正確， 這將使在把這些模塊裝配成OS時發(fā)生困難；其次，從功能觀點來劃分模塊時，未能將共享資源和獨占資源加以區(qū)別； 由于管理上的差異，又會使模塊間存在著復(fù)雜的依賴關(guān)系使OS結(jié)構(gòu)變得不清晰。,3. 分層式OS結(jié)構(gòu),1) 有序分層的基本概念 從改進設(shè)計方式上說，應(yīng)使我們的每一步設(shè)計都是建立在可靠的基礎(chǔ)上。我們可以從物理機器開始， 在其上面先添加一層具有一定功能的軟件A1, 由于A1是建立在完全確定的物理機器上的，在經(jīng)過精心設(shè)計和幾乎是窮盡無遺的測試后，可以認為A1是正確的；然后再在A1上添加一層新軟件A2，如此一層一層地自底向上增添軟件層，每一層都實現(xiàn)若干功能，最后總能構(gòu)成一個能滿足需要的OS。,分層式結(jié)構(gòu)設(shè)計的基本原則是：每一層都僅使用其底層所提供的功能和服務(wù)，這樣可使系統(tǒng)的調(diào)試和驗證都變得容易， 例如，在調(diào)試第一層軟件A1時，由于它只使用了物理機器提供的功能，因此它將與其所有的高層軟件A2，An無關(guān)； 同樣在調(diào)試A2時，它也只使用了A1和物理機器所提供的功能， 而與其高層軟件A3, ，An無關(guān)，這樣，一旦發(fā)現(xiàn)Ai出現(xiàn)錯誤時，通常該錯誤只會局限于Ai，因為它與所有其高層的軟件無關(guān)，而Ai層以下的各層軟件，又都經(jīng)過仔細的調(diào)試。,2) 層次的設(shè)置 (1) 程序嵌套。 通常OS的每個功能的實現(xiàn)， 并非是只用一個程序便能完成的，而是要經(jīng)由若干個軟件層才有可能完成。因此在劃分OS層次時，首先要考慮在實現(xiàn)OS 的每個功能時所形成的程序嵌套。例如，作業(yè)調(diào)度模塊須調(diào)用進程控制模塊；在為某作業(yè)創(chuàng)建一進程時，進程控制模塊又須調(diào)用內(nèi)存管理模塊為新進程分配內(nèi)存空間，可見，進程控制模塊應(yīng)在內(nèi)存管理模塊之上； 而作業(yè)調(diào)度模塊又應(yīng)在更高層。,(2) 運行頻率。在分層結(jié)構(gòu)中，各層次軟件的運行速度是不同的，因為A1層軟件能直接在物理機器上運行， 故它有最高的運行速度。隨著層次的增高，其相應(yīng)軟件的運行速度就隨之下降，因而An層軟件的運行速度最低。 為了提高OS的運行效率，應(yīng)該將那些經(jīng)?；钴S的模塊放在最接近硬件的A1層，如時鐘管理、進程調(diào)度，通常都放在A1層。,(3) 公用模塊。應(yīng)把供多種資源管程程序調(diào)用的公用模塊， 設(shè)置在最低層，不然，會使比它低的層次模塊由于無法調(diào)用它而須另外配置相應(yīng)功能的模塊。例如，用于對信號量進行操作的原語Signal和Wait。 (4) 用戶接口。為方便用戶(程序)，OS向用戶提供了“用戶與OS的接口”，如命令接口、程序接口以及圖形用戶接口。這些接口應(yīng)設(shè)置在OS的最高層，直接提供給用戶使用。,1.5.3 微內(nèi)核OS結(jié)構(gòu),1. 客戶/服務(wù)器模式(Client-Server Model) 1) 基本概念 為了提高OS的靈活性和可擴充性而將OS劃分為兩部分， 一部分是用于提供各種服務(wù)的一組服務(wù)器(進程)，如用于提供進程管理的進程服務(wù)器、提供存儲器管理的存儲器服務(wù)器提供文件管理的文件服務(wù)器等，所有這些服務(wù)器(進程)都運行在用戶態(tài)。 當有一用戶進程(現(xiàn)在稱為客戶進程)要求讀文件的一個盤塊時，該進程便向文件服務(wù)器(進程)發(fā)出一個請求；當服務(wù)器完成了該客戶的請求后，便給該客戶回送一個響應(yīng)。 操作系統(tǒng)的另一部分是內(nèi)核，用來處理客戶和服務(wù)器之間的通信， 即由內(nèi)核來接收客戶的請求，再將該請求送至相應(yīng)的服務(wù)器；同時它也接收服務(wù)器的應(yīng)答， 并將此應(yīng)答回送給請求客戶。 此外，在內(nèi)核中還應(yīng)具有其它一些機構(gòu)，用于實現(xiàn)與硬件緊密相關(guān)的和一些較基本的功能。,圖 1-6 單機環(huán)境下的客戶/服務(wù)器模式,2) 客戶/服務(wù)器模式的優(yōu)點 提高了系統(tǒng)的靈活性和可擴充性。 (2) 提高了OS的可靠性。 (3) 可運行于分布式系統(tǒng)中。,2. 面向?qū)ο蟮某绦蛟O(shè)計技術(shù)(Object-Orientated Programming),1) 面向?qū)ο蠹夹g(shù)的基本概念 面向?qū)ο蠹夹g(shù)是20世紀80年代初提出并很快流行起來的。該技術(shù)是基于“抽象”和“隱蔽”原則來控制大型軟件的復(fù)雜度的。所謂對象，是指在現(xiàn)實世界中具有相同屬性、服從相同規(guī)則的一系列事物的抽象，而把其中的具體事物稱為對象的實例。OS中的各類實體如進程、線程、消息、存儲器等，都使用了對象這一概念，相應(yīng)地，便有進程對象線程對象、 存儲器對象等。,圖 1-7 一個對象的示意圖,2) 面向?qū)ο蠹夹g(shù)的優(yōu)點 (1) 可修改性和可擴充性。由于隱蔽了表示實體的數(shù)據(jù)和操作，因而可以改變對象的表示而不會影響其它部分， 從而可以方便地改變老的對象和增加新的對象。 (2) 繼承性。繼承性是面向?qū)ο蠹夹g(shù)所具有的重要特性。繼承性是指子對象可以繼承父對象的屬性，這樣，在創(chuàng)建一個新的對象時， 便可減少大量的時空開銷。 (3) 正確性和可靠性。由于對象是構(gòu)成操作系統(tǒng)的基本單元，可以獨立地對它進行測試，這樣，比較易于保證其正確性和可靠性，從而比較容易保證整個系統(tǒng)的正確性和可靠性。,3. 微內(nèi)核技術(shù) 微內(nèi)核技術(shù)的引入,所謂微內(nèi)核技術(shù)，是指精心設(shè)計的、能實現(xiàn)現(xiàn)代OS核心功能的小型內(nèi)核，它與一般的OS(程序)不同， 它更小更精煉，它不僅運行在核心態(tài)，而且開機后常駐內(nèi)存， 它不會因內(nèi)存緊張而被換出內(nèi)存。微內(nèi)核并非是一個完整的OS， 而只是為構(gòu)建通用OS提供一個重要基礎(chǔ)。由于在微內(nèi)核OS結(jié)構(gòu)中，通常都采用了客戶/服務(wù)器模式，因此OS的大部分功能和服務(wù)，都是由若干服務(wù)器來提供的， 如文件服務(wù)器、作業(yè)服務(wù)器和網(wǎng)絡(luò)服務(wù)器等。,2) 微內(nèi)核的基本功能 微內(nèi)核所提供的功能，通常都是一些最基本的功能，如進程管理、存儲器管理、進程間通信、 低級I/O功能。 (1) 進程管理。 (2) 存儲器管理。 (3) 進程通信管理。 (4) I/O設(shè)備管理。,第二章 進程管理,2.1 進程的基本概念 2.2 進程控制 2.3 進程同步 2.4 經(jīng)典進程的同步問題 2.5 管程機制 2.6 進程通信 2.7 線程,2.1 進程的基本概念,2.1.1 程序的順序執(zhí)行及其特征,1. 程序的順序執(zhí)行 僅當前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。例如，在進行計算時，總須先輸入用戶的程序和數(shù)據(jù)，然后進行計算，最后才能打印計算結(jié)果。 S1: a=x+y; S2: b=a-5; S3: c=b+1;,圖 2-1 程序的順序執(zhí)行,2. 程序順序執(zhí)行時的特征,順序性： (2) 封閉性： (3) 可再現(xiàn)性：,2.1.2 前趨圖,前趨圖(Precedence Graph)是一個有向無循環(huán)圖，記為DAG(Directed Acyclic Graph)，用于描述進程之間執(zhí)行的前后關(guān)系。圖中的每個結(jié)點可用于描述一個程序段或進程，乃至一條語句；結(jié)點間的有向邊則用于表示兩個結(jié)點之間存在的偏序(Partial Order)或前趨關(guān)系(Precedence Relation)“”。 =(Pi, Pj)|Pi must complete before Pj may start, 如果(Pi, Pj),可寫成PiPj，稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。在前趨圖中，把沒有前趨的結(jié)點稱為初始結(jié)點(Initial Node)，把沒有后繼的結(jié)點稱為終止結(jié)點(Final Node)。,每個結(jié)點還具有一個重量(Weight)，用于表示該結(jié)點所含有的程序量或結(jié)點的執(zhí)行時間。,IiCiPi和S1S2S3,圖 2-2 前趨圖,對于圖 2-2(a)所示的前趨圖， 存在下述前趨關(guān)系：,P1P2, P1P3, P1P4, P2P5, P3P5, P4P6, P4P7, P5P8, P6P8, P7P9, P8P9 或表示為： P=P1, P2, P3, P4, P5, P6, P7, P8, P9 = (P1, P2), (P1, P3), (P1, P4), (P2, P5), (P3, P5), (P4, P6), (P4, P7), (P5, P8), (P6, P8), (P7, P9), (P8, P9) 應(yīng)當注意，前趨圖中必須不存在循環(huán)，但在圖2-2(b)中卻有著下述的前趨關(guān)系： S2S3, S3S2,2.1.3 程序的并發(fā)執(zhí)行及其特征,1. 程序的并發(fā)執(zhí)行,圖 2-3 并發(fā)執(zhí)行時的前趨圖,在該例中存在下述前趨關(guān)系： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+1 而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之間，可以并發(fā)執(zhí)行。 對于具有下述四條語句的程序段： S1: a=x+2 S2: b=y+4 S3: c=a+b S4: d=c+b,圖 2-4 四條語句的前趨關(guān)系,2. 程序并發(fā)執(zhí)行時的特征,間斷性 2) 失去封閉性 3) 不可再現(xiàn)性,例如，有兩個循環(huán)程序A和B，它們共享一個變量N。程序A每執(zhí)行一次時，都要做N=N+1操作；程序B每執(zhí)行一次時， 都要執(zhí)行Print(N)操作，然后再將N置成“0”。程序A和B以不同的速度運行。 (1) N=N+1在Print(N)和N=0之前，此時得到的N值分別為n+1, n+1, 0。 (2) N=N+1在Print(N)和N=0之后，此時得到的N值分別為n, 0, 1。 (3) N=N+1在Print(N)和N=0之間，此時得到的N值分別為n, n+1, 0。,2.1.4 進程的特征與狀態(tài),1. 進程的特征和定義,結(jié)構(gòu)特征 2) 動態(tài)性 3) 并發(fā)性 4) 獨立性 5) 異步性,較典型的進程定義有： (1) 進程是程序的一次執(zhí)行。 (2) 進程是一個程序及其數(shù)據(jù)在處理機上順序執(zhí)行時所發(fā)生的活動。 (3) 進程是程序在一個數(shù)據(jù)集合上運行的過程，它是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。 在引入了進程實體的概念后，我們可以把傳統(tǒng)OS中的進程定義為：“進程是進程實體的運行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位”。,2. 進程的三種基本狀態(tài),就緒(Ready)狀態(tài) 2) 執(zhí)行狀態(tài) 3) 阻塞狀態(tài),圖 2-5 進程的三種基本狀態(tài)及其轉(zhuǎn)換,3. 掛起狀態(tài) 引入掛起狀態(tài)的原因 終端用戶的請求。 (2) 父進程請求。 (3) 負荷調(diào)節(jié)的需要。 (4) 操作系統(tǒng)的需要。,2) 進程狀態(tài)的轉(zhuǎn)換,活動就緒靜止就緒。 (2) 活動阻塞靜止阻塞。 (3) 靜止就緒活動就緒。 (4) 靜止阻塞活動阻塞。,圖 2-6 具有掛起狀態(tài)的進程狀態(tài)圖,2.1.5 進程控制塊,1. 進程控制塊的作用,進程控制塊的作用是使一個在多道程序環(huán)境下不能獨立運行的程序(含數(shù)據(jù))，成為一個能獨立運行的基本單位，一個能與其它進程并發(fā)執(zhí)行的進程。或者說，OS是根據(jù)PCB來對并發(fā)執(zhí)行的進程進行控制和管理的。,2. 進程控制塊中的信息,1) 進程標識符 進程標識符用于惟一地標識一個進程。一個進程通常有兩種標識符： (1) 內(nèi)部標識符。在所有的操作系統(tǒng)中，都為每一個進 程賦予一個惟一的數(shù)字標識符，它通常是一個進程的序號。 設(shè)置內(nèi)部標識符主要是為了方便系統(tǒng)使用。 (2) 外部標識符。它由創(chuàng)建者提供，通常是由字母、數(shù)字組成，往往是由用戶(進程)在訪問該進程時使用。為了描述進程的家族關(guān)系， 還應(yīng)設(shè)置父進程標識及子進程標識。此外，還可設(shè)置用戶標識，以指示擁有該進程的用戶。,2) 處理機狀態(tài) 處理機狀態(tài)信息主要是由處理機的各種寄存器中的內(nèi)容組成的。 通用寄存器，又稱為用戶可視寄存器，它們是用戶程序可以訪問的，用于暫存信息， 在大多數(shù)處理機中，有 832 個通用寄存器，在RISC結(jié)構(gòu)的計算機中可超過 100 個； 指令計數(shù)器，其中存放了要訪問的下一條指令的地址； 程序狀態(tài)字PSW，其中含有狀態(tài)信息，如條件碼、執(zhí)行方式、 中斷屏蔽標志等； 用戶棧指針， 指每個用戶進程都有一個或若干個與之相關(guān)的系統(tǒng)棧，用于存放過程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址。棧指針指向該棧的棧頂。,3) 進程調(diào)度信息 在PCB中還存放一些與進程調(diào)度和進程對換有關(guān)的信息，包括： 進程狀態(tài)，指明進程的當前狀態(tài)， 作為進程調(diào)度和對換時的依據(jù)； 進程優(yōu)先級，用于描述進程使用處理機的優(yōu)先級別的一個整數(shù)， 優(yōu)先級高的進程應(yīng)優(yōu)先獲得處理機； 進程調(diào)度所需的其它信息，它們與所采用的進程調(diào)度算法有關(guān)，比如，進程已等待CPU的時間總和、 進程已執(zhí)行的時間總和等； 事件，是指進程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件，即阻塞原因。,4) 進程控制信息 進程控制信息包括： 程序和數(shù)據(jù)的地址， 是指進程的程序和數(shù)據(jù)所在的內(nèi)存或外存地(首)址，以便再調(diào)度到該進程執(zhí)行時，能從PCB中找到其程序和數(shù)據(jù)； 進程同步和通信機制，指實現(xiàn)進程同步和進程通信時必需的機制， 如消息隊列指針、信號量等，它們可能全部或部分地放在PCB中； 資源清單，是一張列出了除CPU以外的、進程所需的全部資源及已經(jīng)分配到該進程的資源的清單； 鏈接指針， 它給出了本進程(PCB)所在隊列中的下一個進程的PCB的首地址。,3. 進程控制塊的組織方式,1) 鏈接方式,圖 2-7 PCB鏈接隊列示意圖,2) 索引方式,圖 2-8 按索引方式組織PCB,2.2 進 程 控 制,2.2.1 進程的創(chuàng)建,1. 進程圖(Process Graph),圖 2-9 進程樹,2. 引起創(chuàng)建進程的事件,用戶登錄。 (2) 作業(yè)調(diào)度。 (3) 提供服務(wù)。 (4) 應(yīng)用請求。,3. 進程的創(chuàng)建(Creation of Progress),(1)申請空白PCB。 (2) 為新進程分配資源。 (3) 初始化進程控制塊。 (4) 將新進程插入就緒隊列，如果進程就緒隊列能夠接納新進程， 便將新進程插入就緒隊列。,2.2.2 進