2017考研計算機沖刺課程操作系統(tǒng)

操作系統(tǒng)1孫衛(wèi)真optsys2001@沖刺班輔導(dǎo)材料第一章 操作系統(tǒng)概述2操作系統(tǒng)的概念、特征、功能和提供的服務(wù)操作系統(tǒng)的發(fā)展與分類操作系統(tǒng)的運行環(huán)境內(nèi)核態(tài)與用戶態(tài)中斷、異常系統(tǒng)調(diào)用操作系統(tǒng)體系結(jié)構(gòu)大綱要求操作系統(tǒng)的概念3OS作為用戶與計算機硬件系統(tǒng)之間的接口OS作為計算機系統(tǒng)資源的管理者OS用作擴展機、虛擬機人機接口主要形式：系統(tǒng)調(diào)用（System

Call）命令輸入（命令行、GUI、NUI）選擇2015-23處理外部中斷時，應(yīng)該由操作系統(tǒng)保存的是A.

程序計數(shù)器(PC)的內(nèi)容B.通用寄存器的內(nèi)容C.快表(TLB)中的內(nèi)容D.

Cache中的內(nèi)容4操作系統(tǒng)的基本特性5并發(fā)(Concurrence)—最基本的特征！并行性和并發(fā)性是既相似又有區(qū)別的兩個概念，并行性是指兩個或多個事件在同一時刻發(fā)生；而并發(fā)性是指兩個或多個事件在同一時間間隔內(nèi)發(fā)生共享(Sharing)在操作系統(tǒng)環(huán)境下，所謂共享是指系統(tǒng)中的資源可供內(nèi)存中多個并發(fā)執(zhí)行的進程(線程)共同使用操作系統(tǒng)的基本特性6虛擬(Virtual)操作系統(tǒng)中的所謂“虛擬”，是指通過某種技術(shù)把一個物理實體變?yōu)槿舾蓚€邏輯上的對應(yīng)物異步性(Asynchronism)在多道程序環(huán)境下，多個進程是以“停停走走”的方式運行失去封閉性選擇2016-24．某單CPU系統(tǒng)中有輸入和輸出設(shè)備各1臺，現(xiàn)有3個并發(fā)執(zhí)行的作業(yè)，每個作業(yè)的輸入、計算和輸出時間均分別為2

ms、3ms和4ms，且都按輸入、計算和輸出的順序執(zhí)行，則執(zhí)行完3個作業(yè)需要的時間最少是A．15msB．17msC．22

msD．27

ms7操作系統(tǒng)的發(fā)展過程無操作系統(tǒng)的計算機系統(tǒng)人工操作方式脫機輸入/輸出(Off-Line

I/O)方式單道批處理系統(tǒng)多道批處理系統(tǒng)分時系統(tǒng)實時系統(tǒng)8選擇2016-23．下列關(guān)于批處理系統(tǒng)的敘述中，正確的是Ⅰ．批處理系統(tǒng)允許多個用戶與計算機直接交互Ⅱ．批處理系統(tǒng)分為單道批處理系統(tǒng)和多道批處理系統(tǒng)Ⅲ．中斷技術(shù)使得多道批處理系統(tǒng)的I/O設(shè)備可與CPU并行工作A．僅Ⅱ、ⅢC．僅Ⅰ、ⅡB．僅Ⅱ

