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

Operating System - CH4 Threads

Process creation is heavy-weight

Thread creation is light-weight

multi-thread優點

• responsiveness
• resource sharing
• economy
• scalability 同一個process內的不同thread可以平行在不同CPUs上執行

multicore programming challenge

• divide activities
• balance
• data splitting
• data dependency
• test and debugging

User Threads

Kernel Threads: kernel 知道每條thread

Operating System - CH3 Process

Process: a program in execution

• program counter 
• stack : temporary data
• data section: global var
• heap: containing memory allocated dynamicalling during run time

Process Control Block(PCB): kernel 為管理眾多processes, 會在kernel memory area中，針對每個process各自建立PCB, 紀錄process之related info.

Process Scheduling: 最大化CPU的使用，quickly switch process onto CPU from time sharing

• job queue: all processes in system
• ready queue: process in main memory, ready to execute
• device queue: process waiting for an I/O devices

Process scheduler

• long-term: 從 job queue 挑出進入ready queue
  • control the degree of multiprogramming
• short-term: 從 ready queue挑出 準備進入ＣＰＵ執行
• medium term： 適合time-sharing, 可以調解CPU-bound and I/O-bound( spending more time doing I/O than computations, many short CPU bursts)

• 當記憶體空間不足時，此時又有較高priority的process需要記憶體，scheduler就會將某些process swap out，等記憶體空間足夠時，才將之swap in 到ready queue

Operating System - CH2 Operating-System Structures

Command line interface or Command Interpreter allow direct command entry

System calls: programming interface to the services provide by the OS. 作為user processes與kernel之間的溝通介面，當執行中的user process需要OS提供的服務時，先發Trap通知OS, 並告訴OS要執行的服務項目, OS才執行一系列相關之system calls，完成該服務請求，並傳回結果給user process。

shells: 提供存取kernel的程式

OS design and implementation: 

• user goals: convenient to use, learn, safe, fast
• system goals: easy to design, implement and maintain

• mechanism: how to do it
• policy: what will be done?

Layered approach

• 上層可以使用下層的服務，但下層不能使用上層
• 上層為interface，下層為hardware
• 優點: 模組化，可以分工加速系統開發，易測試與維護
• 缺點: 難以界定層次的劃分

Microkernel system structure

• 將OS kernel眾多模組中移除一些較非必要的模組，改成在user mode下 以system library(software)或user program來執行
• use message passing
• 優點
  • 容易extend
  • 移植到另一平台會更方便
  • more reliable(安全性提升)

Virtual Machines

• OS 利用software技術, 創造出一份與底層硬體一模一樣的功能介面，此一abstract machine，稱為VM。
• 很難去implement，must provide 底層硬體的複製，typically runs in user mode

core dump: application error log file

crash dump: os error log file

Operating System - CH1 Introduction

User View of OS

• mainframe view: 最大化resource utilization
• workstation or server view: individual usability and resource utilization 的取捨
• PC view: ease of use, performance
• handheld: individual usability and performance per amount of battery

bootstrap program: 一開機時會載入的

• 存在 ROM、EEPROM 就是 firmware
• load OS kernel and starts execution

Interrupt

• hardware: sending a signal to CPU
• software: system call
• functions:
  • (1) Trap, Exception: from software ex: devided by zero, illegal memory access
  • (2) interrupt: from hardware  ex: I/O complete
• OS會查詢 interrupt vector 確認何種中斷發生，並找出對應interrupt service routine的address

Multiprocessor systems

• parallel system、 tightly-coupled system
• 多顆CPU存在於同一部機器，所有cpu共享memory, I/O devices, bus etc.
• 優點： 
  • increase throughput
  • economy of scale
  • increase reliability- graceful degradation(無視硬體的錯誤，而持續運作的能力，稱適度的降級) or fault tolerance
• two types
  • asymmetric: 有主從架構，有一個master CPU, 其餘為 slave CPU, 效能較差(Master 是瓶頸)，reliability較差。
  • symmetric: load balance，有一個break, 其他可以馬上補上。

Clustered systems: like multiprocessor, 但他是集結許多CPU來完成工作

• high-availability
• asymmetric: one machine in standby mode, 監督工作用。 
• symmetric: multiple nodes run app and monitoring each other。