[058]

作業系統怎麼念？筆記看熟，蓋起來唸，念架構，可以自己把章節結構畫出來

申論題平常在練習時，假設一天練習十題的情境下，

3題動手去寫，剩下7題把架構畫出來就好

[TOC]

Chapter1 Intruduction

管理硬體的軟體就是作業系統，硬體包含CPU，Memory，I/O設備等等…作業系統就是負責管理這些硬體的系統。一個電腦系統可以被粗略的劃分成下面四個組件：

• 硬體(hardware)
• 作業系統(operating system)
• 應用程式(application programs)
• 使用者(user)

Hardware

包括CPU(Central Processing Unit)，記憶體(Memory)，Input/output設備…提供給系統基本的計算資源

Operating System

負責協調硬體與應用程式，給不同的使用者

Application Programs

例如Word，Excel，Chrome之類的應用程式，來處理使用者的計算問題(Computing Problems)

補充：

1. Bare Machine(裸機): 純粹只有硬體組成，沒有OS及System Programs
2. Extended Machine: Bare Machine加上OS/system programs

• In Memory
  • Command Interpreter(命令解譯器)

Multiprogramming System

1. 定義：系統允許多個Jobs(Process)同時執行，即是Multiprogramming

• 主要目的：提高CPU Utilization
• 作法：透過Job Scheduling or CPU Scheduling技術達成

example：當執行中的process waiting for I/O completed, 則OS可將CPU切換給另一個process執行，避免CPU idle 。

即只要系統內有夠多的工作存在，則CPU IDLE的機會就下降

2. Mulitiprogramming Degree之定義

• 系統內的Process的數目：一般而言，Degree越高，CPU利用率就越高。

(Note：Virtual Memory Thrashing狀況除外)

3. 多個Process的定義、以及如何執行

   1. Concurrent execution(並行)：一顆CPU，大家一起輪番使用

   

   1. Parallel execution(平行)：多顆CPU或是Multi-core(多核)，各自執行

Time-Sharing System

分時系統

定義：又叫Multitasking[恐龍本如是說]

It’s a logical extension of Multiprogeamming system

與Multiprogramming的最大差異：CPU的切換頻率極高

• Time-Sharing System features

  • 強調對User Response的時間要短(<1秒)
  • 適用於user interactive的Computing/ Environment
  • 對每一個process都公平

Main Frame(主機)

• CPU Scheduling採取RR的排班法則(第四章會介紹)
• 使用Virtual Memory的技術，擴展Logical Memory Space
• 使用Spooling的技術(不太會考)實現I/O Device的共用，類似現代的Buffering技術，讓每個user，皆以為自己有專屬的的Computer

Multiprocessors System

定義：又叫Multiprocessing or Paraller or Tightly-coupled system(緊密耦合系統)

faeture：

1. 一個機器(or MotherBoard)內，有多個Processors(or CPUs)
2. 這些CPUs彼此共享此機器的Memory,Bus,I/O-Device, power-supplier etc…
3. 通常受同一Clock之時脈控制
4. 由同一個OS管理
5. processors之間的溝通大都採shared Memory方式

Benefits(好處)：

1. Increased Throughput：產能增加
2. Increased Reliability：可靠度的提升
3. Economy Of Scale：運算能力的擴充比較好

　分析如下：

Increased Throughput：

可支持多個工作在不同CPU上平行執行(paraller Computing)，注意，N顆CPU之產能絕對小於1顆CPU產能xN倍，意即CPU數量的提升與產能的提升並非線性成長。原因是因為

1. Resource Contetion(資源的競爭)
2. Processors間的Communication會抵消產能

Increased Reliability:

某一顆CPU壞了，則System不會因此而停頓，因為其他CPU仍可運作

1. Graceful degradation(漸進式的滅亡)

• System不至因為某些Hardward/Software之元件故障而停頓，仍然保有持續運作的能力，這性質就稱為fail-soft

2. Fault-Tolerant system(容錯系統)考試不太會考

   • 具有graceful degradation性質之系統就叫做Fault-Tolerant system，想要達成容錯的技術需要有兩件事情的支援
   1. 要有backup的系統，切換也要流暢

Economy of Scale:

運算能力擴充符合經濟效益

• ∵N顆CPU在一部機器內，與N部機器相比，成本較便宜∵這些CPUs共享同一機器之Memory, Bus, I/O-Device, etc

Two SubType in Multiprocessors System

1. SMP(Symmetric MultiProcessors) 對稱的
2. ASMP(Asymmetric MultiProcessors) 非對稱的

SMP

定義：每個Processor的工作能力是相同的(Identical)，且每個CPU都有對等、平等的權利來存取資源

優點：

1. 可靠度較ASMP高，因工作能力相同，即使其中一個cpu掛了也可以被立刻取代
2. 效能較高

缺點：

1. SMP的OS設計開發較為複雜(互斥存取的機制設計,資源的競爭)

ASMP

定義：每個Processor之工作能力不盡相同，通常是採取Master-Slave的架構(恐龍本有時候會寫成Boss-Employee

Master-Processor負責工作分派及資源分配，監督Slaves等管理工作

Slave Processors負責執行工作

優點：ASMP的OS設計開發較為Simple，∵與Simple-Cpu Os版類似

缺點：

1. 可靠度低，Master CPU如果壞了，就會停擺，直到另一顆CPU被Train接手
2. 效能較低∵Master CPU是瓶頸

Multiprocessors System VS MultiCores CPU

從作業系統來看差異不大，主要差異是硬體的差異(主要)，以OS來看，你裝了一顆兩核的CPU，OS會視作兩顆CPU；裝四核的視作四顆CPU

1. MultiProcessors

2. MultiCores CPU

優點

1. Power Saving：相較MultiProcessor，在一個CPU上提供兩個Core的能源耗損會比在一張板子上提供兩顆CPU的能源耗損還來得低。
2. Speed比較快(∵處在同一個晶片內資料傳輸速度較快)

Distribute System

定義：又叫Loosely-Coupled system(鬆散耦合系統)，主要的Feature如下

1. 多部機器彼此透過Network(or Bus)相互串連

2. 每部機器之CPU有各自私有的Memory, Bus, I/O-Device, etc 並非共享

3. 各CPU之Clock時脈控制不一定相同

4. 各CPU上之OS也不一定相同

5. 各Processors之間的溝通大都採**“Message Passing”**方式

   Message Passing (類似講電話)

   Step

   1. 建立Communication Link
   2. Message 相互傳輸
   3. 釋放Link

Advantage of Distribute-System

1. Increased Throughput(支持Paraller Computing)
2. Increased Reliability(一個掛掉，還有其他可以擋)
3. Resource Sharing(資源共享因此成本降低)

支持"Client-Server" Computing Model之實施

1. Server(伺服器)：提供某些服務的機器 example: mail server, file server ,DNS,printer server, computing server …
2. Client：本身不提供服務，且它需要某些服務時，則發請求至Server, Server服務完再將結果回傳Client

Note

Peer-to-Peer model：peer意指同時具有server及Client的角色，英文意思是同等的、對等的

4. Remote sites Communication的需求被滿足 example：email, FTP via Internet

Real-Time System

(即時系統)

分成兩種

1. Hard real-time System
2. Soft real-time System

Hard real-time system

定義：This system must ensure the critical tasks complete on time，即工作必須在規定的時間限制內完成，否則即算失敗

舉例：軍事防衛系統、核能安控系統、工廠自動化生產…

設計考量：

• 所有時間延遲之因素皆須納入考量 eg：sensor data 傳輸速度、運算速度、Signal的傳輸 etc，確保這些時間的加總能夠滿足時間deadline的要求
• 所有會造成處理時間過久或無法預測之設備或機制，盡量少採用或不用 eg：Disk不用或少用、Virtual Memory 絕對不採用
• 就CPU Scheduling設計(Ch4)而言，需先考量Schedulable與否，再進行排程(eg rate-monotonic, EDF scheduling)，確定CPU能負荷再進行排程
• Time Sharing system 無法與之並存(Time sharing是屬於Multitasking，可以同時執行多個程序，並透過一些風勢去優先執行某些程序，而Hard real-time比較像單運算系統，要求在指定時間內完成，因此更專注於單一程序的執行，由於這兩個系統有這樣的差異，因此無法共榮)
• OS所造成的Dispatch latency etc. 宜降低(interrupt的處理, system call的請求)，一般實務上，hard-real-time system，鮮少有OS的存在(幾乎不存在)，尤其是embedded real-time system，因需要及時的響應
• 現行的商用OS不支援Hard real-time features 通常都是客製化的特殊設計eg : Linux, Unix, Window, Apple Os, Solaris etc

​

Soft real-time system

定義：This system must ensure the real-time process get the hightest priority than the others and retain(維持) this priority level unit it completed

舉例：Multimedia System, Simulation system, VR system, etc

設計考量：

• 就 CPU Scheduling 設計(ch4)而言，
  1. 必須支持preemptive priority scheduling
  2. 不可提供Aging技術(活得越久，priority越高)
• 盡量降低kernel的Dispatch latency time
• 可支援virtual memory 並存，但前提是real-time-process的全部pages必須皆待在memory中，直到完工，高優先權的Process不要使用virtual memory
• 與Time-sharing system 可以並存，eg：solaris
• 一般商用OS都支援Soft-real-time system

Batch System

定義：將一些較不緊急，定期性、非交談互動性的Job，累積成堆，再分批次，送入系統處理

舉例：庫存系統、報稅系統、掃毒、磁碟重組、清算系統…

主要目的：提高resource utilization，尤其是在冷門時段，不適合用在real-time-system, user-interactive application eg：電腦遊戲

Hand Held system

定義：單手可掌握操作的系統

• Hardware 天生之限制，帶來software必須配合之處

Chapter2 Computer System Architecture

I/O Operating And Hardware Resources Protection

• 學習路線

I/O運作方式

Polling I/O

Interrupted I/O

DMA

Interrupt機制處理與種類

HW Resource Protection

基礎建設

Dual Model Operation

Privileged Instruction

I/O

Memory Protection

CPU

I/O Operating

Polling I/O I/O

Polling(輪巡,詢問式) I/O

定義：又叫Busy_waiting I/O or Programmed I/O

步驟如下

1. I/O Request 給 OS (執行中的Process不會自己做I/O)
2. OS收到請求後，(可能)會暫停此Process執行，並執行對應的System Calls.
3. Kernel 的 I/O-subsystem(專門用來處理I/O的請求，只是個過水而已)會Pass此請求給Device driver
4. Divice Driver 依此請求，設定對應的I/O Commands參數給Device Controller
5. Device Controller 啟動監督I/O-Device之I/O運作進行
6. 在這段時間內，OS(可能)將CPU切給另一個process執行
7. 然而，沒人主動去告訴CPU I/O的執行狀況，因此CPU在執行process工作過程中，卻要不斷去Polling Device Controller，已確定I/O運作是否完成或有I/O error

缺點：

• CPU耗費大量時間用於polling I/O Device Controller上，並未全用於process execute上，故CPU utilization低、throughput不高

Interrupted I/O

Interrupted (中斷,中斷式)I/O I/O

定義：

步驟如下：

1. I/O Request 給 OS (執行中的Process不會自己做I/O)

2. OS收到請求後，(可能)會暫停此Process執行，並執行對應的System Calls.

3. Kernel 的 I/O-subsystem(專門用來處理I/O的請求，只是個過水而已)會Pass此請求給Device driver

4. Divice Driver 依此請求，設定對應的I/O Commands參數給Device Controller

5. Device Controller 啟動監督I/O-Device之I/O運作進行

6. 在這段時間內，OS(可能)將CPU切給另一個process執行

7. 當I/O運作完成，Device Controller 會發出 I/O-Completed Interrupt 通知OS(CPU)

8. OS收到中斷後(可能)會暫停目前Process的執行(因有些Interrupt優先權可能很低，可以先暫時不處理)

9. OS必須查詢 Interrupt Vector，確認何種中斷發生，同時也要找到該中斷的服務處理程式(ISR：Interrupt Service Routine)的位址(每一個中斷都有一個對應的中斷處理服務程式

10. Jump to ISR位址 執行ISR

11. ISR完成後，return control to kernel，kernel也許做一些通知工作

12. 恢復(resume)原先中斷前的工作執行或交由CPU Scheduler決定

優點：CPU不須耗費時間用於Polling I/O-Device，而是可以用於Process execute上，CPU utilization提升，throughout提高，improve the system performance

缺點：

1. Interrupt之處理仍需耗費CPU time，如果 I/O運作時間 小於 Interrupt處理時間，則使用Interrupt I/O就不划算，不如使用polling I/O
2. 若中斷的頻率過高，則大量的中斷處理會占用幾乎全部的CPU Time，則系統效能會很差
3. CPU仍需耗費一些時間用於監督I/O-Divice與Memory之間的Data Transfer過程

DMA (Direct Memory Access) I/O

• 定義：DMA Controller 負責 I/O-Device(設備)與Memory 之間的Data transfer(傳輸)工作，過程中不需CPU之參與監督，因此CPU有更多時間用於Process execute上

優點：

1. CPU Utilization更高
2. 適合用在Block-Transfer oriented I/O-Device上(代表中斷發生的頻率不致於過高 eg:Disk, 磁碟的控制器會和DMA的控制器兩個會相互合作，磁碟控制器會去指揮磁碟的運作，讀出來的資料會通知DMA的控制器，DMA會把資料輸進Memory裡) 不是用於Byte-transger oriented I/O-Device

缺點：

1. 引進DMA Controller會增加HW設計複雜度(Complicated the HW design)

原因：DMA的Controller會跟CPU競爭爭奪Memory(記憶體)、Bus(匯流排)的使用權，若DMC Controller 占用了memory , Bus 時，CPU要被迫等待

補充：DMA Controller通常採用"Cycle Stealing"技術 (or Interleaving)與CPU 輪番(交替)使用memory跟Bus，如果CPU與DMA Controller發生conflict(同時要用Memory 與 bus)，則會給DMA較高的的優先權

2. 通常系統會給予「對該資源需求量、頻率等較小」的對象有較高的優先權，這樣會獲得

   1. 平均等待時間較小
   2. 平均產能較高

   的好處

3. 機器指令的Stages (CPU執行的幾個階段)

1. IF：Instruction Fetch 抓指令：根據Programming Counter的值，到記憶體去把指令抓出來
2. DE：Decode 解碼：知道這條指令到底做什麼事情
3. FO：Fetch Operands 抓取運算元：運算元可能來自記憶體、也可能來自暫存器
4. Ex：Execution　執行
5. WM：Write Result to Memory　將結果寫入記憶體

Cycle Stealing：當CPU會使用或不會使用Memory Access時，DMA都會去爭奪Memory的使用權，亦為Stealing(偷)，因為DMA擁有最高使用權。

DMA Six Steps

(早:中央、清華、交大)

1. Device Driver User Process 告訴 I/O subsystem(kernel)告訴 Device Driveris told to transfer Disk data to Buffer address X
2. Device Driver tells disk controller to transfer C bytes from disk to Buffer at address X從磁碟讀C byte的量，分配到記憶體位址X的地方
3. Disk controller initiates DMA Transfer
4. Disk controller sends each byte to DMA controller
5. DMA transfer bytes to Buffer X in creasing memory address and decreasing Counter utill Counter =0
6. When C=0, DMA interrupts CPU to signal transfer compeletion

Life cycle of I/O-request via Interrupted I/O

Blocking and Non-Blocking I/O

Blocking(會暫停的) and Non-Blocking(不會暫停的)I/O

所謂的Blocking的意思是，當User process發出I/O請求之後，接下來這個prcess就會suspend，直到這個I/O被完成

Blocking-I/O:

(等於Synchronous)：Process suspended until I/O completeed

• 優：Easy to use and understand, process在waiting的時候，可以把CPU放出去給其他process做使用
• 缺：Insufficient for some needs

Non-Blocking I/O：

I/O calls returns as much as available I/O請求發出去後，控制權立刻返回給user process

• example：user interface, data copy
• Implemented via multi-threading
• Returns quickly with count of Bytes read or written

Asynchronous-I/O:

(屬於Non-blocking)：Process runs while, I/O executes

• Difficult to use
• I/O subsystem signals process when I/O-completed

Asynchronous與Non-Blocking的小差異

Asynchronous I/O：整個I/O完成，才通知Process

Non-Blocking I/O：I/O完成Data return as much as possible (能回傳就回傳， 少量即可回傳)

舉例說明：userProcess發出100 byte的I/O請求

• Asynchronous的方式，會將100byte的I/O做完後，才告訴Process做完了
• Non-Blocking的方式，每讀25Byte就通知一次， 逐步回報給Process，會發出比較多次的Interrupt

Interrupt Policy and

1. 當Interrupt發生，OS之處理Steps如下：
   1. OS收到中斷後(若此中斷要被立即處理，則OS會暫停目前Process之執行，且保存其Status and Registers Contents)
   2. OS會依照Interrupt ID(No.)查詢Interrupt Vector中斷向量表，確認何種Interrupt發生，且找出其ISR的位址
   3. Jump to ISR 位址，執行ISR
   4. ISR完成後，控制權返回Kernel
   5. OS會恢復(resume)中斷之前Process之執行

2. Interrupt種類

   1. 早期恐龍分為三種

      1. External Interrupt：CPU以外的周邊設備、控制卡、etc，所發出的中斷

      例：I/O-Completed, I/O-error, Machine-check,

      2. Internal Interrupt：CPU在執行Process過程中，遭遇重大錯誤而引發

      例：Divide-by-zero除以零、執行非法的特權指令、etc

      3. Software Interrupt：user process 在執行中，若須要OS提供服務時，發出此類型的中斷，目的是通知作業系統，請它執行對應的服務請求

      例：I/O-request 好比是KTV的服務鈕，按下去就會有人過來問你要幹嘛

   2. 現在恐龍分為兩種

      1. Interrupt：硬體所產生就叫Interrupt
      2. Trap：軟體所產生的就叫Trap

   

   例：設備發出I/O-Completed,I/O-Error,Machine-check,etc及Time-out by Timer

   用途主要有二

   • Catch the arithematic error

   例：Divide-by-zero, 執行非法特權指令, illegal memory access

   • user process 執行需要OS提供服務時，也會發trap通知OS

   例：I/O　Request

   3. 分成兩類背後哲學：中斷之間也有優先權高低之分
      1. Maskable Interrupt遮罩：此類中斷發生後，可被Ignored或延後處理不一定要馬上處理
         • 例如：Software-interrupt
      2. Non-Maskable不可遮罩：此類中斷必須立刻處理
         • Internal interrupt(重大error), I/O-error,etc

Hardware Resources Protection

• 基礎建設
  • Dual-modes operation(雙重模式)
  • Privilege instructions

Dual-modes operation

定義：System之運作模式至少(可再往下分，依照系統設計的必要性)可被區分為2種modes

1. kernel mode
2. user mode

kernel mode

又叫做system mode, supervisor mode, privileged mode, monitor mode(早期有，現移除)，代表此刻是kernel取得系統控制(取得CPU執行權)，允許privilege instructions(特權指令)在此mode下執行

user mode

代表user process取得CPU執行，在此mode,不允許執行privilege instructions(特權指令)，若執行則會發生trap的重大錯誤

此外，Dual-modes必須要有HW的支持，才可實現

例如：CPU內會有Mode Bit，用以區分現在是哪個mode當CPU在執行機器指令時，IF、DE...之類的階段，若解碼完發現是個特權指令，這時候Control unit就要檢查目前的mode bit，判斷是否可不可以執行，若不行就丟出一個interrupt，不允許執行

Priveleged instruction(特權指令)

定義：任何可能會造成系統重大危害的指令，可設為特權指令(端看工程師如何設計)，只可以在Kernel Mode去執行，不可以再User mode下執行，一旦在User Mode下執行，會發Trap通知OS，將此user process terminates.

如果把所有的指令設為特權指令，好處就只有超級安全，因為這些指令都只有OS可以做，如果user想做就只能委託OS執行，但這樣performance會很差，因為所有事情都要給OS處理

例如：

• Turn-off(Disable) interrupt, clear memory, I/O instruction(for I/O protection),Timer值 set/change (for CPU protect)

• Base/Limit register 修改/set (for memory protection)

• Change mode from user mode to kernel mode

• 1 2 3 4 5 6 7 8

  1). Set value of Timer 2). Read the clock 3). Claer memory 4). Turn-off interrupt 5). Switch from user to monitor mode 哪些是特權指令? 1,3,4,5

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  1. Change to user mode 2. Change to monitor mode 3. Read from monitor memory 4. Write into monitor memory 5. Fetch an instruction from memory 6. Turn on timer interrupt 7. Turn off timer interrupt 哪些是特權指令? 2,4,7 詳解： 6. 本身就是打開的，因為要做CPU的保護 7. 但關掉不是 有爭議的部分 3. user process去讀kernel process的資料，恐龍認為是，因為kernel裡面掌管所有Process的information，而process間不應該各個process的狀態 5. 從Monitor memory(Kernel)裡面去讀指令出來，恐龍認為不是，因為就算抓了，但你的mode不是Privilege instruction就會把你擋掉