D．僅Ⅰ、Ⅲ9操作系統(tǒng)的運行環(huán)境內(nèi)核態(tài)與用戶態(tài)中斷、異常系統(tǒng)調(diào)用10內(nèi)核態(tài)與用戶態(tài)11內(nèi)核態(tài)與用戶態(tài)是指進程（線程）在執(zhí)行代碼過程中為了安全保護而設(shè)置的二個不同的階段。內(nèi)核態(tài)可以執(zhí)行所有的系統(tǒng)代碼，包括特權(quán)指令；而用戶態(tài)只能執(zhí)行用戶的代碼。若用戶需要執(zhí)行特權(quán)代碼時，必須發(fā)起一次系統(tǒng)調(diào)用。內(nèi)核態(tài)與用戶態(tài)操作系統(tǒng)代碼，系統(tǒng)調(diào)用，共享庫用戶進程1計算機資源用戶進程2用戶進程5用戶進程3用戶進程4內(nèi)核態(tài)用戶態(tài)系統(tǒng)調(diào)用 訪管指令12特權(quán)指令內(nèi)核態(tài)與用戶態(tài)一般示例：用戶代碼不能互訪內(nèi)核代碼也不能訪問用戶代碼中斷、異常13所謂中斷（interrupt）是指處理機對系統(tǒng)中或系統(tǒng)外發(fā)生的異步事件的響應(yīng)。異常（有時也稱為陷阱trap）是指由系統(tǒng)發(fā)起的一次確定的服務(wù)過程（也稱為軟中斷）中斷、異常14訪管指令不是特權(quán)指令用戶從用戶態(tài)進入內(nèi)核態(tài)必定通過訪管指令從內(nèi)核態(tài)返回用戶態(tài)可以修改狀態(tài)字實現(xiàn)系統(tǒng)調(diào)用15系統(tǒng)調(diào)用是指當(dāng)用戶需要使用某些計算機資源時，因為這些資源是被操作系統(tǒng)所控制的，用戶不能直接使用該資源，而是必須向操作系統(tǒng)提出“請求”，由操作系統(tǒng)安排合理、高效、安全地使用這些資源這種“請求”便稱為系統(tǒng)調(diào)用這種“請求”的格式通常是指令名加上請求的服務(wù)識別號（有時是中斷號）選擇2012-23．下列選項中，不可能在用戶態(tài)發(fā)生的事件是A．系統(tǒng)調(diào)用B．外部中斷C．進程切換D．缺頁16選擇2013-28．下列選項中，會導(dǎo)致用戶進程從用戶態(tài)切換到內(nèi)核態(tài)的操作是I．整數(shù)除以零II．sin()函數(shù)調(diào)用III．read系統(tǒng)調(diào)用A．僅I、IIB．僅I、IIIC．僅II、IIID．I、II和III17選擇2014-25．下列指令中，不能在用戶態(tài)執(zhí)行的是A．trap指令B．跳轉(zhuǎn)指令C．壓棧指令D．關(guān)中斷指令18操作系統(tǒng)的體系結(jié)構(gòu)19單一結(jié)構(gòu)分層結(jié)構(gòu)客戶/服務(wù)器結(jié)構(gòu)（微內(nèi)核）虛擬機結(jié)構(gòu)本章重要習(xí)題分析20以概念題為主其中：OS的目標(biāo)、作用，人機接口，OS特性以及OS的主要功能是考查重點形式以選擇題（包括多項組合題）為主，鮮有綜合題占2-6分，趨勢是減少。第二章 進程管理進程與線程處理機調(diào)度同步與互斥死鎖進程與線程進程概念、進程的狀態(tài)與轉(zhuǎn)換、進程控制、進程組織、進程通信（共享存儲系統(tǒng)；消息傳遞系統(tǒng)；管道通信）、線程概念與多線程模型處理機調(diào)度調(diào)度的基本概念、調(diào)度時機、切換與過程、調(diào)度的基本準則、調(diào)度方式、典型調(diào)度算法（先來先服務(wù)調(diào)度算法；短作業(yè)（短進程、短線程）優(yōu)先調(diào)度算法；時間片輪轉(zhuǎn)調(diào)度算法；優(yōu)先級調(diào)度算法；高響應(yīng)比優(yōu)先調(diào)度算法；多級反饋隊列調(diào)度算法）同步與互斥進程同步的基本概念、實現(xiàn)臨界區(qū)互斥的基本方法（軟件實現(xiàn)方法；硬件實現(xiàn)方法）、信號量、管程、經(jīng)典同步問題（生產(chǎn)者-消費者問題；讀者-寫者問題；哲學(xué)家進餐問題）死鎖死鎖的概念、死鎖處理策略、死鎖預(yù)防、死鎖避免（系統(tǒng)安全狀態(tài)；銀行家算法）、死鎖檢測和解除大綱要求進程與線程進程的基本概念進程的狀態(tài)與轉(zhuǎn)換進程控制進程組織進程通信線程概念與多線程模型進程的基本概念一個具有一定獨立功能的程序?qū)δ硞€數(shù)據(jù)集合上的一次動態(tài)執(zhí)行過程和資源分配過程進程的元素：代碼、數(shù)據(jù)、進程表（進程控制塊）Code、Data、PT（PCB）進程和程序的區(qū)別與聯(lián)系進程是動態(tài)的，程序是靜態(tài)的進程是暫時的，程序是永久的進程和程序的組成不同程序主要包含代碼和數(shù)據(jù)進程除了包含代碼和數(shù)據(jù)以外，還有進程表進程和程序間有非常緊密的聯(lián)系程序經(jīng)過多次創(chuàng)建，可以對應(yīng)不同的進程一個進程通過系統(tǒng)調(diào)用，可以被多個程序所使用示例進程包含（）、（）和（）數(shù)據(jù)；記錄項；目錄；代碼；進程表；文件，共享庫示例（）是進程存在的唯一標(biāo)志數(shù)據(jù)；記錄項；目錄；代碼；進程表；文件，共享庫進程的三種基本狀態(tài)及其轉(zhuǎn)換就緒(Ready)狀態(tài)執(zhí)行(Running)狀態(tài)阻塞(Blocking)狀態(tài)進程控制進程的創(chuàng)建（創(chuàng)建原語）進程的創(chuàng)建過程申請空白進程表為新進程分配資源初始化進程表將新進程插入就緒隊列示例進程創(chuàng)建后，所有創(chuàng)建完成后的進程PCB被鏈接成一個序列，這個序列稱為什么？阻塞序列掛起序列就緒序列運行序列選擇2011-25下列選項中，導(dǎo)致創(chuàng)建新進程的操作是I．用戶登錄成功II．設(shè)備分配III．啟動程序執(zhí)行A．僅I和IIB．僅II和IIIC．僅I和IIID．I、II和III進程控制進程的終止正常結(jié)束（自愿的）異常結(jié)束出現(xiàn)錯誤控制退出（自愿的）致命錯誤被迫退出（非自愿的）外界干預(yù)（非自愿的）進程控制進程的終止過程從進程控制塊中讀出該進程的狀態(tài)若被終止進程正處于執(zhí)行狀態(tài)，立即終止該進程的執(zhí)行若該進程還有子孫進程，還應(yīng)將其所有子孫進程予以終止將被終止進程所擁有的全部資源，或者歸還給其父進程，或者歸還給系統(tǒng)將被終止進程的進程控制塊移出進程控制進程的阻塞與喚醒請求系統(tǒng)服務(wù)啟動某種操作新數(shù)據(jù)尚未到達無新工作可做選擇2014-26一個進程的讀磁盤操作完成后，操作系統(tǒng)針對該進程必做的是A．修改進程狀態(tài)為就緒態(tài)B．降低進程優(yōu)先級C．為進程分配用戶內(nèi)存空間D．增加進程的時間片大小進程控制進程的掛起與激活進程組織進程表中的信息進程組織鏈接方式就緒隊列鏈表（一般為一個）阻塞隊列鏈表（可能依據(jù)不同阻塞原因有多個隊列鏈表）索引方式就緒隊列索引阻塞隊列索引進程通信Shared

memory(共享內(nèi)存)Message(消息機制)Pipe(管道)Signal(信號)Socket(套接字)線程線程的基本概念線程線程的屬性輕型實體（容易創(chuàng)建和撤銷）獨立調(diào)度和分派的基本單位可并發(fā)執(zhí)行共享進程資源適應(yīng)硬件的發(fā)展線程

在具有線程OS中，進程是作為擁有系統(tǒng)資源的基本單位，進程不再作為一個執(zhí)行的實體。具有線程的OS中的進程有以下屬性：作為系統(tǒng)資源分配的單位可包括多個線程進程不是一個可執(zhí)行的實體線程線程間的同步和通信互斥鎖(mutex):互斥鎖是一種比較簡單的、用于實現(xiàn)線程間對資源互斥訪問的機制條件變量線程共享同一進程的全局變量2016-30．進程P1和P2均包含并發(fā)執(zhí)行的線程，部分偽代碼描述如下所示。下列選項中，需要互斥執(zhí)行的操作是A．a(chǎn)=1與a=2B．a(chǎn)=x與b=xC．x+=1與x+=2D．x+=1與x+=3//進程P1int

x=0：Thread1(

){ int

a：a=1；x+=1；}Thread2(

){ int

a：a=2；x+=2；}//進程P2int

x=0：Thread3(

){ int

a；a=x；x+=3；}Thread4(

){ int

b；b=x；x+=4；}選擇線程內(nèi)核支持線程內(nèi)核支持線程是在內(nèi)核的支持下運行的，即無論是用戶進程中的線程，還是系統(tǒng)進程中的線程，他們的創(chuàng)建、撤消和切換等，也是依靠內(nèi)核實現(xiàn)的。在內(nèi)核空間還為每一個內(nèi)核支持線程設(shè)置了一個線程控制塊，內(nèi)核是根據(jù)該控制塊而感知某線程的存在的，并對其加以控制線程內(nèi)核支持線程線程用戶級線程用戶級線程僅存在于用戶空間中。這種線程的創(chuàng)建、撤消、線程之間的同步與通信等功能，都無須利用系統(tǒng)調(diào)用來實現(xiàn)。對于用戶級線程的切換，通常是發(fā)生在一個應(yīng)用進程的諸多線程之間，無須內(nèi)核的支持。由于切換的規(guī)則比進程切換的規(guī)則簡單，因而使線程的切換速度特別快。線程用戶級線程線程混合線程處理機調(diào)度處理機調(diào)度的基本概念調(diào)度算法處理機調(diào)度處理機調(diào)度的基本概念處理機調(diào)度處理機調(diào)度高級、中級和低級調(diào)度FCFSSJFHRFSRFFCFSSPFRRPS處理機調(diào)度高級調(diào)度(High

Scheduling)，宏觀調(diào)度，作業(yè)調(diào)度在每次執(zhí)行作業(yè)調(diào)度時（由外存創(chuàng)建到內(nèi)存成為進程），都須做出以下兩個決定接納多少個作業(yè)?接納哪些作業(yè)?處理機調(diào)度中級調(diào)度(Intermediate-Level

Scheduling)

