Operating System - CH7 Deadlocks

deadlock example

sempohere A and B =1,

  P0              P1

wait(A)     wait(B)

wait(B)     wait(A)

7.1 System Model

每一種看都有一定的instances，像是可能有五個disk，不止一個的I/O devices，

每一個 process 要利用資源都有以下三種階段

1. 要求資源 request
2. 使用資源 use
3. 釋放資源 release

7.2 Deadlock Character

要死結必須要滿足以下四個條件，缺一不可

1. Mutual exclusion: 一個資源一次只能被一個process所使用
2. Hold and Wait: process取得一個資源之後等待其他的資源
3. No preemption: 資源只能由process自己釋放，不能由其他方式釋放
4. Circular wait: 每個process都握有另一個process請求的資源，導致每一個process都在等待另一個process釋放資源

Resource-Allocation Graph

• 沒有 cycle -> 沒有deadlock
• 如果有cycle
  • 每個resource裡 只有一個instance的話，則有cycle -> 有 deadlock
  • 每個resource裡 有好幾個instance的話 -> 可能有deadlock

Graph with a cycle but no deadlock

• 可以把p4佔據的資源free掉，但p4可能starvation

Method for Handling Deadlocks

1. ensure never enter deadlock
2. allow enter deadlock, but can recovery
3. ignore

Operating System - CH6 Process Synchronization

Race condition

一組Processes 在Shared Memory溝通方式下，若未對共享變數提供互斥存取等同歩機制，

則會造成 “共享變數之最終結果値，會因 Processes之間執行順序不同而有所不同 ”，導致不可預期之錯誤發生。

Consider this execution interleaving with “count = 5” initially:

S0: producer execute register1 = counter{register1 = 5}

S1: producer execute register1 = register1 + 1 {register1 = 6}

S2: consumer execute register2 = counter {register2 = 5}

S3: consumer execute register2 = register2 -1 {register2 = 4}

S4: producer execute counter = register1{count = 6 }

S5: consumer execute counter = register2 {count = 4}

解決方式:

1. disable interrupt
2. Critical Section design

Each process must ask permission to enter critical section in entry section, ...

Solution to critical-section problem

1. Mutual Exclusion
   Def：
   最多只允許一個process在其Critical Section內活動，若其它processes也想進入它們本身的Critical Section，則必須等待值到該process離開Critical Section才能再擇一進入(即不允許多個processes在各自Critical Section內同時活動)
2. Progress
   Def：
   1. 不想進入Critical Section的process(即在Remainder Section內活動)，不能妨礙(阻止)其它process進入Critical Section
      (不能參與進入Critical Section的決策過程)
   2. 決定哪個process可以進入Critical Section的時間是有限的(不能無窮止境)⇒No DeadLock
   3. 設計 entry section(入口) exit section (出口)
3. Bounded Waiting
   Def：
   自process提出欲進入Critical Section的請求到其獲准進入Critical Section的等待時間是有限的(⇒No starvation)
   若有n個processes欲進入Critical Section，則任一process至多等待(n-1)以後必可進入Critical Section

Operating Systems - CH5 CPU Schedling

CPU-I/O Burst Cycle

process execution包含 CPU execution 和 I/O wait

CPU Scheduler = short-term scheduler

• 從ready queue 裡 挑出process給CPU執行
• CPU Sceduling decision 發生當
  • 從running 到 wait
  • terminated
  • 從 wait 到 ready (preemptive)
  • 從running 到 ready (preemptive)

Dispatcher

• 將CPU的控制權授予經由short-term scheduler選擇的process
• 會做以下工作
  • context switching
  • 從 monitor mode 跳到 user mode
  • 跳到 user program 裡的執行位置 來restart program
• dispatch latency
  • 上述三項工作總和，即停止process並開始另一process的時間

Scheduling algorothm optimization Criteria

• max CPU utiliztion
• max throughput: 讓整體可以服務的process越多越好
• min turnaround time: 執行process時間越短越好
• min waiting time
• min response time