為什麼Dual-mode跟Privilege Isntruction可以構成保護基礎

所有會危害OS的操作都是在Kernel 發生，因此不可以放任user可以直接操作Kernel

I/O-Protection

目的：由於I/O運作較為繁瑣複雜，為了降低user processes 操控I/O之複雜度`，讓user processes去處理應用的問題，I/O則交由OS去處理；及避免user process對I/O-Devices之不當操作，胡搞瞎搞，因此才有I/O protection。簡單來講就是不要讓user processes去操作I/O

作法：把所有I/O指令皆設為privileged instruction配合Dual-modes, 一律讓user process委託 kernel執行I/O運作

Memory Protection

目的：防止user process 存取其他user processes 之 memory area 及 kernel memory area

作法：(以 contiguous Memory Allocatation 為例) 針對每個Process, kernel會提供一套Registers：叫base/limit register, 其中

• Base register紀錄Process之起始位址
• Limit register紀錄Process之大小

將來Process執行，會進行下列的Checking

為什麼Address的判斷是由Hardware來做而不是OS來做呢？

因為交給OS來做就會產生中斷interrupt，又因程式在執行的時候對記憶體的存取是很頻繁的，兩個影響之下會導致你的CPU一直被interrupt打擾，因此交給Hardware來做會比較符合成本一點。

並且，還要將 Base與Limit register 值之set/change須設為"Privilege Code(特權指令)"，避免user Process把Base跟Limit的位址直接改成無限，這樣就完成了Memory的Protection

CPU Protection

目的：防止user process無限期/長期佔用CPU而不釋放

作法：利用Timer實施，同時OS會規定Process使用CPU time之最大配額值(MAX. Time Quantum)

當process 取得CPU後，Timer初值即設為Max Time Qauntum值，隨著Process執行 time增加, Timer值會逐步遞減，直到Timer值為0, Timer會發出 Time-out的interrupt通知OS，OS便可強迫此process放掉CPU，此外，Timer值之set/change 也須設為特權指令

OS Structure Operating-System

OS之Development

OS應提供的服務項目

OS之服務元件種類

System Calls之介紹(使用者程式跟OS之間溝通的介面)

OS之Structure種類

Simple

More Complex than simple

Layered Approach

Microkernel

Module

Hybrid(混合?)

設計原則：Policy與Mechanism policy管行為,比較常變，例如數值的變動; mechanism負責處理how,比較不會變,例如邏輯的判斷

Virtual Machine介紹

System Call

定義：作為執行中user process與kernel之間的溝通界面，當user process需要OS提供某種服務時，會先trap通知OS，並帶入System call ID(No)及所需參數，然後OS執行對應的System call

It’s a programming Interface to the services privided by the OS

用舉例來講的話

• Trap = 服務紐
• System call = 服務項目

System Call的種類(中央考過類似的題目)

1. Process Control eg：建立、終止、暫停、恢復執行process, set/read attribute
2. File Management eg：建立、read, write, open, close, delete …
3. Device Management eg：建立、read, write, open, close, delete …
4. Information of Maintenance eg：取得系統日期/時間、取得Process屬性 etc
5. Communications eg: Processes之間的通訊而且只針對Message Processing方式提供服務
6. Protection　eg: Hw resources protection, File access contorller, etc

System Call的參數(Parameters)傳遞方式：3種方式

1. 利用暫存器(Registers)保存參數
   • 優點：
     1. 最簡單
     2. 存取速度最快( without memory access)
   • 缺點:
     1. 不適用於大量參數之情況
2. 利用Memory，以一個Block(Table)儲存這些參數，並將這些表格的起始位址置於1個Register中，Pass給OS
   • 優點:
     1. 適用於大量參數
   • 缺點:
     1. 存取速度較慢，且操作較為麻煩
3. 利用Stack將參數push入此Stack, OS再pop from stack, 以取得參數
   • 優點:
     1. 適用於大量參數之情況
     2. 也很簡單
   • 缺點:
     1. Stack的空間須要預先準備，避免stackoverflow

OS之系統架構分類

OS之Structure種類

Simple: MS-DOS系統

More Complex than simple: UNIX系統

• Limited by Hardware functionality
• The original UNIX had limited structuring
• The UNIX 包含兩個Separate parts
  1. System Programs
  2. The Kernel

• Beyond simple but not fully layered(分層)

Layered Approach

• 定義：採取Top-Down方式，切割系統功能/元件，以降低複雜度。元件/模組之間呼叫關係分層

  即上層可以使用下層的功能，但下層不可以使用上層的功能。完成後要使用Bottom-up方式進行測試，debugging(由底層一路往外測)

• 層次的劃分沒有明確規定

  

• 優點：

  • 降低設計複雜度
  • 有助於分工
  • 測試、除錯、維護容易

• 缺點：

  • 很難做到精準的分層劃分
  • 若Layer數太多，則System performance is very poor( 切到四層剛好、五層太多，極限中的極限是七層)

Microkernel(微核心)：由CMU(卡內基-美隆大學)率先提出，代表產品：Mach o.s。它們認為UNIX的服務項目太多、太龐大，不利移植

• 定義：將Kernel中一些Non-essential services(比較不是那麼基本、重要、必要)，自Kernel當中移除，改成在User Mode(Site)提供這些服務，以System programs方式存在，如此一來，可以得到一個比較小的kernel，稱之為microkernel, 一般而言，Microkernel提供下列三個minimum service：

1. Porcess Controll
2. Memory Management(不包括Virtual memory)
3. Process Communications(提供message Processing服務而已)

• Benefits(好處)

1. Easier to extend a microkernel
   • 服務的增加/刪除是容易的，因為這些服務是在user site執行，所以服務的增、刪不需要牽扯到Kernel也要變更，即使要，也是少量
2. Easier to port the OS to new architectures
   • 因為Kernel很小，所以移植到新的硬體平台之更改幅度不大(因為只有三個服務run在kernel)
3. More Reliable
   • 萬一某一個服務在執行中掛掉了，充其量只是相當於一個user process死掉而已，所以對HW, kernel, 其他user process沒有不良影響，因為把大部分的服務移到user mode去做了，因此更加安全、可靠
4. More secure
   • 萬一某一個服務在執行中掛掉了，充其量只是相當於一個user process死掉而已，所以對HW, kernel, 其他user process沒有不良影響，因為把大部分的服務移到user mode去做了，因此更加安全、可靠

• 缺點

1. Performance overhead of user space to kernel space communication(效能較差)，因為process Communication充斥大量訊息傳遞

Note：microkernel的相反詞：Monolithic kernel

定義：所有的Services皆須Run in kernel mode，大部分的商用OS幾乎都是Monolithic kernel，因為如果把所有的service移到user site去做，那它的控制就會很低。當這個控制力很低的時候，user或program就可以自己去Inhence一些東西，影響OS

優點、缺點：和microkernel相反

Module

• Many OS implement loadable(有需要才載入) kernel modules
• use Object-oriented approach
• Each core component is separate
• Each talks to the others over known interface
• Each is loadable as heeded within the Kernel
• 簡而言之：similar to Layers but with more flexible, 效能更好

例如：Linux, solaris, etc …

Hybrid(混合?)：現在作業系統很難純粹歸屬於某一型

• Linux(中央考過) and Solaris 是 Monolithic (所有東西都run在kernel mode)，且也是Modular for dynamic loading
• 例：windows mostly monolithic，有時針對不同客戶需求，會再加上microkernel for subsystem
• 例：Apple Mac Os 也是混合的

kernel 包含

Mach microkernel

部分的BSD UNIX

I/O Kit

dynamic Loadable module(叫做 kernel extension)

Virtual Machine

定義：利用sofeware技術模擬出一份與底層HW一模一樣的功能介面之抽象代理器(abstract machine)，稱之Virtual Machine模擬的方式類似於CPU schdueling

名詞解析：

Host：undelying hardware system, os

VMM(Virtual Machine Manage)或Hypervisor：creates and managing/ runs virtual machines

Guest：process provided with virtual copy of the host

恐龍本之其他英文

• Abstract hardware of a single computer into several different execution environments
• Similar to layered approach, But layer crates virtual machine(VM)

優點

• 作為測試開發中的OS，提供一個良好的負載平台，具有下列好處：

  1. 其他user, user processes工作，仍可持續運作，不須暫停
  2. 萬一測試中的OS不穩定、掛掉/失敗了，也不會影響host Hw, OS, 其他user processes 之工作，因為只是相當於一個user process fails而已，不會對system有重大危害

  

  3. 同一部Host Hardware上可以執行多個OS running on 多個virtual machines，這樣可以節省成本

  4. Consolidation(合併)：在 Cloud computing environment，我們會用有限的機器，建立為數注眾多的virtual machines，我們可以依VM上的Applications之執行負擔輕重，調用Host machines資源，做因應的支援，有需要就在加開，沒需要就關掉，做資源的合併與調度

  5. VM較為安全(如果VM被病毒入侵，不致擴散，因為各VM之間是相互獨立的)

  6. 可以Freeze, suspend, running VM, 及Clone(複製) VM

  

VMM的Implementation

Hypervisor : 虛擬機管理程式

1. Type0 Hypervisor(硬體層次)：

   1. Hardware-based solutions via firmware
      • 例如：IBM LPARS and Oracle LDOMs

2. Type1 Hypervisor(Kernel Mode層次)

   1. OS-like software

      • 例：VMware ESX, Joyent SmartOS, Crtrix XenServer

   2. general purpose OS that provide VMM functions (services)

      • 例如Microsoft Window Server with HyperV, Redhat Linux with KVM

3. Type2 Hypervisor(user mode層次)：

   3. Applications level provides VMM functionality

      eg. Paraller Desktop, Oracle VirtualBox

還有一些其他的變形上面那三類都是要創造跟底層硬體(Host HW)一樣的Virtual Machine，但下面這些卻不是

4. Paravirtualization☆考試重點

   • The guest OS need modify to work in cooperation with VMM to optimize performance
   • presents guest(run 在virtual Machine上的都叫guest) with similar but Not identical to Host Hardware
   • Guest must be modified(必須要被修改才可以用) to Run ON Paravirtualization virtual hardware

5. Programming-environment virtualization

   • VMMs do not virtualize, HW but instead create on optimized virtual system .(創造全新的Virtual Machine)

     eg. Java virtual machine(JVM), Microsoft .NET

     JVM is a SPECification(規格), not an implementation

     規範

     1. Class Loader(把bype code load下來)
     2. Class verifier(驗證器，驗證byte Code安不安全，比如是否包含pointer)
     3. Java interpreter(執行byte code)

     

6. Emulators：Allow application written for one HW to run on a very different HW such as different type of CPU。例：PS4模擬器、3DS模擬器

7. Application containment (底層沒有Virtual Machine，而是 創造執行環境，而不是模擬)

   eg. Oracle Solaris Zones BSD Jails, IBM AIX WPARs application

   

   Policy(政策、策略 ) 與 Mechanism

   1. Policy定義

      1. “What” to be proovided
      2. 經常改變、朝令夕改

   2. Mechanism定義

      1. How to do that
      2. The underlying(基本的) mechanism甚少改變或不變

   3. 設計原則：

      Policy與Mechanism宜separate，以增進system flexibility

   4. 舉例

      • 運用Timer作為CPU protection > Mechanism
      • Max.Time Quantum大小制定 > Policy
      • CPU排版採Priority Scheduling 排班 > Mechanism
      • Priority大小之定義 > Policy

Chapter 3 System Structure

這個部分和第二章寫在一起了

Chapter4 Process Management And Thread Management

Process 定義與Progeam比較

PCB內容 考試重點

Process State Transition Diagram (S.T.D)考試重點

Scheduler的種類(解釋名詞)

長期

短期

中期

Context Switching (解釋名詞)

Dispatcher, Dispatch latency(較少考)

Process Controller Operations(UNIX, System Call為主的程式追蹤) 考試重點

評估CPU Scheduling 效能的好或不好的5個Criteria(清大喜歡考)

各種CPU 排班法則(7個)介紹及相關名詞(Starvation,Aging,Preemptive,Non-preemptive,Convoy effect) 考試重點

特定System的排班設計

MultiProcessors System

Real-time System

Soft (考申論題)

Hard(考計算題)

Thread Management

Process Definition

定義：A program in execution[恐]

• Process 建立後，其主要組成有：
  • Process No(ID): Process被生成出來時，會有一個Process Id，作為識別
  • Process State
  • Code Section, Data Section：Process占用的 Memory Space
  • Programming Counter(PC)：程式計數器，告訴我們現在這個Process執行到哪裡，裡面放下一條指令的位址
  • Stack
  • CPU Register value
  • 是OS 分配 **Resource(CPU,I/O-Divice, Memory) **之對象單位：跟Thread的差別
• 與Program(程式)的比較

Process Control Block

(PCB內容)

定義：OS為了管理所有Processes，會在Kernel memory中，替每個Process，各自準備一個Block(Table, 表格)，用來記錄Process之所有相關資訊

PCB的主要內容有(要背，考選擇)：

1. Process No(ID)：是Unique(唯一的)

2. Process state：eg. ready, running, wait, etc

3. Programming Counter：內放 the next instruction’s address

4. **CPU Registers：eg. 紀錄使用到的暫存器的值 eq. Accumulator, PSW(Process Status Word), Stack Top ,etc **

5. CPU Scheduling Info：eg. Process 的優先權，First-In First-Out(FIFO)

6. Memory Management Info(隨OS的記憶體管理方法不同，紀錄不同資訊)：eg. Base/Limit register或 Page Table 或 Segment Table

7. Accounting Info：eg. Process已使用了多少CPU Time, 哪些資源, 還剩多少資源,多少CPU Time可以用 Note：目的

   計算使用量，記帳、收＄

   Administrator 調教Performance的依據

8. I/O Status Info：eg. process已經發出多少I/O-Request, 完成 狀況如何，占用那些I/O Resource(目前還沒釋放的)

Process State Transition Diagram

狀態轉換圖(S.T.D)

目的：描述Process之Life Cycle，用來記錄Process建立，到它被終止之間，所發生的事

各個版本的STD定義都不太一樣

1. [恐] 5個State的STD
2. [Stalling]7個State STD (比恐龍多兩個狀態)
3. [Stalling] UNIX的STD

5 Steps of State Transition Diagram

要會畫，會說明，超基礎，考出來是送分題

7 Steps of State Transition Diagram[Stalling]

補上Middel Term Scheduler

為了解決一個問題

當記憶體被占滿了，有一個更高優先權的Process近來，該如何處理？

把wait狀態的process踢出去，放到磁碟去保存

UNIX STD[Stalling]

Scheduler Type(Important)

1. Long-term Scheduler

   • 定義：又叫Job Scheduler，目的是從Job Queue中挑選一些Jobs載入到Memory中
   • 特色：
     1. 執行頻率最低，所以才叫長期
     2. 可以調控Multiprogramming Degree
     3. 可以調控 I/O-Bound Job與CPU-Bound Job之混合比例(下面有解釋)
     4. Batch System採用，但是real-time system以及time-sharing不會採用這種機制。因為real-time系統處理的process都是比較緊急的，因此就需要直接丟進memory去執行。而time-sharing系統要求對每一個user公平，沒有優先度需要處理，如果memory不夠則調用virtual memory，因此time-sharing系統只存在medium-term以及short-term

2. Short-term Scheduler：

   • 定義：又叫CPU Schduler或Process Scheduler，目的是從Ready Queue中挑出一個高優先權的process，分派CPU，給CPU執行
   • 特色：
     1. 執行速度是三者裡面最高的
     2. 無法調控Multiprogramming Degree，因為它不是負責將程式load進memory與Swap out出去的人
     3. 無法調控I/O-Bound Job與CPU-Bound Job之混合比例，頂多決定誰要先做，不能決定比例
     4. 所有的 System採用

3. Medium-term Scheduler(最常被考)：

   • 定義：Time-Sharing System採用，當Memory空間不足，且又有其他高優先權Processes需要Memory Space時，此Scheduler會啟動，它會挑選一些Processes(eg. Blocked Process, 低優先Process) 將其Swap Out到Disk中，保存，以空出Memory Space，供其他Process使用，將來等到有足夠的Memory Space released後，此Scheduler可再將它們Swap In 回Memory, ready for execution

   • 特色：

     1. 執行速度是三者裡面居中的

     2. 可以調控Multiprogramming Degree，因為它不是負責將程式load進memory與Swap out出去的人

     3. 可以法調控I/O-Bound Job與CPU-Bound Job之混合比例，頂多決定誰要先做，不能決定比例

     4. Time-Sharing System採用

Multiprogramming Degree：系統內的Process的數目：一般而言，Degree越高，CPU利用率就越高。

I/O-Bound Job與CPU-Bound Job

1. I/O-Bound(受限) Job

   定義：此類型工作大都是需要大量的I/O operation(resource)，但對於CPU Time(Computation)需求很少，因為其工作效能受限於I/O-Device之速度，稱之I/O-Bound，對CPU有最高優先權，因為它占用CPU的時間最短

   例如：Data Base Management, 財報的處理列印

2. CPU-Bound(受限) Job

   定義：需要大量的CPU計算，產生數筆資料，對I/O有最高優先權，因為它占用CPU的時間最短

   例如：氣象預估、科學模擬

如果OS發現I/O-Bound過多，則會透過Schduler來調控兩者之間的比例

Context Switching

• 定義：當CPU要從Running Process切給另一個Process使用之前，Kernel必須**保存(Store) Running Process的目前狀態資訊(eg. Programming Counter的值，Stack的值，CPU Register的值，etc)，即存回此Process之PCB **。且要載入(restore)另一個Process之狀態資訊from此Process PCB，這樣的行為就叫做Context Switching，Context Switch本身是一個額外的負擔，因為需要花CPU的時間去做切換，不能用在Process的執行上，因此時間大多取決於硬體的因素居多(eg. Register的數量夠不夠，Memory存取指令速度

• 如何將低Context Switching負擔

  1. 如果Register的數量足夠多，則可以讓每一個Process皆有自己的(Private) Register Set，OS只要切換Point指向另一個process之Register Set 即可完成Context Swtitching without memory store/restore ，因為速度夠快。但這個方法不太切實際，因為Register的成本關係
  2. 使用Multithreading機制。
  3. 讓System process及User Process各自擁有自己的Register set，如此兩者之切換只要Registers Set的Pointer即可

Dispatcher And Dispatch Latency

分派器與分派延遲

• 定義：Dispatcher，此一模組的目的是要將CPU控制權授予經由CPU Scheduler依據CPU排班法則所選出之Process，選好後CPU Scheduler會將工作交給CPU Dispatcher，主要的工作項有下列三項

  1. Context Switching
  2. Change Mode from to Kernel mode to User Mode
  3. Jump to the execution entry of that selected proces

  上述這三個工作所耗費的時間總和就是Dispatch Latency

• 希望Dispatch Latency越短越好，這些Process可以盡早開工

Process Control Operations☆☆☆☆☆

Lession 1 Theory

• 定義：Process建立、終止、暫停、恢復執行、設定／修改／讀取 Process Attributes值 etc.

  上述這些皆是OS應該提供的服務(i.e System Call)

• Procss是可以建立自己的Process(Child Process)，目的是要Child Process做工作

• Child Process所做的工作，可以分為2類：

  1. 與Parent 相同的工作(子承父業)
  2. 特定工作(與Parent不同)

• Parent與Child之間的互動關係為：

  1. Concurrent execution(交錯使用，通常是執行第一類的工作(子承父業))
  2. Parent waits for Child until child terminated(等著收割Child的成果)

• Child Process 所須的資源由何處取得?

  1. OS供應(這種情況OS會去限制每個process最大可產生多少個Child Process)
  2. Parent供應(整個家族Process的資源都是共享，Parent Process的Sharing Time有一小時，那麼整個家族的Sharing Time 就是一個小時

• Parent 若終止，則Child Process會如何處理?

  1. 一併終止(最常被使用) ：稱之為Cascading(層疊的) termination

  2. Parent Process死了，但Child Process存活，那Child的資源由以下兩者提供

     • 向OS取得資源

     • 向祖先Process取得資源

Lession 2 Example - UNIX System Call

• fork()：此System call. 用以建立 Child Process，而fork()之傳回結果，對象如下

失敗：因為資源不足(記憶體不夠，PCB也不夠)，無法建立，會傳回負值(-1)給OS, then Pass to parent process，通常失敗的話，OS也會順便把Parent process砍死

成功：OS會傳回一個值，用以區分child or parent：

0值：給child process

.> 0值：給Parent，且此值為Child Process ID

• wait()：此System Call用以暫停Process execute, 直到某個事件發生，eg. 父等子直到子終止 。

• exit()：此System Call用以終止Process的執行，回收其資源但PCB的空間可能還留著，直到父把子的結果回收回來才回收通常exit(0)表示正常終止，exit(-1)表示異常終止。子Process做完工作後，子Process要自己發出一個exit的System Call，讓OS來殺掉子Process。

• execlp()或exec(), execve()：此system call用於請OS載入特定的binary code(可執行的檔案)，來執行。這個System call可以交由子process執行，讓子process執行特定的工作，去執行之後就不會再回來執行原程式下面的指令了，因為已經去執行特定的工作了

  eg. execlp(“目錄名稱”,“檔名”,參數)

• getpid()：此System Call用以取得Prcess的Id

​ 說明：

​ OS會配置child process memory space, 此空間是占用不同的記憶體空間，且子process的Data section 及 code section內容均來自父process的copy, initially。

​ 若子process所作之工作與父process相同，則fork()完，就已經達成目的。

​ 若子process要做特定工作(與父process不同)，則子process必須執行execlp()這個system call

​

Lession3 Programming

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

//例題1；建立Child process執行ls命令檔，且父等子完成後才列印Child completed

    void main(){
    int pid ;
    pid = fork();
    if(pid<0){
        printf("fork fails \n");
        exit(-1); //爸爸自己自殺
    }else if (pid ==0){
        //兒子要做的事情
        execlp("/bin/ls","ls",null);
        exit(); //這段code不會執行，原因是因為execlp()會把process指向/bin/ls的binary code，接著就是去執行那段binary code了，就不會回來執行這個exit();
    }else //pid >0{
        //爸爸要做的事情
        wait(); //父Process子Process直到子Process終止 子Process做完工作後，子Process要自己發出一個exit的System Call，讓OS來殺掉子Process。
        printf("child Completed");
        exit();
    };
	{
        //不管怎樣都會執行的地方
    }
}	

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

//例題2 假設Parent, child 之process ID為2600, 2603 求line A, B, C, D 印出值
void main(){
    pid-t pid, pid1; //pid-t: 一個名為pid 的type，就是整數，是C語言的寫法
    pid-fork(); //pid 放的是子process的ID， pid1放的是自己process的ID
    if(pid==0){
        pid1=getpid();
        printf(pid); //A 0
        printf(pid1); //B 2603
    }else if(pid >0){
        pid1=getpid(); 
        printf(pid); //C 2603
        printf(pid1); //D 2600
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

//例題3  問A的值value是多少 

int value =5;
void main(){
    pid-t pid;
    pid = fork();
    if(pid ==0){
        value +=15;
        return 0;
    }else if(pid >0){
        wait(null);
        print(value);  //A=5 就算是global的變數，也是只能在自己的process作用
        return 0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

//例題4 求列印結果
(1.)
void main(){
    int pid;
    pid =fork();
    if(pid==0){
        printf("A\n");
    }else //pid >0{
        printf("B\n");
    }
}
Ans: 父與子是並行的，因為父process沒有wait(), 因此答案可能是AB或BA
(2.)
void main(){
    int pid;
    pid =fork();
    if(pid==0){
        printf("A\n");
    }else //pid >0{
        printf("B\n");
	    wait();
    }
	printf("C\n");
}
Ans: ACBC,ABCC,BACC,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

//例題5 假設Count，是一個父與子Process的共享變數 ，初值為5
(1.)
void main(){
    int pid;
    pid=fork();
    if(pid==0){
        count++;
        printf(count);
    }else if (pid >0){
        wait();
        count--;
        printf(count);
    }
}
Ans.6,5
    (2.) //父與子並行
void main(){
    int pid;
    pid=fork();
    if(pid==0){
        count++;
    }else if (pid >0){
        count--;
    }
     printf(count);
}
Ans. 45,54,55 //這是基本情況
    
    //以高階程式語言的角度來看，count++實際上是兩條code
    //count+1跟count=count+1
    //先加然後再附值
    //如果以組合語言的角度來看，就是三行code
    //LOAD R1, Count
    //INC R1, 1;
    //STORE Count,R1
    //但Process沒有辦法保證這三條Code會連續做完，有可能做到一半就被另一個Process搶走了
    //所以還有一種情況是+1完之後，還來不及Assign，CPU就被另一個Process搶走了

    Ans.66,44,46,64
    

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

//例題6
(1.) How mant processes are created? (include main())
    
    void main(){
    fork();
    fork();
    fork();
}
Ans.8
(2.)
    void main(){
    if(fork()==0){ //等同於 pid=fork(); if(pid ==0) ....
        fork();
        fork();
    }
    fork();
}
Ans.10
(3.)
    void main(){
    fork();
    if(fork()>0){
        fork();
    }else if(fork() ==0){
        fork();
        fork();
    }
}
Ans.14
(4.)
    void main(){
    for(i=0;i<3;i++){
        if(fork()==0){
            fork();
            fork();
            fork();
        }
    }
}
Ans.729
(5.)
    void main(){
    for(i=0;i<3;i++){
        if(fork()==0){
            fork();
        }else if(fork() > 0){
            if(fork()==0){
                fork();
            }
        }
    }
}

(6.) 
	void main(){
        int a =2;
        fork();
        a--;
        printf(a);
        if(fork()==0){
            a--;
            printf(a);
            fork();
        }else{
            a++;
            fork();
            printf(a);
        }
    }
(i.) printf(a)共做了幾次?
(ii.)印出0的有幾次?
(iii)印出1的有幾次?
(iiii.)印出2的有幾次?

例題1

例題2

例題3

例題4

parse1

parse2

parse3

例題5

parse1

parse2,3

例題6

Evalue CPU Scheduling Performance 5 criteria

1. CPU utilization：cpu花在Process exec time / CPU total time(process exec time + context switching time+ idle time)

   • 舉例：Process平均花5ms在exec上 ,context switching = 1ms,則CPU utilization = 5/5+1 =5/6

2. Throughput(產能)：單位時間內完成的Job數目

3. Waiting Time(等待時間，考試重點)：process花在ready queue中等待獲得CPU之等待時間加總

   

4. Turnaround Time(完成時間)：從Process進入(到達)到它工作完成的這段時間差值

   

5. Response Time(回應時間)：自user(user process) input 命令/Data 給系統到系統產生第一個回應的時間差，沒有一個特定的量法去量它，稱之Time-sharing system, user-mteractive, application特別重視這一塊

由上述得知，排班的目標必是，**利用度越高、產能越高，時間相關的東西越短越好 **

CPU排班法則行為介紹

1. FIFO
2. SJF
3. SRTF
4. Priority
5. RR
6. Multilevel Queues
7. Multilevel Feedback Queues (MFQs)

FIFO法則

• 定義：到達時間最小的process，優先取得CPU

• 例如：

  Process	CPU(burst) Time 要花的CPU time
  P1	24
  P2	3
  P3	3

  到達時間皆為0(從一開始就到了)

  到達順序為：P1, P2, P3(擺到ready queue的順序)

  Question

  1. 畫出Gantt Chart
  2. 求Avg. waiting time
  3. 求Avg. Turnaround Time

  

• 分析

  1. 排班效能最差，即Waiting time & Turnaround time 最長

  2. 可能會有**Convoy Effect(護衛效應：許多Processes 均在等待一個需要很長CPU time之process 完成工作，才能取得CPU，造成Avg waiting time 很長之不良效應) **

  3. 公平

  4. No Starvation

     • (沒有飢餓現象：Process因為長期無法取得完工所需各式資源，導致它遲遲無法完工，形成Indefinite Blocking 現象，稱之Starvation，容易發生在不公平對待之環境，若再加上Preemptive機制，則更是容易發生，補償方案：“Aging(老化)“技術，隨著Process待在System內的時間逐漸增加，我們也逐步提高此process的優先權，故可取得Process Resources完工，因為不會Starvation。注意：Soft real-time System不採用Aging，因為Soft real-time system是為了確保real-time process取得最高優先權，如果加入Aging機制，就有可能有process的priority高於real time process)

  5. Non-preemptive(不可插隊；不可搶奪)法則

     • 版本1(白話文)

       1. Non-preemptive法則

          • 定義：除非執行中的process自願放掉CPU，其他Process才會有機會取得CPU，否則就只能wait，不可逕自搶奪CPU
          • 例如：完成工作、Wait for I/O-completed after issue I/O-request
          • 優點：
            1. Context Switching的次數比較少，因為不可插隊，所以Switching的頻率小很多
            2. process之完工時間點較可預期(Predictable)，因為不可插隊
            3. 比較不會有Race Condition Problem
          • 缺點：
            1. 排班的效能較差，因為可能有Convoy effect
            2. 不適合用在Time-sharing System, Real time System，因為這兩個都需要插隊的機制

       2. Preemptive法則

          • 定義：執行中的Process有可能被迫放棄CPU，回到ready Queue，將CPU切給別人使用，eg. Time-out, interrupt etc
          • 優點：
            1. 排班效益較佳，平均waiting/ turnound Time較小，可以把耗時較長的Process Preemptive掉
            2. 適用於Real-time sysem(要能夠把real time 的process插入進去) 及Time-Sharing System
          • 缺點：
            1. 完工時間較不可預期
            2. Context Switching次數多，負擔較重
            3. 須注意Race Condition之發生

     • 版本2：從CPU排班決策(啟動)之時機點來做區分(可以參考 State Transition，以下是五種情況做解說)

       1. Running —> Block eg: wait for I/O completed [自願放棄]
       2. Running —> Ready eg: time-out [被迫放棄]
       3. Wait —> Ready eg: I/O-completed [尊爵不凡的process醒來了，所以要啟動CPU scheduling，獲得CPU，低優先權的process被迫放棄CPU]
       4. Running —> Exit eg:完成工作 [自願放棄]

       所以若排班決策之啟動點只包含1,4，未包含2,4，則為Non-preemptive,否則preempt。

       Note：凡是 xxx —> ready 皆列入preemptive元素(選項)，所以

       ready/suspend —> ready

       New —> Ready

       皆列入preemptive

SJF(Shortest Job First)法則

• 定義：具有最小的CPU TIME之Process，優先取得CPU，若都一樣小，則採FIFO。

• 例如：

  Process	CPU Time
  P1	6
  P2	8
  P3	7
  P4	3

  Process到達時間皆為0，求Avg waiting time

  

• 分析：

  1. 排班效益最佳(optimal)，即Avg waiting/ turnaround time最小

     • 說明：Why optimal?

       

       因為Short Job所減少的等待時間必定>= Long-Job所增加的等待時間，因為平均等待時間會最小

  2. 不公平，偏好short Job

  3. 可能會Starvation(for long Job)

  4. 可以分成

     Non-preemptive —> SJF做代表

     Preemptive —> 另外叫做SRTF法則

  5. 較不適合用在Short-term scheduler(比較不恰當啦，但你要用也是可，因為Short-term scheduler執行頻率太高，所以很難在極短的時間間隔內去預估出精確的CPU Burst time for each process 且排出最小值，不易真正呈現出SJF之行為，反倒是適合用long-term scheduler

     Short time scheduler是指專門負責處理短暫的工作的計劃程序。這些工作通常會在短短的時間內完成，並且有許多工作要求同時進行。在這種情況下，使用short job first（SJF）法則來處理工作可能不是最佳選擇。這是因為SJF法則是基於工作預計完成時間的，並假設工作的預計完成時間是可以預先知道的。但是，在short time scheduler中，大多數工作的預計完成時間都是未知的，因此無法準確地應用SJF法則。另一個原因是，SJF法則會將短工作放在優先執行的位置，因此會把許多短工作排在一起。在short time scheduler中，這可能會導致許多短工作之間的競爭，從而導致效率降低。總的來說，short time scheduler更適合使用其他計劃策略，例如基於先進先出（FIFO）或基於最短剩餘時間（SRT）的策略，來處理短暫的工作。)

     如何評估process之the next cpu burst time?

     1. 公式(加權指數平均公式)

        

        	t0	t1	t2	t3
        實際值	20	10	40	20
        預估值	20(一開始還沒預估，所以都是抓t0的值)				?
        	T0	T1	T2	T3	T4

        

     2. 意義:　

        

SRTF,SRJF,SRTN( Shortest Remaining-Time Job First(Next))

• 定義：即為Preemptive-SJF法則，即剩餘CPU Burst Time(CPU完成一次短時間工作所需的時間)最小的 Process，取得CPU。也就是若新到達的Process其CPU Burst TIme 小於目前執行中process剩下的CPU time, 則新到達之Process可以**插隊(preemption)**執行。

• 舉例：

  Process	到達時間	CPU Time
  P1	0	8
  P2	1	4
  P3	2	9
  P4	3	5

  求Avg waiting Time for

  1. SRTF

     

  2. SJF(不可插隊)

     

  3. FIFO

     

• 分析：

  1. 與SJF相比，SRTF之平均waiting/Turnaround time會比較小(SRTF是SJF的一個子類，因為SRTF可插隊，所以會有最小的waiting time, 但是付出較大的Context Switching的overhead(負擔)
  2. 不公平，偏好Short remaining-time Job
  3. 會有Starvation的問題
  4. Preemptive法則

Priority法則

• 定義：可參數化的法則，具有Highest Priority之Process，優先取得CPU，若多個Process權值相同，則以FIFO為準，也有分成Non-preemptive, Preemptive的差異。

• 舉例：不可插隊

  Process	CPU time	Priority No.
  P1	10	3
  P2	1	1
  P3	2	3
  P4	1	4
  P5	5	2

  且，Priority No越小，優先權越大The Smaller Priority No. Implies the higher priority。求Avg waiting Time

• 分析：

  1. 是一個具參數化的法則，即給予不同的priority高低定義，可展現出不同的排班行為。

     Priority定義	行為
     抵達時間越早，優先權更高	FIFO
     CPU　Time越小，優先權越高	SJF
     剩餘時間越小，優先權越高	SRTF

     因此FIFO, SJF, SRTF都是屬於Priority的一種

  2. 不公平

  3. 會有Starvation (可用Aging去解決)

  4. 分為Non-preemptive, preemptive兩種

RR(Round Robin)法則(考試重點)

• 定義：Time-Sharing System採用，OS會規定一個CPU time Quantun(or Slice)，當Process取得CPU執行後，若未能在此Quantum內完成工作，則Timer會發出"Time-out” interrupt通知OS，OS會強迫此process放掉CPU，且回到ready queue中，等待下一輪再取得CPU執行，每一輪之中，process是以FIFO排隊方式取得CPU

• 舉例1：

  Process	Cpu time
  P1	8
  P2	4
  P3	9
  P4	5

  到達時間皆為0，順序是P1~P4, 使用RR(Quantum=4), 求Avg waiting time

  

  舉例2:

  Process	Arrival Time	Cpu Time
  P1	0	10
  P2	2	5
  P3	7	3
  P4	13	8

  

舉例3:

Quantum= 5，問turnaound time ? waiting time ?

• 注意：有些題目是有爭議的

​ eg.

​ 採RR(Q=4)

​

• 分析：

  1. Time-sharing System 採用
  2. 也是一個可參數化的法則(ie. Quantum)
  3. 公平
  4. No starvation
  5. preemptive法則(Real-Time, Time-Sharing適用，RR超過Quantum time後會被迫回到ready

• 舉例2

  Quantum=∞

  則RR會變成FIFO法則—> 排班效能很差

  注意：也因此，FIFO屬於RR的一種

• 舉例3

  Quantum =極小值

  則Context Switching太頻繁，CPU Utilization會很低

  依經驗法則，若Quantum值能讓**80%**的Job在Quantum內完成，效能較佳。

• 補充：RR雖然是公平的，但也可支持差異化(優先權差異)之實現，How do you achieve this?

  Ans.

  1. 針對高優先權Process在ready Queue中置入多個PCB pointer 指向此Process，使得每一輪當中，它有多次取得CPU之機會
  2. 針對高優先權Process給予較大的Time Quantum

MultiLevel Queues(多層佇列)法則

• 定義：

  1. 將原本單一一條ready queue變成多條ready queues且高、低優先權不同
  2. Queues之間的排班法則，通常採取Preemptive and Priority法則
  3. 每個Queue 可以有自己的排班法則 eg. RR
  4. Process一旦被置入於某個Queue中，就不可(不允許)在不同ready queues之間移動

• 舉例：I/O-Bound與CPU-Bound Job你會置於哪個Queue中?

  Ans：I/O-Bound Job —>Q1

​ 　　　CPU-Bound Job —>Q3

• 分析：

  1. 可參數化的項目眾多1. Queue的數目 2. Queue之間的排班法則 3. 每個Queue自己的排班法則 4. Process被放入哪個Queue之Criteria ，有助於排班設計及效能調校之Flexibility

  2. 不公平

  3. 有Starvation(被放在Q3 的Process永世不得翻身，因為Process一旦被置入於某個Queue中，就不可(不允許)在不同ready queues之間移動☆☆☆☆☆

  4. Preemptive

MultiLevel Feedback Queues(MFQs)(多層回饋佇列)

• 定義：與MultiLevel Queue相似，差別：允許Process 在不同Queues 之間移動，可採取類似Aging技術，甚至可以搭配降級的做法，來避免Starvation
• 分析：
  1. 可參數化的項目眾多1. Queue的數目 2. Queue之間的排班法則 3. 每個Queue自己的排班法則 4. Process被放入哪個Queue之Criteria 5.Process在不同佇列之間移動的規則，有助於排班設計及效能調校之Flexibility
  2. 不公平
  3. 不會有Starvation(被放在Q3 的Process永世不得翻身，因為Process一旦被置入於某個Queue中，就不可(不允許)在不同ready queues之間移動☆☆☆☆☆
  4. Preemptive

小結

1. 哪些是Non-preemptive法則

   Ans. FIFO,SJF,SRTF, Non-preemptive priority

2. 哪些是No Starvation

   Ans. FIFO, RR, MFQs

3. 哪些包含於(∊)關係是錯的

​ A. FIFO ∊ Priority

​ B. SJF ∊ Priority

​ C. FIFO ∊ RR

​ D. SJF ∊ RR

​ E. RR ∊ MFQs 是喔，MFQs的參數可以設定成一條Queue

​ Ans. (D)

補充 CPU Utilization計算

例1.

假設採RR排班

Time Quantum值= Q

Context Switch Time = S

Process 平均執行每隔T時間會發出I/O-request, 求下列Case之CPU Utilization(cpu花在Process exec time / CPU **total time(process exec time + context switching time+ idle time)** )

1. 0 < S < T «Q

   

2. 0<S<Q«T

​

3. 0<S=Q «T

   

4. Q非常小

   

例2. [恐] (看不懂)

10個I/O-Bound Tasks(很花I/O)

1 個CPU-Bound Tasks(很花CPU)

I/O-Bound task執行每隔1ms 發出 I/O-request，每個I/O-運作花10ms

Context Switching Time = 0.1 ms, 求CPU utilization, 採RR法則

1. Quantum = 1ms

   

2. Quantum = 10ms

   

​ 寫完之後會發現有個info沒有用到「每個I/O-運作花10ms 」，因為有CPU-Bound的存在，所以不存在idle Time，如果不存在CPU-Bound，則可能存在idle的情形，就需要考慮這種情形

特殊系統之排班設計考量

Multiprocessors System

1. Multiprocessors分為

   1. ASMP(非對稱的，Master-slave架構) —> 沒有什麼特殊設計，嘻嘻，因為只有Master這個CPU去看ready queue以及job的assign，所以其實沒啥特殊設計

   2. SMP(對稱式) —>

      1. 每個CPU共享同一條Ready Queue，當CPU完成某Process後，就去存取ready Queue，取走一個Process執行。設計重點：必須提供ready queue的互斥存取機制，若未提供，則可能發生Process重複執行或Process被ignored(無人執行)之錯誤。

         

         例如：CPU去取得Process之工作如下

         1. 取得(read) Ready Queue, Frond End的process之PCB Pointer
         2. 刪除此Process Pointer from Queue

         CPU1	CPU2
         T1: step1: 取得P1 PCB pointer	T2:step1取得P1 PCB pointer
         T3: Dequeue執行	T4: Dequeue執行

         設計重點：

         1. 必須提供ready Queue的互斥存取機制
         2. 不須考量Load Balancing

      2. 每個CPU有自己的Ready Queue

         每個CPU只會檢查自己的ready Queue, 有工作就執行，無工作就idle

         設計重點：

         1. 不須有互斥存取的考量，一旦發生idle，則把其他CPU的queue調整過來
         2. 需考量Load Balancing，避免有CPU沒事，有CPU很忙。通常使用兩種機制來調整CPU Loading
            1. Push migration(移轉)
            2. Pull migration(移轉)

Processor affinity

• 定義：在multiprocessors system中，當process已決定某CPU上執行，則在他執行過程當中，盡量不要將之移轉到其他CPU上執行(除非有其必要，eg. processor BAD, load Balancing, etc)避免CPU內之cache等內容要複製，且刪除，影響到效能表現，可以有
  1. Hard affinity：規定process不可移轉
  2. Soft affinity：盡可能不轉，但不強制限制，若有需要還是可以轉

Real-Time System排班設計考量

Hard real-time system

• 排班設計考量

  Step

  1. 先確定這些工作是否schedulable(可排程化，CPU可以負荷的了)

  2. 確定可schedulable後，然後在考慮是否可以滿足各工作的DeadLine

     兩個排班法則

     1. Rate-Montonic scheduling
     2. EDF(Earliest Deadline First)法則

• Schedulable與否之判斷公式：

  

  例：有下列4個Real-time event. 其CPU burst time,Period Time 分別是：

  CPU Burst Time	Period Time
  20ms	80ms
  50ms	100ms
  30ms	30ms
  Xms	1Sec

  ，則在Schedulable要求下，x不可超過?ms

  Ans

  

• 怎麼排程以滿足個工作DeadLine after Schedulable?

  • Rate-Monotonic法則

    1. 採取Static priority(一旦process的優先權高低順序訂定了，就不會再改變) 且 preemptive 法則

    2. Period Time愈小，優先權越高

    3. 舉例

       Process	Period Time	CPU time
       P1	50	20
       P2	100	35

       Q1. schedulable與否?

       

       Q2. 若規定P2的優先高，且preemptive, 這樣是否滿足DeadLine?這題感覺怪怪的，不懂

       ​

       Q3. 採用Rate-Monotonic, 是否滿足Deadline?

       ​

    4. 分析：

       1. 並不保證可以滿足DeadLine
       2. 在Static priority要求下，它是Optimal(若它無法滿足DeadLine,其他Static priority 法則也是無法滿足

  • EDF(Earliest Deadline First)

    • 定義：採用Dynamic priority 且Preemptive

    • 規定：DeadLine越小(早)優先權越高

    • 舉例：

      Process	Period	CPU Time
      P1	50	25
      P2	80	35

      是否滿足Deadline?

      1. Rate-Monotonic

         

      2. EDF

         

    • 分析：

      1. EDF保證是optimal in the schedulable case(任何工作都可以滿足 DeadLine)
      2. 理論上，CPU utilization 可達100%，但實際上不可能，因為有Context switching, interrupt handling 等額外負擔

Soft real-time system

• 定義：這個系統要確保real-time的process取得最高優先權，同時，這個real-time的process priority不能做衰減

• 就CPU Scheduling Design 而言，必須

  1. 支援preemptive-priority
  2. 不支援Aging技術
  3. 盡可能降低Kernel Dispatch latency time, 使得real-time process可以及早開工

• 降低kernel Dispatch latency

  1. 困難度(緣由) ：大部分的OS，皆不允許當kernel正在執行System Call or 其他System processes時，被user process任意插隊(preemption)，目的是為了確保kernel Data Structures的正確性(即不要有Race Condition)，然而此種做法，對於Soft real-time system極為不利

     eg. 假設目前kernel 正在執行一個Long-time system call(eg. I/O operation)，而此時real-time process到達/fork(),它必須等到kernel完成此long-time system call後，才能取得CPU，所以

     Dispache latency太長，要解決此一問題，原則是: 必須插隊kernel 且要保障kernel Data Structure之正確性

     方法

     1. Preemption Point：

        • 定義：在此System calls code中，加入一些Preemption Point(在此時點插隊時，Kernel是安全的)將來，System call執行時若遇到Preemption Point ，System call會先暫停，Kernel會檢查此時是否還有real-time process存在/到達，若有，則Kernel system call暫停執行，CPU分派給real-time Process使用，若無，則System Call繼續執行，直到遇見下一個Preemption Point
        • 缺點：System Call中可以加入的Preemption Point數目不夠多，因為Dispatch Latency仍然很長。

     2. Kernel可隨時被real-time process插隊，但要對於Kernel的共享Data Structure/resoruce提供嚴謹的互斥存取(Synchronization 機制)，以確保資料之正確性(當P1對某個Data進行操作，執行到一半時被real-time process給搶走，此時會把該Data給Lock住，不讓real-time process操作該Data，以保護資料)

        • 缺點：可能造成Priority Inversion問題(優先權反轉)，高優先權的Process所須的共享Data/resources恰好被一些低優先權的Process把持，無法存取(所以互斥存取控制之故)，造成高優先權等待低優先權Process之情況(即高process要等低process釋放這些共享Data/resource)

          

          當高優先權的Process因為遲遲等不到Lock解除，會因為time-out的關係而放棄CPU，此時可能有其他中優先權的Process取得CPU的使用權，因此低優先權的Process完成不了，進而完成對共享Data/resources之使用進而Release, 所以高優先權process被迫要等一段很久的時間

        • 解決方法：Priority Inheritance

          • 定義：讓低優先權的Process暫時繼承高優先權之權值，使得低優先權Process可以很快取得CPU完成對共享Data/Resouce之使用，並release them. 同時，也立刻恢復其原本的低權值

Real-time system之Dispatch Latency 組成

Dispatch Latency有兩個phase組成

1. Conflict Phase：
   1. Preempts kernel
   2. 低優先權realse高優先權所需之Data/resource
2. Dispatch Phase
   1. Context Switching
   2. Change mode to user Mode
   3. Jump

Thread Management(貝多芬)

Thread( or Multithreading)定義、優點

Process(Single-Threaded) vs Thread (Multithreading)

user-level thread 與 kernel-level thread

Multithreading Model(3種)

Multithreading issue

fork()

signal delivery

Threads pool

程式追蹤(PThread library)

Thread

• 定義：又叫lightweight-process(傳統的process就叫heavyweight process)，是OS分配CPU time 之對象單位**(恐：It’s a basic unit of CPU Library)**

• Thread 建立後，其私有的(private)內容組成包含有(都是與執行相關的)

  1. Programming Counter
  2. CPU registers value
  3. Stack
  4. Thread ID, State, etc …(Note: record in TCB[Thread Control Block])此外，同一個Process內不同之Threads彼此共享此Process的
     1. Code Section(合稱Memory space, address space)
     2. Data Section(合稱Memory space, address space)
     3. other OS resources eg. open files, I/O resources ,singal, etc …

• 圖示

  1. MultiThreading Model

     

  2. Process = Single-Threaded Model

     

     Note: 類比

     Process —> 汽車

     Thread —> 引擎

     汽車會有一個引擎，也可以有很多，MutliThread就像是一部車子有多個引擎，然後共享車子有的配件(儀表板、方向盤等等)。CPU Time是以Thread為對象在畫分

• 優點(Benefits)

  1. Responsiveness：當Process內執行中的Thread被Blocked，則CPU可以切給此Process內其他available Threads 執行，故整個Process不會被Blocked，仍持續Going, 所以Multithreading用在user-interactive application, 可增加對User 之回應程度
  2. Resource Sharing：因為Process內之多條Threads 共享此Process code section，所以在同一個Memory space上可有多個工作同時執行
  3. Economy：因為同一個Process內之不同Threads彼此共享此Process的memory 及 other OS resources, 因為Thread 之 私有成分量少，故Thread之Creation, Context Switching fast, Thread management cost is cheap(fork一個Process的成本遠大於複製一個Thread)
  4. Scalability(Utilization of Multiprocessors Architecture)：可以做到同一個Process內之不同Threads可以在不同CPUs上平行執行，所以可以增加對Multiprocessors System之效益(平行程度)提升

Process Vs Thread

其實是在比Singal Thread and MultiThread

Thread的的優點

Thread的的缺點

Philosophy

Process與Thread沒有功能差異，只有效能差異(你會的，我也可以，你不會的，我也不會)。

哪些工作適合用MultiThreads?

Ans. 一個時間點有多個工作要執行。例：Client-server Model(同時有人過來要檔案，看檔案)

哪些工作不適合用MultiThreads?

Ans. 一個時間點最多只有一個工作可以做。例：命令解譯器(eg. UNIX 之 Shell)

Thread分類：user-Thread與Kernel-Thread

區分角度：**Thread Management工作(如：Thread Creation, Destroy, Suspend, wakeup, Scheduling, Context Switching, etc)**由誰負責

1. User-Level Thread

   • 定義：Thread Management是由在User Site之Thread Library提供APIs, 供User Process呼叫使用，進而管理，稱之
   • Kernel 完全不知道(is Unaware of) Use-Level Threads 之存在Note：只知有Process(Singal-Threaded)
   • Thread management不須Kernel介入干預**(kernel unware user-thread)**
   • 優點：There creation, context switching 等，Management is fast 成本較低
   • 缺點：
     1. 當Process內某條執行中的user-thread is blocked(eg. i/o)，會導致整個Process亦被Blocked(即使process內還有其他available threads)這個process都是user Thread，發出一個blocking的system call, kernel會認為是這個Single process發出的請求，因為kernel不知道process裡頭還有其他user Thread的存在，於是就把整個process block住，CPU切到其他process去執行
     2. MultiProcessors架構效益發揮較差(因為無法做到process內之多條user-threads平行執行，但這樣也是有好處的，整個thread的管理不需要kernel的干預，不需要再user, kernel間切換，降低管理的成本)
   • 例：舉凡Thread library皆是user-threads(eg. POSIX 的 PThread library是規格，只在UNIX系統上, Mach的C-Thread Library, Solaris2以上的 UI Thread Library及Green Thread Library).

2. Kernel-Level Thread

   • 定義：Thread Management完全由kernel負責，Kernel知道每一條Thread之存在並進行管理

   • 優缺點與user-thread相反

   • 例：大部分OS皆支援 (Windos系列 etc. 2000, Xp, UNIX, LINUX, Solaris)

   • 舉例：[Module版]

     

     • CPU Time依分配對象數，平均分配(10個人就分10%，20個人就分5%)
     • 則Pa, Pb各分到?%CPU Time，if All Threads are
       1. User Thread：kernel只知道有兩個Process要來搶CPU，來分CPU Time，Pa,Pb各分50%
       2. Kernel Thread：kernel知道有5條Thread要分CPU time，1條分20%，Pa分到3條，所以是60%, Pb是40%

MultiThreading Model [恐龍本獨有]

恐龍本用來詮釋user Thread跟Kernel Thread的見解

[user thread mapping kernel thread的數目]

1. Many-to-One Model
2. One-to-One Model
3. Many-to-Many Model

1. Many-to-One

• 定義：This model maps many use threads to one kernel Thread. Thread Management is done in use space
• 優、缺點：如同user thread
• 例：thread library皆是
• 圖示：

2. One-to-One Model

• 定義：This model maps each use Threads to a kernel Thread. Thread Management is done in use space
• 優點：同kernel thread
• 缺點：
  1. Slower
  2. Process每建立一條user-thread, system就必須配合生一條kernel thread與之，所以user thread數目眾多，系統負擔會很重，耗資源
• 例：Window NT, Window2000, OS/2, Linux(個人電腦系列幾乎都是ONE-TO-ONE)

3. Many to Many

• 定義：This model maps many use Threads to a small or equal number of kernel Thread. Thread Management is done in use space
• 優點：同前述kernel thread, 負擔也不像one to one的model來的重
• 缺點：1. slower 2. 製作設計上，較為複雜

MultiThreading Issue

原本Single Thread沒這問題

1. fork() issue

2. Signal delivery(傳送) issue

   1. Signal：it is used in UNIX to notify(通知) the process that a particular event has occurred

   

   當process收到signal通知後，它必須處理(可由process自己處理或交給default signal handler處理)

   

   2. Signal的種類

      1. Synchronous signal[自作自受，這件事情是由你這個Process發生的，所以Signal就是發給你]eg. Divide-by-zero, illegal memory access,
      2. Asynchronous signal[池魚之殃，事情不是你做的，但別人發出，卻是砍你] eg. ctrl-c by administrator, time-out by timer

      

      3. Signal Delivery issue

         4個options

         1. 發給那個thread

         

         2. 發給大家

            

         3. 發給一些threads

            

         4. 發給一個thread，這個thread再把signal轉派給大家

            

3. Threads Pool

   • 緣由：在Client-Server Model中，當Server 收到Client’s request後，Server才建立Thread去服務此一請求，然而Thread creation 仍須耗用一些時間，所以對client 之回應不是那麼迅速
   • 解法：採用Thread pool機制，process(server)先建立一些Threads，置於threads pool中，當收到Client’s request後，就從Thread pool中指派一條 available thread去服務此請求，不須creation回應較fast，當此Thread 完成工作以後，再回到Threads pool中Stand By 如果Threads Pool中無可用的Threads，則Client’s request 須等待
   • 缺點：
     1. 萬一Process事先生出過多的Threads in the Thread pool, 對System resource耗用很高，Note:通常ＯＳ會限制Threads pool size

Thread程式追蹤

(以PThread library為例)

例：P4-49

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <Pthread.h>
int sum;
void *runner (void * param){
    sum =0;
    for(int i=1;i<=upper;i++){
        sum+= i;
        Pthread-exit(0); //thraed終止
    }
};
main(){
    Pthread-t tid; //tid就代表Thread的id
    Pthread-attr_t arrt; //代表attribute屬性 Thread attributes set
    ...
   Pthread-attr-init(&attr) ;//取得attr 初始值
   ★Pthread-create(&tid, &attr, runner, argv[1]); //根據attr 屬性值建立一條Thread，Id記在tid中，執行runner()副程式
   Pthread-join(tid, NULL); //main() thread 在此等待，直到tid thread結束
   printf(sum);
}

例：P4-50 程式二

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int value = 0; 
void main(){
    int pid ;
    pthread-t tid;
    Pthread_arrt_t attr;
    pid = fork(); //create child process
    if(pid==0){ //子prcess要做的事情
        pthread_create(&tid, &attr , runner,NULL); //子Process去create一條thread
        printf(value); //line C   
    }else if(pid > 0){
        wait();
        printf(value); //line P
    }
}
void *runner(){
    value =5;
    pthread_exit();
}

例 p4-70

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

shared by threads
A. static local variables(共享)
B. program text/exec, binary (code sec)共享
C. register value of CPU(私有)
D. heap memory (code+ Data sec memory space)共享
E. Programming Counter (私有)
F. Stack memory(私有)
G. Open Files(共享)
H. I/O resources(共享)
I. local variable(私有)
J. Global variables(共享)

Chapter 5 DeadLock

• 定義：成立的四個必要條件，例子, 與Starvation做比較

• Deadlock的處理方法

  1. Deadlock Prevention ★★★★
  2. Deadlock Avoidance(Banker’s Algo★★★★★)
  3. Deadlock Detection and Recovery★★
  4. Ignores it .

• 定理★★★★★：

• 相關圖形

  Resource Allocation Graph(RAG)+3點結論★★★★★

  Claim edgy+RAG(for Avoidance)

  wait for Graph(for Detection)★

DeadLock

• 定義：系統中存在一組Processes彼此形成循環等待之情況，造成這些Processes皆無法往下執行(和starvation不同，Starvation還有一絲可能會做到)，並降低Throughput之現象。

• 死結成立的4個必要條件(4 necessary condition)，即缺一個，死結就不會發生. Ex. if there 4 conditions are true, then the deadlock will arise. Ans. False，都有不代表一定會發生

  1. Mutual Exclusion

     互斥性質，這是對Resource(正在搶奪的資源)而言，具有此性質的Resouce，在任何時間點最多只允許一個Process持有使用，不可多個process同時持有/使用。

     例：大多數的資源皆具此性質，eg. CPU, Memory, Disk, printer, etc …

     例：read-only file：不具互斥性質

  2. Hold & wait

     持有並等待，Process持有部分資源，且又在等待其他Process持有的資源

  3. No preemption

     不可搶奪，**Process不可以任意剝奪其他Process所持有的資源，**必須等到對方釋放資源後才有機會取得資源若可Preemption，則必無DeadLock，頂多只有Starvation

  4. Circular Waiting

     循環等待，系統中存在一組Processes形成循環等待之情況，eg.

     

  恐龍本：4 implies 2

  其他版本：4 implies 1,2,3eeeee

  ex. Why Singl-process不會造成DeadLock?

  A：因為Circular waiting 不存在，只少要有兩個process才可以形成循環等待，因此四個必要條件有一個不符合，即不會造成DeadLock

• 例子：

  

  • 與Starvatiom比較

    不同點：

    DeadLock	Starvation
    一組Processes形成Circular waiting，造成這些Processes皆無法往下執行，Waiting forever	Process因為長期無法取得完工所需的各式資源，造成它遲遲無法完工，有完工的機會喔，只是機會渺茫
    會連帶造成throughput低落	與throughput高低無關
    有4個必要條件，其中一定是No preemptive	容易發生在Preemption的環境(沒有一定，只是容易)
    解法有prevention, Avoidance, Detection & recovery	採用Aging技術防止

    相同點：

    DeadLock 7 Starvation
    皆是資源分配管理機制設計不恰當相關。

Resource Allocation Graph(R.A.G)

資源分配圖

• 定義：令Ｇ=<V,E> 有向圖代表RAG，其中

  1. Vertex(頂點)：有兩個類型：

     1. Process：以O來表示

     2. Resource：以表示

        其中”·“數目代表The Number of instances

  2. Edge(邊)：分為２種edge：

     1. Allocation Edge：
     2. Requset Edge：

• 例子 ：

  

RAG的三點結論☆☆☆☆☆必考

1. No Cycle則No DeadLock
2. 有Cycle不一定有死結 例：因為P3一定可以完工，會釋放1個R2, 可佩給P2，此時圖無Cycle，No DeadLock
3. 除非(若)每一類型的資源，皆為Single instance(單一數量)，則有Cycle必為死結

DeadLock處理方式

1. DeadLock Prevention
2. DeadLock Avoidance(避免) Banker’s Algo
3. DeadLock Detection & Recovery

1.2

• 優點：

  1. 保證System is Deadlock free (or never enters the deadlock state)

• 缺點：

  1. 對Resource的使用/取得限制多，因為resource utilization 偏低，連帶throughput 也偏低
  2. 可能造成Starvation

3

• 優點：
  1. Resources utilization相對較高. throughput也連帶較高
• 缺點：
  1. System有可能進入DeadLock state
  2. Detection & Recovery之cost相當高

DeadLock Prevention

• 原則：破除4個必要條件之其中一個，則死結必不發生

1. 破除 “Mutual Exclusion” -> 兩個字「辦不到」！因為這是Resource與生俱來(inheritance)的性質

2. 破除 “Hold & wait " - > 兩個方法(protocols)可用，想辦法讓Hold不成立，或是讓Wait不成立

   1. OS實施規定：除非Process可一次取得全部所需資源，才准許持有資源，否則不得持有任何資源，但這樣子會有資源利用度低的問題(明明可用，但卻要等到全部都可以用才可以使用)
   2. OS實施規定：Process可先持有部分資源，但當Process要申請其他資源時，必須Release持有的全部資源(不再Hold)，才可提出申請。但資源利用率一樣很低，因為有可能會把即將要使用的資源釋放出去

3. 破除"No preemption”　-> 改為"preemption” 即可, eg. based on priority-level

4. ☆☆☆☆☆破除"Circular waiting" -> 方法叫做"resource ordering" ，

   1. OS會賦予每一個類型資源一個Unique(唯一的)Resource id

   2. OS會規定Process必須按照Resource Id Ascending(遞增、遞減都行，你爽就好)的方式對資源提出申請

      持有的	欲申請的	允許或不允許
      R1	R3	允許
      R5	R3	必須先放到R5，才可提R3(因為不符合遞增)
      R1,R5	R3	必須先放到R5，才可提R3(因為不符合遞增)

      WHY?

      pf：假設在這樣的規定下，系統仍存在一組Processes形成Circular waiting如下

      

      依規定，我們可以推導出資源ID大小關係如下

      r0 < r1 < r2 < … <rn < r0

      竟推出 r0 <r此一矛盾式子，因此Circular waiting必不存在

Deadlock Avoidance

• 定義：當某個Process提出某些資源申請時，則OS必須執行Banker’s Algorithm，以確定倘若分配給process其申請資源後，System未來處於safe state，若Safe則核准其申請，否則(unsage)則否決其申請，process必須等一段時間後，再重提申請。

  

• Deadlock是unsafe之subset

Banker’s Algo ☆☆☆☆☆

本章的計算題都在這 Banker's Alog and Safety Algo

• 定義：使用的Data Structures

• 看不懂的話直接看下面範例比較快

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

  假設 n：process個數 m: resource種類數 1. Request i ：［1..m］of int -> Pi提出之各式資源申請量 2. Allocation : n*m martrix -> 各個process目前持有的各式資源數量 3. MAX: n*m martrix -> 各process完工所需之各式資源最大數量 4. Need：n*m martrix(自己算) -> 各process尚須(欠)各式資源數量才能完工，因此Need= MAX -Allocation 5. Avaliable：[1..m]of int -> 系統目前可用的，各式資源數量，因此Available=資源總量-Allocation 舉例說明：假設有人來貸款3,000萬，那麼Requesti =3000萬、Allocation就是自己的存款，假設這邊是2,000萬，想買一棟9,000萬的房子，這9,000萬就是他的MAX，那麼Need= 9,000-2,000= 7,000萬，Available 就是銀行目前金庫裡能借給你的錢，這邊假設是10,000萬。 Step1. Check Request <= Need ?若成立，則往下執行，若不成立，則終止Process。 Request=3,000萬，Need= 7,000萬。這樣就是合理的，但假設你今天需求7,000萬，可是卻貸了3,000兆，遠超於你的需求，那就有問題了 Step2. Check Request <=Available?若成立，則往下執行，若不成立，則Pi waits until resouce availalbe 概念就是你去貸3,000萬，可是銀行金庫目前的錢不夠，需要你稍等一下 Step3 (試算) 假設貸款成功 Allocation = Allocation + Request Need = Need - Request Available = Available - Request Step4 依上述試算值，必須執行 "safety" algo，若回傳"Safe" state則核准Pi此次申請。若回傳"unsafe" state，則否決Pi此次申請。Pi必須等一段時間再重提申請

Safety Algorithm

1. Data Structures used 除上述之外，另外加入

   1. Work:[1..m] of int -> 表系統目前可用Resources之累計數量

   2. Finish:[1..m] of Boolean -> 針對Process

      Finish[i]=

      True: 表Pi可完工

      False: 表Pi尚未完工

      ∀1<=i<=n

2. Procedures

   Step

   1. 設定初值

      Work = Available

      Finish[i]皆為False

      ∀1<=i<=n

   2. 看可否找到Pi滿足：

      1. Finish[i]為False且
      2. Needi <= Work (我所需要的資源，)

      若可找到，則進3,否則則進4

   3. 設定Finish[i]=True，且Work= Work + Allocationi, then, 回到2

   4. Check Finish Array, 若皆為True，則傳回Safe State，否則傳回Unsafe state

範例

1
2
3
4
5
6

5個Process(P0,P1,P2,P3,P4)
3種resource(A,B,C)
資源量(A,B,C) = (10,5,7)

1. 求出Need及Available
2. P1提出(A,B,C)= (1,0,2)申請，是否核准?Why?

Ans.

• Allocation-各個Process身上所持有的資源

• MAX- Process完成工作最多所需要的資源數量分別是多少

• Need= MAX-Allocation

• Available= 系統目前還剩的可用資源數，資源總量()-已經配置出去的(Allocation出去的)

Request=(1,0,2), Banker’s Algo

1. Check Request <= Need ? (你所要求的小於你真正需要的，亦即你買東西只要500，不能跟銀行借到500萬)

   

2. Check Request <= Available (你要的借的錢是否小於銀行本身所持有的錢，亦即如果你要借1億，但銀行只有一百萬)?

   

3. (試算)

   P1:

   Allocation = <2,0,0>+<1,0,2>(申請量) = <3,0,2>

   Need = <1,2,2> - < 1,0,2>(申請量) = <0,2,0>

   Available = <3,3,2> - <1,0,2>(申請量) = <2,3,0>

4. 依上述調整值，來執行"Safety" Algo

• Allocation

• MAX

• Need

• Available

Safety Algo

1. 初值的設定

   • Work = Abailable = <2,3,0>

   • Finish

     0	1	2	3	4
     F	F	F	F	F

   尋找有沒有Process還沒完成工作，並且它的needi <= work的

2. 可找到P1滿足Finish[i]= False且Need <=work

​

3. 設定Finish[i]=True，且Work= Work+Allocation = (2,3,0) + (3,0,2) = (5,3,2) , then goto 2
4. work = (2,3,0) > (5,3,2)

​

5. 選擇P3滿足 Need<= Work，且Finish[i] = False

6. 設定Finishj[3]=True，且Work=(5,3,2) +(2,1,1) = (7,4,3), then goto 2

7. … 以此類推，P0, P2, P4皆可Finish，直到大家都Finish，因此大家都滿足了。

8. Check Finish陣列，因為皆為True，所以傳回Safe State，因此核准P1此次的申請

9. 列出上述其中一組Safe SequenceSafe Sequence/ Safe State定義：至少可以找到>=1組，Safe Sequence，成為Safe State，否則unsafe state。代表OS未來依此Processes順序可分配各Process所need的資源，使得大家皆可順利完工

   Ans. P1,P3,P0,P2,P4

10. 依現在狀況，若P4提出(3,3,0)申請，是否核准?why? (練習題)

    Ans. Banker’s algo

    1. Check Request (3,3,0) <= Need(4,3,1) 通過

       • Need

       	A	B	C
       P0	7	4	3
       P1	0	2	0
       P2	6	0	0
       P3	0	1	1
       P4	4	3	1

​ 2. Check Request4(3,3,0) <= Available (2,3,0)?

​ 不成立，因為無法核准，可用資源不足

11. 依現在情況，若P0提出(0,2,0)，是否核准? Ｗhy?

    Ans. Banker’s Algo

    1. 快速跑過，確認可以過，資源分配改變如下

       • Allocation

         	A	B	C
         P0	0	3	0
         P1	3	0	2
         P2	3	0	2
         P3	2	1	1
         P4	0	2	2

       • Need

         	A	B	C
         P0	7	2	3
         P1	0	2	0
         P2	6	0	0
         P3` | 0 | 1 | 1 |
         P4	4	3	1

       • Available

         A	B	C
         2	1	0

    2. 執行Safety’s algo

       1. 設定初值，Work=(2,1,0)
       2. 找尋是否有符合Needi <= Work 的Process，且還有Process為False**(不通過)**，所以unsafe

