• 실제로 필요할 때 page를 메모리에 올리는 것
  • I/O 양의 감소
  • Memory 사용량 감소
  • 빠른 응답 시간
  • 더 많은 사용자 수용
• Valid / Invalid bit
  • Invalid
    • 사용되지 않는 주소 영역인 경우
    • page가 물리적 메모리에 없는 경우
  • address translation 시에 invalid bit이 set되어 있으면 "page fault" => CPU가 운영체제로 넘어감

Page Fault

• Invalid page를 접근하면 MMU가 trap을 발생시킴
• Kernel mode로 들어가서 page fault handler가 실행됨
• 처리 과정
  1. Invalid reference? (eg. bad address, protection violation) => abort
  2. 빈 page frame을 가져온다 (없으면 뺏어옴, replace)
  3. 해당 page를 disk에서 memory로 읽어온다 (1) disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함(block) (2) Disk read가 끝나면 page tables entry 기록, valid/invalid bit = "valid" (3) ready queue에 process를 insert
  4. 이 프로세스가 CPU를 잡고 다시 run

Page Replacement

• 어떤 frame을 빼앗아올지 결정해야 함
• page fault rate을 최소화하는 것이 목표

  Replacement Algorithm

  • Optimal Algorithm
    • 미래의 reference를 알고있다고 가정
    • 가장 먼 미래에 참조되는 page를 replace
    • 다른 알고리즘의 성능에 대한 upper bound 제공

      FIFO Algorithm

  • 먼저 들어온 것을 먼저 내쫓음
  • FIFO Anomaly(Belady's Anomaly) : more frames => more page faults

    LRU(Least Recently Used) Algorithm

  • 가장 오래전에 참조된 것을 지움
  • O(1) complexity (linked-list를 이용해 구현)

    LFU(Least Frequently Used) Algorithm

  • 참조 횟수가 가장 적은 페이지를 지움
  • 최저 참조 횟수인 page가 여러개 있는 경우
    • 여러 page 중 임의로 선정
    • 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있음
  • O(log n) complexity (heap을 이용해 구현)

Caching

• 한정된 빠른 공간에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스하는 방식
• paging system 외에도 cache memory, buffer caching, web caching 등 다양한 분야에서 사용
• paging system에서는 실제로 LRU, LFU같은 알고리즘을 적용할 수 없음
  • page fault가 일어난 경우에만 CPU가 OS로 넘어가기 때문에 모든 정보를 받아올 수 없음

Clock Algorithm

• LRU의 근사 알고리즘
• reference bit을 이용
• 하드웨어가 page가 참조될 때 reference bit을 1로 설정
• OS는 reference bit이 0인 것을 쫓아내고, 이동하는 중에 1은 0으로 바꿈

Global/Local Replacement

• Global replacement : Replace시 다른 process에 할당된 frame을 뺏어 올 수 있다
• Local replacement : 자신에게 할당된 frame 내에서만 replacement

• Logical memory는 page(고정된 사이즈)로 분리되어 있고, physical memory는 frame(고정된 사이즈)으로 분리되어 있음.
• Page table
  • Logical memory를 physical memory로 변환할 때 사용
  • 각 page가 어느 frame에 mapping되어 있는지를 저장
  • Main memory에 상주 => 모든 메모리 접근 연산에는 2번의 memory access 필요
  • 성능 향상을 위해 page table 중에서 자주 사용되는 entry를 TLB에 저장
• internal fragmentation 발생

Segmentaion

• 프로그램은 의미 단위인 여러 개의 segment로 구성
  • 작게는 프로그램을 구성하는 함수 하나하나를, 크게는 프로그램 전체를 하나의 segment로 정의 가능
  • 일반적으로 code, data, stack 부분이 하나씩의 segment로 정의됨
• Logical address는 <segment-number, offset>으로 구성
• Segment table
  • base : segment의 시작 physical address
  • limit : segment의 길이
• 공유(여러 프로세스가 같은 segment를 공유)와 보안(read/write 권한)에 있어 paging보다 효과적
• segment의 길이가 동일하지 않으므로 external fragmentation 발생

• Logical address
  • 프로세스마다 독립적으로 가지는 주소 공간
  • 각 프로세스마다 0번지부터 시작
  • CPU가 보는 주소
• Physical address
  • 메모리에 실제 올라가는 위치
• 주소 바인딩 : 주소를 결정하는 것

Memory-Management Unit(MMU)

• logical address를 physical address로 매핑해주는 Hardware device
• 레지스터 두개로 주소 변환
• Relocation register(=base register) : 프로세스의 시작위치를 저장
• Limit register : 프로세스의 사이즈를 저장
• 접근 가능한 메모리 영역 x : base <= x <= base + limit 이 영역 밖의 메모리를 요구하면 trap 발생

Dynamic Loading

: 프로세스 전체를 메모리에 미리 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것

Swapping

: 프로세스를 일시적으로 메모리에서 디스크로 쫓아내는 것

Allocation of Physical Memory

• 메모리는 일반적으로 OS 영역과 사용자 프로세스 영역으로 나뉘어 사용
• 사용자 프로세스 영역의 할당 방법
  • Contiguous allocation : 각각의 프로세스가 메모리의 연속적인 공간에 적재
    • Fixed partition
    • Variable partition
  • Noncontiguous allocation : 하나의 프로세스가 메모리의 여러 영역에 분산
    • Paging
    • Segmentation
    • Paged Segmentation

: 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

Deadlock 발생 조건

(1) Mutual exclusion : 매 순간 하나의 프로세스만이 자원을 사용할 수 있음 (2) No preemption : 프로세스는 자원을 스스로 내어 놓을 뿐 강제로 빼앗기지 않음 (3) Hold and wait : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음 (4) Circular wait : 자원을 기다리는 프로세스간에 사이클이 형성되어야 함

Deadlock 처리 방법

(1) Prevention : Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 함

• Mutual Exclusion
  • 공유해서는 안되는 자원의 경우 반드시 성립해야 함
• Hold and Wait
  • 프로세스 시작 시 모든 필요한 자원을 할당 or
  • 자원이 필요할 경우 보유 자원을 모두 놓고 요청
• No preemption
  • 자원을 빼앗을 수 있도록 함
  • State를 쉽게 저장할 수 있는 자원에서 주로 사용(CPU, memory)
• Circular Wait
  • 모든 자원에 할당 순서를 정함

(2) Avoidance : 자원 요청에 대한 부가정보(ex. 자원별 최대 사용량)를 이용해서 자원 할당이 deadlock으로부터 안전한지를 조사해서 안전한 경우에만 할당

• Resource Allocation Graph Algorithm, Banker's Algorithm

(3) Detection and Recovery : Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover

• Recovery
  • Process termination
    • Deadlock 상태의 프로세스들을 모두 중지
    • Deadlock 상태가 제거될 때까지 프로세스 하나씩 중지
  • Resource Preemption
    • 비용을 최소화할 victim을 선정
    • safe state로 rollback하여 process를 restart

(4) Ignorance : Deadlock에 대해 아무런 조치도 취하지 않음

• Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음
• 사람이 직접 process를 죽이는 방법 등으로 대처
• UNIX, Windows 등 현대의 대부분 운영체제들이 채택

: 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐

Race condition이 발생하는 상황

(1) 커널 모드 실행 중 인터럽트가 발생하는 경우(둘 다 커널 코드이므로 kernel address space 공유) => 커널 모드에서 데이터를 다루고 있을 때는 인터럽트 처리를 하지 않게 함

(2) 프로세스가 system call을 하여 커널 모드로 수행 중인데 context switch가 일어나는 경우 => 커널 모드에서 수행 중일 때는 할당 시간이 지나도 CPU를 뺏지 않게 함

(3) Multiprocessor에서 shared memory 내의 kernel data => 한 번에 하나의 CPU만이 커널에 들어갈 수 있게 함 => 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock/unlock을 함

Critical Section (임계 영역)

: 공유 데이터를 접근하는 코드

The Critical-Section Problem

: n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우

해결을 위한 충족 조건

• Mutual Exclusion : 한 프로세스가 critical section을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다
• Progress : 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 들어가게 해주어야 한다
• Bounded Waiting : 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다

해결책

Synchronization Hardware

: Critical section에 들어가는 프로세스는 lock을 획득하고(true), critical section을 빠져나올 때 lock을 방출(false)함으로써 동시에 접근할 수 없도록 한다

Semaphores

• Semaphore S : 자원의 개수(integer) P연산 : 공유 데이터를 획득하는 과정 V연산 : 데이터를 반납하는 과정

  P(S) : while (S <= 0) do no-op
      S--
   ---critical section---
  V(S) : S++

• Busy wait(=spin lock) : Critical section에 진입해야 하는 프로세스는 진입 코드를 계속 반복 실행해야 하며, CPU를 낭비한다
• Block & wakeup
  • block : semaphore를 획득할 수 없으면 프로세스를 block시키고, 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
  • wakeup : 다른 프로세스가 semaphore를 반납하게 되면, block된 프로세스를 wakeup시킴
• Busy wait vs Block & wakeup
  • Critical section의 길이가 긴 경우 block/wakeup이 적당
  • Critical section의 길이가 매우 짧은 경우 block/wakeup의 오버헤드가 busy-wait 오버헤드보다 커질 수 있음
• Counting semaphore : Semaphore의 값이 임의의 정수 값. 주로 resource counting에 사용
• Binary semaphore(=mutex) : Semaphore의 값이 0 또는 1 (lock과 unlock)
• Deadlock : 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

CPU 스케줄링

: 어떤 프로세스에게 CPU를 줄 것인지를 결정 (누구한테 줄 것인가? 언제 뺏을 것인가?)

선점 / 비선점 스케줄링

• 선점(preemptive) : 강제로 회수 ex) timer interrupt, I/O 완료 후 interrupt
• 비선점(nonpreemptive) : 자진 반납 ex) I/O 시스템 콜, Terminate

