CS/운영체제

[운영체제] 4. 프로세스 스케줄링

hyomee2 2025. 3. 5. 20:57

다중프로그래밍(multi programming)

시스템 내에는 여러개의 프로세스가 존재하므로 자원을 나누어서 사용해야 하고,

따라서 자원을 할당할 프로세스를 선택하는 "스케줄링"이 필요하다.

 

자원 관리에서는 아래 두 가지 개념을 다룬다.

1. 시간 분할(time sharing) 관리

: 하나의 자원을 여러 스레드들이 번갈아가며 사용

e.g., 프로세서(CPU)는 1번에 1개만 사용 가능하다.

  • 프로세스 스케줄링: 프로세서 사용시간을 프로세스들에게 분배

2. 공간 분할(space sharing) 관리

: 하나의 자원을 분할하여 동시에 사용

e.g., 메모리

스케줄링의 목적

  • 시스템의 성능 향상

1. 대표적인 시스템 성능 지표(index)

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

 

(1) 응답시간(response time)

: 작업 요청(submission)으로부터 응답을 받을 때까지의 시간

  • interactive system(사용자 대화형 시스템) 또는 real-time system(제한된 시간 안에 답을 줘야하는 시스템)에서 중요

(2) 작업 처리량(throughput)

: 단위 시간동안 완료된 작업의 수

  • batch system(일괄처리 시스템)에서 중요

(3) 자원 활용도(resource utilization)

: 주어진 시간(Tc)동안 자원이 활용된 시간(Tc)

최댓값 1

  • 비싼 장비에서 중요

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

스케줄링의 기준

1. 스케줄링 기법이 고려하는 항목들

  • 프로세스의 특성
    • I/O-bounded / compute-bounded
  • 시스템 특성
    • Batch system / interactive system
  • 프로세스의 긴급성
    • Hard- / soft- real time, non-real time systems
  • 프로세스 우선순위
  • 프로세스 총 실행시간
  • ...

2. CPU burst(CPU 사용)와 I/O burst(I/O 대기)

  • 프로세스 수행 = CPU 사용 + I/O 대기
  • compute-bounded process: CPU burst > I/O burst
  • I/O-bounded process: CPU burst < I/O burst
  • Burst time은 스케줄링의 중요한 기준 중 하나이다.
    • burst time: 프로세스가 CPU를 점유하여 실행할 때 필요한 시간 (주로 CPU burst 시간만을 의미)

스케줄링의 단계(level)

발생하는 빈도 및 할당 자원에 따른 구분

  • Long-term scheduling
  • Mid-term scheduling
  • Short-term scheduling

1. Long-term scheduling(장기 스케줄링)

  • 가끔 발생한다.
  • ~= Job scheduling: 줄 서있는 job들 중 시스템에 제출할 (커널에 등록할) job 결정(실행 여부 결정)
    • Admission scheduling(= High-level scheduling)은 새로운 job이 시스템에 들어올 수 있는지, 즉 입장 여부를 결정하는 것. Admision scheduling(= High-level scheduling)을 통과한 job이 job scheduling 단계로 넘어간다.
  • 다중프로그래밍 정도(degree, 시스템 내의 프로세스 수) 조절
  • I/O-bounded와 compute-bounded 프로세스들을 잘 섞어서 선택해야 한다.
    • 자원 활용률 최적화, 멀티태스킹 성능 향상, context switching 비용 감소 등을 위해
  • 시분할 시스템(time sharing system)에서는 모든 작업을 시스템에 등록
    • Long-term scheduling이 덜 중요하다.

2. Mid-term scheduling(중기 스케줄링)

  • 종종 발생한다.
  • 메모리 할당 결정(memory allocation)
    • midterm scheduling이 프로세스를 메모리로 불러오는 역할을 하면, intermediate level scheduling은 그 프로세스를 실행할 수 있는 상태로 준비시킨다.
    • Swapping(swap-in / swap-out)