，中程調(diào)度引入中級調(diào)度的主要目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐量中級調(diào)度的算法主要由內(nèi)存管理來實現(xiàn)，與高級調(diào)度和低級調(diào)度的算法不同，故一般在存儲管理中分析，虛擬存儲的中級調(diào)度即頁面調(diào)入、置換等實現(xiàn)處理機調(diào)度低級調(diào)度(LowLevelScheduling)，微觀調(diào)度，進程調(diào)度，線程調(diào)度非搶占方式(Non-preemptive

Mode)搶占方式(Preemptive

Mode)調(diào)度算法先來先服務(wù)算法比較有利于長作業(yè)，而不利于短作業(yè)有利于CPU繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)調(diào)度算法短作業(yè)(進程)優(yōu)先調(diào)度算法優(yōu)點：比FCFS改善平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間，縮短作業(yè)的等待時間提高系統(tǒng)的吞吐量缺點：對長作業(yè)非常不利，可能長時間得不到執(zhí)行，饑餓未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先級難以準確估計作業(yè)（進程）的執(zhí)行時間，從而影響調(diào)度性能調(diào)度算法“最短剩余時間優(yōu)先”SRT(Shortest

RemainingTime)允許比當(dāng)前進程剩余時間更短的進程來搶占“最高響應(yīng)比優(yōu)先”HRRN(Highest

Response

RatioNext)響應(yīng)比R=(等待時間+要求執(zhí)行時間)/要求執(zhí)行時間是FCFS和SJF的折衷調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法非搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)的類型靜態(tài)優(yōu)先級動態(tài)優(yōu)先級調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法(RR:

Round

Robin)調(diào)度算法多級反饋隊列調(diào)度算法(Round

Robin

with

Multiple

Feedback)多級反饋隊列算法是時間片輪轉(zhuǎn)算法和優(yōu)先級算法的綜合和發(fā)展調(diào)度算法多級反饋隊列調(diào)度算法PS選擇2009-24下列進程調(diào)度算法中，綜合考慮進程等待時間和執(zhí)行時間的是A．時間片輪轉(zhuǎn)調(diào)度算法B．短進程優(yōu)先調(diào)度算法C．先來先服務(wù)調(diào)度算法D．高響應(yīng)比優(yōu)先調(diào)度算法選擇2010-26下列選項中，降低進程優(yōu)先級的合理時機是A．進程的時間片用完B．進程剛完成I/O，進入就緒隊列C．進程長期處于就緒隊列D．進程從就緒狀態(tài)轉(zhuǎn)為運行態(tài)調(diào)度算法實時調(diào)度算法給定m個周期事件事件i的周期為Pi需要處理器時間Ci可能調(diào)度的條件是同步與互斥進程同步的基本概念兩種形式的制約關(guān)系間接相互制約關(guān)系直接相互制約關(guān)系臨界資源(Critical

Resource)臨界區(qū)(Critical

Section)一個飛機訂票系統(tǒng)（軟件相同），兩個終端，運行T1、T2進程T1：……read(x);if

x>=1

thenx:=x-1;write(x);……T2：……read(x);if

x>=1

thenx:=x-1;write(x);……互斥關(guān)系Coming

data

blocks初始狀態(tài)結(jié)果正確錯誤錯誤錯誤錯誤錯誤同步關(guān)系同步與互斥同步機制應(yīng)遵循的規(guī)則空閑讓進忙則等待有限等待讓權(quán)等待同步與互斥(Peterson’s

Algorithm)：先修改、后檢查；后修改者等待正確的算法turn=j;描述可進入的進程（同時修改標(biāo)志時）在進入?yún)^(qū)先修改后檢查，并檢查并發(fā)修改的先后：檢查對方flag，如果不在臨界區(qū)則自己進入－－空閑則入否則再檢查turn：保存的是較晚的一次賦值，則較晚的進程等待，較早的進程進入－－先到先入，后到等待選擇2010-27進程P0和P1的共享變量定義及初值為boolean

flag[2];int

turn

=

0;flag[0]

=

FALSE;

flag[1]

=FALSE;若進程P0和P1訪問臨界資源的類C偽代碼實現(xiàn)如下：void

P0（）

//進程P0{while（TRUE）{flag[0]

=

TRUE;

turn

=

1;while（flag[1]&&（turn

==

1））;臨界區(qū);flag[0]

=

FALSE;}}void

P1（）

//進程P1{while（TRUE）{flag[1]=TRUE;turn=0;while（flag[0]&&（turn==0））;臨界區(qū);flag[1]

=

FALSE;}}則并發(fā)執(zhí)行進程P0和P1時產(chǎn)生的情況是A．不能保證進程互斥進入臨界區(qū)，會出現(xiàn)“饑餓”現(xiàn)象B．不能保證進程互斥進入臨界區(qū)，不會出現(xiàn)“饑餓”現(xiàn)象C．能保證進程互斥進入臨界區(qū)，會出現(xiàn)“饑餓”現(xiàn)象D．能保證進程互斥進入臨界區(qū)，不會出現(xiàn)“饑餓”現(xiàn)象同步與互斥硬件TSL指令2016-27．使用TSL(Testand

SetLock)指令實現(xiàn)進程互斥的偽代碼如下所示。下列與該實現(xiàn)機制相關(guān)的敘述中，正確的是A．退出臨界區(qū)的進程負責(zé)喚醒阻塞態(tài)進程

B．等待進入臨界區(qū)的進程不會主動放棄CPU

C．上述偽代碼滿足“讓權(quán)等待”的同步準則

D．while(TSL(&lock))語句應(yīng)在關(guān)中斷狀態(tài)下執(zhí)行do

{……while(TSL(&lock))；critical

section；lock=FALSE；……}while(TRUE)；選擇同步與互斥信號量機制整型信號量：最初由Dijkstra把整型信號量定義為一個整型量，僅能通過初始化和兩個標(biāo)準的原子操作(AtomicOperation)wait(S)和signal(S)來訪問。兩個操作被分別稱為P、V操作(primitive)同步與互斥78P

原語wait(s);

down(s);P(s)--s.count; //表示申請一個資源;if

(s.count

<0)//表示沒有空閑資源;{調(diào)用進程進入等待隊列s.queue;阻塞調(diào)用進程;}同步與互斥79V