範例二

• Allocation

  	A	B	C
  P0	0	3	0
  P1	3	0	2
  P2	3	0	2
  P3	2	1	1
  P4	0	0	2

• Need

  	A	B	C
  P0	7	2	3
  P1	0	2	0
  P2	6	0	0
  P3	0	1	1
  P4	4	3	1

• Available

  A	B	C
  2	1	x

求x的最小值，使其成為Safety

1. 設置初值，work= (2,1,x)
2. 找尋 Need <= work
3. 找到了，P3，先暫定x=1 (2,1,1)
4. P3因為可以完成，完成後資源就可以釋放出來，因此work (2,1,1) > (4,2,2)
5. 繼續找尋Need <=work
6. 找到了，P1
7. P1因為可以完成，完成後資源就可以釋放出來，因此work(4,2,2) > (7,2,4)
8. …往復循環，以此類推

​

x= 1;

Banker’s Algo 之 Time Complexity

先講結論，複雜度就是O(n^2*m)

(n: Process 數目, m:resource 種類數)

Banker’s Algo Time Complexity

Step

1. O(m)Check Request <= Need
2. O(m) Check Request <=Available
3. O(m)試算
4. Run safety algo
5. 設置初值work -> 1~m的一維陣列，因此複雜度為O(m)。Finish ->1~n的一維陣列，因此複雜度為 O(n)
6. 先來看看Safety’s algo的步驟