3. Short-term scheduling(단기 스케줄링)

  • low-level scheduling
  • 프로세서를 할당할 프로세스를 결정
    • Processor scheduler, dispatcher,...
  • 가장 빈번하게 발생한다.
    • interrupt, block(I/O), time-out, ...
    • 매우 빨라야한다.
      • process scheduling이 느리면 시스템이 전반적으로 느려진다.
      • e.g., average CPU burst(CPU 사용 시간)가 100ms, scheduling decision(스케줄링을 위해 추가로 필요한 시간)이 10ms이면, 이 프로세스가 일하는데 걸린 시간은 110ms이다. -> 10ms는 오버헤드로, 약 9%가 오버헤드.

* 스케줄링 전체 흐름

스케줄링 정책(policy, 방법)

1. Preemptive(선점) / Non-preemptive(비선점) scheduling

(1) Preemptive scheduling

  • 타의에 의해 자원을 빼앗길 수 있다.
    • e.g., 할당 시간 종료, 우선순위가 높은 프로세스 등장, ...
  • context switch overhead가 크다. -> 시스템 부하(오버헤드) 증가
  • time-sharing system, real-time system 등 응답성이 높은 경우 적합하다.

(2) Non-preemptive scheduling

  • 할당받을 자원을 스스로 반납할 때까지 사용한다. (타의에 의해 자원을 빼앗길 수 없다.)
    • e.g., system call, I/O, ...
  • 장점) context switch overhead가 적다.
  • 단점) 잦은 우선순위 역전(우선순위 높은 일을 제때 수행 불가), 평균 응답 시간 증가 

2. Priority (우선순위)

: 프로세스의 중요도

(1) Static priority (정적 우선순위)

  • 프로세스 생성 시 결정된 우선순위가 유지된다.
  • 장점) 구현이 쉽고, 오버헤드가 적다.
  • 단점) 시스템 환경 변화에 대한 대응이 어렵다. (중간에 우선순위가 변경된 경우)

(2) Dynamic priority (동적 우선순위)

  • 프로세스의 상태 변화에 따라 우선순위 동적으로 변경
  • 장점) 시스템 환경 변화에 유연한 대응 가능
  • 단점) 구현이 복잡, 우선순위 재계산 오버헤드가 크다.

기본 스케줄링 알고리즘

  • FCFS(First Come First Service)
  • RR(Round Robin)
  • SPN(Shortest Process Next)
  • SRTN(High Response Ratio Next)
  • MLQ(Multi-level Queue)
  • MFQ(Multi-level Feedback Queue)

1. FCFS(First Come First Service)

  • Non-preemptive scheduling (프로세스 하나가 코어를 할당받으면 끝날 때까지 쓰겠다.)
  • 도착시간(ready queue 기준)을 기준으로 스케줄링. 먼저 도착한 프로세스를 먼저 처리한다.(선착순)
  • 자원을 효율적으로 사용 가능(High resource utilization)
    • 그냥 선착순이니까 스케줄링 오버헤드가 낮으므로 CPU가 계속 일할 수 있다.
  • Batch system(일괄처리 시스템, 작업을 순차적으로 처리. 사용자가 요청한 작업들을 일괄처리)에 적합, interactive system(대화형 시스템, 빠른 응답이 중요)에 부적합
  • 단점
    • Convoy effect: 하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게 되는 현상 (대기시간 >> 실행시간)
    • 긴 평균 응답시간(response time)
  •  

    • e.g.,

 

2. RR(Round Robin)

