第一章（1）操作系統（OperatingSystem）：操作系統是一組控制和管理計算機硬件和軟件資源，合理地對各類作業進行調度，以及方便用戶使用的程序的集合。（2）操作系統最基本的特征：共享性、并發性（3）操作系統的特性：eq\o\ac(○,1)并發性：兩個或多個事件在同一事件間隔發生；eq\o\ac(○,2)共享性：系統中的資源可供內存中多個并發進程共同使用，也稱為資源共享或資源復用；eq\o\ac(○,3)虛擬技術：把一個物理實體變成若干個邏輯上的對應物；eq\o\ac(○,4)異步性：進程是以人們不可預知的速度，停停走走地向前推進的。（4）OS的主要任務：為多道程序的運行提供良好的環境，保證多道程序能有條不紊地、高效地運行，并能最大程度地提高系統中各種資源的利用率和方便用戶的使用。（5）OS的功能：（1）處理機管理：對處理機進行分配，并對其運行進行有效的控制和管理；（6）存儲器管理：內存分配、內存保護、地址映射（變換）、內存擴充；（3）設備管理：（4）文件管理：文件的存儲空間管理、目錄管理、文件的讀／寫管理和保護；（5）操作系統和用戶之間的接口：命令接口、程序接口（系統調用組成）、圖形接口（6）面向網絡的服務功能（7）eq\o\ac(○,1)多道批處理系統（吞吐量、周轉時間）：多道性、宏觀上并發、微觀上串行、無序性、調度性；eq\o\ac(○,2)分時系統（響應時間）：多路性、交互性、獨占性、及時性；eq\o\ac(○,3)實時系統（實時性和可靠性）：（8）多道程序設計技術是操作系統形成的標志（9）分時系統：響應時間=用戶數*時間片，時間片=切換時間+處理時間（10）實時系統：系統能及時響應外部事件的請求，在規定的時間內完成對該事件的處理，并控制所有實時任務協調一致地運行。（11）并發：兩個或多個事件在同一時間間隔發生；并行：兩個或多個事件在同一時刻發生。（12）虛擬：通過某種技術把一個物理實體變為若干個邏輯上的對應物。（13）微內核ＯＳ結構：能實現ＯＳ核心功能的小型內核，并非一個完整的ＯＳ，與ＯＳ的服務進程（如文件服務器、作業服務器等）共同構成ＯＳ。基本原理：只有最基本的操作系統功能才能放在內核中。不是最基本的服務和應用程序在微內核之上構造，并在用戶模式下執行。微內核通常提供最小的進程和內存管理以及通信功能。微內核的主要功能是提供客戶程序和運行在用戶空間的各種服務之間進行通信的能力。通信以消息傳遞形式提供，一般采用客戶/服務器模式.第二章（1）程序（不是進程）并發執行時的特征：間斷性、失去封閉性、不可再現性（2）進程與程序的區別：（1）程序是為了完成某項工作時需要計算機執行的指令的集合，是靜態的概念；而進程是程序的執行，是動態的概念。（2）程序是永遠存在的，進程則有生存期，它的存在是暫時的。（3）進程是一個獨立調度并能和其它進程并發運行的單位，而程序和程序段則不能作為一個獨立調度運行的單位，也不能并發執行。（3）進程的靜態描述：由程序、數據段、PCB組成。進程是一個程序段在一個數據集合上的一次運行的過程。（4）進程與線程：eq\o\ac(○,1)線程為調度和分派的基本單位。進程為擁有資源的基本單位。線程不擁有資源。eq\o\ac(○,2)進程間可并發執行，一個進程中的多個線程間也可并發執行。eq\o\ac(○,3)線程切換的開銷遠小于進程切換的開銷；（5）1)就緒狀態：除了CPU，其它所需資源都已占有，一旦得到處理機即可運行，則稱此進程處于就緒狀態；2)執行狀態：占有CPU；3)阻塞狀態，又稱等待狀態：等待某些事件（6）就緒到阻塞不存在，阻塞到運行也不會發生。（7）執行阻塞：進程因等待I/O而阻塞；時間片到：執行就緒；進程調度：就緒執行；I/O完成：阻塞執行（改為圖）（8）被優先級高的進程搶占了CPU，由運行態轉換為就緒態1：在操作系統中，進程是一個具有一定獨立功能程序在某個數據集合上的一次﹎﹎A﹎運行過程﹎，進程是一個﹎B動態﹎概念，而程序是一個﹎C靜態﹎的概念。在一單處理機中，若有5個用戶進程，在非管態的某一時刻，處于就緒狀態的用戶進程最多有﹎D4﹎個，最少有﹎E0﹎個。A：(1)并發活動；(2)運行過程；(3)單獨操作；(4)關聯操作。B，C：(1)組合態；(2)關聯態；(3)運行態；(4)等待態；(5)靜態；(6)動態。D，E：(1)1；(2)2；(3)3；(4)4；(5)5；(6)0。2：從靜態角度看，進程由﹎APCB﹎、﹎﹎B程序段﹎﹎和﹎﹎C數據空間﹎﹎三部分組成，用戶可通過﹎D系統調用﹎建立和撤消進程。A：(1)JCB；(2)DCB；(3)PCB；(4)PMT。B:(1)程序段；(2)文件體；(3)I/O；(4)子程序。C：(1)文件描述塊；(2)數據空間；(3)EOF；(4)I/O緩沖區。D：(1)函數調用；(2)宏指令；(3)系統調用；(4)過程調用。3：正在執行的進程由于其時間片完而被暫停執行，此時進程應從運行態變為﹎﹎A就緒﹎狀態；處于阻塞/掛起狀態的進程，在進程等待的事件出現后，應轉變為﹎﹎B就緒/掛起﹎狀態；若進程正處于運行態時，應終端的請求而暫停下來以便研究其運行情況(執行掛起進程原語)，這時進程應轉變為﹎C就緒/掛起﹎﹎狀態，若進程已處于阻塞狀態，則此時應轉變為﹎﹎D﹎阻塞/掛起﹎狀態，若進程已處于就緒狀態，則此時應轉變為﹎﹎E就緒/掛起﹎﹎狀態；執行解除掛起進程原語后，如掛起進程處于就緒/掛起狀態，則應轉變為﹎就緒（活動就緒）﹎F﹎﹎態，如處于阻塞/掛起狀態，則應轉變為﹎﹎G﹎阻塞（活動阻塞）﹎態；一個進程剛被創建時，它的初始狀態為﹎﹎H﹎﹎就緒（活動就緒）。A，...，H：(1)阻塞/掛起（靜止阻塞）；(2)阻塞（活動阻塞）；(3)就緒/掛起（靜止就緒）；(4)就緒（活動就緒）；(5)執行。（12）PCB（進程控制塊）的作用：使一個在多道環境下不能獨立運行的程序成為一個能獨立運行的基本單位，一個能與其它進程并發執行的進程。OS根據PCB來對并發執行的進程進行控制和管理。PCB是進程存在的唯一標志。（13）一個進程剛被創建時，它的初始狀態為就緒（活動就緒）。（14）PCB一般包括：進程標識符、處理機狀態、調度信息、控制信息（15）處理機的執行狀態：系統態（在系統程序中執行，OS內核）；用戶態（在用戶程序中執行）（16）進程的創建：1）申請空白PCB：申請唯一的數字標識符；2）為新進程分配資源：為程序、數據、用戶棧分配必要的空間；3）初始化進程控制塊：標識信息、處理機狀態信息、處理機控制信息；4）將新進程插入就緒隊列（17）原語由若干條指令構成的“原子操作”，原語是操作系統核心的一個組成部分，它必須在核心態下執行，并且常駐內存。（18）原語和系統調用的區別：原語有不可中斷性，通過在其執行過程中關閉中斷實現的，且一般由系統進程調用；許多系統調用都可在用戶態下運行的系統進程完成，而不一定要在核心態下完成。（19）同步與互斥：eq\o\ac(○,1)進程同步也是進程之間直接的制約關系，是為完成某種任務而建立的兩個或多個線程，這個線程需要在某些位置上協調他們的工作次序而等待、傳遞信息所產生的制約關系。進程間的直接制約關系來源于他們之間的合作。eq\o\ac(○,2)進程互斥是進程之間的間接制約關系。當一個進程進入臨界區使用臨界資源時，另一個進程必須等待。只有當使用臨界資源的進程退出臨界區后，這個進程才會解除阻塞狀態。（20）臨界區：每個進程中訪問臨界資源的那段代碼(一段程序)。（21）同步機制應遵循的準則：空閑讓進、忙則等待、有限等待、讓權等待（22）信號量實現互斥：初值為1；同步：取決于問題。互斥：wait和signal在一起，同步：signal在前一個操作，wait在后一個操作（23）核心級線程：#優點：對于多處理器，內核可以同時調度同一進程的多個線程。阻塞是在線程一級完成。線程的切換速度較快，切換開銷小。內核例程是多線程的。#缺點：在同一進程內的線程切換調用內核，導致速度下降。用戶級線程：#優點：線程切換不調用內核。調度是應用程序特定的：可以選擇最好的算法。ULT可運行在任何操作系統上（只需要線程庫）。#缺點：大多數系統調用是阻塞的，因此內核阻塞進程，進程中所有線程將被阻塞。內核只將處理器分配給進程，同一進程中的兩個線程不能同時運行于兩個處理器上例題1．若P、V操作的信號量S初值為2，當前值為-1，則表示有_____D____等待進程。A．0個B．1個C．2個D．3個2．用P、V操作管理互斥區時，信號量的初值應定義為_____C_____。A.-1B．0C．1D．任意值3．用V操作喚醒一個等待進程時，被喚醒進程的狀態變為____B______。A.等待B．就緒C運行D．完成4.有m個進程共享同一臨界資源，若使用信號量機制實現對臨界資源的互斥訪問，則信號量值的變化范圍是__1-m~1____。5．兩個進程合作完成一個任務。在并發執行中，一個進程要等待其合作伙伴發來消息，或者建立某個條件后再向前執行，這種制約性合作關系被稱為進程的____A____。A.同步B．互斥C.調度D．執行6．對于兩個并發進程，設互斥信號量為mutex，若mutex=O，則____B_____。A.表示沒有進程進入臨界區B.表示有一個進程進入臨界區C.表示有一個進程進入臨界區，另一個進程等待進入D.表示有兩個進程進入臨界區7.信號量的物理意義是當信號量值大于零時表示__①系統中可供分配的資源的數目__；當信號量值小于零時，其絕對值為__②_在信號量鏈表中已阻塞進程的數目_。8.臨界資源的概念是__①同一時間內只允許一個進程訪問的資源稱臨界資源__，而臨界區是指__②每個進程中訪問臨界資源的那段代碼_。9.下面所述步驟中，__A____不是創建進程所必需的。A.由調度程序為進程分配CPUB．建立一個PCBC.為進程分配內存D．將進程控制塊鏈入就緒隊列10．在多道程序環境下，操作系統分配資源以＿C＿＿為基本單位，調度執行以＿D＿為基本單位。A．程序B．指令C進程D．線程11.某進程的一個線程處于阻塞狀態，則該進程必然處于阻塞狀態。（F）12.在操作系統中引入線程概念的主要目的是處理進程與進程之間的競爭。（F）引入進程的目的：為了使多個程序并發執行，以提高資源利用率和系統吞吐量；進入線程的目的：減少程序在并發執行時所付出的時空開銷，使OS具有更好的并發性。13.在多道程序設計環境中，為了提高CPU的效率，內存中的進程越多越好。（F）思考題1、（南京大學2000年研究生試題）桌上有一只盤子，最多可容納兩個水果，每次只能放入或取出一個水果。爸爸專向盤中放蘋果，媽媽放專向盤中放桔子；兩個兒子專等吃盤子中的桔子，兩個女兒專等吃盤子中的蘋果。請用P、V操作來實現爸爸、媽媽、兒子、女兒之間的同步與互斥關系。2、某招待所有100個床位，住宿者住入要先登記（在登記表上填寫姓名及床位號），離去時要撤消登記（在登記表上刪去姓名和床位號）。請給出住宿登記及撤消登記過程的算法描述。3、一閱覽室，讀者進入閱覽室必須先在一張登記表（TB）上登記，該表為每一座位設一個表目，讀者離開時要消掉其登記信息，閱覽室共有100個座位。請寫出進程間的同步算法。約定：（1）flag的值：0座位空閑，1座位被占用。（2）用語句i=getflag（0）可搜索到一個空座位i，用語句i.falg=0或1可給標志位賦值。（3）用i=getname（readername）可搜索到某讀者所登記的座位號i；用=0或=readername可給姓名字段賦值，0表示消除讀者姓名。（4）計數信號量用count，互斥信號量用mutex。4、某寺廟，有小和尚、老和尚若干。有一水缸，有小和尚提水入缸供老和尚飲用。水缸可容10桶水，水取自同一井中。水井徑窄，每次只能容一個桶取水。水桶總數為3個。每次入、取缸水僅為1桶，且不可同時進行。試給出有關取水、入水的算法描述。第三章（1）高級調度（作業調度、長程調度）：把外存上處于后備狀態的作業按照一定的算法，調入內存，創建該作業的進程，再將新進程排在就緒隊列上。低級調度（進程調度、短程調度）：決定在就緒隊列中哪一個進程將分配到處理機，并由分派程序把處理機實際分配給這個進程。三種操作系統都有低級調度。中級調度涉及進程在內外存間的交換（2）作業：包含程序、數據和JCB（作業控制塊）（3）分時系統和實時系統中沒有作業調度（4）接納多少個作業取決于多道程序度；接納哪些作業取決于調度算法。（5）進程調度中的三個基本機制：排隊器、分派器、上下文切換機制（當前程序—分派程序—新程序）（6）進程調度方式：非搶占方式、搶占方式（7）周轉時間：從作業被提交給系統開始，到作業完成為止的時間間隔；響應時間：從用戶提交一個請求到系統產生首次響應；吞吐量：單位時間內系統完成的作業數。（8）先來先服務（FCFS）：eq\o\ac(○,1)有利于CPU繁忙型的作業，不利于I/0繁忙型作業。eq\o\ac(○,2)有利于長作業（進程），而不利于短作業（進程）。eq\o\ac(○,3)不能保證良好的響應時間，在處理交互用戶時很少用這種方法。（9）短作業（進程）優先調度算法SJ(P)F；優先權（級）調度算法；（10）高響應比優先調度算法（動態優先權）：優先權=（等待時間+要求服務的時間）/（11）RR：時間片輪轉算法（同一時刻新來的進程在剛結束的進程之前）（12）多級反饋隊列調度算法：插到第一隊列隊尾，在該時間片下沒有運行完則插到下一級隊列的隊尾；僅當上一級的隊列為空才調度本級隊列；級別越低，時間片越長。（13）死鎖：所謂死鎖,是指多個進程因競爭資源而造成的一種僵局,若無外力作用,這些進程將永遠不能再向前推進.（13）產生死鎖的必要條件：互