操作系統(tǒng)實驗指導(dǎo)書煙臺大學(xué)計算機學(xué)院操作系統(tǒng)課程組2008-9-20第一部分 操作系統(tǒng)上機指導(dǎo)Linux操作系統(tǒng)環(huán)境：RedHat Enterprise Linux ES release 3 (Taroon Update 1) (2.4.21-9.EL)Red Flag Linux release 4.0 (HOT) (2.4)登錄到系統(tǒng)RedHat LinuxRed Flag Linux啟動Grub啟動Grub在GRUB中選擇Red Flag Linux （Console Mode） /*命令行模式*/在GRUB中選擇RedHat Enterprise Linux ES(2.4.21-9.EL)登錄界面*用戶名：root *密碼：computerLocalhost Login:Password:注意密碼沒有回顯登錄成功Last login:web Oct 20 15:35:17 tty1rootlocalhost root#常用命令練習(xí)：用root賬號（超級用戶）注冊，口令為computer（注意大小寫）。注冊成功出現(xiàn)#號（超級用戶系統(tǒng)提示符,普通用戶的系統(tǒng)提示符為$）。1 注銷（退出）系統(tǒng)：logout 或exit3練習(xí)使用命令ls（注意Linux命令區(qū)分大小寫。）使用ls 查看當(dāng)前目錄內(nèi)容；使用ls 查看指定目錄內(nèi)容，如/目錄，/etc目錄使用ls all 查看當(dāng)前目錄內(nèi)容；使用dir 查看當(dāng)前目錄內(nèi)容 4使用cd改變當(dāng)前目錄cd . 回到上層目錄 ；cd / 回到根目錄5pwd 顯示當(dāng)前路徑 6建立目錄mkdir mkdir 目錄名 ； mkdir /home/s2001/newdir 7刪除目錄：rmdir；8復(fù)制文件cp： 如 cp 文件名1 文件名29移動文件或目錄: mv 10刪除文件 rm11. 顯示文件內(nèi)容：more (分頁顯示); 12. 顯示文件：cat 文件名 建立文件：cat 文件名，ctrl+d結(jié)束輸入使用編輯器vi 編輯文件1. 進(jìn)入linux的文本模式之后，在命令行鍵入vi filename.c 然后回車。下面作一些簡單的解釋：首先vi命令是打開vi編輯器。后面的filename.c是用戶即將編輯的c文件名字，注意擴展名字是.c；當(dāng)然，vi編輯器功能很強，可以用它來編輯其它格式的文件，比如匯編文件，其擴展名字是.s；也可以直接用vi打開一個新的未命名的文件，當(dāng)保存的時候再給它命名，只是這樣做不很方便。2. 最基本的命令I(lǐng) ：當(dāng)進(jìn)入剛打開的文件時，不能寫入信息，這時按一下鍵盤上的I鍵（insert），插入的意思，就可以進(jìn)入編輯模式了。如下圖所示： 3. a與i是相同的用法4. 當(dāng)文件編輯完后，需要保存退出，這時需要經(jīng)過以下幾個步驟：1）按一下鍵盤上的Esc 鍵；2）鍵入冒號(：)，緊跟在冒號后面是wq（意思是保存并退出）。如果不想保存退出，則在第二步鍵入冒號之后，鍵入q！（不帶w，機尾部保存）。如下圖所示：5. 退出vi編輯器的編輯模式之后，要對剛才編寫的程序進(jìn)行編譯。編譯的命令是：gcc filename.c -o outputfilename.out，其中g(shù)cc是c的編譯器。參數(shù)：filename.c 是要編譯的源文件的名稱，outputfilename表示輸出文件名稱，中括號表示括號內(nèi)部的內(nèi)容可輸入也可以不輸入（中括號本身不再命令行中出現(xiàn)）。如果不輸入outputfilename.out，默認(rèn)的輸出文件是a.out 。6. 最后一步是運行程序，方法如下：./outputfilename.out添加新用戶、修改文件屬性1 添加新用戶（在root下，按默認(rèn)值回答）adduser 用戶名；如adduser s2001 ; 以新用戶登錄到系統(tǒng)2修改用戶口令 passwd 用戶名3控制文件屬性使用ls l 查看文件屬性改變用戶的所有權(quán)：chown 用戶名 文件名改變文件權(quán)限：chmod g+w 文件名；chmod o-r 文件名或使用數(shù)字方式修改：如chmod 644文件名；chmod 755文件名u (user用戶)，g ( group組)，o (other其他); w 寫訪問權(quán)限,r 讀訪問權(quán)限, x 執(zhí)行權(quán)限4查看相關(guān)命令的幫助：man 命令名5顯示當(dāng)前系統(tǒng)中已注冊的用戶信息：who6顯示當(dāng)前注冊的用戶信息：whoami Tip:與文件鏈接的數(shù)Unix文件目錄的屬性顯示格式：如：-rw-rw-rw- 1 steve users 138 Apr 5 19:34 readme文件的訪問權(quán)限文件的擁有者用戶所在的組文件或目錄名drwxrwxrwx 3 steve users 80 Apr 5 19:43 dir1 最后修改的日期和時間三種權(quán)限： owner group others第二部分 操作系統(tǒng)實驗實驗1 Linux基本環(huán)境1、實驗?zāi)康?（1）熟悉Linux下的基本操作，學(xué)會使用各種Shell命令去操作Linux，對Linux有一個感性認(rèn)識。 （2）學(xué)會使用vi編輯器編輯簡單的C語言程序，并能對其編譯和調(diào)試。2、實驗預(yù)備內(nèi)容（1）參閱相關(guān)Linux操作系統(tǒng)的安裝手冊，熟悉Linux的基本安裝和配置；（2）參閱相關(guān)Linux的命令參考手冊，熟悉Linux下的操作命令。3、實驗內(nèi)容（1） 以root用戶身份登陸，并使用“l(fā)s”,“cat”“cd”等命令來實現(xiàn)基本的文件操作并觀察Linux文件系統(tǒng)的特點；（2） 使用vi編輯器編寫一C程序，并用gcc命令進(jìn)行編譯和鏈接，并用a.out來進(jìn)行輸出結(jié)果。4、思考 （1）Linux系統(tǒng)在用戶登陸和操作界面以及文件系統(tǒng)上有哪些特點？實驗2 進(jìn)程管理1、實驗?zāi)康?（1）加深對進(jìn)程概念的理解，明確進(jìn)程和程序的區(qū)別。 （2）進(jìn)一步認(rèn)識并發(fā)執(zhí)行的實質(zhì)。 （3）分析進(jìn)程競爭資源現(xiàn)象，學(xué)習(xí)解決進(jìn)程互斥的方法。 （4）了解Linux系統(tǒng)中進(jìn)程通信的基本原理。2、實驗預(yù)備內(nèi)容 （1）閱讀Linux的sched.h源文件，加深對進(jìn)程管理概念的理解。 （2）閱讀Linux的fork.c源文件，分析進(jìn)程的創(chuàng)建過程。3、實驗內(nèi)容 （1）進(jìn)程的創(chuàng)建 編寫一段源程序，使系統(tǒng)調(diào)用fork()創(chuàng)建兩個子進(jìn)程，當(dāng)此程序運行時，在系統(tǒng)中有一個父進(jìn)程和兩個子進(jìn)程活動。讓每一個進(jìn)程在屏幕上顯示一個字符：父進(jìn)程顯示字符“a”;子進(jìn)程分別顯示字符“b”和字符“c”。試觀察紀(jì)錄屏幕上的顯示結(jié)果，并分析原因。 （2）進(jìn)程的控制 修改已編寫的程序，將每個進(jìn)程輸出一個字符改為每個進(jìn)程輸出一句話，在觀察程序執(zhí)行時屏幕出現(xiàn)的現(xiàn)象，并分析原因。 如果在程序中使用調(diào)用lockf()來給每一個子進(jìn)程加鎖，可以實現(xiàn)進(jìn)程之間的互斥，觀察并分析出現(xiàn)的現(xiàn)象。 （3）編寫一段程序，使其現(xiàn)實進(jìn)程的軟中斷通信。 要求：使用系統(tǒng)調(diào)用fork()創(chuàng)建兩個子進(jìn)程，再用系統(tǒng)調(diào)用signal()讓父進(jìn)程捕捉鍵盤上來的中斷信號（即按DEL鍵）；當(dāng)捕捉到中斷信號后，父進(jìn)程用系統(tǒng)調(diào)用Kill()向兩個子進(jìn)程發(fā)出信號，子進(jìn)程捕捉到信號后分別輸出下列信息后終止： Child Processll is Killed by Parent! Child Processl2 is Killed by Parent! 父進(jìn)程等待兩個子進(jìn)程終止后，輸出如下的信息后終止 Parent Process is Killed! 在上面的程序中增加語句signal (SIGNAL, SIG-IGN) 和signal (SIGQUIT, SIG-IGN), 觀察執(zhí)行結(jié)果，并分析原因。 （4）進(jìn)程的管道通信 編制一段程序，實現(xiàn)進(jìn)程的管理通信。 使用系統(tǒng)調(diào)用pipe()建立一條管道線；兩個子進(jìn)程P1和P2分別向管道中寫一句話： Child 1 is sending a message! Child 2 is sending a message! 而父進(jìn)程則從管道中讀出來自于兩個子進(jìn)程的信息，顯示在屏幕上。 要求父進(jìn)程先接收子進(jìn)程P1發(fā)來的消息，然后再接收子進(jìn)程P2發(fā)來的消息。4、思考 （1）系統(tǒng)是怎樣創(chuàng)建進(jìn)程的？ （2）可執(zhí)行文件加載時進(jìn)行了哪些處理？ （3）當(dāng)首次調(diào)用新創(chuàng)建進(jìn)程時，其入口在哪里？ （4）進(jìn)程通信有什么特點？實驗3 進(jìn)程間通信1、實驗?zāi)康?Linux系統(tǒng)的進(jìn)程通信機構(gòu) (IPC) 允許在任意進(jìn)程間大批量地交換數(shù)據(jù)。本實驗的目的是了解和熟悉Linux支持的消息通訊機制及信息量機制。2、實驗預(yù)備內(nèi)容 閱讀Linux系統(tǒng)的msg.c、sem.c和shm.c等源碼文件，熟悉Linux的三種機制。3、實驗內(nèi)容 （1）消息的創(chuàng)建，發(fā)送和接收。 使用系統(tǒng)調(diào)用msgget (), msgsnd (), msgrev (), 及msgctl () 編制一長度為1k的消息的發(fā)送和接收程序。 觀察上面的程序，說明控制消息隊列系統(tǒng)調(diào)用msgctl () 在此起什么作用？ （2）共享存儲區(qū)的創(chuàng)建、附接和段接。 使用系統(tǒng)調(diào)用shmget(),shmat(),sgmdt(),shmctl(),編制一個與上述功能相同的程序。（3） 比較上述（1），（2）兩種消息通信機制中數(shù)據(jù)傳輸?shù)臅r間。實驗4 存儲管理1、實驗?zāi)康?存儲管理的主要功能之一是合理地分配空間。請求頁式管理是一種常用的虛擬存儲管理技術(shù)。 本實驗的目的是通過請求頁式存儲管理中頁面置換算法模擬設(shè)計，了解虛擬存儲技術(shù)的技術(shù)特點，掌握請求頁式存儲管理的頁面置換算法。2、實驗內(nèi)容 （1）通過隨機數(shù)產(chǎn)生一個指令序列，共320條指令。指令的地址按下述原則生成： 50%的指令是順序執(zhí)行的； 50%的指令是均勻分布在前地址部分； 50%的指令是均勻分布在后地址部分。 具體的實施方法是： 在 0，319 的指令之間隨即選取一起點m; 順序執(zhí)行一條指令，即執(zhí)行地址為m+1的指令； 在前地址0，m+1中隨機選取一條指令并執(zhí)行，該指令的地址為m； 順序執(zhí)行一條指令，其地址為 m+ 1； 在后地址m+ 2，319中隨機選取一條指令并執(zhí)行； 重復(fù)上述步驟-，直到執(zhí)行320次指令。 （2）將指令序列變換為頁地址流 設(shè)：頁面大小為1k； 用戶內(nèi)存容量為4頁到32頁； 用戶虛存容量為32k。 在用戶虛存中，按每k存放10條指令排在虛存地址，即320條指令在虛存中的存放方式為： 第0條-第9條指令為第0頁（對應(yīng)虛存地址為0，9）； 第10條-第19條指令為第一頁（對應(yīng)虛存地址為10，19）； 第310條第319條指令為第31頁（對應(yīng)虛地址為310，319）。 按以上方式，用戶指令可組成32頁。 （3）計算并輸出下述各種算法在不同內(nèi)存容量下的命中率。 先進(jìn)先出的算法（FIFO）； 最近最少使用算法（LRR)； 最佳淘汰算法（OPT）先淘汰最不常用的頁地址； 最少訪問頁面算法（LFR）； 最近最不經(jīng)常使用算法（NUR）。 其中和為選擇內(nèi)容。命中率=1-頁面失效次數(shù)/頁地址流長度 在本實驗中，頁地址流長度為320，頁面失效次數(shù)為每次訪問相應(yīng)指令時，該指令所對應(yīng)的頁不在內(nèi)存的次數(shù)。3、隨機數(shù)產(chǎn)生辦法，Linux或UNIX系統(tǒng)提供函數(shù)strand()和rand(),分別進(jìn)行初始化和產(chǎn)生隨機數(shù)。例如： srand (); 語句可初始化一個隨機數(shù)； a0=10*rand()/65535*319+1; a1=10*rand()/65535*a0;語句可用來產(chǎn)生a0與a1中的隨機數(shù)。實驗5 文件系統(tǒng)設(shè)計1、實驗?zāi)康?通過一個簡單多用戶文件系統(tǒng)的設(shè)計，加深理解文件系統(tǒng)的內(nèi)部功能及內(nèi)部實現(xiàn)。2、實驗內(nèi)容 為linux系統(tǒng)設(shè)計一個簡單的二級文件系統(tǒng)。要求做到以下幾點： （1）可以實現(xiàn)下列幾條命令（至少4條）； login用戶登陸 dir 列文件目錄 create創(chuàng)建文件 delete刪除文件 open 打開文件 close關(guān)閉文件 read 讀文件 write寫文件 （2）列目錄時要列出文件名、物理地址、保護(hù)碼和文件長度； （3）源文件可以進(jìn)行讀寫保護(hù)。3、實驗提示 （1）首先應(yīng)確定文件系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)：主目錄、子目錄及活動文件等。主目錄和子目錄都以文件的形式存放于磁盤，這樣便于查找和修改。 （2）用戶創(chuàng)建的文件，可以編號存儲于磁盤上。如file0，file1,file2.并以編號作為物理地址，在目錄中進(jìn)行登記。實驗6 處理器調(diào)度一、實驗內(nèi)容選擇一個調(diào)度算法，實現(xiàn)處理器調(diào)度。二、實驗?zāi)康脑诓捎枚嗟莱绦蛟O(shè)計的系統(tǒng)中，往往有若干個進(jìn)程同時處于就緒狀態(tài)。當(dāng)就緒進(jìn)程個數(shù)大于處理器數(shù)時，就必須依照某種策略來決定哪些進(jìn)程優(yōu)先占用處理器。本實驗?zāi)M在單處理器情況下的處理器調(diào)度，幫助學(xué)生加深了解處理器調(diào)度的工作。三、實驗題目本實驗有兩個題，學(xué)生可選擇其中的一題做實驗。第一題：設(shè)計一個按優(yōu)先數(shù)調(diào)度算法實現(xiàn)處理器調(diào)度的程序。提示：(1) 假定系統(tǒng)有五個進(jìn)程，每一個進(jìn)程用一個進(jìn)程控制塊PCB來代表，進(jìn)程控制塊的格式為：進(jìn)程名指針要求運行時間優(yōu)先數(shù)狀態(tài)其中，進(jìn)程名作為進(jìn)程的標(biāo)識，假設(shè)五個進(jìn)程的進(jìn)程名分別為P1，P2，P3，P4，P5。指針按優(yōu)先數(shù)的大小把五個進(jìn)程連成隊列，用指針指出下一個進(jìn)程的進(jìn)程控制塊的首地址，最后一個進(jìn)程中的指針為“0”。要求運行時間假設(shè)進(jìn)程需要運行的單位時間數(shù)。優(yōu)先數(shù)賦予進(jìn)程的優(yōu)先數(shù)，調(diào)度時總是選取優(yōu)先數(shù)大的進(jìn)程先執(zhí)行。狀態(tài)可假設(shè)有兩種狀態(tài)，“就緒”狀態(tài)和“結(jié)束”狀態(tài)。五個進(jìn)程的初始狀態(tài)都為“就緒”，用“R”表示，當(dāng)一個進(jìn)程運行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”表示。(2) 在每次運行你所設(shè)計的處理器調(diào)度程序之前，為每個進(jìn)程任意確定它的“優(yōu)先數(shù)”和“要求運行時間”。(3) 為了調(diào)度方便，把五個進(jìn)程按給定的優(yōu)先數(shù)從大到小連成隊列。用一單元指出隊首進(jìn)程，用指針指出隊列的連接情況。例： 隊首標(biāo)志 K2 K1P1 K2P2 K3P3 K4P4 K5P50K4K5K3K12312415342RRRRRPCB1PCB2PCB3PCB4PCB5(4) 處理器調(diào)度總是選隊首進(jìn)程運行。采用動態(tài)改變優(yōu)先數(shù)的辦法，進(jìn)程每運行一次優(yōu)先數(shù)就減“1”。由于本實驗是模擬處理器調(diào)度，所以，對被選中的進(jìn)程并不實際的啟動運行，而是執(zhí)行：優(yōu)先數(shù)-1要求運行時間-1來模擬進(jìn)程的一次運行。提醒注意的是：在實際的系統(tǒng)中，當(dāng)一個進(jìn)程被選中運行時，必須恢復(fù)進(jìn)程的現(xiàn)場，讓它占有處理器運行，直到出現(xiàn)等待事件或運行結(jié)束。在這里省去了這些工作。(5) 進(jìn)程運行一次后，若要求運行時間0，則再將它加入隊列（按優(yōu)先數(shù)大小插入，且置隊首標(biāo)志）；若要求運行時間=0，則把它的狀態(tài)修改成“結(jié)束”（E），且退出隊列。(6) 若“就緒”狀態(tài)的進(jìn)程隊列不為空，則重復(fù)上面（4）和（5）的步驟，直到所有進(jìn)程都成為“結(jié)束”狀態(tài)。(7) 在所設(shè)計的程序中應(yīng)有顯示或打印語句，能顯示或打印每次被選中進(jìn)程的進(jìn)程名以及運行一次后進(jìn)程隊列的變化。(8) 為五個進(jìn)程任意確定一組“優(yōu)先數(shù)”和“要求運行時間”，啟動所設(shè)計的處理器調(diào)度程序，顯示或打印逐次被選中進(jìn)程的進(jìn)程名以及進(jìn)程控制塊的動態(tài)變化過程。第二題：設(shè)計一個按時間片輪轉(zhuǎn)法實現(xiàn)處理器調(diào)度的程序。提示：(1) 假定系統(tǒng)有五個進(jìn)程，每一個進(jìn)程用一個進(jìn)程控制塊PCB來代表。進(jìn)程控制塊的格式為：進(jìn)程名指針要求運行時間已運行時間狀態(tài)其中，進(jìn)程名作為進(jìn)程的標(biāo)識，假設(shè)五個進(jìn)程的進(jìn)程名分別為Q1，Q2，Q3，Q4，Q5。指針進(jìn)程按順序排成循環(huán)隊列，用指針指出下一個進(jìn)程的進(jìn)程控制塊的首地址，最后一個進(jìn)程的指針指出第一個進(jìn)程的進(jìn)程控制塊首地址。要求運行時間假設(shè)進(jìn)程需要運行的單位時間數(shù)。已運行時間假設(shè)進(jìn)程已經(jīng)運行的單位時間數(shù)，初始值為“0”。狀態(tài)有兩種狀態(tài)，“就緒”和“結(jié)束”，初始狀態(tài)都為“就緒”，用“R”表示。當(dāng)一個進(jìn)程運行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”表示。(2) 每次運行所設(shè)計的處理器調(diào)度程序前，為每個進(jìn)程任意確定它的“要求運行時間”。(3) 把五個進(jìn)程按順序排成循環(huán)隊列，用指針指出隊列連接情況。另用一標(biāo)志單元記錄輪到運行的進(jìn)程。例如，當(dāng)前輪到P2執(zhí)行，則有：標(biāo)志單元 K2 K1Q1 K2Q2 K3Q3 K4Q4 K5Q5K2K3K4K5K12312410000RRRRRPCB1PCB2PCB3PCB4PCB5(4) 處理器調(diào)度總是選擇標(biāo)志單元指示的進(jìn)程運行。由于本實驗是模擬處理器調(diào)度的功能，所以，對被選中的進(jìn)程并不實際的啟動運行，而是執(zhí)行：已運行時間+1來模擬進(jìn)程的一次運行，表示進(jìn)程已經(jīng)運行過一個單位的時間。請同學(xué)注意：在實際的系統(tǒng)中，當(dāng)一個進(jìn)程被選中運行時，必須置上該進(jìn)程可以運行的時間片值，以及恢復(fù)進(jìn)程的現(xiàn)場，讓它占有處理器運行，直到出現(xiàn)等待事件或運行滿一個時間片。在這時省去了這些工作，僅用“已運行時間+1”來表示進(jìn)程已經(jīng)運行滿一個時間片。(5) 進(jìn)程運行一次后，應(yīng)把該進(jìn)程的進(jìn)程控制塊中的指針值送到標(biāo)志單元，以指示下一個輪到運行的進(jìn)程。同時，應(yīng)判斷該進(jìn)程的要求運行時間與已運行時間，若該進(jìn)程的要求運行時間已運行時間，則表示它尚未執(zhí)行結(jié)束，應(yīng)待到下一輪時再運行。若該進(jìn)程的要求運行時間=已運行時間，則表示它已經(jīng)執(zhí)行結(jié)束，應(yīng)指導(dǎo)它的狀態(tài)修改成“結(jié)束”（E）且退出隊列。此時，應(yīng)把該進(jìn)程的進(jìn)程控制塊中的指針值送到前面一個進(jìn)程的指針位置。(6) 若“就緒”狀態(tài)的進(jìn)程隊列不為空，則重復(fù)上面的（4）和（5）的步驟，直到所有的進(jìn)程都成為“結(jié)束”狀態(tài)。(7) 在所設(shè)計的程序中應(yīng)有顯示或打印語句，能顯示或打印每次選中進(jìn)程的進(jìn)程名以及運行一次后進(jìn)程隊列的變化。(8) 為五個進(jìn)程任意確定一組“要求運行時間”，啟動所設(shè)計的處理器調(diào)度程序，顯示或打印逐次被選中的進(jìn)程名以及進(jìn)程控制塊的動態(tài)變化過程。四、實驗報告(1) 實驗題目。(2) 程序中使用的數(shù)據(jù)結(jié)構(gòu)及符號說明。(3) 流程圖。(4) 打印一份源程序并附上注釋。(5) 打印程序運行時的初值和運行結(jié)果。要求如下： 進(jìn)程控制塊的初始狀態(tài)。 選中運行的進(jìn)程名以及選中進(jìn)程運行后的各進(jìn)程控制塊狀態(tài)。對于要求每選中一個進(jìn)程運行后都要打印。實驗7 主存儲器空間的分配和回收一、實驗內(nèi)容主存儲器空間的分配和回收。二、實驗?zāi)康囊粋€好的計算機系統(tǒng)不僅要有一個足夠容量的、存取速度高的、穩(wěn)定可靠的主存儲器，而且要能合理地分配和使用這些存儲空間。當(dāng)用戶提出申請存儲器空間時，存儲管理必須根據(jù)申請者的要求，按一定的策略分析主存空間的使用情況，找出足夠的空閑區(qū)域分配給申請者。當(dāng)作業(yè)撤離或主動歸還主存資源時，則存儲管理要收回作業(yè)占用的主存空間或歸還部分主存空間。主存的分配和回收的實現(xiàn)雖與主存儲器的管理方式有關(guān)的，通過本實驗幫助學(xué)生理解在不同的存儲管理方式下應(yīng)怎樣實現(xiàn)主存空間的分配和回收。三、實驗題目本實驗?zāi)M在兩種存儲管理方式下的主存分配和回收。第一題：在可變分區(qū)管理方式下采用最先適應(yīng)算法實現(xiàn)主存分配和實現(xiàn)主存回收。提示：可變分區(qū)方式是按作業(yè)需要的主存空間大小來分割分區(qū)的。當(dāng)要裝入一個作業(yè)時，根據(jù)作業(yè)需要的主存量查看是否有足夠的空閑空間，若有，則按需要量分割一個分區(qū)分配給該作業(yè)；若無，則作業(yè)不能裝入。隨著作業(yè)的裝入、撤離，主存空間被分成許多個分區(qū)，有的分區(qū)被作業(yè)占用，而有的分區(qū)是空閑的。例如：05k10k14k26k32k128k操作系統(tǒng)作業(yè)1作業(yè)3空閑區(qū)作業(yè)2空閑區(qū)為了說明哪些區(qū)是空閑的，可以用來裝入新作業(yè)，必須要有一張空閑區(qū)說明表，格式如下：起 址長 度狀 態(tài)第一欄14 K12 K未 分 配第二欄32 K96 K未 分 配MM空 表 目空 表 目MM其中，起址指出一個空閑區(qū)的主存起始地址。 長度指出從起始地址開始的一個連續(xù)空閑的長度。 狀態(tài)有兩種狀態(tài)，一種是“未分配”狀態(tài)，指出對應(yīng)的由起址指出的某個長度的區(qū)域是空閑區(qū)；另一種是“空表目”狀態(tài)，表示表中對應(yīng)的登記項目是空白（無效），可用來登記新的空閑區(qū)（例如，作業(yè)撤離后，它所占的區(qū)域就成了空閑區(qū)，應(yīng)找一個“空表目”欄登記歸還區(qū)的起址和長度且修改狀態(tài)）。由于分區(qū)的個數(shù)不定，所以空閑區(qū)說明表中應(yīng)有適量的狀態(tài)為“空表目”的登記欄目，否則造成表格“溢出”無法登記。上述的這張說明表的登記情況是按提示（1）中的例所裝入的三個作業(yè)占用的主存區(qū)域后填寫的。(2) 當(dāng)有一個新作業(yè)要求裝入主存時，必須查空閑區(qū)說明表，從中找出一個足夠大的空閑區(qū)。有時找到的空閑區(qū)可能大于作業(yè)需要量，這時應(yīng)把原來的空閑區(qū)變成兩部分：一部分分給作業(yè)占用；另一部分又成為一個較小的空閑區(qū)。為了盡量減少由于分割造成的空閑區(qū)，而盡量保存高地址部分有較大的連續(xù)空閑區(qū)域，以利于大型作業(yè)的裝入。為此，在空閑區(qū)說明表中，把每個空閑區(qū)按其地址順序登記，即每個后繼的空閑區(qū)其起始地址總是比前者大。為了方便查找還可使表格“緊縮”，總是讓“空表目”欄集中在表格的后部。(3) 采用最先適應(yīng)算法（順序分配算法）分配主存空間。按照作業(yè)的需要量，查空閑區(qū)說明表，順序查看登記欄，找到第一個能滿足要求的空閑區(qū)。當(dāng)空閑區(qū)大于需要量時，一部分用來裝入作業(yè)，另一部分仍為空閑區(qū)登記在空閑區(qū)說明表中。由于本實驗是模擬主存的分配，所以把主存區(qū)分配給作業(yè)后并不實際啟動裝入程序裝入作業(yè)，而用輸出“分配情況”來代替。最先適應(yīng)分配算法如圖4-1。(4) 當(dāng)一個作業(yè)執(zhí)行結(jié)束撤離時，作業(yè)所占的區(qū)域應(yīng)該歸還，歸還的區(qū)域如果與其它空閑區(qū)相鄰，則應(yīng)合成一個較大的空閑區(qū)，登記在空閑區(qū)說明表中。例如，在提示（1）中列舉的情況下，如果作業(yè)2撤離，歸還所占主存區(qū)域時，應(yīng)與上、下相鄰的空閑區(qū)一起合成一個大的空閑區(qū)登記在空閑區(qū)說明表中。歸還主存時的回收算法如圖4-2。(5) 請按最先適應(yīng)算法設(shè)計主存分配和回收的程序。然后按（1）中假設(shè)主存中已裝入三個作業(yè)，且形成兩個空閑區(qū)，確定空閑區(qū)說明表的初值。現(xiàn)有一個需要主存量為6K的作業(yè)4申請裝入主存；然后作業(yè)3撤離；再作業(yè)2撤離。請你為它們進(jìn)行主存分配和回收，把空閑區(qū)說明表的初值以及每次分配或回收后的變化顯示出來或打印出來。第二題：在分頁式管理方式下采用位示圖來表示主存分配情況，實現(xiàn)主存空間的分配和回收。提示：(1) 分頁式存儲器把主存分成大小相等的若干塊，作業(yè)的信息也按塊的大小分頁，作業(yè)裝入主存時可把作業(yè)的信息按頁分散存放在主存的空閑塊中，為了說明主存中哪些塊已經(jīng)被占用，哪些塊是尚未分配的空閑塊，可用一張位示圖來指出。位示圖可由若干存儲單元來構(gòu)成，其中每一位與一個物理塊對應(yīng)，用0/1表示對應(yīng)塊為空閑/已占用。(2) 假設(shè)某系統(tǒng)的主存被分成大小相等的64塊，則位示圖可用8個字節(jié)來構(gòu)成，另用一單元記錄當(dāng)前空閑塊數(shù)。如果已有第0，1，4，5，6，9，11，13，24，31，共10個主存塊被占用了，那么位示圖情況如下：字 位 節(jié) 數(shù) 號01234567 011001110 101010100 200000000 310000001 400000000 500000000 600000000 700000000圖4-1 最先適應(yīng)分配模擬算法圖4-2 主存回收算法(3) 當(dāng)要裝入一個作業(yè)時，根據(jù)作業(yè)對主存的需要量，先查當(dāng)前空閑塊數(shù)是否能滿足作業(yè)要求，若不能滿足則輸出分配不成功。若能滿足，則查位示圖，找出為“0”的一些位，置上占用標(biāo)志“1”，從“當(dāng)前空閑塊數(shù)”中減去本次占用塊數(shù)。按找到的計算出對應(yīng)的塊號，其計算公式為： 塊號= j8+i其中，j表示找到的是第n個字節(jié)，I表示對應(yīng)的是第n位。根據(jù)分配給作業(yè)的塊號，為作業(yè)建立一張頁表，頁表格式：頁 號塊 號012MM(4) 當(dāng)一個作業(yè)執(zhí)行結(jié)束，歸還主存時，根據(jù)該作業(yè)的頁表可以知道應(yīng)歸還的塊號，由塊號可計算出在位示圖中的對應(yīng)位置，把對應(yīng)位的占用標(biāo)志清成“0”，表示對應(yīng)的塊已成為空閑塊。歸還的塊數(shù)加入到當(dāng)前空閑塊數(shù)中。由塊號計算在位示圖中的位置的公式如下：字節(jié)號 j=塊號/8 （ 表示取整）位數(shù) i=塊號/8 （ 表示取余）(5) 設(shè)計實現(xiàn)主存分配和回收的程序。假定位示圖的初始狀態(tài)如（2）所述，現(xiàn)有一信息量為5頁的作業(yè)要裝入，運行你所設(shè)計的分配程序，為作業(yè)分配主存且建立頁表（格式如（3）所述）。然后假定有另一作業(yè)執(zhí)行結(jié)束，它占用的塊號為第4，5，6和31塊，運行你所設(shè)計的回收程序，收回作業(yè)歸還的主存塊。要求能顯示和打印分配或回收前后的位示圖和當(dāng)前空閑塊數(shù)，對完成一次分配后還要顯示或打印為作業(yè)建立的頁表。四、實驗報告(1) 實驗題目。(2) 程序中使用的數(shù)據(jù)結(jié)構(gòu)及符號說明。(3) 流程圖。(4) 打印一份源程序并附上注釋。(5) 打印程序運行時的初值和運行結(jié)果，要求如下：第一題：打印空閑區(qū)說明表的初始狀態(tài)，作業(yè)4的申請量以及為作業(yè)4分配后的空閑區(qū)說明表狀態(tài)；再依次打印作業(yè)3和作業(yè)2的歸還量以及回收作業(yè)3，作業(yè)2所占主存后的空閑區(qū)說明表。第二題：打印位示圖和當(dāng)前空閑塊數(shù)的初值；要求裝入的作業(yè)對主存的申請量，為作業(yè)分配后的位示圖、當(dāng)前空閑塊數(shù)和頁表；作業(yè)歸還的塊號、回收作業(yè)所占主存后的位示圖和當(dāng)前空閑塊數(shù)。第三部分 操作系統(tǒng)實驗指導(dǎo)實驗2 指導(dǎo)實驗內(nèi)容1 進(jìn)程的創(chuàng)建任務(wù)編寫一段程序，使用系統(tǒng)調(diào)用fork( )創(chuàng)建兩個子進(jìn)程。當(dāng)此程序運行時，在系統(tǒng)中有一個父進(jìn)程和兩個子進(jìn)程活動。讓每一個進(jìn)程在屏幕上顯示一個字符；父進(jìn)程顯示字符“a”，子進(jìn)程分別顯示字符“b”和“c”。試觀察記錄屏幕上的顯示結(jié)果，并分析原因。程序#includemain()int p1,p2;if(p1=fork() /*子進(jìn)程創(chuàng)建成功*/ putchar(b);else if(p2=fork() /*子進(jìn)程創(chuàng)建成功*/ putchar(c); else putchar(a); /*父進(jìn)程執(zhí)行*/bca(有時會出現(xiàn)abc的任意的排列)分析：從進(jìn)程執(zhí)行并發(fā)來看，輸出abc的排列都是有可能的。原因：fork()創(chuàng)建進(jìn)程所需的時間雖然可能多于輸出一個字符的時間，但各個進(jìn)程的時間片的獲得卻不是一定是順序的，所以輸出abc的排列都是有可能的。2 進(jìn)程的控制 修改已編寫好的程序，將每個程序的輸出由單個字符改為一句話，再觀察程序執(zhí)行時屏幕上出現(xiàn)的現(xiàn)象，并分析其原因。如果在程序中使用系統(tǒng)調(diào)用lockf()來給每個程序加鎖，可以實現(xiàn)進(jìn)程之間的互斥，觀察并分析出現(xiàn)的現(xiàn)象。程序1#includemain()int p1,p2,i;if(p1=fork() for(i=0;i500;i+) printf(parent%dn,i); wait(0); /* 保證在子進(jìn)程終止前，父進(jìn)程不會終止*/exit(0);else if(p2=fork() for(i=0;i500;i+) printf(son %dn,i); wait(0); /* 保證在子進(jìn)程終止前，父進(jìn)程不會終止*/ exit(0); /*向父進(jìn)程信號0且該進(jìn)程推出*/ else for(i=0;i500;i+) printf(“grandchild %dn,i); exit(0);運行結(jié)果parent.songrandchildgrandchild或grandchildsongrandchildsonparent分析：由于函數(shù)printf()輸出的字符串之間不會被中斷，因此,每個字符串內(nèi)部的字符順序輸出時不變。但是 , 由于進(jìn)程并發(fā)執(zhí)行時的調(diào)度順序和父子進(jìn)程的搶占處理機問題，輸出字符串的順序和先后隨著執(zhí)行的不同而發(fā)生變化。這與打印單字符的結(jié)果相同。程序2#includemain()int p1,p2,i;if(p1=fork() lockf(1,1,0); for(i=0;i500;i+) printf(parent %dn,i); lockf(1,0,0); wait(0); /* 保證在子進(jìn)程終止前，父進(jìn)程不會終止*/ exit(0);else if(p2=fork() lockf(1,1,0); for(i=0;i500;i+) printf(son %dn,i); lockf(1,0,0); wait(0); /* 保證在子進(jìn)程終止前，父進(jìn)程不會終止*/exit(0); else lockf(1,1,0); for(i=0;i500;i+) printf(daughter %dn,i); lockf(1,0,0); exit(0); 運行結(jié)果輸出parent塊,son塊,grandchild塊的順序可能不同，但是每個塊的輸出過程不會被打斷。分析：因為上述程序執(zhí)行時，lockf(1,1,0)鎖定標(biāo)準(zhǔn)輸出設(shè)備，lockf(1,0,0)解鎖標(biāo)準(zhǔn)輸出設(shè)備，在lockf(1,1,0)與lockf(1,0,0)中間的for循環(huán)輸出不會被中斷，加鎖與不加鎖效果不相同。3軟中斷通信任務(wù)1編制一段程序，使用系統(tǒng)調(diào)用fork()創(chuàng)建兩個子進(jìn)程，再用系統(tǒng)調(diào)用signal()讓父進(jìn)程捕捉鍵盤上來的中斷信號（即按ctrl+c鍵），當(dāng)捕捉到中斷信號后，父進(jìn)程用系統(tǒng)調(diào)用kill()向兩個子進(jìn)程發(fā)出信號，子進(jìn)程捕捉到信號后，分別輸出下列信息后終止：child process1 is killed by parent!child process2 is killed by parent!父進(jìn)程等待兩個子進(jìn)程終止后，輸出以下信息后終止：parent process is killed! 程序#include#include#include void waiting(),stop(),alarming();int wait_mark;main()int p1,p2;if(p1=fork() /*創(chuàng)建子進(jìn)程p1*/if(p2=fork() /*創(chuàng)建子進(jìn)程p2*/wait_mark=1;signal(SIGINT,stop); /*接收到c信號，轉(zhuǎn)stop*/signal(SIGALRM,alarming);/*接受SIGALRMwaiting();kill(p1,16); /*向p1發(fā)軟中斷信號16*/ kill(p2,17); /*向p2發(fā)軟中斷信號17*/ wait(0); /*同步*/wait(0);printf(parent process is killed!n);exit(0); else wait_mark=1;signal(17,stop);signal(SIGINT,SIG_IGN); /*忽略 c信號*/while (wait_mark!=0);lockf(1,1,0);printf(child process2 is killed by parent!n);lockf(1,0,0);exit(0);elsewait_mark=1;signal(16,stop);signal(SIGINT,SIG_IGN); /*忽略c信號*/while (wait_mark!=0)lockf(1,1,0);printf(child process1 is killed by parent!n);lockf(1,0,0);exit(0);void waiting()sleep(5);if (wait_mark!=0) kill(getpid(),SIGALRM);void alarming()wait_mark=0;void stop()wait_mark=0; 不做任何操作等待五秒鐘父進(jìn)程回在子進(jìn)程縣推出后退出，并打印退出的順序；或者點擊ctrl+C后程序退出并打印退出的順序。任務(wù)2在上面的任務(wù)1中，增加語句signal(SIGINT,SIG_IGN)和語句signal(SIGQUIT,SIG_IGN)，觀察執(zhí)行結(jié)果，并分析原因。這里，signal(SIGINT,SIG_IGN)和signal(SIGQUIT,SIG_IGN)分別為忽略鍵信號以及忽略中斷信號。#include#include#includeint pid1,pid2;int EndFlag=0;int pf1=0;int pf2=0;void IntDelete()kill(pid1,16);kill(pid2,17);void Int1()printf(child process 1 is killed !by parentn);exit(0);void Int2()printf(child process 2 is killed !by parentn);exit(0);main()int exitpid;if(pid1=fork() if(pid2=fork() signal(SIGINT,IntDelete);waitpid(-1,&exitpid,0);waitpid(-1,&exitpid,0);printf(parent process is killedn);exit(0); else signal(SIGINT,SIG_IGN);signal(17,Int2);pause(); elsesignal(SIGINT,SIG_IGN);signal(16,Int1);pause();運行結(jié)果請讀者將上述程序輸入計算機后，執(zhí)行并觀察。3 進(jìn)程的管道通信任務(wù) 編制一段程序，實現(xiàn)進(jìn)程的管道通信。使用系統(tǒng)調(diào)用pipe()建立一條管道線。兩個子進(jìn)程p1和p2分別向通道個寫一句話： child1 process is sending message!child2 process is sending message!而父進(jìn)程則從管道中讀出來自兩個進(jìn)程的信息，顯示在屏幕上。程序#include #include #include int pid1,pid2; main( ) int fd2;char outpipe100,inpipe100;pipe(fd); /*創(chuàng)建一個管道*/while (pid1=fork( )=-1);if(pid1=0) lockf(fd1,1,0); sprintf(outpipe,child 1 process is sending message!); /*把串放入數(shù)組outpipe中*/ write(fd1,outpipe,50); /*向管道寫長為50字節(jié)的串*/ sleep(5); /*自我阻塞5秒*/ lockf(fd1,0,0); exit(0); else while(pid2=fork( )=-1); if(pid2=0) lockf(fd1,1,0); /*互斥*/ sprintf(outpipe,child 2 process is sending message!); write(fd1,outpipe,50); sleep(5); lockf(fd1,0,0); exit(0); else wait(0); /*同步*/ read(fd0,inpipe,50); /*從管道中讀長為50字節(jié)的串*/ printf(%sn,inpipe); wait(0); read(fd0,inpipe,50); printf(%sn,inpipe); exit(0); 運行結(jié)果延遲5秒后顯示:child1 process is sending message! 再延遲5秒:child2 process is sending message!分析請讀者自行完成 。 1、程序中的sleep(5)起什么作用？2、子進(jìn)程1和2為什么也