原語signal(s);up(s);V(s)//表示釋放一個資源；//表示有進程處于阻塞狀態(tài)；++s.count;if

(s.count

<=

0){從等待隊列s.queue中取出一個進程P;進程P進入就緒隊列;}選擇2010-25設(shè)與某資源相關(guān)聯(lián)的信號量初值為3，當(dāng)前為1，若M表示該資源的可用個數(shù)，N表示等待該資源的進程數(shù)，則M，N分別是A．0、1B．1、0C．1、2D．2、0經(jīng)典進程的同步與互斥問題生產(chǎn)者—消費者問題利用信號量解決生產(chǎn)者—消費者問題2009-45三個進程P1、P2，P3互斥使用一個包含N（N>0）個單元的緩沖區(qū)。P1每次用produce（）生成一個正整數(shù)并用Put（）送入緩沖區(qū)某一空單元中；P2每次用

getodd（）從該緩沖區(qū)中取出一個奇數(shù)并用countodd（）統(tǒng)計奇數(shù)個數(shù)；P3每次用geteven（）從該緩沖區(qū)中取出一個偶數(shù)并用counteven（）統(tǒng)計偶數(shù)個數(shù)。請用信號量機制實現(xiàn)這三個進程的同步與互斥活動，并說明所定義信號量的含義。要求用偽代碼描述82綜合題//并發(fā)進程//生產(chǎn)者進程//等待調(diào)度解答：semaphoremutex=1，odd=

0，even

=

0，empty

=

N；//緩沖區(qū)可用，沒有放置奇數(shù)和偶數(shù)，全空，odd+even+empty=Nmain（）cobegin{Process

P1while（true）{number=produce（）；

//生產(chǎn)者生產(chǎn)數(shù)P（empty）；P（mutex）；//有無空間//能否進入緩沖區(qū)83//放置數(shù)字//釋放緩沖區(qū)//是否偶數(shù)//偶數(shù)信號量加1put（）；V（mutex）；If number

%

2

=

=

0V（even）；elseV（odd）；}//否則奇數(shù)信號84

量加1process

P2//消費者進程1//有無奇數(shù)//能否進入緩沖區(qū)//取奇數(shù)//釋放緩沖區(qū)//空間加1while（true）{

P（odd）；P（mutex）；getodd（）；V（mutex）；V（empty）；countodd（）；}//計算奇數(shù)個數(shù)85//有無偶數(shù)//能否進入緩沖區(qū)//取偶數(shù)//釋放緩沖區(qū)//空間加1Process

P3while（true）{

P（even）；P（mutex）；geteven（）；V（mutex）；V（empty）；counteven（）；}}coend//計算偶數(shù)個數(shù)//并發(fā)結(jié)束86【分析】：本題是生產(chǎn)者和消費者問題的延伸。從生產(chǎn)者-消費者的原題出發(fā)，正確設(shè)置信號量，保證進程同步和互斥的實現(xiàn)?？紤]緩沖區(qū)是一互斥資源，因此設(shè)互斥信號量mutex。對于同步問題：P1、P2因為奇數(shù)的放置與取用而同步，設(shè)同步信號量odd；

P1、P3因為偶數(shù)的放置于取用而同步，設(shè)同步信號量even；P1、P2，P3因為共享緩沖區(qū)，設(shè)同步信號量empty872015-45．（9分）有A、B兩人通過信箱進行辯論，每個人都從自己的信箱中取得對方的問題，將答案和向?qū)Ψ教岢龅男聠栴}組成一個郵件放入對方的信箱中。假設(shè)A的信箱最多放M個郵件，B的信箱最多放N個郵件。初始時A的信箱中有x個郵件(0<x<M)，B的信箱中有y個郵件

(0<y<N)。辯論者每取出一個郵件，郵件數(shù)減1。A和B兩人的操作過程描述如下：綜合題CoBeginA

{while(TRUE){從A的信箱中取出一個郵件；回答問題并提出一個新問題；將新郵件放人B的信箱；}}B

{while(TRUE){從B的信箱中取出一個郵件；回答問題并提出一個新問題；將新郵件放人A的信箱；}}CoEnd當(dāng)信箱不為空時，辯論者才能從信箱中取郵件，否則等待。當(dāng)信箱不滿時，辯論者才能將新郵件放入信箱，否則等待。請?zhí)砑颖匾男盘柫亢蚉、V(或wait、signal)操作，以實現(xiàn)上述過程的同步。要求寫出完整的過程，并說明信號量的含義和初值。解答：本題在PV操作中是比較簡單的題，從題意可以看出，AB的信箱雙方分別可以讀寫，因此需要設(shè)置互斥信號量。又由于信箱的大小受限，因此要設(shè)置資源信號量。資源信號量要設(shè)空和滿的二種。semaphore

EA=M-x；//A信箱空緩沖區(qū)數(shù)

semaphore

EB=N-y；//B信箱空緩沖區(qū)數(shù)

semaphore

FA=x；//A信箱滿緩沖區(qū)數(shù)

semaphore

FB=y；//B信箱滿緩沖區(qū)數(shù)semaphore

mutexA=1；//用于實現(xiàn)讀寫A信箱的互斥量

semaphore

mutexB=1；//用于實現(xiàn)讀寫B(tài)信箱的互斥量(1分)CoBeginA

{B

{while(TRUE){while(TRUE){P(FA)；P(FB)；P(mutexA)；P(mutexB)；從A的信箱中取出一個郵件；從B的信箱中取出一個郵件；V(EA)；V(EB)；V(mutexA)；V(mutexB)；回答問題并提出一個新問題；回答問題并提出一個新問題；P(FB)；P(FA)；P(mutexB)；P(mutexA)；將新郵件放入B的信箱；將新郵件放入A的信箱；V(EB)；V(EA)；V(mutexB)；V(mutexA)；}}}}CoEnd【分析】：在書寫P操作時，一定將資源信號量在先，互斥量在后。而在V操作時沒有這個要求。一定需要對空位和滿位均設(shè)置信號量，否則可能造成讀空信箱或?qū)憹M信箱。經(jīng)典進程的同步與互斥問題哲學(xué)家進餐問題Philosophers

eat/thinkEating

needs

2

forksPick

one

fork

at

a

timeHow

to

prevent

deadlock讓奇數(shù)號的哲學(xué)家先取右手邊的筷子，讓偶數(shù)號的哲學(xué)家先取左手邊的筷子。else{P(c[i+1

mod

5]);P(c[i]);eat;V

(c[i]);V(c[i+1mod5]);}send(i)beginif

i

mod

2

==0