스케줄링 척도(Criteria)

• CPU utilization (이용률) : 전체 시간 중에서 CPU가 사용된 시간의 비율 (시스템 입장)
• Throughput (처리량) : 주어진 시간 동안에 몇개의 작업을 수행했는가 (시스템 입장)
• Turnaround time (소요시간) : 실행시간과 대기시간을 합한 시간
• Waiting time (대기 시간) : 대기시간의 총합 (preemptive 스케줄링의 경우, 대기를 여러번 할 수 있음)
• Response time (응답 시간) : CPU를 처음 얻기까지 걸린 시간

스케줄링 알고리즘

• FCFS(First-Come First-Served)
  • 큐에 도착한 순서대로 CPU 할당
  • nonpreemptive
  • 실행시간이 짧은 프로세스가 나중에 배치되면 대기시간이 길어짐
• SJF(Shortest Job First)
  • 실행시간이 짧은 프로세스를 먼저 수행
  • nonpreemptive
  • 평균 대기시간 감소
  • 수행시간이 긴 프로세스는 CPU를 받지 못할수도 있음 (Starvation)
  • CPU 수행시간을 정확히 알 수 없음 (과거를 통해 예측은 가능)
• SRTF(Shortest Remaining Time First)
  • SJF의 preemptive 버전
  • 현재 수행중인 프로세스의 남은 시간보다 더 짧은 시간을 가지는 프로세스가 도착하면 CPU를 빼앗김
  • minimum average waiting time을 보장