​ 第一次最多會檢查n次，再來第二次檢查n-1次…

​ =(n+1)n/2個Processes。每次檢查Need <=Work 花O(m)的時 間，最多花O(n^2*m) time

7. 花O(n) Check Finish

因此複雜度就是O(n^2*m)

針對每一項類型資源，皆為Single-instance情況下，有較簡易的Avoidance作法

1. 利用RAG，搭配Claim edge(宣告邊)使用

2. Claim edge:

   

   代表Pi未來會對Rj提出申請(即表MAX/NEED之意義)

3. Steps：

   當Pi提出Rj申請後

   1. 檢查有無Pi對Rj的這條宣告邊(Claim edge)存在，若有，則goto2否則，終止Pi

   2. Check Rj是否Available，若是，則goto3，否則Pi waits(變成申請邊)

   3. (試算)暫時把宣告邊改為配置邊

   4. 執行safety’s Algo, check 圖中是否有cycle存在

      若沒有，則為safe -> 可核准

      有Cycle，則為unsafe -> 否決

4. 例：

   

   1. 若P1提出R2之申請，是否核准?

      Ans.

      

   2. 若P2提出R2之申請，是否核准?

      

補充：Deadlock是unsafe之subset(或unsafe有可能導致死結，也有可能不會導致死結)