then{P(c[i]);P(c[i+1

mod

5]);eat;V(c[i+1

mod

5]);V

(c[i]);}end數(shù)據(jù)區(qū)讀者計數(shù)互斥經(jīng)典進程的同步與互斥問題讀者-寫者問題互斥利用信號量解決讀者-寫者問題2014-46．(8分)系統(tǒng)中有多個生產(chǎn)者進程和多個消費者進程，共享一個能存放1000件產(chǎn)品的環(huán)形緩沖區(qū)(初始為

空)。當(dāng)緩沖區(qū)未滿時，生產(chǎn)者進程可以放入其生產(chǎn)的一件產(chǎn)品，否則等待；當(dāng)緩沖區(qū)未空時，消費者進程可以從緩沖區(qū)取走一件產(chǎn)品，否則等待。要求一個消費者進程從緩沖區(qū)連續(xù)取走10件產(chǎn)品后，其他消費者進程才可以取產(chǎn)品。請使用信號量的P、V(wait( )、signal( ))操作實現(xiàn)進程間的互斥與同步，要求寫出完整的過程，并說明所用信號量的含義和初值。綜合題解答：本題考查信號量的使用及P、V操作偽代碼如下：初始化semaphore

empty=1000；semaphore

full=0；semaphore

mutex1=1；semaphore

mutex2=1；int

in=0；int

out=0；//空緩沖區(qū)數(shù)//非空緩沖區(qū)數(shù)(1分)//用于實現(xiàn)生產(chǎn)者和消費者之間的互斥//用于實現(xiàn)消費者之間的互斥(1分)//初始化//初始化//調(diào)度//生產(chǎn)產(chǎn)品//P空閑位置同步量//P與消費者和其他生產(chǎn)者互斥量//放置產(chǎn)品//循環(huán)指針加1//釋放互斥量//釋放同步量while(TRUE){

produce；P(empty)；P(mutexl)；put

an

item

into

buf[in]；in=(in+1)mod

n；Ⅴ(mutex1)；Ⅴ(full)；}生產(chǎn)者進程(2分)//調(diào)度//P消費者互斥量2//連續(xù)消費10//P產(chǎn)品的同步量//P生產(chǎn)者互斥量1//取貨//設(shè)置消防循環(huán)指針//釋放互斥量1//釋放同步量//釋放互斥量2//消費while(TRUE){

P(mutex2)；for(int

i=0；i<10；i++){

P(full)；P(mutex1)；get

anitem

from

buf[out]；out=(out+1)mod

n；Ⅴ(mutex1)；Ⅴ(empty)；}Ⅴ(mutex2)；consume；}消費者進程(4分)2016-46．(6分)某進程調(diào)度程序采用基于優(yōu)先數(shù)(priority)的調(diào)度策略，即選擇優(yōu)先數(shù)最小的進程運行，進程創(chuàng)建時由用戶指定一個nice作為靜態(tài)優(yōu)先數(shù)。為了動態(tài)調(diào)整優(yōu)先數(shù)，引入運行時間cpuTime和等待時間waitTime，初值均為0。進程處于執(zhí)行態(tài)時，cpuTime定時加1，且waitTime置0；進程處于就緒態(tài)時，

cpuTime置0，waitTime定時加1。請回答下列問題。若調(diào)度程序只將nice的值作為進程的優(yōu)先數(shù)，即priority=nice，則可能會出現(xiàn)饑餓現(xiàn)象，為什么?使用nice、cpuTime和waitTime設(shè)計一種動態(tài)優(yōu)先數(shù)計算方法，以避免產(chǎn)生饑餓現(xiàn)象，并說明waitTime的作用。綜合題解答：nice固定時為“固定優(yōu)先級”調(diào)度算法，此時。若發(fā)生nice較低的進程源源不斷進入就緒隊列，較高nice的進程就會得不到調(diào)度，引起饑餓。簡單的解決方法是改為“動態(tài)優(yōu)先級”調(diào)度算法，利用waitTime的值，將

priority=nice–waitTime，當(dāng)進程在就緒隊列中等待時間waitTime增加時，適當(dāng)提高優(yōu)先級，即減少優(yōu)先數(shù)priority，直到為0（即最高優(yōu)先級），這樣就解決了饑餓的問題。

waitTime起到提升優(yōu)先級的作用。更復(fù)雜的算法可以將cpuTime也考慮進去。死鎖產(chǎn)生死鎖的原因和必要條件解決死鎖的方法死鎖產(chǎn)生死鎖的原因互斥資源分配不當(dāng)（造成剩余資源不足，非資源不足）進程間推進順序不當(dāng)死鎖死鎖死鎖死鎖定義:同一進程集中的二個以上的不同進程都在互相等待對方為自己釋放資源因而造成的進程無法推進的現(xiàn)象死鎖產(chǎn)生死鎖的四個必要條件互斥條件請求和保持條件不剝奪條件環(huán)路等待條件2016-25．系統(tǒng)中有3個不同的臨界資源R1、R2和R3，被4個進程p1、p2、p3及p4共享。各進程對資源的需求為：

p1申請R1和R2，p2申請R2和R3，p3申請R1和R3，p4申請

R2。若系統(tǒng)出現(xiàn)死鎖，則處于死鎖狀態(tài)的進程數(shù)至少是A．1B．2C．3D．4死鎖處理死鎖的基本方法忽略死鎖(鴕鳥算法)檢測和解除死鎖(有向圖，矩陣:剝奪資源)避免死鎖(銀行家算法)預(yù)防死鎖(打破死鎖的四個必要條件)死鎖死鎖的檢測死鎖資源矩陣死鎖死鎖的恢復(fù)剝奪資源回溯到還原點撤消進程重起系統(tǒng)死鎖安全和不安全狀態(tài)利用銀行家算法避免死鎖一個銀行家把他的固定資金（capital）貸給若干顧客。只要不出現(xiàn)一個顧客借走所有資金后還不夠，銀行家的資金應(yīng)是安全的。銀行家需一個算法保證借出去的資金在有限時間內(nèi)可收回死鎖預(yù)防死鎖摒棄互斥條件摒棄“請求和保持”條件摒棄“不剝奪”條件摒棄“環(huán)路等待”2009-25某計算機系統(tǒng)中有8臺打印機，由K個進程競爭使用，每個進程最多需要3臺打印機。該系統(tǒng)可能會發(fā)生死鎖的K最小值是A．2

B．3

C．4

D．5選擇2015-26．若系統(tǒng)S1采用死鎖避免方法，S2采用死鎖檢測方法。下列敘述中，正確的是Ⅰ．S1會限制用戶申請資源的順序，而S2不會

Ⅱ．S1需要進程運行所需資源總量信息，而S2不需要

Ⅲ．S1不會給可能導(dǎo)致死鎖的進程分配資源，而S2會A．僅Ⅰ、Ⅱ

C．僅Ⅰ、ⅢB．僅Ⅱ、Ⅲ

