프로세스 스케줄링

여러개의 프로세스가 시스템 내 존재

자원을 할당 할 프로세스를 선택해야함

• 스케줄링

자원관리

• 시간 분할(time sharing) 관리
  • 하나의 자원을 여러 스레드들이 번갈아 가며 사용(ex 프로세서)
  • 프로세스 스케줄링(Process scheduling)
    • 프로세서 사용시간을 프로세스들에게 분배
• 공간 분할(space sharing) 관리
  • 하나의 자원을 분할하여 동시에 사용(ex 메모리)

스케줄링의 목적

시스템의 성능(perfomance) 향상

대표적 시스템 성능 지표

• 응답시간 : 요청부터 응답 받기 까지의 시간
• 작업 처리량 : 단위 시간동안 완료된 작업의 수
• 자원 활용도 : 주어진 시간(T) 동안 자원이 활용된 시간

목적에 맞는 지표를 고려하여 스케줄링 기법을 선택

대기시간, 응답시간, 반환 시간

• 대기시간 : 도착해서 실행하기 전까지
• 응답시간 : 도착해서 첫 출력하기 전까지
• 실행시간 : 실행시작 부터 실행 종료까지
• 반환시간 : 도착부터 실행 종료 까지

스케줄링 기준

• 스케줄링 기법이 고려되는 항목들
• 프로세스의 특성, 시스템 특성, 프로세스 긴급성, 우선순위, 총 실행 시간 등

CPU burst vs I/O burst (프로세스 특성)

• 프로세스 수행 = CPU 사용 + I/O 대기
• cpu 사용이 더 많으면 compute-bounded
• I/O가 더 많으면 I/O bounded

스케줄링 레벨

Long-term Scheduling

job scheduling : 시스템에 제출(kernel에 등록)할 작업(job) 결정

• 다중프로그래밍 정도(degree) 조절 : 프로세스 수 조절
• 프로세스들(compute, I/O)을 잘 섞어서 선택 -> 프로세스들이 모두 일하게 하는 것이 효율적이다.
• 시분할 시스템에서는 덜 중요하다.

Mid-term Scheduling

메모리 할당 결정 : long-term 보다 자주 사용

Short-term Scheduling

Process scheduling : processor를 할당할 프로세스를 결정

• 가장 빈번하게 발생 : 매우 빨라야 한다!

📌스케줄링 정책(Policy)

선점 vs 비선점

• Non-premmptive 비 선점
  • 할당 받을 자원을 스스로 반납할 때까지 사용
  • Context Switch Overhead가 적음 | 잦은 우선순위 역전(우선순위가 높아도 기다려야 함), 평균 응답시간 증가
• premmptive 선점
  • 타의에 의해 자원을 뺏김
    • 할당시간종료, 우선순위가 높은 프로세스 등장
  • Context swtich overhead가 큼, 시스템 부하가 큼
  • 시분할 시스템, real-time 시스템 등에 적합 => 응답성이 높음

우선순위

• 프로세스의 중요도
• static priority(정적 우선순위)
  • 프로세스 생성시 결정된 priority가 유지 됨
  • 구현이 쉽고, overhead가 적음 ↔ 시스템 환경 변화에 대한 대응이 어려움
• Dynamic priority(동적 우선순위)
  • 프로세스 상태 변화에 따라 priority 변경
  • 구현이 복잡, priority 재 계산으로 overhead가 큼 ↔ 시스템 환경 변화에 유연한 대응 가능

📌비선점 스케줄링

FCFS(First-Come-First_Service)

• 스케줄링 기준 : ready queue 도착 시간
• 자원을 효율적으로 사용 가능 (스케줄링 오버헤드가 낮음, 계속해서 사용 가능함)
• 일괄처리 시스템에 적합 ↔ 대화형 시스템에 부적합
• 단점: 긴 평균 응답시간, 다른 프로세스들이 긴 대기시간을 갖게 됨, convoy effect
• 걸린시간(종료시간-도착시간)/필요시간

