/ OS

OS(4) - CPU Scheduling

OS 관련 포스팅

CPU Scheduling

  • Preemptive(선점)
    → CPU가 어떤 프로세스를 실행 중에 강제로 쫓아내고 다른 프로세스를 실행시킬 수 있는 scheduling 방식
  • Non-preemptive(비선점)
    → CPU가 어떤 프로세스를 실행 중이라면 해당 프로세스가 I/O를 만나거나 종료되지 않은 상황에서는 절대 scheduling이 일어나지 않는 방식
  • CPU Utilization(CPU 이용률)
    → CPU가 얼마나 열심히 일하고 있는가(%)
  • Throughput(처리율)
    → 시간당 몇 개의 작업을 처리하는가(jobs/sec)
  • Turnaround time(반환시간)
    → 어떤 작업이 ready queue에 들어가서 작업을 끝내고 나오는 시간(sec)
  • Waiting time(대기시간)
    → ready queue에서 기다린 시간(sec)
  • Response time(응답시간)
    → interactive system(대화형 시스템)에서 중요
    → 첫 응답이 나오는 데까지 걸리는 시간

CPU Scheduling Algorithms

1. First-Come, First-Served(FCFS)

  • 먼저 들어오면, 먼저 서비스 함
  • 간단하며, 공평하지만 반드시 좋은 성능을 보장하지는 않음
  • Average Waiting Time(AWT): ready queue에서 기다리는 시간
  • 단점: Convoy Effect(호위 효과)
    → burst time이 긴 프로세스가 앞에 있으면 나머지 프로세스는 뒤에서 오래 기다리게 되는데 그 모양새를 왕을 호위하는 사람에 비유
  • Non-preeptive scheduling방식

2. Shortest-Job-First(SJF)

  • 실행 시간이 짧은 것을 먼저 서비스 함
  • 대기 시간을 줄이는 최적의 방법
  • 단점: 비현실적임(실제 CPU 사용 시간은 실행을 해보기 전에는 알 수 없음)
    예측이 필수(과거를 기억하고 있어야 함)
    → overhead 발생, 시간이 많이 걸림
    → 현실적인 적용이 어려움
  • 선점(preemptive)/비선점(non-preemptive) 두 가지 방식 가능
  • 선점 방식의 경우 최소 잔여 시간 우선

3. Priority Scheduling

  • 우선 순위가 높은 것을 먼저 서비스 함
  • 우선 순위 설정
    • integer number
    • 내부적: 실행 시간 짧은, 메모리 작게 차지하는, I/O가 긴(=CPU가 짧은) 등
    • 외부적: 비용을 많이 지불한 쪽, 정치적인 요소 등
  • 선점 또는 비선점
  • 문제점: starvation 돌입 가능 - 우선 순위에서 밀리면 아무리 기다려도 서비스를 받지 못 함
  • 해결: aging - ready queue에서 오래 기다릴 수록 priority를 조금씩 상승시킴

4. Round-Robin(RR)

  • time-sharing system에서 많이 사용
  • time quantum(시간 양자) = time slice = Δ
    → 10 ~ 100msec: 1초당 10 ~ 100 번의 switching 발생
  • time quantum에 따라 성능이 달라짐
  • Δ → ∞ : FCFS
  • Δ → 0 : switching이 빈번해 여러 프로세스가 동시에 서비스 되는 것 같은 느낌을 줌

Multilevel Queue Scheduling

  • process별로 queue를 달리해 서비스 함
  • 여러 single ready queue의 묶음
  • queue마다 우선 순위는 다름
  • CPU time을 각 queue에 차등 배분함
  • queue별로 다른 scheduling 정책을 실행함

Multilevel Feedback Queue Scheduling

  • 여러 개의 queue
    → multilevel queue scheduling과의 공통점
  • 모든 process는 하나의 입구로 진입
  • 너무 많은 CPU time 소비 시, 기아 상태가 우려될 시 다른 queue로 이동

Process Creation

  • 프로세스는 프로세스에 의해 만들어짐
    → parent/child/sibling process, process tree
  • Process Identifier(PID)
    → 사람의 주민등록번호와 같은 것
    cf.) Parent Process Identifier(PPID)
  • system call
    • fork(): parent process 복사
    • exec(): 실행파일을 메모리로 가져오기

Process Termination

  • system call
    • exit(): 해당 프로세스의 자원 OS에 반환