• Priority Scheduling
  • 우선순위가 높은 프로세스에게 CPU를 할당
  • preemptive, nonpreemptive 두가지 버전 존재
  • SJF는 일종의 priority 스케줄링. Starvation 현상 발생 => Aging으로 해결 (오래 기다린 프로세스의 우선순위를 높임)
• Round Robin Scheduling
  • 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐
  • preemptive
  • Response time이 작아짐
  • time quantum이 크면 FCFS와 같게 되고, 작으면 context switch 오버헤드가 커짐
  • n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 => 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
• Multilevel Queue
  • Ready queue를 여러 개로 분할
  • 각각의 큐는 우선순위를 가짐
• Multilevel Feedback Queue
  • 처음에는 우선순위가 가장 높은 큐에 배정
  • 해당 큐의 time quantum을 다 채운 프로세스는 그 다음 우선순위인 큐로 내려감

• fork() : 자식 프로세스를 생성(부모 프로세스를 복제)
• exec() : 새로운 프로그램으로 덮어씌움
• wait() : 자식이 종료될 때까지 기다림(blocked)
• exit() : 프로세스 종료
  • 자발적 종료
    • 프로그램에 명시적으로 적어주지 않아도 main 함수가 리턴되는 위치에 컴파일러가 넣어줌
  • 비자발적 종료
    • 부모 프로세스가 자식 프로세스를 강제 종료 (ex) 자식 프로세스가 한계치를 넘어서는 자원 요청
    • 키보드로 kill, break 등을 친 경우
    • 부모가 종료하는 경우 (부모 프로세스가 종료하기 전에 자식들이 먼저 종료됨)