D．Ⅰ、Ⅱ、Ⅲ選擇本章重要習(xí)題分析重點！重點！重點！大量考題，選擇、綜合復(fù)雜綜合題總體占10-15分第三章 內(nèi)存管理內(nèi)存管理基礎(chǔ)虛擬內(nèi)存管理內(nèi)存管理基礎(chǔ)內(nèi)存管理概念（程序裝入與鏈接；邏輯地址與物理地址空間；內(nèi)存保護）、交換與覆蓋、連續(xù)分配管理方式、非連續(xù)分配管理方式（分頁管理方式；分段管理方式；段頁式管理方式）虛擬內(nèi)存管理虛擬內(nèi)存基本概念、請求式分頁管理方式、頁面置換算法（最佳置換算法（OPT）；先進先出置換算法（FIFO）；最近最少使用置換算法（LRU）；時鐘置換算法（CLOCK））、頁面分配策略、工作集、抖動大綱要求簡單存儲管理定位和重定位程序的裝入絕對裝入方式(Absolute

Loading

Mode)程序中所使用的絕對地址，既可在編譯或匯編時給出，也可由程序員直接賦予例如：ORG

1000H可重定位裝入方式(Relocation

Loading

Mode)靜態(tài)動態(tài)簡單存儲管理動態(tài)運行時裝入方式(Dynamic

Run-time

Loading)動態(tài)運行時裝入程序，在把裝入模塊(Loader)裝入內(nèi)存后，并不把其它模塊裝入內(nèi)存，而是把裝入過程推遲到程序真正要執(zhí)行時才進行簡單存儲管理程序的鏈接靜態(tài)鏈接方式(Static

Linking)裝入時動態(tài)鏈接(Load

time

Dynamic

Linking)運行時動態(tài)鏈接(Run-time

Dynamic

Linking)簡單存儲管理簡單連續(xù)分配方式單一連續(xù)分配固定分區(qū)分配(等額和差額)動態(tài)分區(qū)分配簡單存儲管理分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)位示圖空閑分區(qū)鏈表簡單存儲管理分區(qū)分配算法首次適應(yīng)算法First

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

Fit最佳適應(yīng)算法Best

Fit最壞適應(yīng)算法Worst

Fit快速適應(yīng)算法Quick

Fit129PointerComing

a

New

process

is

16KWorst

fit選擇2010-28某基于動態(tài)分區(qū)存儲管理的計算機，其主存容量為55MB（初始為空閑），采用最佳適配（Best

Fit）算法，分配和釋放的順序為：分配15MB、分配30MB、釋放15MB、分配8MB、分配6MB，此時主存中最大空閑分區(qū)的大小是A．7MBB．9MBC．10MBD．15MB簡單存儲管理交換(Swapping)覆蓋(Overlay)簡單存儲管理基本分頁存儲管理方式頁號P位移量W0簡單存儲管理分頁地址中的地址結(jié)構(gòu)如下31

12

11簡單存儲管理多級頁表(Multi-Level

Page

Table)Windows

的多級頁表結(jié)構(gòu)選擇2014-32下列選項中，屬于多級頁表優(yōu)點的是A．加快地址變換速度B．減少缺頁中斷次數(shù)C．減少頁表項所占字節(jié)數(shù)D．減少頁表所占的連續(xù)內(nèi)存空間段號段長/段內(nèi)地址簡單存儲管理基本分段存儲管理方式31

16

15

02016-28．某進程的段表內(nèi)容如下所示。當(dāng)訪問段號為2、段內(nèi)地址為400的邏輯地址時，進行地址轉(zhuǎn)換的結(jié)果是

A．段缺失異常

B．得到內(nèi)存地址4400

C．越權(quán)異常

D．越界異常段號段長內(nèi)存起始地址權(quán)限狀態(tài)01006000只讀在內(nèi)存1200—讀寫不在內(nèi)存23004000讀寫在內(nèi)存選擇選擇2009-27一個分段存儲管理系統(tǒng)中，地址長度為32位，其中段號占8位，則最大段長是A．28字節(jié)B．216字節(jié)C．224字節(jié)D．232字節(jié)選擇2010-29某計算機采用二級頁表的分頁存儲管理方式，按字節(jié)編址，頁大小為210字節(jié)，頁表項大小為2字節(jié)，邏輯地址結(jié)構(gòu)為下圖所示，邏輯地址空間大小為216頁，則表示整個邏輯地址空間的頁目錄表中包含表項的個數(shù)至少是A．64B．128C．256D．512頁目錄號頁號頁內(nèi)偏移量XXXXXX簡單存儲管理分頁和分段的主要區(qū)別頁是信息的物理單位，分頁是為實現(xiàn)離散分配方式，提高內(nèi)存的利用率。是由于系統(tǒng)管理的需要而不是用戶的需要段則是信息的邏輯單位，它含有一組其意義相對完整的信息。分段的目的是為了能更好地滿足用戶的需要頁的大小固定且由系統(tǒng)決定，而段的長度卻不固定分頁的作業(yè)地址空間是一維的，而分段的作業(yè)地址空間則是二維的虛擬存儲管理虛擬存儲器的基本概念多次性對換性虛擬性虛擬存儲管理局部性原理時間局部性，程序執(zhí)行時，大多數(shù)情況下是順序執(zhí)行的空間局部性，程序中存在許多循環(huán)結(jié)構(gòu)，它們將多次執(zhí)行。程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理，如對數(shù)組進行操作，它們往往都局限于很小的范圍內(nèi)虛擬存儲管理虛擬存儲器定義所謂虛擬存儲器，是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)。其邏輯容量由CPU及其存儲器的地址線寬度，實際容量由內(nèi)存容量和外存容量之和決定，其運行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存虛擬存儲管理虛擬存儲器的實現(xiàn)方法分頁請求系統(tǒng)：頁表機制硬件支持：缺頁中斷機構(gòu)；地址變換機構(gòu)實現(xiàn)請求分頁的軟件虛擬存儲管理頁表表項Virtual

time

and

so

onOnly

for

memory

mapped

I/OBeyond

fault虛擬存儲管理選擇2014-28．下列措施中，能加快虛實地址轉(zhuǎn)換的是Ⅱ．讓頁表常駐內(nèi)存

Ⅲ．增Ⅰ．增大快表(TLB)容量大交換區(qū)(swap)A．僅IB．僅IIC．僅I、IID．僅II、III虛擬存儲管理頁面置換算法最佳置換算法其所選擇的被淘汰頁面，將是以后永不使用的，或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率虛擬存儲管理FIFO432143543215頁1432143555211頁243214333522頁34321444355頁面置換算法先進先出置換算法(FIFO)x

x

x

x

x

x

x

x

x

共缺頁中斷9次虛擬存儲管理時鐘算法虛擬存儲管理頁面置換算法最近最久未使用置換算法(LRU)LRU432143543215頁1432143543215頁243214354321頁34321435432xxxxxxxxxx共缺頁中斷10次虛擬存儲管理工作集算法w(k,t)

is

the

size

of

the

working

set

at

time,

tLocality

of

reference若工作集的窗口大小為6，則在t時刻的工作集為A．{6，0，3，2}B．{2，3，0，4}C．{0，4，3，2，9}D．{4，5，6，0，3，2}選擇2016-29．某進程訪問頁面的序列如下所示。虛擬存儲管理Belady’s

異常Thrashing

