<style>

html, body, .ui-content {
background-color: #333;
color: #ddd;
}

.markdown-body h1,
.markdown-body h2,
.markdown-body h3,
.markdown-body h4,
.markdown-body h5,
.markdown-body h6 {
color: #ddd;
}

.markdown-body h1,
.markdown-body h2 {
border-bottom-color: #ffffff69;
}

.markdown-body h1 .octicon-link,
.markdown-body h2 .octicon-link,
.markdown-body h3 .octicon-link,
.markdown-body h4 .octicon-link,
.markdown-body h5 .octicon-link,
.markdown-body h6 .octicon-link {
color: #fff;
}

.markdown-body img {
background-color: transparent;
}

.ui-toc-dropdown .nav>.active:focus>a, .ui-toc-dropdown .nav>.active:hover>a, .ui-toc-dropdown .nav>.active>a {
color: white;
border-left: 2px solid white;
}

.expand-toggle:hover,
.expand-toggle:focus,
.back-to-top:hover,
.back-to-top:focus,
.go-to-bottom:hover,
.go-to-bottom:focus {
color: white;
}

.ui-toc-dropdown {
background-color: #333;
}

.ui-toc-label.btn {
background-color: #191919;
color: white;
}

.ui-toc-dropdown .nav>li>a:focus,
.ui-toc-dropdown .nav>li>a:hover {
color: white;
border-left: 1px solid white;
}

.markdown-body blockquote {
color: #bcbcbc;
}

.markdown-body table tr {
background-color: #5f5f5f;
}

.markdown-body table tr:nth-child(2n) {
background-color: #4f4f4f;
}

.markdown-body code,
.markdown-body tt {
color: #eee;
background-color: rgba(230, 230, 230, 0.36);
}

a,
.open-files-container li.selected a {
color: #5EB7E0;
}

</style>

# 大三上-作業系統課後練習、考卷
## 說明
此份MD主要由VP(1410732048)和他的幾位同學夥伴整理及統整
如有不完整還請見諒，並麻煩不要隨意轉載(因考量到著作權問題)