프로세스 간 협력 메커니즘(IPC: Interprocess Communication)

• message passing : 커널을 통해 메세지를 전달
• shared memory : 원칙적으로 프로세스는 각자의 주소 공간을 가지고 수행되지만, 일부 주소 공간을 공유하게 하는 메커니즘

: 프로세스 내부의 CPU 수행 단위

• program counter, register set으로 구성되고 나머지 영역은 다른 thread들과 공유. stack에 할당.

Thread의 장점

• 응답성 : 다중 스레드로 구성된 구조에서는 하나의 스레드가 blocked 상태인 동안에도 동일한 태스크 내의 다른 스레드가 실행되어 빠른 처리를 할 수 있다.

• 자원 공유

• Economy : 스레드를 생성하고, switching 하는 것이 프로세스보다 overhead가 훨씬 적음.

: 실행중인 프로그램

프로세스의 context

: 특정 시점에서 프로세스의 상태를 규명하기 위한 요소들

프로세스의 상태(state)

• Running : CPU를 잡고 instruction을 수행중인 상태
• Ready : CPU를 기다리는 상태
• Blocked(wait, sleep) : CPU를 주어도 당장 instruction을 수행할 수 없는 상태 ex) 디스크에서 file을 읽어온 후 처리해야 하는 경우
• Suspended : 외부적인 이유로 프로세스의 수행이 정지된 상태 프로세스 통째로 디스크에 swap out 된다. ex) 메모리에 너무 많은 프로세스가 올라와 있을 때

Process Control Block(PCB)

: 운영체제가 각 프로세스를 관리하기 위해 프로세스당 유지하는 정보

(1) OS가 관리상 사용하는 정보 - Process state, Process ID, scheduling information, priority

(2) CPU 수행 관련 하드웨어 값 - Program counter, registers

(3) 메모리 관련 - Code, data, stack의 위치 정보

(4) 파일 관련

Context Switch

: CPU를 한 프로세스에서 다른 프로세스로 넘겨주는 과정 - CPU를 내어주는 프로세스의 상태를 PCB에 저장 - CPU를 새롭게 얻는 프로세스의 상태를 PCB에서 읽어옴 -> 한 프로세스가 CPU를 잃었다가 다시 얻었을때, 이전에 실행되었던 위치의 다음부터 실행이 된다.

**반효경 교수님 KOCW 공개강의 정리**