抖動選擇2014-30在頁式虛擬存儲管理系統(tǒng)中，采用某些頁面置換算法，會出現(xiàn)

Belady異常現(xiàn)象，即進程的缺頁次數(shù)會隨著分配給該進程的頁框個數(shù)的增加而增加。下列算法中，可能出現(xiàn)Belady異?，F(xiàn)象的是Ⅰ．LRU算法

Ⅱ．FIFO算法

Ⅲ．OPT算法A．僅IIB．僅I、IIC．僅I、IID．僅II、III虛擬存儲管理局部置換全局置換7

frames2015-30．在請求分頁系統(tǒng)中，頁面分配策略與頁面置換策略不能組合使用的是A．可變分配，全局置換

B．可變分配，局部置換

C．固定分配，全局置換

D．固定分配，局部置換選擇選擇2009-26分區(qū)分配內(nèi)存管理方式的主要保護措施是A．界地址保護B．程序代碼保護C．?dāng)?shù)據(jù)保護D．棧保護綜合題2009-45請求分頁管理系統(tǒng)中，假設(shè)某進程的頁表內(nèi)容如左表所示，頁面大小為4KB，一次內(nèi)存的訪問時間是100ns，一次快表（TLB）的訪問時間是10ns，處理一次缺頁的平均時間為108ns（己含更新TLB和頁表的時間），進程的駐留集大小固定為2，采用最近最少使用置換算法（LRU）和局部淘汰策略。假設(shè)①TLB初始為空；②地址轉(zhuǎn)換時先訪問TLB，若TLB未命中，再訪問頁表（忽略訪問頁表之后的TLB更新時間）；③有效位為0表示頁面不在內(nèi)存，產(chǎn)生缺頁中斷，缺頁中斷處理后，返回到產(chǎn)生缺頁中斷的指令處重新執(zhí)行。設(shè)有虛地址訪問序列2362H、1565H、25A5H，請問：依次訪問上述三個虛地址，各需多少時間？給出計算過程?；谏鲜鲈L問序列，虛地址1565H的物理地址是多少？請說明理由。頁號頁框號有效位0101H11-02254H1161解答：1565H指令P=1，訪問快表10ns，不在TLB，訪問頁表

100ns，不在內(nèi)存，發(fā)生缺頁中斷花費108ns，取得新頁框號（含TLB更新），合成物理地址后去主存取指令需要花費100ns?？倳r間10ns+100ns+108ns+100ns≈108ns。25A5H指令，P=2，訪問快表，因第一次訪問己將該頁號放入快表，因此花費10ns便可合成物理地址，訪問主存取指100ns，共計10ns+100ns=110ns。地址頁號頁內(nèi)位移2362H2362H1565H1565H25A5H25A5H162當(dāng)訪問虛地址1565H時，因不在內(nèi)存而產(chǎn)生缺頁中斷，因駐留集為2個頁，現(xiàn)在已有0頁和2頁在內(nèi)存，必須從中淘汰一個頁面，從而將新1頁調(diào)入內(nèi)存。根據(jù)LRU置換算法，0頁和2頁除有效位以外的其它信息未知，但是，2頁剛剛訪問過，其引用位應(yīng)剛置為1且時間間隔不長，根據(jù)最近最少使用置換算法，相比之下應(yīng)首先淘汰0號頁面，因此1565H的對應(yīng)頁框號為101H。由此可得1565H的物理地址為101565H。（1）

210ns；108ns；110ns。（2）

101565H。163【分析】：根據(jù)頁式管理的工作原理，應(yīng)先將頁號和頁內(nèi)位移地址分解出來。頁面大小為4KB，即212，則得到頁內(nèi)位移占虛地址的低12位，頁號占剩余高4位。可得三個虛地址的頁號P如上表，2362H指令，P=2，訪問快表

10ns，因初始為空，需要再到內(nèi)存訪問頁表，花費100ns得到頁框號，合成物理地址后去主存取指令需要花費

100ns?？倳r間10ns+100ns+100ns=210ns。164本章重要習(xí)題分析重點！特別是虛擬存儲技術(shù)！各種變換！選擇題（包括多項組合題）、綜合題均有總體占10-12分，保持穩(wěn)定。165第四章文件管理文件系統(tǒng)基礎(chǔ)文件系統(tǒng)實現(xiàn)磁盤組織與管理文件系統(tǒng)基礎(chǔ)文件概念、文件的邏輯結(jié)構(gòu)（順序文件；索引文件；索引順序文件）、目錄結(jié)構(gòu)（文件控制塊和索引節(jié)點；單級目錄結(jié)構(gòu)和兩級目錄結(jié)構(gòu)；樹形目錄結(jié)構(gòu)；圖形目錄結(jié)構(gòu)）、文件共享、文件保護（訪問類型；訪問控制）文件系統(tǒng)實現(xiàn)文件系統(tǒng)層次結(jié)構(gòu)、目錄實現(xiàn)、文件實現(xiàn)磁盤組織與管理磁盤的結(jié)構(gòu)、磁盤調(diào)度算法、磁盤的管理大綱要求文件文件、記錄和數(shù)據(jù)項文件屬性可以包括文件類型文件長度文件的物理位置文件的建立時間示例在一個學(xué)生的文件記錄中，哪個可以作為主鍵用于檢索姓名年齡學(xué)號性別示例從用戶角度看，我們建立文件系統(tǒng)是為了實現(xiàn)（），為達到此目的，我們必需建立（）文件管理；文件訪問；按名存儲；文件保存；文件安全文件名；目錄；字典；文件識別號；文件屬性文件文件類型按文件中數(shù)據(jù)的形式分類系統(tǒng)文件/用戶文件/庫文件/源文件按用途分類目標(biāo)文件/可執(zhí)行文件按存取控制屬性分類只執(zhí)行文件只讀文件/讀寫文件文件文件的邏輯結(jié)構(gòu)累積文件索引結(jié)構(gòu)文件文件文件的物理結(jié)構(gòu)磁盤磁帶光盤非易失存儲器件磁盤磁盤的結(jié)構(gòu)磁盤磁盤管理磁盤存儲塊分配表（FAT）位示圖（Bitmap）選擇2014-27．現(xiàn)有一個容量為10GB的磁盤分區(qū)，磁盤空間以簇(Cluster)為單位進行分配，簇的大小為4KB，若采用位圖法管理該分區(qū)的空閑空間，即用一位(bit)標(biāo)識一個簇是否被分配，則存放該位圖所需簇的個數(shù)為A．80B．320C．80KD．320KFCB文件外存分配方式(物理結(jié)構(gòu))連續(xù)分配順序訪問容易，速度快要求有連續(xù)的存儲空間必須事先知道文件的長度示例視頻流數(shù)據(jù)最好存儲在什么結(jié)構(gòu)的文件系統(tǒng)中？順序隨機索引索引節(jié)點2014-46、(7分)文件F由200條記錄組成，記錄從1開始編號。用戶打開文件后，欲將內(nèi)存中的一條記錄插入到文件F中，作為其第30條記錄。請回答下列問題，并說明理由。若文件系統(tǒng)采用連續(xù)分配方式，每個磁盤塊存放一條記錄，文件F存儲區(qū)域前后均有足夠的空閑磁盤空間，則完成上述插入操作最少需要訪問多少次磁盤塊?F的文件控制塊內(nèi)容會發(fā)生哪些改變?若文件系統(tǒng)采用鏈接分配方式，每個磁盤塊存放一條記錄和一個鏈接指針，則完成上述插入操作需要訪問多少次磁盤塊?若每個磁盤塊大小為1KB，其中4個字節(jié)存放鏈接指針，則該文件系統(tǒng)支持的文件最大長度是多少?17綜合題解答：本題考查文件系統(tǒng)的物理結(jié)構(gòu)(1)向前移動文件的1-29共29條記錄，每條記錄讀寫各1次，騰出原第29個磁盤塊空間，以將該記錄插入到此磁盤塊作為文件的第30條記錄。(1分)故需要磁盤訪問的次數(shù)為：