[Eating支援參考](https://www.itread01.com/content/1544945283.html)
## CH-01
### 1.3 何時，使用者最好使用分時(time-sharing)系統，而非PC或工作站?
當其他使用者很少時，任務很大，硬體速度快，分時是有意義的。系統的全部功能可以解決使用者的問題。
### 1.5 叢集和多處理器的差別? 同一叢集兩台機器進行合作提供服務時需要什麼?
叢集系統通常是通過將多臺電腦組合成一臺計算機來構建系統執行分佈在叢集中的計算任務。
多處理器系統則是由多個CPU組成的單一物理實體。

叢集系統使用訊息進行通訊，而多處理器系統中的處理器可以使用共享記憶體進行通訊。
叢集系統進行合作提供服務時，應該複製兩臺機器上的狀態並保持一致更新。
### 1.8 中斷目的為何?中斷和陷阱差哪?陷阱可以被使用者產生嗎?如果可，目的?
中斷是系統中由硬體所產生的訊號，呼叫中斷處理程式來解決造成中斷的原因

陷阱是錯誤或使用者要求而產生的中斷，可以用來呼叫作業系統功能(如:發出I/O完成的訊號，以消除對裝置輪詢)或捕獲算數錯誤。

### 1.9 為避免CPU負擔，DMA被使用在高速I/O裝置
a.CPU如何與裝置介面溝通?
CPU可以通過將值寫入可以被裝置獨立訪問的特殊暫存器來啟動DMA操作。
當它從CPU接收到命令後，裝置開始相應的操作

b.CPU怎知道傳輸何時完成?
當裝置傳輸完成，會向CPU發出中斷訊號

c.DMA在傳輸時，CPU被允許執行其他應用，這樣會干擾嗎?如果會，怎樣的干擾?
CPU必須與裝置競爭以獲得對記憶體的訪問權

### 1.13 討論如何維護快取一致性
a.單處理器系統

b.多處理器系統

c.分散式系統

在單處理器系統中，當處理器發出對快取值的更新時，需要更新記憶體。這些更新可以
立即執行，也可以延遲執行。在多處理器系統中，不同的處理器可能快取相同的記憶體位置
在它的本地快取中。當進行更新時，其他位置的快取需要失效或者更新。在分散式系統中
，快取記憶體值的一致性不是問題。但是，當客戶機快取檔案資料時，可能會出現一致性問題。
### CH-01考卷

1.請解釋下列名詞:
1. 多元程式規劃
多元程式規劃就是讓CPU始終有工作可做，增加CPU的使用率。作業系統在同一時間內，將多個工作(Job)放入記憶體內，CPU一次執行一個工作，等該工作要執行I/O動作時，作業系統就把CPU拿回來給下一個工作使用，如此地繼續下去，最後還是會輪到第一個工作使用CPU。
2. 直接記憶體存取
controller負責I/O Device與Memory之間的資料傳輸，其過程完全不需CPU參與，CPU就有更多時間用在process執行。
3. 程式計數器
A:指定下一個等待執行的指令的位址

4. 雙模 dual mode
A:分成 user mode 跟 kernal mode
user mode
user program可以執行的狀態
在此mode之下，不能執行特權指令！否則會產生致命錯誤中斷(trap)，OS會強迫process中止
kernal mode
可執行特權指令
在此mode下，主要是OS的system processes在執行(OS的system process執行的狀態，在此mode下，OS掌控系統的控制權)

5. 中斷向量
是中斷服務程式的入口位址，或中斷向量表（它是一個中斷處理程式位址的陣列）的表項。
系統程式必須維護一份中斷向量表，每一個表項紀錄一個中斷處理程式(ISR，Interrupt Service Routine)的位址

---

2.

1. 何時會發生中斷?何時發生陷阱?

中斷:
硬體中斷: CPU運行某個指令，發生錯誤，應而被迫中斷。或者由I/O發起硬體訊號，而將CPU中斷。
陷阱:
CPU執行組合語言中的中斷指令(像是 INT 3)，可由使用者發出
2. 中斷時作業系統需要進行的處理
當中斷發生時，作業系統會先停止正在執行的工作，並將目前執行的指令位址存到暫存器，去執行中斷服務常式，當中斷要求被完成後，會回到原本執行的指令位址，繼續執行。

---

3.說明三者處理
1. caching
快取 : 儲存部分資料在更快速的儲存體，以提升性能
2. buffering
緩衝 : 資料被傳輸時的暫時儲存
是記憶體中的一個空間，將 I/O 的資料先收集至 buffer 中，待達至 CPU 可運算的資料量時，CPU 再將資料由 buffer 中一次取出計算，在 CPU 開始計算的同時， I/O則可繼續收集資料，達到 CPU 與 I/O可同時運行的目的。
3. spooling
Spooling（Simultaneous Peripheral Operation On-Line） : 一個工作的輸出和其它工作的輸入重疊
是將磁碟機視為一個大 buffer，資料讀取與寫入時，不直接讀取，而由磁碟機中讀取。 例如有很多筆資料要交給印表機輸出時，可將待印資料的清單放在一個表格中，印表機印完依筆資料後，可直接至表格讀取下一比待印資料，而 CPU 把待印資料的清單放在表格中後，可以去做別的計算，I/O也可繼續執行。

4.說明作業系統特性
1. 即時系統
A:資料輸入電腦立刻處理，在一定的時間內將結果傳回
2. 多工系統
A:可將一個行程分割成多個時程，並輪流執行不同行程的工作以達成多工處理

3. 平行系統
A:有兩個以上的核心同時進行不同的工作

4. 虛擬機器系統
A:在系統中切割一個空間裝虛擬環境，ex:在windows中安裝linux作業系統

5.說明環境特性
1. 客戶 一 伺服器系統

server端通常需要很強的運算能力，client向server請求所需資源與運算
2. 雲端計算

將資料傳上網到雲端做計算
優點:
可以快速部屬
可以控制流量大小
比較不用技術上需求(ex 自己架設伺服器)

6.說明多核心系統 與 獨立晶片多處理器系統特性
1.多核心系統是在單一晶片放置多個CPU核心彼此互相共用晶片內的暫存器和快取。
2.獨立晶片多處理器系統則是在單一晶片只有一個核心，擁有自己的暫存器和快取，透過主記憶溝通交換資料，比多核心系統耗電。

[Eating支援參考](https://blog.csdn.net/qq_32252957/article/details/86485584)

## CH-03
### 3.1 描述短程排班、中程排班、長程排班的差別
短程
>從記憶體選擇以就緒的行程並將CPU資源分配給它

中程
>SWAP(記憶體不夠或是降低多元程式規劃的程度)

長程
>選擇工作(job)從硬碟載入到記憶體(決定多元程式規劃的程度)

### 3.2 描述核心在做內容轉換所執行的動作
作業系統必須保存當前正在運行的程序的狀態，並且恢復下個準備要運行的程序的狀態
通常包含儲存暫存器的狀態(更新PCB表)

### 3.5 包含最初的父行程，圖3.31產生了多少行程?
16個(1→2 2→4 4→8 8→16)

### 3.6 解釋在什麼情況圖3.32中標示printf("LINE J")的那行會執行到
當fork成功但/bin/ls檔案(ls指令)不存在時

### 3.7 使用圖3.33的程式，指出在行A、B、C和D的pid數值(假如父行程和子行程的真實pid分別是2600和2603)
fork() 可能會有以下三種回傳值：
* -1 ： 發生錯誤
* 0 ： 代表為子程序
* 大於 0 ： 代表為父程序, 其回傳值為子程序的 ProcessID
A 0(fork成功)
B 2603(子行程)
C 2603
D 2600
爸爸的回傳值就會是小孩子的ID 所以C跟B一樣
[參考](https://www.ptt.cc/bbs/Grad-ProbAsk/M.1326974869.A.22F.html)

### 3.10 使用圖3.34的程式，解釋在X行和Y行將輸出什麼?
0 -1 -4 -9 -16(子行程)
0 1 2 3 4 (父行程不受子行程的影響)

**************************************************************************還沒更新

### 3.11 解釋下列的優缺點(請考慮系統和程式人員的層次)
a.同步和非同步通信

同步和異步通信–同步的優點是它允許發送方和接收方之間進行約定。
阻塞發送的一個缺點是可能
不能約定，並且消息可能異步傳遞.因此，消息傳遞系統通常提供兩種形式的同步

b.自動和指定緩衝

自動和顯示緩衝–自動緩衝提供一個具有不定長度的隊列，因此確保發送方在等待複製消息時永遠不必
阻塞.關於如何自動緩衝的規範沒有提供;一種方案可以保留足夠大的內容，這些內存被浪費了
顯示緩衝
指出了緩衝區的大小.在這種情況下，發送方在等待隊列中可用的空間時被阻塞.但是，顯示緩沖不太可能
浪費內存.

c.藉由拷貝傳送和經由參考值傳送

複製傳送和引用傳送—
複製傳送不允許發送者去改變參數的狀態;

引用傳送
可以改變參數狀態
一個好處是它允許程序員編寫分佈式版本的集中應用.Java的RMI都提供了.然而，通過引用傳送一個
參數還需要在將這個參數聲明為遠程對象

d.固定長度和可變長度的訊息

固定大小和可變大小消息—這個的實現主要與緩衝問題有關;對於固定大小的消息，具有特定大小的
緩衝區可以容納已經數量的消息.可變大小消息是不清楚的.考慮windows 2000處理如下情況:
對於固定大小的消息(小於256字節),從發送方的地址空間複製到接受進程的地址空間。更大的消息使用
共享內存傳遞消息.(很明顯是提高效率，減少內存地址空間的浪費)

### CH-03考卷
**一、下列程式執行時，最多會有多少個行程並行執行?請說明理由。(8%)**
main() {
fork();
fork();
exit();
fork();
exit();
}

ANS: 4個，前兩次fork 1->2 / 2->4 exit全關掉 →0 0→0

**二、針對行程產生一個新子行程時，請分別說明下列的處理：(21%)**
(1) 新行程的資源
(2) 新行程的記憶體內容
(3) 兩個行程的執行順序

ANS:

1. 當行程產生另一個子行程時，這個子行程需要某些資源（如:CPU 時間、記憶體、檔案、輸 入/輸出裝置）才能完成其任務。子行程或許能夠直接從作業系統取得需要的資源，或是它 可能受限於只能使用其父行程所擁有的部分資源。

2. 新行程位址空間的可能方法有兩種：子行程是父行程的複製品（子行程有父行程相同的程式和資料）、子行程有一個程式載入其中。

3. 執行作法上有兩種：父行程繼續執行而子行程也同時執行、父行程等著他的子行程中止後才繼續執行。

**三、不同行程間利用緩衝區進行溝通時，請分別說明下列容量時的同步方式。**
1. 零容量 (Zero Capacity)︰佇列的最長長度為 0，因此鏈(Link)中將不含有任何等候的訊息。
zero capacity：一定要收完之後才能再送，沒有地方給資料排隊。

2. 有限的容量 (Bounded Capacity)︰佇列具有有限長度 n；因此最多有 n 個訊息存於其中。
bounded capacity：有限量的空間給資料排隊，若是滿了就必須要等。

3. 無限制的容量 (Unbounded Capacity)︰佇列具有無限長度的潛力；因此任何訊息能在佇列中等候，傳送者從不阻塞，而且傳送者也不需等候。
unbounded capacity：無限的空間給資料，sender可以一直送資料。

**四、請畫出行程狀態圖，並詳細說明running process會在哪些因素發生時改變其狀態？(25%)**
⚫ 新產生(new)：該行程正在產生中。
⚫ 執行(running)：指令正在執行。
⚫ 等待(waiting)：等待某件事件的發生（譬如輸入/輸出完成或接收到一個信號）。
⚫ 就緒(ready)：該行程正等待指定一個處理器。
⚫ 結束(terminated)：該行程完成執行。 running process 會在中斷、I/O 或事件等待、離開發生時改變其狀態。
**五、請詳細說明下列行程排班的佇列圖，並說明行程進入與離開各個佇列時的狀態。(25%)**
一個新的行程最初是至於就緒佇列中。它就一直在就緒佇列中等待，直到選來執行或被分派 (dispatched)。一旦這個行程被配置 CPU 並且進行執行，則會有以下三種事件之一可能發生：
1. 行程可發出 I/O 要求，然後置於一個 I/O 佇列中。
2. 行程可產生出一個新的子行程並等待子行程的結束。
3. 行程被強制地移出CPU（如:中斷），然後放回就緒佇列中。
在前面兩種情況時，行程最後將從等待狀態轉移到就緒狀態，而後放回到就緒佇列之中。一個 行程將繼續此週期，直到它結束為止，屆時它將自所有佇列移除，並且它的 PCB 和資源會重新被分配。

## CH-05
### 1 為何區分IO傾向和CPU傾向對排班是重要的?
I/O傾向的行程在運行I/O操作前只需要很少的計算，這種行程一般來說不會使用很多的CPU。
CPU傾向的行程能利用整個時間片，且不做任何阻礙I/O操作的工作。

因此，通過給I/O傾向的行程優先權和允許在CPU傾向的行程之前運行，可以很好地利用電腦資源。

### 4 每個kernel有自己的執行佇列 一個執行佇列被所有kernel共用

### 5 解釋參數的意義
a.
= 0 and 0 = 100milliseconds
b.
= 0.99 and 0 = 10milliseconds

### 6 退化依序循環是對 CPU傾向 還是 I/O 傾向有利?
CPU傾向
********等等翻
This scheduler would favor CPU-bound processes as they are rewarded with a longer time quantum as well as priority boost whenever they consume an entire time quantum.
This scheduler does not penalize I/O-bound processes as they are likely to block for I/O before consuming their entire time quantum, but their priority remains the same.

### 7 考慮以下行程，都在時間0到達，順序為P1 P2 P3 P4 P5

| 行程 | 分割時間 | 優先順序 |
| ---- | ---- | ---- |
| P1 | 2 | 2 |
| P2 | 1 | 1 |
| P3 | 8 | 4 |
| P4 | 4 | 2 |
| P5 | 5 | 3 |

1.畫甘特圖
FCFS SJF 不可搶先優先權排班 RR(時間=2)

2.回復時間

3.等待時間

4.哪種演算法可以最短平均時間
A:SJF
### 8 (((略

### 10 哪些排班會產生飢餓?
最短工作優先調度 和 優先順序調度演算法 會引起饑餓
### 13 考慮系統製作多層次佇列排班，一個電腦配給使用者行程最大的CPU時間量策略為何?
這個程式可以使分配給它的沒有被完全利用的CPU時間最大化。它可以使用分配給它的時間片中的絕大部分，但在時間片結束前放棄CPU，因此提高了與進程有關的優先順序。
### 15 解釋下列演算法對短小行程有利的差異程度
a.FCFS----區別短任務是因為任何在長任務後到達的短任務都將會有很長的等待時間。
b.RR-----對所有的任務都是能夠相同的（給它們相同的CPU時間區間），所以，短任務可以很快的離開系統，只要它們可以先完成。
c. 多級回饋佇列和RR調度演算法相似——它們不會先選擇短任務。
### 18 (ㄟ靠，這個要給表r)
考慮在Solaris作業系統中的為分時執行緒的調度演算法：
a:一個優先權是10的執行緒的時間片是多少？優先權是55的呢？
b:假設優先權是35的一個執行緒用它所有的時間片在沒有任何阻止的情況下，這調度演算法將會分配給這個執行緒什麼樣新的優先權？
c:假設一個優先權是35的執行緒在時間片結束前阻止I/O操作。這調度演算法將會分配給這個執行緒什麼樣新的優先權？ 
答：a:160和40
b:35
C：54
### 22 (目前找不到)

## CH-06 (略過，如果她考的話就是低能、故意刁難)

### 3

### 6

### 8

## CH-07

### 7
Suppose the system is deadlocked.
This implies that each process is holding one resource and is waiting for one more.
Since there are three processes and four resources, one process must be able to obtain two resources.
This process requires no more resources and, therefore it will return its resources when done.

### 8
Using the terminology of Section 7.6.2, we have:
a.
n
i = 1 Ma xi < m + n
b. Ma xi ≥ 1 for all i
Proof: Needi = Ma xi − Alloca tioni
If there exists a deadlock state then:
c.
n
i = 1 Alloca tioni = m
Use a. to get:
Needi +
Alloca tioni =
Ma xi < m + n
Use c. to get:
Needi + m < m + n
Rewrite to get:
n
i = 1 Needi < n
This implies that there exists a process Pi such that Needi = 0. Since
Ma xi ≥ 1 it follows that Pi has at least one resource that it can release.
Hence the system cannot be in a deadlock state.

### 12

### 13

## CH-08

### 1
### 3
### 4
### 5
### 20
### 23

當程序僅佔其大型程序的一小部分時
虛擬地址空間，由於以下原因，散列頁表可能是首選
它的尺寸較小。但是，哈希頁表的缺點是
由於將多個頁面映射到頁面上而產生的衝突問題
相同的哈希頁表條目。如果許多頁面映射到同一條目，
然後遍歷與該哈希表條目相對應的列表可能會產生大量開銷；這樣的開銷在分段中是最小的
分頁方案，其中每個頁表項都維護僅與一頁有關的信息。

## CH-09

### 3

### 4

### 5

### 8

### 14

### 16

###### tags: `大學-大三上`