OS Final One-Page Note

10–20장 시험범위 요약

  • Haram Lee
  • 2026-06-22
  • studies / 26-1 / operating-systems

시험범위: 10–15, 17–20 / 16 SSD 제외

전체 흐름

text 
10: physical memory 부족 → disk를 backing store로 사용
11~14: thread 동시 실행 → shared data 문제 → lock/semaphore/CV → concurrency bug
15: persistent storage 접근 → I/O device, HDD, disk scheduling
17~20: file system abstraction → implementation → performance(FFS) → consistency

10. Virtual Memory Swapping

  • 핵심: physical memory를 disk의 cache처럼 본다.

  • process 전체 address space를 memory에 둘 필요 없이, 현재 필요한 page만 memory에 둔다.

  • page fault: 접근한 page가 memory에 없을 때 발생.

  • swap space: memory에서 쫓겨난 page를 저장하는 disk 영역.

  • page replacement: memory가 부족할 때 어떤 page를 evict할지 결정.

  • when to swap

    • lazy: memory가 꽉 찬 뒤 evict, 비현실적.
    • proactive: LW/HW watermark, free page가 LW 아래면 swap daemon이 page를 evict.

  • policy

    • OPT: 미래에 가장 늦게 쓰일 page evict. 최적이지만 구현 불가.
    • FIFO: 가장 오래 memory에 있던 page evict. 단순하지만 Belady’s anomaly.
    • LRU: 가장 오래 사용 안 된 page evict. locality 활용, 구현 비용 큼.
    • RANDOM: random evict. 단순하고 특정 workload에서 괜찮음.
    • Clock: LRU approximation. reference bit 보고 second chance.

  • dirty page는 disk에 write-back 필요, clean page는 그냥 drop 가능.

  • thrashing: working set 총합이 physical memory보다 커서 대부분 시간을 paging에 쓰는 상태.

11. Threads

  • process = resource container

    • address space, PID, open files, current directory.

  • thread = execution stream

    • PC, SP, registers, stack.

  • 같은 process 안 thread들은 code/data/heap 공유, stack은 각자 가짐.

  • Threads are the unit of scheduling.

  • 장점:

    • process보다 생성/전환이 싸다.
    • I/O와 computation overlap.
    • responsiveness 향상.
    • multi-core 활용.

  • 단점:

    • address space 공유로 protection 없음.
    • shared data 때문에 race condition 가능.

  • threading model

    • 1:1: user thread 1개 ↔ kernel thread 1개. 현대 OS에서 흔함.
    • N:1: user thread 여러 개 ↔ kernel thread 1개. 빠르지만 하나 block되면 전체 block.
    • M:N: user thread 여러 개 ↔ kernel thread 여러 개. 유연하지만 복잡.

12. Locks

  • race condition: 여러 thread가 shared resource에 동시에 접근하고, 하나 이상이 write.

  • critical section: shared data를 접근/수정하는 코드 구간.

  • lock은 critical section에 한 번에 하나의 thread만 들어가게 함.

  • acquire() / release()

    • acquire: lock free 될 때까지 기다렸다가 잡음.
    • release: lock 풀고 waiter 깨움.

  • pthread_mutex_lock(&L->lock);

    • 잡는 대상은 L->lock이라는 mutex 변수.
    • 보호 대상은 보통 L->head 같은 shared data.

  • spinlock: lock 얻을 때까지 busy-wait.

  • mutex: 못 얻으면 block/sleep.

  • lock 구현:

    • single core: interrupt disable 가능.
    • multi-core: atomic instruction 필요.

  • atomic primitive:

    • test-and-set
    • compare-and-swap
    • fetch-and-add
    • ticket lock

  • lock 요구사항:

    • mutual exclusion
    • deadlock-free / progress
    • starvation-free / bounded waiting
    • fairness
    • performance

13. Semaphores & Condition Variables

  • Semaphore: integer value를 가진 synchronization object.

  • wait(S):

    • value 감소.
    • resource 없으면 block.

  • signal(S):

    • value 증가.
    • waiter 하나 wakeup.

  • binary semaphore

    • value = 1.
    • mutex처럼 mutual exclusion에 사용 가능.

  • counting semaphore

    • value = N.
    • resource 여러 개를 표현.

Bounded Buffer

text 
mutex = 1   // buffer, in, out 보호
empty = N   // 빈 slot 개수
full = 0    // 찬 slot 개수

producer:

c 
wait(&empty);
wait(&mutex);
/* insert item */
signal(&mutex);
signal(&full);

consumer:

c 
wait(&full);
wait(&mutex);
/* remove item */
signal(&mutex);
signal(&empty);

Condition Variable

  • 특정 condition이 만족될 때까지 기다리는 queue.

  • 반드시 mutex와 함께 사용.

  • wait(cv, mutex)

    • mutex 잡은 상태에서 호출.
    • thread sleep + mutex release를 atomic하게 수행.
    • 깨어나면 mutex를 다시 잡고 return.

  • signal(cv): waiter 하나 깨움.

  • broadcast(cv): waiter 모두 깨움.

  • CV는 semaphore와 달리 history 없음. 기다리는 thread가 없으면 signal은 사라짐.

  • Mesa semantics에서는 반드시 while 사용.

c 
pthread_mutex_lock(&m);
while (condition == false)
    pthread_cond_wait(&c, &m);
pthread_mutex_unlock(&m);

14. Concurrency Bugs

  • Atomicity bug

    • atomic해야 하는 sequence가 중간에 끊겨서 생김.
    • 해결: lock으로 check/use 또는 read/write를 감싼다.

  • Ordering bug

    • A가 먼저 일어나야 B가 안전한데 순서 보장 안 됨.
    • 해결: condition variable로 event ordering 보장.

  • Deadlock

    • 서로 resource를 잡고 상대 resource를 기다림.

  • deadlock 4 conditions:

    1. mutual exclusion
    2. hold and wait
    3. no preemption
    4. circular wait

  • prevention:

    • mutual exclusion 제거: lock-free, CAS.
    • hold-and-wait 제거: 모든 lock을 한 번에 잡기.
    • no preemption 제거: trylock 실패 시 가진 lock release.
    • circular wait 제거: global lock ordering.

15. I/O Devices & HDD

  • I/O device 구성:

    • status register
    • command register
    • data register
    • controller
    • local buffer

  • 제어 방식:

    • port-mapped I/O: in, out
    • memory-mapped I/O: load/store

  • data transfer:

    • PIO: CPU가 직접 data 이동. CPU 낭비.
    • DMA: device controller가 memory에 직접 transfer. 완료 시 interrupt.

  • completion 확인:

    • polling: CPU가 계속 status 확인.
    • interrupt: device가 CPU에게 완료 알림.

  • device 종류:

    • block device: disk, fixed-size block, random access 가능.
    • character device: keyboard, mouse, stream, seek 없음.

  • HDD access time:

text 
T I/O = Tseek + Trotation + Ttransfer
  • HDD는 random I/O가 느림. seek와 rotation이 비싸기 때문.

Disk Scheduling

  • FCFS: 온 순서대로. 단순, starvation 없음, seek 낭비.

  • SSTF: 현재 head에서 가장 가까운 request. seek 감소, starvation 가능.

  • SCAN: elevator. 한 방향 처리 후 방향 전환.

  • F-SCAN: sweep 시작 시 queue freeze. 새 request는 다음 round.

  • C-SCAN: 한 방향으로만 처리, 끝에서 처음으로 돌아감. wait time 더 균일.

  • SPTF: seek + rotational delay까지 고려.

  • modern disk:

    • host OS: request merge/sort, fairness, starvation 방지.
    • disk drive: NCQ 등으로 내부 geometry 기반 scheduling 가능.

17. File Systems Basics

  • file system은 mapping problem:
text 
<filename, data, metadata> → <set of disk blocks>

  • file: persistent byte sequence, inode number를 가짐.

  • directory: <file name, inode number> mapping을 담는 special file.

  • inode

    • file metadata 저장.
    • file type, permission, owner, size, timestamps, block locations, link count.
    • 파일 이름은 inode 안이 아니라 directory entry에 있음.

  • file descriptor

    • process가 open file을 가리키는 작은 정수.

  • Unix open file 구조:

text 
per-process descriptor table
→ system-wide open file table
→ vnode/inode table
  • 같은 파일을 두 번 open()하면 file position은 보통 따로.
  • fork()하면 open file table entry를 공유하므로 file position도 공유.
  • pathname translation:
text 
open("/a/b/c")
→ "/"에서 a 찾기
→ a에서 b 찾기
→ b에서 c 찾기
  • write()는 보통 page cache에 먼저 기록.
  • persistence 필요하면 fsync().
  • hard link: 같은 inode를 가리키는 다른 이름.
  • symbolic link: pathname을 내용으로 가지는 special file.
  • mount: file system을 directory tree에 붙임.

