計算題複習資料
1、 程序同步 ：
重點：會用訊號量實現前趨關係以及程序同步。掌握經典的程序同步問題：生產者-消費者問題。
例如：利用訊號量實現下圖的前趨關係。
參答：var a,b,c,d,e,f,g; semaphore ∶= 0,0,0,0,0,0,0;
begin
parbegin
begin s1; signal(a); signal(b); end;
begin wait(a); s2; signal(c); signal(d); end;
begin wait(b); s3; signal(e); end;
begin wait(c); s4; signal(f); end;
begin wait(d); s5; signal(g); end;
begin wait(e); wait(f); wait(g); s6; end;
parend
end（2）桌上有一空盤，允許存放乙個水果。爸爸可向盤中放蘋果，或放橘子，兒子專門等著吃盤中的橘子，女兒專門等著吃盤中的蘋果。規定當盤空時一次只能放乙個水果供取用，試實現爸爸、兒子和女兒三個併發程序的同步。
解決：訊號量:empty=1;orange=0;apple=0;
爸爸程序:
while(1)
兒子程序:
while(1)
女兒程序:
while(1)
（3）經典的程序同步問題：生產者-消費者問題
k個緩衝區、i個生產者和j個消費者，通過乙個迴圈有界多緩衝區把i個生產者和j個消費者聯絡起來。
解決：struct semaphore mutex=1, empty=k, full=0;
struct message buffer[k],
int in,out =0;
; }
***sumer( )
;} }}
2、掌握常用的排程演算法，掌握銀行家演算法
(1) 先來先服務(fcfs) 排程演算法
作業排程中：
基本思想：以作業進入後備佇列的先後為依據。
● →從後備佇列選乙個或多個最先進入佇列的作業
● →將作業調入記憶體、分配資源、建立程序
● →放入程序就緒佇列
程序排程中：
基本思想：從就緒佇列中選擇乙個最先進入該佇列的程序，將cpu分配給該程序，進入執行狀態，一直執行到完成或發生某事件而讓出cpu。
例如：解決：
（2）短作業(程序) 排程演算法sj(p)f
作業排程中：
基本思想：作業排程程式在後備佇列中選擇乙個或多個估計執行時間最短的作業 ，將它們調入記憶體執行。
程序排程中：
基本思想：從就緒佇列中選出乙個估計執行時間最短的程序，將cpu分配給該程序，進入執行狀態，一直執行到完成或發生某事件而讓出cpu。
例如：解決：
（3）最高優先權優先(fpf)排程演算法
作業排程中：
基本思想：從後備佇列中選擇若干個優先權最高的作業，裝入記憶體。
程序排程中：
基本思想：為系統中每乙個程序規定乙個優先順序，就緒佇列中具有高優先順序的程序有優先獲得cpu的權利；如果幾個程序的優先順序相同，則按先來先服務演算法排程。
例如：和短作業優先演算法類似，只要把執行時間換成優先順序即可。
（4）高響應比優先排程演算法
● 作業的響應比rp：某一作業已經等待的時間+要求執行時間與所需執行時間之比。
● rp = 作業響應時間 /要求執行時間
作業已等待時間+要求執行時間)/要求執行時間
= 1+作業已等待時間/要求執行時間
● 作業排程程式每當挑選作業時，先計算當時後備佇列中各作業的響應比 ，然後選擇其中響應比最高的作業進入執行狀態。
例如：解決：
（5）銀行家演算法
● os根據程序提出資源請求時的資源使用情況，按照一定的演算法模擬分配，若認為分配後系統將處於「安全狀態」，就實行分配；若認為分配後系統將處於「不安全狀態」，就取消分配。從而保證系統處於「安全狀態」，使死鎖得以避免。
● 避免死鎖的實質:使系統不進入「不安全狀態」。
例如：假定系統中有五個程序｛p0, p1, p2, p3, p4｝和三類資源｛a, b, c｝，各種資源的數量分別為10、5、7，在t0時刻的資源分配情況如圖 3-15 所示。
（1）問此時該系統是否是安全狀態？如果是，寫出乙個安全序列。
答：t0時刻存在乙個安全序列(p1, p3, p4, p0, p2)或(p1, p3, p4, p2, p0) 。所以系統是安全的。
在此基礎上
（1）p1請求資源(1, 0, 2 )，系統能否把資源分配費它？為什麼？
可以。見書上p111.
在(1)的基礎上
（2）p0請求資源(0, 2, 0 )，系統能否把資源分配費它？為什麼？
系統不能把資源分配給它，因為分配後新的p0 need向量為（），其它程序的need向量不變，而新的可用資源向量為（），不滿足p0～p4的所有need向量。所以造成死鎖。
3、儲存器管理
（1）基本頁式儲存器管理
邏輯位址到實體地址的轉換
當程序訪問某邏輯位址3081時，位址變換過程：
邏輯位址3081 實體地址）
邏輯位址3081 （頁號,頁內位址） (3,9) [頁面長度1k]
比較：頁號＞ 頁表長度（頁表暫存器中） 越界中斷
n表項在頁表中位置 = 頁表始址+頁號×頁表項長度
從表項中取得對應該頁的物理塊號，裝入實體地址暫存器
第3頁面對應塊號是11)
邏輯位址暫存器的頁內位址實體地址暫存器的塊內位址
物理塊號11+ 塊內位址9 實體地址[11*1024+9=11273]
例如：已知記憶體容量為64kb，某一作業a的邏輯位址空間共有4k，分為4個頁面，頁面0、1、2、3分別被分配到記憶體空間的2、4、6、7四個物理塊中，在邏輯位址為200處有一條取數指令「load 1，3500」，
（1）畫出作業a的頁表；
（2）當指令「load 1，3500」執行時，產生的實體地址應是什麼？
解： (1) 頁表
（2）虛擬位址3500對應的頁號是：
3500/1024=3（「/」是整除運算子）
對應的頁內位移是：
3500/1024=428（「%」是求餘運算子）
3500對應的數對為（3，428），
用3去查頁表，知道第3頁現在存放在記憶體的第7塊。第7塊的起始位址為7168。因此，邏輯位址3500所對應的實體地址是：
∴實體地址為（7，428），
由於頁面大小為1k
∴實體地址為：7×1024+428=7596
（2）頁面淘汰演算法
先進先出頁面淘汰演算法（fifo）
選擇在記憶體中駐留時間最長的頁並淘汰之
理想淘汰演算法—最佳頁面演算法（opt）
淘汰以後不再需要的或最遠的將來才會用到的頁面
最近最少使用頁面淘汰演算法（lru）
選擇最後一次訪問時間距離當前時間最長的一頁並淘汰之，即淘汰沒有使用的時間最長的頁
例如：某程式在記憶體中分配三個物理塊，初始為空，頁面走向為4，3，2，1，4，3，5，4，3，2，1，5，計算缺頁次數和缺頁率。
共缺頁中斷9次
共缺頁中斷10次
共缺頁中斷7次
4、磁碟儲存器管理
● 磁碟排程策略：
先來先服務（fcfs）策略
統計學原理 計算題
電大專科統計學原理計算題試題及答案 計算題1 某單位40名職工業務考核成績分別為 68 89 88 84 86 87 75 73 72 68 75 82 97 58 81 54 79 76 95 76 71 60 90 65 76 72 76 85 89 92 64 57 83 81 78 77 7...
計算機作業系統複習
1.作業系統的定義 根據馮 諾依曼的思想，將運算部件 記憶體 輸入和輸出部件等裝置安裝在計算機的主機板上，通過邏輯連線構成計算機硬體系統，要使這些部件能夠充分發揮其效能，盡可能地按人們預期的目的和要求來執行各類程式，就需要一套管理硬體和組織程式有序執行的程式，則這套程式就稱為作業系統。2.作業系統的...
作業系統複習
一 什麼是作業系統 在回答這個問題之前，我們先來了解一下什麼是計算機系統。計算機系統是按使用者的要求接收和儲存資訊 自動進行資料處理並輸出結果資訊的系統。計算機系統由硬體系統和軟體系統組成。軟硬體系統的組成部分就是計算機系統的資源，當不同的使用者使用計算機時都要占用系統資源並且有不同的控制需求。作業...