---
tags: 作業系統
---

# 作業系統 (期末)

## Ch 5 Scheduling

- Scheduling type
- FCFS: convey effect
- SJF (Shortest-Job-First): nonpreemptive, type of priority(time)
- SRTF (Shortest-remaining-time-first): SJF && preemptive
- RR (Round Robin):preemptive, better response (time quantum > context switch time)
- Priority

- Scheduling Criteria
- cpu throughput
- cpu utilization
- waiting time
- turnaround time
- response time

- Multi-Level ( Single CPU )
- multi-level queue: process cann’t move between queues
- multi-level feedback queue: can move between queues

- Multiple-Processor ( Multi-core )
- processor affinity

- 補充名詞
- hardware real time: must complete before deadline
- software real-time system: priority high, not sure complete before deadline
- interrupt latency: interrupt service routine
- dispatch latency: stop one and swap another one to run(includ context switch)
- interrupt -> dispatch -> context switch

---

### Ch 6 Synchronization

- solution of critical section
- progress
- if a don't want to entry, a can't effect determine
- no deadlock, choose one entry in limit time
- mutual excludsive
- bounded waiting (no starvation)

- type of solution
- Hardware: atomic instruction (only in kernal mode)
- test_and_set
- compare_and_swap
- Mutex Locks(spinLock)
- os provide software solution
- acquire(lock), release(unlock)
- busy waiting
- mutex init = 1(no one, can entry)
- as binary semaphore
- Semaphore
- waiting queue to avoid busying waiting
- wait() -> signal()
- semaphore < 0 => can’t entry critical section
- Monitor
- high-level abstraction data type
- x.wait(), suspend util x.signal()

- 補充名詞
- race condition: result depend on excute order
- critial section (enter , exit)
- memory transaction: a sequence of read-write operation that are atomic

wait() {
    while(s<=0);
    s--;
}

signal() {
    s++;
}

i want to entry

do {
    flag [i] = true
    turn = j
    while(turn == j && flag[j] == true);
    (critical section)
    flag[i] = false
    (remainder section)
} while(true)

---

### Ch 8 deadlock

- deadlock condition
- circular wait
- hold and wait
- no preemptive
- mutual exclusive

- solution of deadlock
- deadlock prevention
- deadlock avodience(priori , safe / unsafe state)
- deadlock detection and recovey
- ignore

- deadlock detection: How to recovery from deadlock
- process termination (abort all or chosen one)
- resource preemption
- select victim
- rollback: return to safe state

---

### Ch 9 Main Memory

- addresss type
- source code (symbolic)
- compile (relocation)
- linker / loader (absolut)

- binding time
- compile ( priori: absoult code )
- load
- execute ( binding delay )
- hardware support (Base and Limit registers)
a. logical address
b. hardware protection

- address type
- logical (virtual) address: generate by CPU
- physical address: memory unit use

- Memory management unit (MMU)
- hardware
- map logical -> physical address
- base register (relocation register、4)

- contiguous allocation
- two partition
- kernal process(resident OS): low memory, interrupt vector
- user process: high memory

- multiple partition allocation
- OS record some information
- a. allocated partition
- b. free partition(hole)

- dynamic allocation ways
- first fit
- best fit
- worst fit(largest)

- swap
- backing store, DMA to memory image
- problem | can't swap out process which use I/O
- solution | transfer I/O to kernel space (double buffering)

- Fragmentation
- internal fragmentation　(solution: segmentation)
- external fragmentation　(solution: compact)

- Segmentation
- user view of memory
- segment table
- segment number < STLR(limit register)
- logic address < segment number, offset>
- protection: validation bit、privilege

- Page
- page(logical), frame(physical)
- each process , each page table
- logic address < page number, offset>
- translate lookaside buffer (TLB): solve two memory access problem

- structure of page table
- hierarchical page table
- 32 bit (12, 10, 10 => outer, inner page number, offset)
- two-level (forward-mapped)=> outer、inner
- hashed page table
- \>32 bit
- inverted page table
- track physical memory
- each frame, have one entry in page table
- < PID, page number >

- 名詞解釋
- dynamic relocation: don't need special support from OS
- dynamic linking (shared lib): stub, excute time, os version
- reentrant: share code, interprocess communication
- execution time binding : binding instruction and data perform by most general OS
- protection bit (R, WR)
- absolute code can be generate for compile time binding

---

### 計算
- page size -> page offset (bits)