: 돌아가면서 프로세서 사용하자 (너 2초, 나 2초, ...)

  • preemptive scheduling
  • 도착 시간(ready queue 기준)을 기준으로 스케줄링. 먼저 도착한 프로세스를 먼저 처리(여기까진 FCFS와 같다.)
  • 자원 사용 제한 시간(time quantum)이 있다.
    • system parameter( δ , 시스템적으로 설정할 수 있는 파라미터)
    • 프로세스는 할당된 시간이 지나면 자원을 반납한다. (timer-runout)
    • 장점) 특정 프로세스의 자원 독점(monopoly) 방지
    • 단점) context switch overhead가 크다.
  • 대화형(interactive system, 응답이 빨라야 하는 시스템), 시분할(time sharing system)에 적합하다.
  • time quantum( δ )이 시스템 성능을 결정하는 핵심 요소이다.
    • δ → ∞(엄청 커지면)이면 FCFS이다. (한 번 자원을 받으면 끝까지 쓰니까)
    • δ → 0(엄청 작아지면)이면  processor sharing이다. (프로세스를 동시에 쓰는 느낌)
      • 사용자는 모든 프로세스가 각각의 프로세서 위에서 실행되는 것처럼 느낀다. (체감 프로세서 속도 = 실제 프로세서 성능의 1/n)
      • context switch overhead가 크다.
  •  

  • e.g., time quantum이 2일 때

  • e.g., time quantum이 3일 때

  • e.g., time quantum이 4일 때

 

3. SPN(Shortest Process Next)

  • Non-preemptive scheduling
  • 실행시간(burst time)을 기준으로 스케줄링. Burst time이 가장 작은 프로세스를 먼저 처리한다.(SJF(Shortest Job First) scheduling)
  • 장점
    • 평균 대기시간(WT) 최소화
    • 시스템 내 프로세스 수 최소화
      • 스케줄링 부하 감소, 메모리 절약 -> 시스템 효율 향상
    • 많은 프로세스들에게 빠른 응답 시간 제공
  • 단점
    • Starvation(무한 대기) 현상 발생
      • BT(Burst Time)가 긴 프로세스는 자원을 할당받지 못할 수도 있다. -> aging 등으로 해결 (e.g., HRRN)
    • 정확한 실행시간을 알 수 없다. (SPN 사용을 위해선 burst time을 알아야 하는데 쉽지 않다 -> 예측할 수 없는 걸 가지고 스케줄링 해야 하는 단점 존재 -> 실행시간 예측 기법이 필요하다.)
  • e.g.,

 

4. SRTN (Shortest Remaining Time Next)

: 남은 시간이 적은 프로세스를 먼저 처리

  • SPN의 변형
  • Preemptive scheduling
    • 잔여 실행 시간이 더 적은 프로세스가 ready 상태가 되면(등장하면) 선점됨
  • 장점
    • SPN의 장점 극대화
  • 단점
    • 프로세스 생성 시, 총 실행 시간 예측이 필요
    • 잔여 실행을 계속 추적해야 한다. (overhead)
    • context switching overhead
  • 구현 및 사용이 비현실적이다.
  • e.g.,

 

5. HRRN (High Respose Ratio Next)

  • SPN의 변형(SPN에 aging concept을 더한 개념, non-preemptive scheduling)
    • SPN의 문제점은 starvation이었다.
  • aging concepts
    • 프로세스의 대기시간(WT)을 고려하여 기회를 제공한다.
  • 스케줄링 기준: response ratio가 높은 프로세스 우선
    • response ratio(응답률) = (WT + BT) / BT  -> 필요한 BT 대비 얼마나 기다렸는가?
    • SPN의 장점 + starvation 방지
    • 실행 시간 예측 기법 필요 (overhead)
  • e.g.,

 

 

위에서 살펴본

FCFS, RR은 fairness(공평성),

SPN, SRTN, HRRN은 efficiency(효율성)과 performance(성능)에 초점을 둔다고 생각할 수 있다.

하지만 SPN, SRTN, HRRN은 실행시간(BT) 예측 부하의 문제점이 있는데,

이를 해결하기 위한 방법이 MLQ(Multi Level Queue)와 MFQ(Multi-level Feedback Queue)이다.

 