18. File Systems Implementation

  • 구현의 두 축:

    1. on-disk structures
    2. access methods

VSFS layout

text 
S i d I I I I I D D D D D ...
  • S: superblock
  • i: inode bitmap
  • d: data bitmap
  • I: inode table
  • D: data blocks
  • superblock: FS type, block size, #blocks, #inodes 등.
  • bitmap: free/in-use 관리.
  • inode table: inode들의 배열.
  • data blocks: file contents.

Allocation

  • contiguous: <start, length>. 빠르지만 external fragmentation, growth 어려움.

  • linked: block들이 linked list. growth 쉬움, random access 나쁨.

  • FAT: linked pointer를 table에 모음. FAT cache로 random access 개선.

  • indexed: pointer array. random access 좋음, metadata overhead.

  • multi-level indexing: direct + indirect pointer.

    • VSFS 예시:
text 
12 direct + 1 single indirect
4KB block, 4B address → indirect block에 1024 pointers
max file size = (12 + 1024) * 4KB = 4144KB
  • extent: <start, length>의 여러 묶음. sequential 좋고 metadata overhead 작음.
  • directory는 special file, 보통 <file name, inode number> entry list.

19. Fast File System, FFS

  • 기존 Unix FS:
text 
Superblock | Inode List | Data Blocks

  • 문제:

    1. block size 작음, 512B.
    2. freelist가 비조직적이라 fragmentation.
    3. inode와 data block이 멀어 locality 나쁨.

  • FFS 핵심:

text 
disk-aware file system
related things together

  • 개선:

    • large blocks: 4KB/8KB로 throughput 증가.

    • fragments: 작은 파일/파일 끝부분 낭비 감소.

    • bitmap: contiguous free blocks 찾기 쉬움.

    • cylinder groups / block groups:

      • group마다 inode, bitmap, data block 배치.
      • superblock replication으로 reliability.

  • allocation policy:

    • directory는 group들에 분산.
    • 같은 directory 파일은 같은 group에.
    • file data는 inode와 같은 group에.
    • large file은 chunks로 여러 group에 분산.

  • 성능:

    • original Unix FS: 약 3%~5% disk bandwidth.
    • FFS: 약 14%~47%.
    • FS가 full에 가까우면 throughput 하락.

20. File System Consistency

  • 문제:

    • system call 하나가 여러 disk write를 필요로 함.
    • disk는 single sector write 정도만 atomic.
    • crash가 중간에 나면 inconsistent state 가능.

  • 목표:

text 
one consistent state → another consistent state

Append example

새 data block Db append 시 필요한 update:

text 
1. data block Db write
2. data bitmap update
3. inode update

partial crash:

  • data only: metadata는 old state라 OK.
  • inode only: inode는 Db 가리키는데 bitmap은 free → inconsistent.
  • bitmap only: allocated인데 inode가 안 가리킴 → lost block.
  • inode + bitmap: metadata OK, data garbage 가능.
  • inode + data: bitmap은 free → inconsistent.
  • bitmap + data: inode가 안 가리킴 → lost block.

FSCK

  • crash 후 전체 file system scan.

  • inode bitmap, data bitmap, link count, duplicate/invalid block pointer 검사.

  • lost file은 /lost+found.

  • 단점:

    • 느림.
    • correct state가 아니라 consistent state로 고칠 뿐.

Journaling

  • write-ahead logging.
text 
1. Journal write: TxB, IN', DB', Db
2. Journal commit: TxE
3. Checkpoint: final location에 반영
  • recovery:
text 
TxE 없음 → discard journal
TxE 있음 → redo / roll-forward
  • metadata journaling: metadata만 journal.
  • ordered journaling: data 먼저 쓰고 metadata commit, garbage data 방지.

마지막 암기 줄

text 
10: memory 부족 → swapping, replacement
11: process보다 가벼운 실행 단위 → thread
12: shared data 보호 → lock
13: event waiting까지 필요 → semaphore, CV
14: 동시성 bug → atomicity, ordering, deadlock
15: HDD는 seek/rotation이 비쌈 → disk scheduling
17: file system abstraction → file, directory, inode, fd
18: disk 위 구현 → superblock, bitmap, inode, allocation
19: 성능 개선 → FFS, locality, cylinder group
20: crash 대비 → fsck, journaling
Discussion