---
# System prepended metadata

title: 作業系統 (期末)
tags: [作業系統]

---

---
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


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

signal() {
    s++;
}
```

i want to entry
```javascript=
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)