1. 可能不會死結

   ans. 搞不好P1在提出R2的申請時，就使用完R1了，這時就不會有死結。或是P2在P1提出申請之前就使用完R2了，此時也不會有死結。

2. 可能會有死結

   ans. P1立刻對R2提出申請，此時RAG有Cycle，且資源都是Single Instance

也就是說死結產生與否取決於宣告邊在哪個moment提出申請

​

定理

系統若有n個processes，m個resource量(單一種類)滿足下列2個條件：

1. 1≦MAXi≦m(每個process的最大需求量至少要有1個，最多不超過m)

2. 且所有n個process的Maxi加總，小於n+m

   $$ \sum_{i=1}^nMAXi<(n+m) $$

   則System is Deadlock free.

例1. 有6部printers被process使用，每個process最多需要2部printers才可以完工，則System 最多允許?個process執行以確保deadlock Free?

ans. m=6, Max=2

開始跑定理

1. 1 ≦ Maxi ≦ m -> 1 ≦ 2 ≦ 6成立

2. $$ \sum_{i=1}^nMaxi<(n+m) $$

​ 所以2n<n+6，n<6，Ans:　最多５個processes

​

詳解

1. 所謂死結的發生，就是系統已經將所有的資源都投入下去，但依然沒有產出，不會有一個系統是佔據著資源不分配，看著底下的Process進入Deadlock還很開心

   

