1. Process Scheduling

왜 프로세스 스케줄링이 필요할까?

• 우리 컴퓨터는 다중 프로그래밍
• 자원을 할당할 프로세스를 선택해야함 → 스케줄링
• 자원관리
  • 시간 분할 관리: 하나의 자원을 여러 스레드들이 번갈아서 사용
    • 예) 프로세서
    • 프로세스 스케줄링: 프로세서 사용시간을 프로세스들에게 분배
  • 공간 분할 관리
    • 하나의 자원을 분할하여 동시에 사용
    • 예) 메모리

스케줄링의 목적

• 시스템 성능의 향상
• 성능의 정의:
  - 응답시간(response time): 작업요청(submission)으로 부터 응답을 받을때까지의 시간 → interactive, real-time
  - 작업처리량(thoughput): 단위시간동안 완료된 작업수 → batch system
  - 자원활용도(resource utilization): 주어진 시간동안 자원이 활용된 시간. 얼마나 프로세서를 놀리지 않고 사용했는가 → 비싼 cpu
  

스케줄링 기준

• 프로세스의 특성: I/O bounded / compute-bounded
  • 프로세스 수행 = CPU 사용 + I/O 대기
  • compute bounded = cpu burst time(실행시간)이 더 큰 프로세스
  • I/O bounded = i/o burst time(실행시간)이 더 큰 프로세스
• 시스템 특성: 배치 시스템/대화형 시스템
• 긴급성
• 프로세스 우선순의
• 프로세스 총 실행시간

스케줄링의 단계

1. long term

   • job scheduling : 잡이 줄을 서있을 때, 누구를 시스템(커널)에 등록시킬 지 결정하는 것
   • 다중 프로그래밍의 정도의 조절 : 시스템 내의 프로세스 수 조절
   • io bounded 와 compute bounded를 잘 섞어서 올려주자
   • 시분할 시스템에서는 모든 작업을 시스템에 등록 → long-term 스케줄링이 덜 중요

2. mid-term

   • 메모리 할당 결정: suspended된 애들 중에 누구에게 메모리를 줄지 결정

3. short-term

   • 프로세스 스케줄링
   • 프로세서를 할당할 프로세스를 결정하자: processor scheduler, dispatcher
   • 가장 빈번→ interrupt, block(io), time-out
   • 매우 빨라야함

   스케줄링의 단계 (level)

스케줄링 정책

1. 선점 vs 비선점

• 선점: 누가와서 내껄 뺏을 수 있다
  • context switching overhead 가 큼
• 비선점: 내껄 뺏을 수 없다
  • 어떤 프로세스가 자원을 할당 받았을 때, 다 쓰기 전까지는 뺏기지 않는다.
  • context switching overhead가 적음
  • 잦은 우선순위 역전, 평균 응답시간 증가

1. 우선순위
   • 정적 우선순위: 프로ㅔ쓰 생성시 결정된 우선순위가 유지됨
     • 오버헤드가 적고 구현 쉬움
     • 시스템 환경변화 대응이 어려움
   • 동적 우선순위: 프로세스 상태변화에 따라 우선순위 변경
     • 오버헤드가 많고 구현 어려운
     • 시스템 환경변화 대응이 쉬움

2. Basic scheduling algorithms

FCFS(First Come First Served)

• 선착순
• 비선점 스케줄링 (Non preemptive scheduling)
• 스케줄링 기준: 도착시간(누가 레디큐에 먼저 도착했는가)
• 자원을 효율적으로 사용가능
  • 스케줄링에 대한 오버헤드가 적고
  • cpu가 계속 일할 수 있다
• 배치 시스템에 적합/ interactive 시스템에 부적합
• 단점:
  - convoy effect: 하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게 되는 현상(대기시간> 실행시간)
  - 긴 평균 응답시간
  

burst time: 실행시간

turn around time: 처음 일을 요청을 해서 끝나는 데 까지 걸리는 시간

normalized TT: 각 프로세스 마다 걸리는 시간이 다르다. 만약 다 같은 시간을 기다렸을 때, 10초가 필요한 프로세스와 1초가 필요한 프로세스의 체감 대기 시간은 다를 것이다. 이를 비교하기 위해 만든 지표. 체감 turn around time. 1보다 클수록 체감시간이 더 길다, 불공평하다.

RR(Round Robin)

• 선점 스케줄링 (preemptive)
• 돌아가면서 프로세서를 쓰자!
  

• 스케줄링 기준

  • 도착 시간 (레디큐에 도착하는 시간 기준)

• 자원사용의 제한 시간이 있음 (time quantum)

  • system parameter
  • 프로세스는 할당된 시간이 지나면 자원을 반납: time-runnout
  • 특정 프로세스의 자원독점 방지
  • context switching 오버헤드가 큼

