#3 프로세스 스케줄링(Scheduling)

CS/운영체제

#3 프로세스 스케줄링(Scheduling)

Scala0114 2021. 12. 21. 14:43

1. 성능(Performance) 판단의 지표 (용어정리)

CPU 사용률(CPU Utilization)
- 단위 시간동안 프로세서가 작업중인 시간의 비율
- 사용률이 높을수록 CPU를 효율적으로 사용하고 있는 상태
처리율(Throughput)
- 단위 시간당 완료하는 작업의 수
반환 시간(Turnarount Time)
- 요청된 작업이 완료될 때 까지의 시간
- 종료 시간 - 도착 시간
대기 시간(Waiting Time)
- 작업이 Ready Queue 에서 대기하는 시간
- 시작 시간 - 도착 시간
반응 시간(Response Time)
- 요청된 작업에 반응이 돌아올 때 까지의 시간
- 첫 응답이 돌아온 시간 - 도착 시간
실행 시간(Burst Time)
- 요청된 작업이 실제로 실행된 시간
- 종료 시간 - 시작 시간

2. 스케줄링의 기준

스케줄링 기법의 선택을 위해 고려해야할 항목
프로세스의 특성
- 프로세서의 작업비중과 입출력(I/O) 작업비중 중에서 어느쪽이 높은지를 고려
시스템의 특성
- 실시간, 대화형 시스템의 경우 반응 시간이 핵심 지표가 된다.
- 일괄 처리 시스템(batch system) 등의 경우 단위 시간당 처리율(Throughput)이 핵심지표가 된다.
프로세스의 긴급성(Urgency)
- hard-realtime : 지정된 응답시간 내에 반응에 실패할 경우 심각한 피해가 발생하는 시스템
- soft-realtime : 지정된 응답시간 내에 반응에 실패할 경우 성능저하가 발생할뿐 동작엔 문제가 없는 시스템
- non-realtime : 실시간 시스템이 아닌 경우
프로세스의 우선순위(Priority)
프로세스의 실행시간(Service Time)

3. 스케줄링의 단계

Short-Term 스케줄링
- Ready Queue에서 대기중인 프로세스중 어느 프로세스에게 프로세서(CPU)를 할당할지 결정
- 일반적으로 말하는 스케줄링은 단기 스케줄러에 의한 스케줄링을 의미함
- 가장 자주 발생하는 스케줄링이기 때문에 성능에 미치는 영향도 매우큼 => 속도가 매우 빨라야한다.
Mid-Term 스케줄링
- 너무 많은 프로세스에게 메모리를 할당하여 시스템 성능이 저하될 경우
  메모리에 적재된 프로세스의 수를 유동적으로 조절하
- 메모리에 적재될 프로세스중 일부를 선택하여 컨텍스트를 디스크의 스왑 영역에
  저장해두고 메모리를 해제한다. 이를 스왑 아웃(Swap Out)이라 한다.

Long-Term 스케줄링
- 메모리에 동시 적재 가능한 프로세스의 수(multi-programming degree) 조절
  => Ready Queue 에 들어갈 프로세스의 수 조절
- 현대의 시분할 시스템이나 실시간/대화형 시스템의 경우 장기 스케줄러를 두지 않거나 최소화시킴
  - 시분할 시스템의 경우 모든 프로세스에 공평하게 정해진 시간동안 자원을 분배하기 위해,
    실시간/대화형 시스템의 경우 요청을 받았을 때 정해진 시간 내에 응답하기 위해 바로 메모리를
    할당하고 Ready Queue에 넣어야하기 때문에 Long-Term 스케줄링의 의미가 없기 때문
- 일괄 처리 시스템(batch system)에 적합하다.

4. 스케줄링 정책

비선점 스케줄링(Non-preemptive Scheduling)
- 한번 자원을 할당받고나면 실행이 완료되고 이를 반납하기 전까지 사용할 수 있음
- 보다 우선순위가 높은 프로세스가 도착하더라도 자신의 작업은 끝까지 수행할 수 있음
- 한 작업이 모두 수행되기 전까지 다른 작업에 대해 응답할 수 없기에 평균 응답시간이 길어짐
- 우선순위가 높은 작업이 먼저 실행되기 시작한 우선순위가 낮은 작업에 밀리는 경우가 자주 발생
- 하나의 프로세스가 실행을 마칠 때 까지 Context Switching이 발생하지 않아 오버헤드가 적음
선점 스케줄링(Preemptive Scheduling)
- 자원을 할당받은 후 실행이 아직 완료되지 않았어도 보다 우선순위가 높은 프로세스가 도착하거나
  자신의 사용시간이 만료되면 자원을 반납해야함
- 선점에 의한 Context Switching 이 자주 발생 => 오버헤드가 큼
- 시분할 시스템이나 실시간/대화형 시스템에는 이 방식이 적합
우선순위(Priority)의 결정
- 정적 우선순위(Static Priority)
  - 프로세스 생성시 변하지 않는 우선순위를 지정
  - 구현이 쉽고 overhead가 적음
  - 상황 변화에 따른 유연한 대처 불가