2. 應此將資源分配下去後，就是長這樣

   

3. Process取得2個Resource後就可以執行，執行完後又釋放2個Resource給其他的Process使用

   

4. 持續的把Resource分配給Process… 往復循環，即可完成。

5. 若很不幸的是，如果今天是6個Process，就會發生死結

   

6. 推導公式，若今天題目改成，每個Process需要3台印表機，現在有10部列表機，最多能允許幾個Process(MAX=3, m=10)

   3n<n+10

   =2n<10

   =n<5

​ ans. n=4

例2. 證明：

​ proof：假設資源全部配置出去

$$ 即\sum_{i=1}^n Allocationi = m $$

​ 又因為

$$ \sum_{i=1}^nNeedi = \sum_{i=1}^nMaxi-\sum_{i=1}^n Allocationi(Banker’s Algo) \
= \sum_{i=1}^nMaxi-m \
∴\sum_{i=1}^nMaxi=\sum_{i=1}^nNeedi+m $$

​

​ 再依據條件(2)

$$ \sum_{i=1}^nMaxi < (n+m) \
∴\sum_{i=1}^nNeedi+m<(n+m) \
$$

​ 得出這個結論

$$ ∴ \sum_{i=1}^nNeedi < n $$

​ 此事代表至少有>=1個Process之Needi為0，代表Process可以完工，且Pi至少會Release出>=1個Resource**(∵條件(1) -> MAX>=1,而Needi=0 ∴Allocation >=1)**使得剩下的Process當中又會有>=1個process之Need為0又可以完工。使得剩下的process中又會有>=1個Process之Need為0又可以完工，依此類推，所有Process皆可完工，∴Deadlock Free

解釋的數學式子如下，類似離散的鴿籠原理

$$ \sum_{i=1}^{n-1}Needi<n-1 $$

Deadlock Detection & Recovery

1. 如果放任resource使用較無限制，雖然Utilization高，但是System有可能進入死結而不自知。因為需要有一個死結偵測演算法，及萬一偵測出有死結，如何破除這個死結(recovery)的作法。

2. Recovery做法：

   1. Kill Process in the deadlock

      方法一：Kill All Processes in the deadlock寸草不生，眼不見為淨

      缺點：成本太高，先前的工作成果全部作廢。

      方法二：Kill processes one by one，Kill一個之後，須再跑偵測Algo，若死結仍存在，再Repeat上述步驟

      缺點：成本太高，Loop次數*偵測成本

   2. Resource Preemption

      步驟一：選擇"Victim" process(假設此Process擁有資源A,B,C)

      步驟二：剝奪他們身上的資源(剝奪B，保留A,B，這是最基本的情況)

      步驟三：回復此Victim process當初未取得此剝奪資源的狀態(這一步非常困難，成本極高，也不一定做得好，此外也可能有Starvation的問題)

Deadlock Detection Algorithm(考比較多的是Banker,Detection稍微知道就好)

1. Data Structures used

   n：process數

   m：resource種類

   1. Allocation：n*m matrix
   2. Availavle：[1…m] of int 目前可用資源數量
   3. Work: [1…m] of int
   4. Finish：[1…n] of Boolean
   5. Request：n*m matrix，各process目前提出之各式資源申請量

   Note：

   1. Avoidance(Banker’s Algo)含有未來(Future)info(MAX,Need)
   2. Detection：只有現在(Current)info

2. Procedures

   步驟一：初值設定

   Work=Available

   Finish[i]= True: if Allocation ==0

   ​ False: **if Allocation ≠0 **

   步驟二：看可否找到Pi滿足：

   1. Finish[i]為False
   2. Requesti ≦ Work

   若找到，則進入步驟三，否則進入步驟四

   步驟三：設定Finish[i]=True，且Work=Work+Allocationi, then 回到步驟二，找不到則回到第四步

   步驟四：Check Finish Array，若皆為True，因此目前無死結，否則則有死結，且Finish[i]= False者，即為陷入死結中

3. Time：O(n^2 *m) –> 死結偵測一次，cost很高，再加上乘以偵測頻率

範例1：

• Allocation

• Request

• Available

偵測目前有哪些死結?

若有，那些process in the Deadlock

Ans.

1. Work = Available = (0,0,0)

   Finish

   0	1	2	3	4
   F	F	F	F	F

   因為Allocation皆≠(0,0,0)

2. ∵可以找到P0滿足Finish[0]為F，且Request≤work ∴到第三步驟

3. 設定Finish[0]為True，且Work=(0,0,0)+(0,1,0)=(0,1,0)，回到第二步驟

4. ∵可以找到P2滿足Finish[2]為F，且Request2 ≤ Work，∴到第三步驟

5. 設定Finsh[2]為True，且Work=(0,1,0)+(3,0,3)=(3,1,3)，回到第三步驟

6. 在步驟二與步驟三之間抽插，往復循環，P1, P3, P4皆可Finished

7. Check Finish Array ∵皆為True，∴目前無死結

若每一類型資源資源皆為Single-instance，則有較簡化的Detection作法-使用Wait-For Graph

• 定義：令G=<V,E>有向圖，代表Wait-For Graph，其中

1. Vertex：只有Process Only，沒有Resource頂點
2. Edge：Pi 等待—>Pj，稱之為wait edge

• 是從RAG簡化而得，即若RAG中存在：

  1 2	graph LR; Pi --申請--> R --配置--> Pj

  則在Wait-For Graph 以

  1 2	graph LR; Pi --等待--> Pj

  呈現

• 偵測作法：在Wait-For Graph中，若有Cycle，則目前有死結，否則目前無死結

• 例：RAG如下

1. 化成Wait-For Graph

2. 目前有無死結

   Ans.∵有Cycle，∴目前有死結

   

Chapter 6 Process Synchronization

Process Communication,Inter Processes Communication; IPC

Process的關係就兩種

1. Independent
2. Cooperating(有資訊交換的需求)

何謂同步(Synchronization)？Process在執行的過程當中，因為某件事情的發生或沒有發生，導致它必須停下來，等對方完成，才可以接著往下做，符合這些事情的就是同步。

• Process Communication兩大方式

  1. Shared Memory

  2. Message Passing

• Race Condition Problem

• 解決Race Condition之兩大策略

  1. Disable interrupt
  2. Critical section design

• C.S.Design 必須滿足的3個Criteria(Mutual Exclustion, Progress, Bounded Waiting)

• C.S Design 方法(架構)

  • SoftWare Solutions
  • HardWare Instructions Support(Test-and-Set, SWAP)
  • semaphore☆☆☆☆☆(號誌)
  • Monitor
  • 解決著名的同步問題
    • Producer-Consumer Problem
    • Reader/Writer Problem
      1. First
      2. Second
    • The Sleeping Barber problem
    • The Dining-Philosophers Problem

• Message Passing 溝通方式(較少考)

Process communication之兩大方式

Shared Memory(本篇重點)

定義：Processes透過共享變數(shared Variable)之存(Write)取(Read)達到溝通(Info exchange)之目的

分析：

1. 適用於大量Data(message)傳輸之狀況
2. 傳輸速度較快(因為不須kernel介入干預/支持，Shared memory是Programmer的責任，Programmer要負責去處理互斥的問題)
3. 不適合用於Distributed System
4. Kernel不需提供額外的支援(頂多供應Shared memory space)
5. 是Programmer的負擔，必須寫額外的程式碼防止Race Condition的發生

Message Passing

定義：Process雙方要溝通必須遵循下列Steps

1. 建立Communication Link
2. 訊息可雙向傳輸
3. 傳輸完畢，必須Release

分析：

1. 適用於少量Data(message)傳輸之情況

2. 傳輸速度較慢(因為需要kernel支持)

3. 適合用於Distribute System

4. Kernel必須提供額外的支援

   例：send/recevice system call, Communication Link管理，Message lost之偵測、例外狀況之處理

5. Programmer沒有什麼負擔，只要會用send/receive的System Call就好

Race Condition problem

in shared memory Communication

定義：In shared memory Communication, 若未對共享變數存取提供任何互斥存取控制之Synchronization機制，則會造成"共享變數的最終結果值會因為Process之間的執行順序不同而有不同的結果值"，此種Data inconsistency情況，稱之為Race Condition

例子：Ｃ是共享變數，初值=5，此時有2個Process

Pi，Pj各執行一次，則C的最終值可能是5 or 4 or 6 ，這種稱之為Race Condition

• 結果為5，執行順序可能為

  T1= Pi = C =C+1

  T2= Pj = C =C -1

  or

  T1 = Pj = C = C - 1

  T2 = Pi = C = C + 1

• 結果為4，執行順序可能為

  T1：Pi執行C+1，得到6，但尚未Assign給C，只是先放在一個佔存器

  T2：Pj執行C-1，得到4，尚未Assign回C

  T3：Pi 6 assign回C

  T4：Pj 4 assign回C

  C的結果為4

• 結果為6，執行順序可能為

  T1：Pi執行C+1，得到6，但尚未Assign給C，只是先放在一個佔存器

  T2：Pj執行C-1，得到4，尚未Assign回C

  T3：Pj 4 assign回C

  T4：Pi 6 assign回C

  結果為6

範例1

x, y 是共享變數，初值x=5, y=7

Pi,Pj各作一次，求(x,y)之可能值

Ans.

(x,y) = (12,84)

(x,y) = (40,35)

(x,y) = (12,35)

範例2

x=0是共享變數，i 是區域變數

Pi,Pj各作一次，求(x)之可能值

提示

Ans.(3,4,5,6)

範例3

x=0是共享變數，i 是區域變數

Pi,Pj各作一次，求(x)之可能值

(-3,-2,-1,0,1,2,3)

解決Race Condition之兩大策略

Disable Interrupt

對CPU下手

定義：Process在對共享變數存取之前，先Disable Interrupt，等到完成共享變數的存取後再才Enable Interrupt。如此一來可以保證Process在存取共享變數的期間CPU不會被Preempted，即此一存取是Atomically Executed

例

優點：

1. Simple, Easy implementation
2. 適用於Uniprocessor System(單一CPU)

缺點：

1. 不適合用於Multiprocessor的系統當中，只Disable 單一CPU的Interrupt，是無法防止Race Condition(因為其他CPUs上執行的Process仍可存取共享變數)，必須要Disable掉全部的CPU’s Interrupt才可防止Race Condition，但這樣會大幅降低Performance(因為無法平行執行)
2. 風險很高，因為必須信任user process在Disable interrupt後，在很短的時間可以在Enable Interrupt，否則CPU never come back to kernel。注意，通常Disable Interrupt做法是不會開放給user Process的，它通常只存在於kernel的製作中(只有OS Developers可以用，因為開發者也要避免kernel內部的Race Condition)

Critical section(臨界區間) Design

對共享Data下手

恐龍誤用Spinlock, Busy-waiting

是一個概念

定義：對共享變數之存取進行管制，當Pi取得共享變數存取權利，在它尚未完成的期間，即使別的Process取得CPU，任何其他Process也無法存取共享變數。

• Critiacal Section：Process中對共享變數進行存、取的敘述之集合

• Remainder Section(RS)：Process中除了Critical Section以外的區間，統稱為Remainder Section

• Process內容：

  

  每個CS的前後，Programmer須設計/加入額外的控制碼，叫Entity Section，即Exit Section

• 而CS Design不是在設計臨界區間，因為臨界區間是個概念，CS Design是在設計Entry Sec及Exit Sec的Code

• 一個process可以擁有不只一個CS 只是範例都是只畫一個而已，要注意,進入C=C+1後，CPU可以被Pj搶走，但Pj想要對C操作時，Pj的Enrty Section就會把它擋下來。

• C.S Design 與 Disable Interrupt相比(spinlock, Busy waiting)

  優點：適用於Multiprocessors system

  缺點：

  1. 設計較為複雜
  2. 較不適合用在uniprocessor