• 대화형, 시분할 시스템에 적합함

• 제한 시간(time quantum)이 시스템 성능을 결정하는 핵심요소
  - 제한시간이 무한대라면 → fcfs
  - 매우 작다면 → processor sharing
  - 사용자는 모든 프로세스가 각각의 프로세서 위에서 실행되는 것처럼 느끼게 될 것이다 → 체감 프로세스 속도 = 실제 프로세서 성능 * 1/n
  

  - time quantum이 끝나면 time-runnout으로 가서 다시 레디큐의 가장 뒤로 가게 된다

SPN(Shortest-Process-Next) or SJF (Shortest Job First)

• 비선점 스케줄링(non-preemptive)
• 스케줄링 기준: 실행시간 (burst time)이 가장 작은 프로세스를 먼저 처리
• shortest Job First
• fcfs에서의 문제점: 나는 1초만 있으면 프로세스를 끝낼 수 있는데 너무 오래 기다려야하는 문제
  

• 장점:

  • 시스템 내에 있는 프로세스의 수를 최소화할 수 있다.

    • 얼마 안걸리는 애들을 빨리빨리 쳐낼 수 있으니까

      → 스케줄링 부하감소, 메모리 절약 → 시스템 효율 향상

  • 평균 대기시간 WT 최소화

  • 많은 프로세스들에게 빠른 응답시간 제공

• 단점:

  • starvation 문제
    • 실행시간이 긴 프로세스는 자원을 할당 받지 못할 수 있음
      • aging등으로 해결 → HRRN
    • 정확한 실행시간을 알 수 없음
      • 실행시간 예측기법이 필요→ terminate 상태에서 대략적으로 예측은 가능하지만 어려움

SRTN(Shortest Remaining Time Next)

• SPN의 변형
• 선점 스케줄링
• 남은 시간이 적은 애들을 먼저 처리해주자 → 잔여실행시간이 더 적은 프로세스가 레디 상태가 되면 선점됨
• 장점: SPN의 장점을 극대화
• 단점:
  • 프로세스 생성시, 총 실행시간 예측이 필요함
  • 잔여실행시간을 계속 추적해야함 → 오버헤드 발생
  • context switching 오버헤드

⇒ 구현 및 사용이 비현실적!

HRRN(High-Response-Ratio-Next)

• SPN의 변형
  • SPN + aging
  • 비 선점
• Aging: 노약자를 배려하자
  • 프로세스의 대기시간을 고려하여 기회를 제공하자
• 스케줄링 기준: response ratio가 높은 프로세스를 우선적으로 고려
• response ratio = (WT+BT)/BT: 내가 필요한 시간(Burst time) 대비 얼마나 기다렸는가
• starvation문제를 해결가능
• 그러나 여전히 실행시간 예측이 필요함
  

MLQ(Multi-Level Queue)

• 앞에 봤던 알고리즘들은 레디큐가 하나
• 작업(or 우선순위) 별 별도의 레디큐를 가질 수 있음 → 레디큐가 여러개
  • 최초 배정된 큐를 벗어나지 못함
  • 각각의 큐는 자신만의 스케줄링 기법을 사용가능
• queue 사이에는 우선순위 기반의 스케줄링 사용
  - fixed priority preemptive scheduling
  
• 장점: 빠른 응답 시간?
  • 우선순위가 높은 큐는 응답시간이 빠르지만, 낮은 큐는 응답시간이 느리다
• 단점: 여러개의 큐 관리 등 스케줄링 오버헤드 발생 (큐 하나만으로도 힘들다!)
• 우선순위가 낮은 큐는 starvation문제

→ 이를 극복하기 위해 나온 방법

MFQ(Multi-Level Feedback Queue)

• 프로세스의 큐 간의 이동이 허용된 mlq
• 피드백을 통해 우선순위 조정
  - 현재까지의 프로세서 정보를 활용
  
• 장점: 프로세스에 대한 사전정보 없이 SPN, SRTN, HRRN 기법의 효과를 볼 수 있음
• 단점:
  • 설계및 구현이 복잡함
  • starvation 문제 발생
• 변형
  • 각 레디큐 마다 시간할당량을 가르게 배정
  • i/o bounded 프로세스를 상위 단계의 큐로 이동. 우선순위를 높인다
    • 프로세스가 블락될 때 상위의 레디큐로 진입하게 함
    • 시스템 전체의 평균응답시간을 줄일 수 있음. 입출력 작업을 분산시킴
    • i/o bounded는 cpu를 잠깐만 쓰고 나오니까, 얘를 위로 올리면 좀 더 많은 애들한테 서비스를 할 수 있음
    • 대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동
      • aging(오래 기다린 애들 위로 올려주자)