29×2+1=59次。(1分)向后移動文件的30-200共171條記錄，每條記錄讀寫各1次，騰出原第30個磁盤塊空間，以將該記錄插入到此磁盤塊作為文件的第30條記錄。故需要磁

盤訪問的次數(shù)為：171×2+1=343次。其中較少的是59次。且文件控制塊中文件的起始地址和文件大小發(fā)生了變化。(1分)18(2)采用鏈接分配方式存儲文件F，需要讀文件的前29塊的鏈接指針(共讀29次)，在第29塊內(nèi)找到指向原第30塊的鏈接指針。再為該記錄分配一個空閑磁盤塊，將該記錄及第29塊內(nèi)保存的鏈接指針寫入其中，將該塊寫到磁盤(寫1次)。最后修改第29塊的鏈接指針，指向新的插入塊，并將第29塊寫回磁盤(寫1次)。(1分)故需要磁盤訪問的次數(shù)：29+2=31次。(1分)該文件系統(tǒng)支持的文件最大長度是：(1024-4)×232B=4080

GB。(2分)18FCB文件鏈接分配(鏈式)隱式鏈接文件鏈接分配(鏈式)顯式鏈接2016-47．(9分)某磁盤文件系統(tǒng)使用鏈接分配方式組織文件，簇大小為4KB。目錄文件的每個目錄項包括文件名和文件的第一個簇號，其他簇號存放在文件分配表FAT中。假定目錄樹如下圖所示，各文件占用的簇號及順序如下表所示，其中dir、dir1是目錄，file1、file2是用戶文件。請給出所有目錄文件的內(nèi)容。若FAT的每個表項僅存放簇號，占2個字節(jié)，則FAT的最大長度為多少字節(jié)?該文件系統(tǒng)支持的文件長度最大是多少?綜合題系統(tǒng)通過目錄文件和FAT實現(xiàn)對文件的按名存取，說明file1的106、108兩個簇號分別存放在FAT的哪個表項中。假設(shè)僅FAT和dir目錄文件已讀入內(nèi)存，若需將文件

dir/dir1/file1的第5000個字節(jié)讀入內(nèi)存，則要訪問哪幾個簇?文件名簇號dir1dir148file1100、106、108file2200、201、202解答：(1)目錄文件dir為根目錄，其內(nèi)容為目錄文件dir1為。。。。。。dir148。。。。。。。。。。。。file1100file2200。。。。。。(2)FAT表占2個字節(jié)即16位，共可以形成簇指針216=65536個，每個指針大小為2B，則FAT需要占用65536*2B=128KB，即

FAT的最大長度為128KB，共需要128KB/4KB=32個簇才能容納下。其支持的最大文件為65536*4KB=256MB。(3)鏈接結(jié)構(gòu)將下一個簇號放在前一個簇號的表項中，第一個簇號放在目錄中。而簇號本身是隱含的。106放在簇號100中，108放在106中，108中放文件結(jié)束符-1（0xFFFF）。(4)訪問文件dir/dir1/file1的第5000個字節(jié)，則計算：訪問dir：免讀簇，得到dir1簇48。訪問dir1：讀簇48；查FAT，免讀簇，得到dir1內(nèi)容file1和file2。計算5000個字節(jié)：5000/4096=1.x=>2，第5000個字節(jié)位于第2個簇內(nèi)；查FAT，免讀簇，查得file1第二個簇位于簇106。訪問file1：讀簇106，得到4KB數(shù)據(jù)，移動指針，找到第5000個字節(jié)。訪問結(jié)束。共訪問了簇48和簇106。文件索引分配單級索引分配多級索引分配FCBcount示例下列文件物理結(jié)構(gòu)中，適合隨機訪問且易于文件擴展的是A．連續(xù)結(jié)構(gòu)B．索引結(jié)構(gòu)C．鏈式結(jié)構(gòu)且磁盤塊定長D．鏈式結(jié)構(gòu)且磁盤塊變長文件

A

UNIX

i-node10256+10=266K256*256+10=64M256*256*256+10=16T2015-31．文件系統(tǒng)用位圖法表示磁盤空間的分配情況，

位圖存于磁盤的32～127號塊中，每個盤塊占1024個字節(jié)，盤塊和塊內(nèi)字節(jié)均從0開始編號。假設(shè)要釋放的盤塊號為

409612，則位圖中要修改的位所在的盤塊號和塊內(nèi)字節(jié)序號分別是A．81、1C．82、1B．81、2D．82、2選擇選擇2010-30設(shè)文件索引節(jié)點中有7個地址項，其中4個地址項為直接地址索引，2個地址項是一級間接地址索引，1個地址項是二級間接地址索引，每個地址項大小為4字節(jié)，若磁盤索引塊和磁盤數(shù)據(jù)塊的大小均為256字節(jié)，則可表示的單個文件最大長度是A．33KBB．519KBC．1057KBD．16513KB目錄目錄管理實現(xiàn)“按名存取”提高對文件的檢索速度文件共享允許文件重名示例設(shè)置當(dāng)前工作目錄的主要目的是A．節(jié)省外存空間B．節(jié)省內(nèi)存空間C．加快文件的檢索速度D．加快文件的讀/寫速度示例在文件系統(tǒng)中是利用（

）來管理文件的，為了允許不同用戶的文件使用相同的文件名，通常文件系統(tǒng)中采用（

）；在目錄文件中的每個目錄項通常就是（

）；在Unix文件系統(tǒng)中的目錄項則是（）文件控制塊；索引結(jié)點；目錄；索引表；多級目錄；文件表指針；文件名和文件物理地址；文件名和索引結(jié)點指針；符號名表示例文件系統(tǒng)中，文件訪問控制信息存儲的合理位置是A．文件控制塊B．文件分配表C．用戶口令表D．系統(tǒng)注冊表磁盤磁盤訪問時間尋道時間(Seek

time)