Busy-Waiting Skill(or Spinlock)

• 定義：透過使用looping相關敘述(eg. for, while, repeat … util)，達到讓process暫時等待之效果

例：

1
2
3

while(條件式){
    //不做事，只是讓它跑
}

當條件式為True時，process就被卡在while中，無法離開while，如此達到Process暫停的效果，直到條件式變為False，process才會離開while，往下執行。

Note：

1. 
2. [恐]誤用：因為在C.S Design Entry section中經常是使用Busy waiting的技巧(或叫Spinlock)，因此恐龍會把spinlock & busy waiting 視作C.S Design，來去跟Disable Interrupt比較

• 分析：

  缺點：等待中的Process，會跟其他的Processes競爭CPU，將搶到的CPU time浪費掉，用於做無實質進展的迴圈測試上。因此，若此Process要等很長的時間才能exit迴圈，則此舉非常浪費CPU time

  優點：若Process卡在Loop的時間很短(i.e 小於Context Switcing time)，則Spinlock十分有利，因為Loop的時間很短，浪費的時間也不會太短。

• 另一種Non-Busy-waiting Skill

  定義：當Process因為同步事件被卡住，且如要卡很久的時間，則可以使用Block(p)的System call，將p暫停，即讓p進入Blocked的狀態，如此一來，P就不會與其他Processes競爭CPU，直到同步事件發生了，才wakeup(p) system call，將P從blocked變成ready state。

  

  優點：等待當中的Process不會與別人競爭CPU，不會浪費CPU Time

  缺點：額外付出Context Switch的事件幹 這真的算缺點嗎

C.S Design應該滿足的3個性質

1. Mutual exclusion
2. Progress
3. Bounded waiting

分述如下

Mutual exclusion(相互排斥)

定義：最重要的一點，如果沒這點的話談個屁的C.S Design，Race Condition都處理不了了。在任何時間點，最多只允許一個Process進入它自己的CS，不可有多個Process分別進入"各自"的CS

Progress(進展)

• 定義：須滿足以下兩點才算Progress
  1. 不想進入C.S的Process(亦即在Ramaid Section活動)，不可以阻礙其他Process進入C.S(或不參與進入C.S之決策)不想進去的process不會阻礙別人進入
  2. 從那些想進入C.S的Processes中，決定誰可以進入C.S的決策時間是有限的(不可以無窮，也就是No Deadlock likes waitgin forever 大家都無法進入CS)

Bounded waiting(有限的等待)

• 定義：以個別process的角度來看，自某progress提出申請到核准進入C.S的等待時間是有限的，即若有n個Process想進入CS，則任一Process至多等(n-1)次後，即可進入CS，即No Startvation，須公平對待

C.S Design的方法(架構圖)重要

Software Solutions

• 特色

  1. 2個Processes(Pi,Pj)(P0,P1)

     Algo1 x

     Algo2 x

     Algo3 o = Peterson’s solution

  2. n個Processes

     Peterson’s Solution(n個Processes)[不太會考了，因為真的很爛]

     Bankery’s Algo[麵包店取號碼牌的演算法，恐龍移掉了，但真的很重要，要學]

2個Processes之C.S Design(Pi,Pj,i≠j)

Algo1

1. 共享變數宣告如下

   1 2	turn: int 值為i或為j 意義：權杖，turn值為i，就是只能讓Pi進入(只有Pi有資格進入)，反之亦然

2. 程式

Algo2

1. 共享變數宣告如下

   1 2 3 4 5 6

   flag[i..j] of boolean; 初值皆為False 意義：flag[i] ={ True:Pi有意進C.S False:Pi無意進C.S }

2. 程式：

   

3. 分析

解析：

Algo3

Peterson's solution

混合Algo1,Algo2做撒尿牛丸

algo1只考慮誰有資格，沒考慮意願。algo2只考量意願，但會造成死結。因此結合百家之長，不只考量資格也考量意願

1. 共享變數宣告如下

   1. Flag[i…j] of Boolean初值皆為False 表意願
   2. Turn：值為i或j only 表資格

2. 程式

   

3. 分析

   CS Design要滿足的條件	滿足與否	解析
   Mutual Exclusion	O	相互排斥，不會有兩個process同時進入C.S：若Pi，Pj皆想進入C.S，代表flag[i]跟flag[j]結為True， 當雙方皆做到while測試的時候(也就是交錯)，表示雙方已分別執行過Turn=i, Trun=j之設定，差別只是先後順序不同而已。若Pi執行比較快，把Turn改成J，接著Pj因為執行比較慢，又把Turn改成i，所以Turn的值只會為i(或j其中一個)，不會同時為兩者，所以只有Pi或Pj一個Process得以進入CS，因此符合Mutual Exclustion
   Progress	O	因為progress有兩個情況，因此分別討論之。 1.不想進去的process不會阻礙別人進入： 假設turn值為i，且Pi不想進入C.S，代表Flag[i]為False，若此時Pj想進去則Pj必可離開while(因為Flag[i]==False)，而進入CS，因為Pi不會阻礙Pj進CS 2.不產生Deadlock：若Pi,Pj皆想進入C.S，則在有限的時間內必可決定出Turn值為i或為j，讓Pi or Pj進入，兩者不會waiting forever
   Bounded Waiting	O	先進去的process出來後，不會立刻再進去，亦即不會有Starvation的情形：假設turn為i，Pi已先於Pj進入CS，而Pj等待進入中，Flag[i]==[j]==True，若Pi離開CS之後，又立刻想進入CS，則Pi必定會做一件事情，就是**~~把Flag[i]自己設為False~~，把Turn設成=j**，一定是Pj進入CS，因為Pj至多等一次後即可進入CS。

N個Processes C.S Design

Bankery’s Algo(麵包店取號碼牌)

解決Race Condition

• 觀念：

  1. 客人(Process)要先取得號碼牌，才可入店內(CS)
  2. 店內(CS)一次只容一人(Process)進入
  3. 號碼最小的客人或同為最小號碼之多個客人中ID最小的(PID)，得以優先進入店(CS)

• 共享變數宣告如下：

  1. Choosing[0…n-1] of Boolean 初值皆為False。

     意義：choosing[i]=

     • True：Pi正在取得號碼牌，尚未確定號碼
     • False：
       • Pi取得號碼牌
       • 初值

  2. Number [0…n-1] of int 代表號碼牌

     意義：代表P0~Pn-1，n個Process之號碼牌值，初值皆為0。

     number[i]：

     • 0：表Pi無意願進入CS
     • .>0：表Pi有意願進入CS

  3. 數學函數used

     1. MAX(…)：取最大值(用來決定號碼牌的值)
     2. (a,b)<(c,d)若要成立，則必須滿足下列兩個條件之其中一個
        1. a<c
        2. a==c and b<d

  4. Pi之程式如下：

  1 2 3 4 5 6 7 8 9 10 11 12 13

  repeat chosing[i]= True; //表明正在取得號碼牌 Number[i] = MAX(Number[0]...[n-1])+1; //決定號碼牌是幾號 choosing[i]= False; //表示已取得號碼牌 for(j=0;j<n;j++){ // 此for-loop去檢測所有process while (choosing[j]){do noting} //若別人pj正在取號碼牌中，則稍等一下，若都沒有被卡住，可以順利跑完，則進入CS while(number[j]>0 and (number[j],j)<(number[i],i)){do noting} //i代表自己，j代表別人。Pj有意願進入CS，並取Pj號碼小於我或跟我同好，Pj Id j <Pi ID i，則我等待。 } C.S Number[i]=0; R.S untill False

經典問題

為何會有很多個Processes取得相同的Number值？