- 동적 우선순위(Dynamic Priority)
  - 프로세스의 상태 변화에 따라 Priority 변경
  - 구현이 복잡하고 Priority 계산을 위한 overhead가 발생
  - 상황 변화에 따른 유연한 대처 가능

5. 스케줄링 알고리즘

① 비선점형 스케줄링 알고리즘

FCFS(First Come First Served)
- 대기열에 먼저 들어온 프로세스를 우선적으로 실행하는 알고리즘
- 장점
  - 구현이 매우 간단하며 오버헤드 또한 거의 없음
  - 작업이 종료될 때를 제외하면 Context Switching이 발생하지 않아 CPU 사용률이 매우 높다
  - 도착한 작업은 자신의 순서가 오면 반드시 실행되기에 starvation(기아) 이 발생하지 않는다.
- 단점
  - 평균 응답시간이 매우 길다
  - 하나의 오래걸리는 작업으로 인해 다른 작업들의 대기시간이 길어지는 문제
SJF(Shortest Job First)
- 실행시간(Burst Time)이 가장 적은 프로세스가 우선적으로 실행되는 알고리즘
- 장점
  - 평균 대기시간 최소화
  - 시스템 내 프로세스의 수를 최소화(실행시간이 짧은 작업들이 빠르게 종료되기 때문)
- 단점
  - 프로세스의 실행시간을 정확히 예측하는 것이 현실적으로 어려움
  - 실행시간이 긴 프로세스가 계속해서 우선순위에서 밀리는 starvation(기아)이 발생
HRRN(Highest Response Ratio Next)
- Response Ratio 공식에 따라 계산된 우선순위가 높은 프로세스를 우선적으로 실행하는 알고리즘
- Response Ratio = (Service Time + Waiting Time) / Service Time
- 서비스 시간이 짧을수록, 대기시간이 길수록 우선순위가 높아지는 방식
- 대기시간의 증가에 따라 우선순위가 높아져 starvation이 발생하지 않도록 하는 에이징(aging) 기법을 사용

② 선점형 스케줄링 알고리즘

RR(Round Robin)
- FCFS의 선점형 버전
- 기본적으로는 대기열에 가장 먼저 도착한 프로세스를 먼저 처리
- 대신 자원의 사용 시간에 제한을 두어 시간이 만료되면 자원을 반납하고 대기열의 맨 뒤로 간다
- 장점
  - 특정 프로세스에 의한 자원 독점의 방지
  - 평균 응답시간이 길어지는 문제 해결
- 단점
  - 잦은 Context Switch로 인한 오버헤드가 큼
- 시분할 시스템이나 실시간/대화형 시스템에 적합
SRT(Shortest Remaining Time)
- SJF의 선점형 버전
- 남은 실행시간이 가장 적은 프로세스를 먼저 처리
- 남은 실행시간이 더 적은 프로세스가 대기열에 들어오면 그 프로세스에 의해 자원이 선점당함
- 장점
  - SJF의 장점(대기시간의 최소화, 시스템 내 프로세스 수의 최소화)을 극대화
- 단점
  - SJF와 마찬가지로 실행시간(Burst Time)의 측정이 어려움
  - 남은 실행시간(Remaining Time)을 지속적으로 추적해야함
MLQ(Multi Level Queue)
- 프로세스들을 그룹화하여 그룹마다 독자적인 큐(대기열)를 사용하는 스케줄링 기법
- 프로세스는 작업의 특성(작업의 중요도, 빠른 응답시간이 요구되는지 등)에 따라 분류
- 각 큐는 그 특성에 맞는 독자적인 스케줄링 기법을 적용
- 한번 배정된 큐에서는 이동할 수 없음
- 큐 사이에는 우선순위 기반의 스케줄링 사용
- 장점
  - 작업의 특성에 따라 적합한 스케줄링 기법을 독립적으로 적용 가능
- 단점
  - 여러개의 큐를 관리해야하는 만큼 스케줄링의 오버헤드가 보다 큼
  - 우선순위가 낮은 큐의 starvation이 발생할 수 있음
  - 처음에 프로세스를 적절한 큐에 배정하지 못하면 이동이 불가능하기에 프로세스에 대한 사전정보가 필요
MFQ(Multi Level Feedback Queue)
- 프로세스가 처음 배정된 큐에서 다른 큐로 이동 가능해진 MLQ 방식
- Feedback 을 통해 우선순위를 조정
- 프로세스에 대한 사전정보를 알지 못해도 HRN과 비슷한 효과를 볼 수 있음
- 장점
  - MLQ가 그러했듯이 각 큐마다 별도의 스케줄링 정책을 사용하는 것으로
    프로세스의 특성에 적합한 스케줄링 방식 적용이 가능
  - 입출력 위주(I/O Bounded)의 프로세스를 상위 큐로 이동
    => I/O 위주의 프로세스는 CPU 사용시간이 짧기 때문(적은 service time)
  - 대기시간이 길어진 프로세스를 상위 큐로 이동(Aging)
    => starvation 의 방지
- 단점
  - 복잡한 설계와 구현
  - 다중 큐의 관리로 인한 오버헤드

저작자표시 (새창열림)