6. MLQ(Multi Level Queue)

  • 작업(or 우선순위) 별 별도의 ready queue를 갖는다. 즉 ready queue가 여러개이다.
    • 최초 배정된 queue는 벗어나지 못하며, 각각의 queue는 자신만의 스케줄링 기법이 사용된다.
  • queue 사이에는 우선순위 기반의 스케줄링을 사용한다.
    • e.g., fixed-priority preemptive scheduling
  • 장점) 빠른 응답시간.....
    • 우선순위가 높은 애들에 대해서는 응답시간이 빠르지만, 아닌 애들(우선순위가 낮은 애들)에 대해서는 느리다. (중요한 애들은 빠르게 처리될 수 있다.)
  • 단점)
    • 여러개의 queue 관리 등 스케줄링 오버헤드 발생
    • 우선순위가 낮은 queue는 starvation 현상 발생 가능
  •  

 

7. MFQ(Multi-level Feedback Queue)

  • 프로세스의 queue 간 이동이 허용된 MLQ
  • feedback을 통해 우선 순위 조정 (현재까지의 프로세서 사용정보(패턴) 활용)
  • 규정 시간량(타임 슬라이드)가 있다. 
  • 특성)
    • dynamic priority
    • preemptive scheduling
    • favor short burst-time processes
    • favor I/O bounded processes
    • improve adaptability
  • 프로세스에 대한 사전 정보 없이 SPN, SRTN, HRRN 기법의 효과를 볼 수 있다.
    • SPN은 실행 시간이 짧은 프로세스를 먼저 실행하는데, MFQ는 짧은 프로세스는 처음부터 높은 우선순위 큐에 배정하고 빠르게 실행되기 때문에 낮은 우선순위 큐로 내려갈 일이 없다. 따라서 SPN과 비슷하게 짧은 프로세스를 우선 실행하는 효과가 있다.
    • SRTN은 남은 실행 시간이 가장 적은 프로세스를 실행하는데, MFQ에서는 짧은 프로세스는 높은 우선순위 큐에서 빨리 끝나고, 긴 프로세스는 실행 시간이 길어질수록 점점 낮은 우선순위 큐로 밀려난다. 따라서 짧은 프로세스가 계속 선점되는 효과가 있다.
    • HRRN은 (대기시간 + 실행시간) / 실행시간, 즉 대기 시간이 긴 프로세스를 우선 실행하는데, MFQ에서는 낮은 우선순위 큐에 있는 프로세스는 실행될 기회를 덜 얻고, 시간이 지나면서 상대적으로 실행될 확률이 높아진다. 즉 HRRN처럼 오래 기다린 프로세스는 상대적으로 우선순위가 높아지는 효과가 생긴다.
  •  

  • 단점)
    • 설계 및 구현이 복잡하며, 스케줄링 오버헤드가 크다.
    • 우선순위가 낮은 애들에 대한 starvation 문제
  • MFQ를 변형해보자면,
    • sol 1) 각 준비 큐마다 시간 할당량(time quantum)을 다르게 배정한다.-> 프로세스의 특성에 맞는 형태로 시스템 운영 가능
    • sol 2) 입출력 위주 프로세스들(I/O bounded process)을 상위 단계의 큐로 이동시켜 우선 순위를 높인다.
      • 프로세스가 block될 떄 상위 준비 큐로 진입하게 한다.
      • I/O bounded process는 CPU를 잠깐만 쓰고 나오기 때문에 많은 수를 빠르게 처리할 수 있다. -> 시스템 전체의 평균 응답 시간을 줄이고 입출력 작업 분산
    • sol 3) 대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동(aging 기법(오래 기다린 애의 우선순위를 높여주겠다.))
  • MFQ 스케줄링의 파라미터들
    • queue의 수
    • queue 별 스케줄링 알고리즘
    • 우선 순위 조정 기준
    • 최초 queue 배정 방법

본 게시물은 아래 강의를 수강한 뒤 공부한 내용을 정리한 글입니다.

https://www.youtube.com/watch?v=_gNeoGQx-Tc&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=8