Ans. 假設MAX(Number [0]~[n-1]值為k，Pi,Pj(i≠j) 2個Processes之交錯執行順序如下：

正確性證明？

Ans.

• Mutual Exclusion：OK

  Case1. 假設Number值皆不同(>0)，則具有最小的Number值之Process，得以優先進入CS，其餘Process wait而最小值必唯一

  Case2. 有多個Processes具最小Number值，則以Processes之PID最小者得以進入CS，而ProcessID具備Unique性質，因為最小值必定唯一。

  藉由Case1, Case2知道唯一性確定，互斥確保

• Progress：OK

  Case1. 假設Pj不想進入CS，代表Number[j]為0，若此時Pi想進入CS則Pi檢查到Pj，Pi必定不會被Pj所阻礙，可以exits for中第二個While(因為while(number[j]>0 )，這個條件判斷不成立)

  Case2. 若P0~Pn1-1，n個Processes皆想進入CS，則在有限的時間內，必有一個Proess(其Number最小或同號中ProcessID最小)，可以順利跑完for loop進入CS，因為No Deadlock

• Bouned waiting：OK

  Case1. 假設P0~Pn-1 n個Processes皆想進入CS，另Pi具有最大的，number值為=K(number[i]=K)，因此Pi會是最後進去的，其他(n-1)個Processes:Pj(j≠i)，必定皆先於Pi進入CS。若Pj離開C.S後，又立刻想再進入C.S，則Pj取得的號碼牌之值Number[j]必定大於K，所以Pj不會再度先於Pi進入CS，因此Pi頂多等(n-1)次後即可進入CS

設計問題

1
2
3
4
5
6
7
8

for(j=0;j<n;j++){
    while(choosing[j]){
       // do noting
    }
    while(number[i]>0 and number[j],j<(number[i],i)){ //問題，既然這邊都會把不符合的Process攔下來，娜何還需要上面的choosing[j]來卡住呢?是不是可以把choosing[j]刪掉，這樣的邏輯對嗎?會出現什麼問題嗎
        // do noting
    }
}

解釋：

違反了互斥。

例：令　目前Number[0,n-1]都還沒領到號碼牌值皆為0，Pi，Pj2個Processes(i≠j)想進入CS，且假設ProcessID是i<j

​ 就好比一個阿婆跟一個年輕妹妹一起去麵包店，年輕人先取完號碼牌，老太婆還沒取完。這時候妹妹領完後，老太婆還沒領，原本的設計下，妹妹會等阿婆領完才執行下一步，但這種情況下，即使阿婆還沒取，妹妹也會直接進入麵包店裡。接著阿婆取完號碼牌，發現跟妹妹同號(Race Condition)，此時他也想進入CS，這時候阿婆的身分證號碼(UID)比妹妹小，所以阿婆也可以進入CS，這種情況下，有兩個Process同時進入CS裡，違反了互斥(Mutual Exclustion)

Hardware Solution - CPU Instructions Support

若CPU有提供下列指令之一

1. Test-and-Set (Lock)
2. SWAP(a,b)

則Programmer可以運用在CS Design

Test-and-Set(Lock) 指令

定義：此CPU Instruction之功能為，傳出Lock參數值Lock的資料型別為boolean且將Lock參數設為True(1)，且CPU保證此指令是☆☆☆"Atomically Executed"☆☆☆，

範例：以Ｃ語言說明此指令功能：

1
2
3
4
5

int Test-and-Set(int *Lock){
    int  temp = *Lock;
    *Lock = 1;
    return temp;
}

用在C.S Design上

[Algo1]：Ｘ不可以用

1. 共享變數如下：

   Lock：boolean = False

2. Pi程式如下：

   1 2 3 4 5 6 7 8 9

   repeat{ while(Test-and-Set(Lock)){ // do nothing } C.S區塊; Lock = False; R.S; Utill False; }

3. 分析：

   1. Mutual Exclustion：OK

      

   2. Progress：OK

      1. 不想進去的人就待在RS裡面，不會去搶
      2. 避免死結，總有一個人會搶到Test-and-Set(Lock)

   3. Bounded Waiting：違反

      假設Pi已先於Pj進入CS，且Pj等待中，當Pi離開CS後，若想在立刻進去CS，則Pi是有機會在優先進去搶到Test-and-set之執行，因此Pj 有可能Starvation

[Algo2] ：穩的，可以用

1. 共享變數如下：

   1. Lock：boolean = False; Test and Set會用到的變數
   2. waiting[0 ..n-1] of boolean初值皆為False，若為True則代表有意進入區間，若為False則代表初值，或準備進入C.S

   意義：

   waiting[i]有兩種，若為

   True：表Pi有意進入CS，且正在等待中

   False：代表初值，或是表示Pi不需要再等了，可以進入CS

2. Pi之程式如下： [034 17 02 CH6 P 6 71時24分02秒 17:57]

   區域變數

   • Key：boolean;

   • j: int

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

   repeat waiting[i] =True; //Pi有意，且等待中... key= True; while(waiting[i]&& key) { key = Test-and-set(Lock); } //--------------------分隔線-------------- //在還沒離開while前，waiting[i]的值不可能為False，Process i 個人而言不可能把waiting[i]值改成False進入CS。因此只剩Key可以動了 // 又因TestAndSet(Lock)方法會返回Lock的Boolean值，並將Lock設為True，也因此，惟有第一個搶到CPU的Process，才會有False的Key值 waiting[i]= False; //☆☆☆☆☆表明Pi不用等了，可以進入CS了☆☆☆☆☆ C.S; j= (i+1) % n; //n是陣列長度, j 是指i的下一個element of array while(j≠i && not waiting[j]){ //若j=i，則表示已經繞了一圈。waiting表意願，True代表想，False代表不想 j=(j+1)%n; //找出下一個想進入C.S之Pj } if(j==i) { //搭配下面的case2，代表都沒人想進入CS，並且因為 Test-and-Set(Lock)會將Lock設為True(可參照上面) Lock =False; //因為都沒人想進去，因此就把鎖打開 } else{ waiting[j]= False; //Pj不用等了，換你進CS } R.S; utill False;

   Case1.

   

   

   Case2：當Pi執行完後，發現外面都沒任何人想進來，只好再把Lock設回False，一切重新ReSet

   

   

Q1：證明正確性

Ans．

[1] Mutual Exclusion：OK

pf： Pi可進入C.S之條件有兩種可能

case1. Key值為False

代表Pi是第一個搶到Test-and-Set(Lock)執行者，如此才能將Key改為False，==因此唯一性確立==

case2. waiting[i]為False

代表Pi在離開while之前，是不會將waiting[i]改為False,==只會將它設為True，只有在CS的Proces當它離開CS後，才能改變其他processes中之一個process的waiting值變False，在CS中的Process只有一個，出來CS後也只改變一個Process之waiting值為False，因此唯一性也確立。換言之，一個process不會自己把自己的waitiing值設成False，一定都是別的process來設的，因此唯一性確立==

因此由case1及2得知，互斥成立

[2] Progress：OK

pf：==若Pi不想進入C.S，其waiting[i]為False，而且Pi不會跟其他Process競爭Test-and-Set(Lock)的執行，且從CS離開之Process，也不會改變Pi之waiting值，因此Pi不會參與進行CS之決策。==

若n個Process都想進入CS，則在有限的時間內必定會決定出第一個搶到Tetst-and-Set()執行，並進入CS。它從CS離開後，也會在有限的時間內讓下一個想進入CS之Process進入CS或Lock設False。

==不會有Deadlock==

[3]Bounded Waiting：OK

pf：假設P₀~P_n-1等n個Processes皆想進入C.S表示waiting[0]~[n-1]皆為True

令Pi是第一個搶到Test-and-Set執行之Process，率先進入CS當Pi離開CS後，會將P_(n+1)%n之waiting值改為False，讓P_(n+1)%n進入cs，依此類推，Process會依P_i,P_(i+1)%n,P_(i+2)%n…P_(i-1)%nFIFO 順序依據進入CS，故不會有Starvation

SWAP(a,b)指令

• 定義：此CPU指令是將a,b兩值互換，且CPU保證它是==Atomically executed==

若以C語言描述，功能如下：

1
2
3
4
5

void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

• 用在C.S design上

[algo1]：Ｘ

共享變數如下

Lock：boolean=False;

區域變數如下：

key：boolean

1
2
3
4
5
6
7
8
9

repeat;
	key=True;
	{repeat;
		swap(Lock,key);
    utill(key==False)} ; //成立才離開 
    C.S
    Lock=False;
    R.S
until False;

分析：

[Algo1]同Test-and-Set

Mutual Exclustion= ok

progress= ok

Bounded waiting= No，只有設成Fales而已，還是無法避免無限等待

[Algo2] 正確的

將Test-and-set的[algo2]中

1
2
3
4
5
6
7
8

...
while(...){
  // key=test-and-set(Lock);
  swap(Lock,key); //改成這樣即可

}
...

綜合練習

在Test-and-set[Algo2]中

1
2
3
4
5

while(waiting[i] and key){
	key = Test-and-Set(Lock);
}
waiting[i] = False; //Pi不用等了，可進入CS
CS

若把waiting[i] = False; 這行刪掉，此行removed是否正確?explain in details

Ans.

違反Progress，不想進入的progress參與決策，並且會發生死結，兩件事情都會發生

Semaphore(號誌)

製作Semaphore的目的就是為了確保 ，號誌的值不會Race Condition

學習地圖

定義

應用

CS Design (臨界區間設計)

synchronization problem solution(解決同步問題)

種類

Binary semaphore vs counting semaphore

spinlock semaphore vs non-busy waiting semaphore

• 定義：令Ｓ為Semaphore type變數，架構在integer type針對S，提供兩個Atomica operations

  1. wait(S)或P(S) 因為是荷蘭人，所以用荷蘭命名
  2. signal(S)或V(S) 因為是荷蘭人，所以用荷蘭命名

  定義如下

wait(S)：

==若S為0則卡住，若S不為0則通過==

1
2
3

while(S≦０){do no-op;} //若semaphore的值為0，則卡在這邊

S=S-1; //退出後semaphore值-1

signal(S)：

1

S=S+1;

note：因為Atomical, 所以S不會有race condition

• 應用：主要用在CS Design，及同步問題之解決

CS Design使用如下

1. 共享變數宣告如下

   mutex常見的變數名稱，代表mutual exclustion的意思：semaphore= 1; //初值為1

2. Pi程式如下：

   1 2 3 4 5 6

   repeat : wait(mutex); C.S signal(mutex); RS untill False;

   Pi	Pj
   T1：wait(mutex); 因為mutex = 1 所以Pi可以離開while，then,mutex值在減1變0，then Pi進入CS	T2：wait(mutex)，因為此時mutex=0，這時候Pj會卡住。符合Mutual exclustion Progress也符合 Bounded waiting也符合

解決簡單的Synchronization problem

​ 何謂Synchronization? Process因為某些事件發生(or未發生)而被迫等待，無法往下執行，直到其他Processes do something才得以往下

範例1：

規定：A必須在B之前執行，試用Semaphore達到此需求

Ans. 宣告一共享變數

S= Semaphore=0;

==Note：semaphore的初值是具有某些意義的，並且初值不一定要是０或１，其實都可以，只是都用０跟１做舉例==

• 初值為1：用作互斥控制
• 初值為0：用作強迫等待

例2：

S1：Semaphore= 0;

S2：Semaphore= 0;

規定執行順序為A -> C -> B 該如何完成?

Ans：

Ex2：希望達成 A,B,C,A,B,C,A,B,C repeatly execuction

承上性質，S1,S2 semaphore=0;S3 semaphore=1

Ex3：C是共享變數，初值為3，請寫出最後C的值為多少

• 第一小題

7或8或4或6

• 第二小題

s= semaphore=1

7或8

• 第三小題

s= semaphore = 0

7

EX4

S1：Semaphore = 1;

S2：Semaphore = 0;

求ABC可能執行順序

Ans：把不可能的刪除就好

ABC,

ACB,

BAC,

BCA,

CAB,

CBA

semaphore之誤用所造成之問題

違反互斥、形成死結

例1

s= Semaphore=1

—> 違反mutual exclusion

例2

s= semaphore = 2

—> 形成死結

例3

S1,S2 = Semaphore = 1;

可能形成deadlock，如果Pi，Pj依照T1~T4之順序交錯執行

著名的Synchronization Problem之解決

想看看何時會停下來

Producer-Consumer Problem(生產者消費者問題)

Producer：此process專門產生資訊供別人使用

Consumer：此process專門消耗別人產生的成果

在sharrd memory溝通方式底下，會準備一個buffer

細分為兩個類型的問題

1. Bounded Buffer Producer-Consumer(Buffer有限)

   有兩個情況會被迫等待

   1. 當Buffer滿了，Producer被迫等待
   2. 當Buffer空了，Consumer被迫等待

2. Unbounded Buffer Producer-Consumer(Buffer無限)

algo1

共享變數宣告如下

1. Buffer: [0..n-1] of items;

2. in,out: int = 0;

Producer 程式：

1
2
3
4
5
6

repeat:
	produce an item in nextp;
	while((in+1)%n==out) {do noting}; //當buffer滿的話，就卡在while中
	Buffer[in] =nextp;
	in = (in+1)%n;
until false;

Consumer程式：

1
2
3
4
5
6
7

repeat
	while(in == out ){ do nothing} //buffer為空
	nextc= Buffer[out];
	out=(out+1) % n;
	...
	consumes  the item in nextc;
until false;

此時producer 無法在加item，因為(in+1)%n == out, 即buffer已經滿了，因此最多利用(n-1)格

algo2

共享變數宣告如下

1. Buffer: [0..n-1] of items;

2. in,out: int = 0;

3. ==count:int =0==

這個count值有可能導致race condition，因此不完全正確

Producer 程式：

1
2
3
4
5
6
7

repeat:
	produce an item in nextp;
	while(count==n) {do noting}; //當buffer滿的話，就卡在while中
	Buffer[in] =nextp;
	in = (in+1)%n;
	count = count +1;
until false;

Consumer程式：

1
2
3
4
5
6
7
8

repeat
	while(count ==0 ){ do nothing} //buffer為空
	nextc= Buffer[out];
	out=(out+1) % n;
	count = count -1;
	...
	consumes  the item in nextc;
until false;

用semaphore解producer-consumer problem

共享變數宣告如下：

1. empty : semaphore = n . 代表buffer內空格數，若空格數變為0，代表滿了
2. full : semaphore=0. 代表buffer區中，填入item之格數，若為0，表buffer為空
3. mutex：semaphore=1; 對buffer, in , out , count做互斥控制，防止race condition

semaphore的設計哲學

1. 滿足同步條件之號誌變數empty, full
2. 互斥控制防止race condition之號誌 mutex
3. 先測同步在測互斥，不然會造成死結
4. ==共享變數取存之前都需要經過互斥的處理==

producer

1
2
3
4
5
6
7

repeat
	produce on item in nextp;
	wait(empty) ; //若無空格則P被迫等待
	wait(mutex); 
	add nextp into Bufffer;  //濃縮很多程式在這行裡面喔
	signal(mutex);
	signal(full); //填入item之格數加1，maybe拯救Consumer

consumer

1
2
3
4
5
6

repeat
	wait(full);
	wait(mutex);
	remove item from Buffer in nextc
	signal(mutex);
	singal(empty)

Read/write Problem

基本的同步條件

1. Reader write要互斥
2. writer,writer也要互斥

此外，這問題再細分成兩類

1. First read/writer problem

   -> 對Reader有利，對writer不利，因此writer可能starvation

2. Second read/writer problem

   -> 對writer有利，對reader不利，因此reader可能startvation

First Reader/Writer Problem

何謂「對Reader有利，Writer不利」?

只要有源源不絕的Reader，則W1可能Starvation

共享變數宣告如下：

1. wrt：semaphore =1

   提供R/W 及 W/W互斥控制，並兼差對Writer不利的控制

2. readcnt：int = 0;

   統計Reader個數，直到沒有Reader，才可以放writer進去

   Reader到->Readcnt +1

   Reader走 ->Readcnt -1

3. mutex：semaphore=1

   由於readcnt是一共享變數，會有Race Condition之問題，故需額外宣告一變數Mutex做互斥控制

程式：

練習：

若目前W1已在寫入中

1. R1到，則R1會卡在wrt 裡，此時readcnt=1
2. R2又到，則R2會卡在mutex，此時readcnt=1
3. R3到，則R3會卡在mutex，此時readcnt=1

Second Reader/ writer problem

何謂對Writer 有利，對Reader不利

T6：w1離開，優先放W2近來(並非R1)

T7：w2離開，優先放W2近來(並非R1)

…(以此類推)

只要Writer離開，發現尚有waiting writer在，那就會優先放writer近來，所以R1有可能Startvation

共享變數之宣告

1. readcnt：int=0 ：統計reader個數

2. wrtcnd：int=0：統計writer個數

3. x：semaphore：１　//用來對readcnt做互斥控制，防止race condition

4. y：semaphore：１ //用來對wrtcnd做互斥控制，防止race condition

5. z：semaphore：１　//有的版本會有，有的版本不會有。作為對reader之入口控制(讓它卡多一些關卡，讓reader slower)

6. rsem：semaphore=1　//作為對reader不利之控制

7. wsem：semephore=1 //提供R/W及W/W互斥控制

程式：

The Sleeping Barbers Problem

描述：有一個barber，一張BarberChair，n張waitingChair。並且有客人。

客人的行為如下

waiting chairs 坐滿(n個等待客人)：不入店

waiting chairs 尚未坐滿：入店內，坐在waitingChair，通知(喚醒)barber

客人睡覺(wait) if barber is busy now… 直到Barber叫他起床剪髮，剪完髮Exit

理髮師的行為如下

睡覺 if no 客人

直到有客人喚醒(通知)他

叫醒客人剪髮

剪完髮後如果還有客人，則叫醒客人剪髮

剪完髮後如果沒有客人，則繼續睡，繼續水時間

共享變數宣告： ==共享變數取存之前都需要經過互斥的處理==

1. Customer：semaphore=0 ：用來卡住理髮師 if no 客人
2. Barber：semaphore=0：用來卡住客人的 if Barber is busy
3. waiting：int=0 // 坐在等待椅上的客人數目。何時+1?何時-1?客人入店，坐上椅子。Barber叫客人起來剪髮，會有race condition的問題
4. mutex：semaphore=1 //防止waiting值race condition

程式：

The Dining-Philosophers Problems

描述

注意：1. 吃中餐：奇數、偶數哲學家皆可

2. 吃西餐：偶數位才可以（刀叉一副

共享變數之宣告

chopstick：[0,1,2,3,4] of semaphore；初值皆為1，對5根筷子做互斥控制。

i號哲學家(i=0~4)哲學家Pi之狀況(這程式是有問題的)

1
2
3
4
5
6
7
8

repeat...
hugry now;
wait(chopstick[i]);
wait(chopstick[(i+1)%5])
eating now;
signal(chopstick[i]);
signal(chopstick[(i+1)%5]);
think now;

此Solution有問題，可能會形成Deadlock!!

若每位哲學家都拿起自己左邊的筷子，則每位哲學家都卡住，皆無法取得右筷，形成circular waiting

解法一

一次最多讓4位哲學家上桌

m=5根,Maxi=2

1. 1≦Maxi≦m成立

2. $$ \sum_{i=1}^nMaxi < n+m,因此2n<n+5, n<5。最多4位 $$

保證DeadLock Free-> 可額外加入另一個號誌 No:semaphore=4，做入口控制

1
2
3
4
5
6
7
8
9

repeat...
wait(No);
hugry now;
wait(chopstick[i]);
wait(chopstick[(i+1)%5])
eating now;
signal(chopstick[i]);
signal(chopstick[(i+1)%5]);
think now;

解法二

除非哲學家可同時取得左右兩邊筷子，才准許持有筷子，否則不得持有任何筷子。否則不得持有任何筷子

破除Hold&wait 條件

解法三

相鄰哲學家之取筷順序不同，創造Asymmetric mode，例如：

破除Circular waiting條件

Note：等同於西餐，大家規定：先取刀再取叉

cigarette smokers problem

很少考，從50年前就沒考過了。Pass

Semaphore之種類

分類一：號誌值域做區分

Binary(二元) Semaphore Vs Counting(計數) semaphore

1. Binary Semaphore

定義：Semaphore之值只有0,與1兩種(C.S Design正常使用下)不可為負值，無法統計有多少個Process卡在wait中

S：Binary-Semaphore=1;

1
2
3
4

Wait(S)：
    While)(S≦0)
   {do no-op}
    S=S-1

1
2
3

Signal(S){
    S=S+1;
}

2. Counting Semaphore

定義：Semaphore值不限於0,1 可以為負值，且若值為-N，可知道(統計出)有N個processes卡在wait中

範例1.

請用Binary Semaphore定義出Counting Semaphore。

共享變數宣告如下

1. C：int //代表 Counting Semaphore號誌值
2. S1：Binary-Semaphore=1 對C作互斥控制，防止C值race Condition
3. S2：Binary-Semaphore=0 ，當C值<0，強迫Process暫停之用

程式：

1
2
3
4
5
6
7
8

wait(C)：
    wait(S1);
	C=C-1;
	if(c<0) then {
        signal(S1);
        wait(S2); //process自己卡住
    }else
        signal(S1)

1
2
3
4
5

Signal(C)：
    wait(S1);
	C=C+1;
	if(c≦0) then Singal(S2);  //救process
	signal(s1)

Demo如下

1
2
3
4
5

C：Counting semaphore= 1
wait(C);
C.S // 臨界區間
Singal(C)
R.S

分類二：是否採用Busy-waiting(Spinlock)技巧來定義Semaphore

Spinlock Vs Non-Busy-waiting Semaphore

Spinlock

定義：令Ｓ為Semaphore變數，而

• wait(S)：

  定義：

  1 2	while(S≦0){do no-op} //採用Busy-waiting Skill S=S-1

• Signal(S)：

  定義：

  1

  Ｓ=S+1;

優缺點：參閱前述Busy-waiting內容

Non-Busy waiting semaphore

定義：Semaphore type定義如下

1
2
3
4

Struct semaphore{
    int value; //號誌值
    Queue Q ; // FIFO Queue
}

令S為Semaphore變數，則

1
2
3
4
5
6

Wait(S)：
    S.value = S.value-1;
	if(S.value <0 ) then{
        add process P into S.Q;
        Block(P); // P之狀態改為block state
    }

1
2
3
4
5
6

Signal(S)：
    S.value = S.value+1;
	if(S.value ≦０)then{
        remove a process form S.Q
         wakeup(P) //將P改為ready state
    }

Note：此號誌也是一個Counting Semaphore

製作Semaphore

using

1. Disable interrupt
2. Software solution or Hardware instructions support

何謂製作Semaphore?

即是如何保證Semaphore值不會Race Condition(or 如何確保wait與singal是Atomic operation?)

製作Semaphore的目的就是為了確保 ，號誌的值不會Race Condition

Algo1

1
2
3
4
5
6
7
8
9

wait(s)：
    Disable interrupt;
	S.value =  S.value -1;
	if(S.value<0) then{
       	Enable Interrupt(); //在這邊打開中斷，而不是在if之外，避免Block(p)之後，因為Disable Interrupt而無法釋放CPU
        add process P into S.Q;
        block(p);
    }

Algo2

將[Algo1]中的Disable Interrupt 換成 Enter Section，Enable Interrupt改成Exit Section。

Enter Section與Exit Section之控制碼找個地方寫出來。取決於題目教你用Software Solution(Bakery’Algo) or Hardware Instrution(Test-and-set or Swap的Algo[2]或Algo[1]時間不夠就寫這個，但這好像不符合什麼Bound wait還是什麼鬼的)

Algo3

1
2
3
4
5
6

wait(s)：while(S≦０){
    Enable Interrupt;
    no-op;
    Disble Interrupt
}
	S=S-1

1

Signal(S)：S=S+1 

Algo4

將[Algo3]中的Disable Interrupt 換成 Enter Section，Enable Interrupt改成Exit Section。

Enter Section與Exit Section之控制碼找個地方寫出來。取決於題目教你用Software Solution(Bakery’Algo) or Hardware Instrution(Test-and-set or Swap的Algo[2]或Algo[1]時間不夠就寫這個，但這好像不符合什麼Bound wait還是什麼鬼的)

Busy-waiting是否可以完全避免之(avoid altogether)

Ans. No, 無法完全避免，以Semaphore為例

Monitor

定義、組成

特性(優點)

Condition 變數使用

解同步問題

Conditional Monitor

種類(3種)

用semaphore Monitor

定義：Ｍonitor是一個用來解決同步問題的高階結構class，是一種ADT(abstract data type)，Monitor之定義，主要有3個

組成：

1. 共享變數宣告區
2. 一組local function(or procedures)
3. Initialization area(初始區)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public Class MonitorName{
    //共享變數宣告
    
   procedure entry function1(參數){
       begin
           Body;
       end 
	}
    procedure entry functionX(參數){
        begin;
        Body;
        end;
    }
    
    begin;
    初始區
    end;
    
   
}

特性(優點)：

Monitor本身已保證互斥(Mutual excluesive)即任何時間點最多只允許，1個Process在Monitor內活動(Active)，也就是說：在任何時間點，最多只允許一個1個Process呼叫(calling)monitor的某個function(或procedure)執行中，不可以有多個processes同時呼叫monitor的functions

此一互斥性質帶來何種好處？

因為共享變數區之共享變數只能被monitor的local function直接存取，外界不能直接存取，外界(process)只能透過呼叫Monitor的Local Function來存取共享變數，而Monitor保障互斥，因此保障了共享變數不會發生Race Condition，所以Programmer毋須煩惱Race Condition problem (不用撰寫額外的Code，或是使用Mutex semaphore)，只需專心處理同步問題即可。此點優於Semaphore

Question：Semaphore 比 Monitor容易使用 when solving synchronization problem

Ans：False，參照如上。並且semaphore一多，容易產生Deadloc

Condition Type

定義：Condition 型別是用Monitor中，提供給Programmer解決同步問題之用，令x是Condition Type變數，在X上提供兩個operations：

x.wait 及 x.signal

1. x.wait：執行此運作的process會被Blocked且置入Monitor內x所屬的waiting queue中(預設是FIFO)
2. x.signal：如果先前有Processes卡在x的waiting queue中，則此運作會自此waiting queue中移走一個process且恢復(resume)其執行，否則無任何作用

使用Monitor解決 The dining-philosophers Problem

先定義所需的Monitor ADT Type

Dining-philosophers = Monitor

Var

1. State[0..4] of {thinking, hungry, eating}
2. self[0..4] of condition;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

procedure entry pickup(i : 0...4){ //拿起筷子
    begin:
    	state[i] = hungry;
    	test(i);
    	if(state[i]≠eating) then self[i].wait; // Pi自己卡住
}

procedure test(k:0...4){ //測試
    begin:
    	if(state[(k+4)%5]≠eating and state[k]==hungry and state[(k+1)%5]≠eating)
            then{
            state[k]= eating;
            self[k].signal
        }
}

procedure entry putdown(i: 0..4){ // 吃飽了放下筷子
    begin
        state[i]= thinking;
    	test((i+4)%5);
        test((i+1)%5);
    end
    begin
        for(i=0;i ≦4 ; i++){
            state[i]= thinking;
        }
    end
}