SJF(Shortest Job First)

• = SPN(Shortest Process Next)
• 스케줄링 기준 : burst time 기준(작으면 우선순위 높음)
• 장점: 평균 대기시간(WT) 최소화, 시스탬 내의 프로세스 수 최소화(부하감소, 메모리 절약 ➡ 시스템 효율 향상), 많은 프로세스들에게 빠른 응답 시간 제공
• 단점: Starvation(기아, 무한대기)현상 발생, BT가 긴 프로세스는 영원히 할당 받지 못 할 수 있음(Aging으로 해결), 정확한 시간 예측 불가
• SRTN
  • spn의 변형, 장점 극대화
  • 선점 스케줄링 (실행 시간이 더 적은 프로세스가 준비되면 선점 됨)
  • 프로세스 생성시, 총 실행시간(BT) 예측이 필요함 + 잔여 실행을 계속 추적 ➡ 부하가 큼
  • 구현 및 사용이 비현실적

HRRN(High-Response-Ratio_NEXT)

• SPN의 변형, SPN + Aging concepts, 비선점
• Aging concepts
  • 프로세스의 대기시간(WT)을 고려하여 기회를 제공
• 스케줄링 기준 : Response-Ratio가 높은 프로세스 우선
• Response ratio = (WT+BT)/BT(응답률)
  • SPN의 장점 + Starvation 방지
  • 실행시간 예측 기법 필요 (overhead 증가)

📌선점 스케줄링

Round-Robin

• 스케줄링 기준 : 도착시간
• 자원 사용 제한 시간이 있음
  • System Parameter
  • 프로세스는 할당된 시간이 지나면 자원 반납
  • 특정 프로세스의 작원 독점 방지 ↔ Context switch overhead가 큼
• 대화형, 시분할 시스템에 적합!
• Time quantum 이 시스템 성능을 결정하는 핵심 요소
  • 제한 시간이 매우 크면 FCFS가 됨
  • 제한 시간이 매우 짧으면 프로세서를 동시에 사용하는 느낌 -> 실제 성능의 1/n
    • high context switch overhead

MLQ(Multi-level queue)

• 작업(or우선순이)별 별도의 ready queue를 가짐
  • 최초 배정 된 queue를 벗어나지 못함
  • 각각의 queue는 자신만의 스케줄링 기법 사용
• Queue 사이에는 우선순위 기반의 스케줄링 사용
• 우선순위가 높으면 빠르게 처리 ↔ 여러 개의 queue 관리 등 스케줄링 overhead, 우선순위가 낮은 queue는 기아현상 발생
• 우선순위가 낮은 큐들이 실행 못하는 걸 방지하고자 각 큐마다 다른 Time Quantum을 설정 해주는 방식 사용

MFQ(Multi-level Feedback queue)

• 프로세스의 Queue간 이동이 허영된 MLQ
• Feedback을 통해 우선 순위 조정
  • 현재까지의 프로세서 사용 정보(패턴) 활용
• 프로세스에 대한 사전 정보 없이 SPN, SRTN, HRRN 기법의 효과를 볼 수 있음
• 단점: 설꼐 및 구현이 복잡, 스케줄링 overhead가 큼, 기아현상

• 변형

  • 각 준비 큐마다 시간 할당량을 다르게 배정
    • 프로세스의 특성에 맞는 형태로 시스템 운영 가능
  • 입출력 위주(I/O) 프로세스들을 상위 단계의 큐로 이동, 우선 순위 높임
    • 프로세스가 block이 되면 상위 큐로 진입
    • 시스템 전체 평균 응답시간을 줄이고 입출력 작업을 분산 시킴
  • 대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동 (Aging)

---

https://youtu.be/EdTtGv9w2sA [Course] Operating System (CPA310) - 운영체제 강의. HPC Lab. KOREATECH