Process Scheduling Algorithm

프로세스 스케줄링 알고리즘

CPU 스케줄링
: 언제 어떤 프로세스에게 CPU를 할당할지 결정하는 작업

스케줄링 평가기준

시스템 입장의 성능 척도
- CPU 이용률 (CPU utilization)
  - 시간당 CPU 사용 시간 비율
  - 전체 시간 중 CPU가 쉬지 않고 일한 시간
- 처리율 (Throughput)
  - 시간당 처리한 작업의 비율
  - 단위 시간 당 수행 완료한 프로세스의 수
프로그램 입장의 성능 척도
- 반환시간 (Turnaround Time)
  - 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는데까지 걸리는 시간
  - ready queue 대기시간 + CPU 실행시간 + I/O 작업시간의 합
- 대기시간 (Waiting Time)
  - 대기열에 들어와 CPU를 할당받기까지 기다린 시간
  - ready queue 대기시간의 총 합
- 반응시간 (Response Time)
  - 대기열에서 처음으로 CPU를 얻을 때까지 걸린 시간
  - CPU를 할당받은 최초의 순간까지 기다린 시간 한번만 측정
- 실행시간 (Burst Time)
  - 프로세스 수행 = CPU burst + I/O burst
  - CPU burst : CPU 사용 시간
  - I/O burst : I/O 대기 시간

시스템 입장의 성능척도(CPU이용률, 처리율)는 늘리고, 프로그램 입장의 성능척도(반환시간, 대기시간, 반응시간)는 줄이는 것이 좋음

프로세스 스케줄링 알고리즘

공평성을 고려한 방식
- FCFS (First-Come-First-Service) : 선착순 방식
- RR (Round-Robin): 제한시간을 두는 방식
시스템 성능과 효율성을 고려한 방식(실행시간 예측 부하의 문제가 존재)
- SPN (Shortest-Process-Next): 짧은 BT를 우선으로 처리하는 방식
- SRTN (Shortest Remaining Time Next): 남은 시간이 짧은 것을 우선으로 처리하는 방식
- HRRN (High-Response-Ratio-Next): RR이 적은 것을 우선으로 처리하는 방식
BT(실행시간) 예측 문제를 개선한 방식들
- MLQ (Multi-level Queue): 여러개의 레디큐를 두는 방식
- MFQ (Multi-level Feedback Queue): MLQ와 동일한 방식에서 queue를 다이나믹하게 운용하는 방식

1. FCFS (First-Come-First-Service)

비선점형 스케줄링
스케줄링 기준
- ready queue 도착시간
특징
- 선입선출(FIFO) Queue로 쉽게 관리 가능
- ready queue에 먼저 도착한 프로세스 먼저 처리
- Batch system(일괄처리 시스템)에 적합, interactive system(대화형 시스템) 부적합
장점
- 스케줄링이 단순함
- 효율적인 자원 사용가능
  - 불필요한 스케줄링 오버헤드 X
단점
- Convoy effect 발생
  - 하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게되는 현상
- 긴 평군 응답시간

2. RR (Round-Robin)

선점형 스케줄링
스케줄링 기준
- ready queue 도착시간
특징
- 자원 사용 제한시간 (time quantum/time slice) 존재
  - time quantum(시간 할당량)이 시스템 성능을 결정하는 핵심요소
  - 각 프로세스가 CPU를 소유하는 시간의 한계
- 프로세스는 할당된 시간이 지나면 자원 반납
- 대화형, 시분할 시스템에 적합
- Time quantum이 커질수록 FCFS 방식과 유사해짐
장점
- starvation(기아) 현상 발생 X
- 응답 시간이 빠름
- 특정 프로세스의 자원독점 방지
단점
- Contetx switch overhead 큼

Time quantum에 따른 Trade-Off

작은 Time quantum
- 응답성 증가
  - 프로세스가 더 빠르게 CPU를 얻음으로 더 빠른 응답과 실행
  - 빠른 응답성이 필요한 상황에 적합
- Context Switching Overhead 증가
  - 빈번한 프로세스 전환으로 오버헤드 증가
큰 Time quantum
- 응답성 감소
  - 한 프로세스가 지나치게 오랫동안 CPU를 점유하게 됨
  - 프로세스가 CPU 기다리는 시간 증가로 더 느린 응답과 실행
- Context Switching Overhead 감소
  - 상대적으로 긴 시간동안 CPU를 사용함으로 오버해드 감소

3. SJF (Short Job First)

SJF은 SPN과 동일한 스케줄링으로 보며, SJF에 선점형이 추가된 것이 SRTN

스케줄링 기준
- 실행시간(burst time)기준
특징
- ready queue에 있는 프로세스의 수행 시간이 짧은 순서대로 CPU 할당
- Convoy effect를 해결하기 위한 방법
- 주어진 프로세스에 대해 최소의 평균 대기시간 보장
- 선점형, 비선점형 스케줄링 두 개의 방식 존재
  - 비선점형 SJF : SPN
  - 선점형 SJF : SRTN
장점
- 평균 대기시간 최소화
- 시스템 내 프로세스 수 최소화
  - 스케줄링 부하 감소, 메모리 절약으로 시스템 효율성 향상
- 많은 프로세스들에게 빠른 응답 시간 제공
단점
- starvation(기아) 현상 발생
  - 실행시간이 긴 프로세스는 자원을 계속 할당 받지못 할 수 있음
- 정확한 다음 프로세스의 실행시간(Next CPU Burst Time)을 알 수 없음
  - 각 프로세스가 얼마나 CPU를 사용할지 모르기 때문에 실행시간 예측 기법 필요
  - 지수 평활법(과거의 CPU burst time 이용 예측) 사용
- 짧은 작업이 먼저 실행되기 때문에 공정하지 못함

3-1. SPN (Shortest-Process-Next)

Non-preemptive SJF
FSFS의 문제점을 개선한 방식
프로세스가 한 번 CPU를 얻으면 CPU burst time이 만료될 때까지 뺏기지 않음
작업간의 context switching 오버헤드 발생

3-2. SRTN (Shortest Remaining Time Next)

Preemptive SJF
최단 잔여시간을 우선으로 하는 스케줄링으로, SRTF(Shortest Remaining Time First)라고도 함
특징
- SPN의 변형
- 현재 실행되고 있는 프로세스의 잔여 실행 시간보다 더 짧은 프로세스가 ready 상태가 되면 선점 됨
장점
- 평균 대기시간(WT)를 최소화하여 시스템의 부하를 줄여주는 등 SJF(SPN)의 장점 극대화
단점
- 프로세스 생성시, 총 실행 시간 예측 필요
- 잔여 시간을 계속 추적해야하여 오버헤드 발생
- 선점형으로 Context Switching overhead 발생
- 기아 현상 발생

4. HRRN (High-Response-Ratio-Next)

HRRN 우선순위 스케줄링 알고리즘은 비선점형/선점형 두 방식으로 나뉠 수 있음
- 선점형 : 우선순위가 높은 프로세스가 대기큐에 들어오면 CPU를 선점함
- 비선점형 : CPU에 할당된 작업이 없을 때 우선순위가 높은 순서로 CPU를 할당하고 프로세스가 완료될 때까지 프로세스 교체가 일어나지 않음
SPN의 변형
- SPN + 에이징 기법 + 비선점형 스케줄링
- 에이징 기법은 SPN의 기아 현상을 해결하기 위한 방법
스케줄링 기준
- Response ratio가 높은 프로세스 우선
Response ratio(응답률)
- Response ratio = (대기시간 + 실행시간) / 실행시간
- SPN의 장점 + starvation(기아) 방지
- 여전히 실행시간 예측이 필요하다는 단점 존재

에이징 기법
시스템에서 특정 프로세스의 우선순위가 낮아 무한정 기다리는 경우를 방지하기 위한 방법. 기다린 시간에 비례해 일정 시간이 지나면 우선순위를 한 단계 높여주는 방법(대기 시간이 긴 프로세스를 배려)

5. MLQ (Multi-Level Queue)

레벨이 여러개인 ready queue
특징
- 작업, 우선순위 별 별도의 ready queue 가짐
  - 최초 배정된 큐를 벗어나지 못함(시스템 변화에 적응 못함)
  - 각각의 큐는 자신만의 스케줄링 기법 사용
- 큐 사이에는 우선순위 기반의 스케줄링 사용
장점
- 우선시간이 높은 ready queue는 응답시간이 빠름
단점
- 여러개의 큐 관리 등 스케줄링 오버헤드 발생
- 우선순위가 낮은 큐는 starvation(기아) 현상 발생가능
  - 큐를 여러 개 두더라도 우선순위가 낮으면 여전히 CPU 할당을 받지 못함

6. MFQ (Multi-Level Feedback Queue)

프로세스의 큐간 이동이 허용된 MLQ
- MLQ의 최초배정된 큐를 벗어나지 못해, 시스템 변화에 적용하기 힘든 단점을 극복하기 위해 나온 방법
특징
- 선점형 스케줄링
- 피드백을 통해 우선순위 조정
  - 현재까지의 프로세서 사용 패턴 활용
- 동적 우선순위 가짐
- 시스템 환경 변화에 적응 가능
장점
- 프로세스에 대한 사전 정보(실행시간)없이 SJF, SRTN, HRRN 기법의 효과를 볼 수 있음
단점
- 설계 및 구현 복잡(여러개의 큐, 큐간의 이동)
- 스케줄링 오버헤드가 큼(변화하는 우선순위)
- starvation(기아) 현상 문제
  - 여전히 우선순위 낮은 프로세스는 CPU 할당 받지 못함

MFQ의 변형

각 ready queue마다 다른 시간 할당량 배정
- 프로세스의 특성에 맞는 형태로 시스템 운영 가능
입출력(I/O)위주 프로세스들은 상위 단계의 큐로 이동으로 우선 순위 높임
- 프로세스가 block될 때 상위의 ready queue로 진입 진행
- 시스템 전체의 평균 응답시간을 줄이고, 입출력 작업 분산시킴
대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동
- 에이징(aging)기법

동시성과 병렬성

동시성 (Concurrency)

하나의 코어에서 여러 스레드가 번갈아가며 실행
여러 작업이 겹치는 기간에 실행될 수 있음을 의미
- 동시에 실행하는 것이 아닌, CPU가 작업마다 시간을 분할해 적절한 context switching을 통해 동시에 실행되는 것처럼 보이게 함
핵심목표
- 유휴시간의 최소화
  - 유휴시간 : 컴퓨가 작동가능한 상태인데 작업을 하고 있지 않은 시간
발생가능한 문제점
- Race Condition
  - 여러 프로세스가 하나의 자원에 접근해 서로의 실행결과에 영향을 주는 현상
- Deadlock
  - 여러 프로세스가 서로 상대방의 작업이 끝나기를 무한히 기다리는 현상
- Starvation
  - 특정 프로세스가 우선순위가 낮아 원하는 자원을 계속 할당받지 못하는 현상

병렬성 (Parallelism)

멀티코어에서 여러 스레드를 동시에 실행
동일한 시간에 독립적인 작업을 실행할 수 있음을 의미
- 동일성과 달리 여러작업을 다른 코어, 프로세스, 별도 컴퓨터등에서 동시 실행가능
예시
- 분산 컴퓨팅 시스템
발생가능한 문제
- 메모리 손상과 누수
  - 여러 작업이 어떤 자원을 공유하고 있는지 고려해야하기 때문

참고

일괄처리 시스템(Batch System)
- 온라인처럼 일에 대한 요청이 발생했을 때, 즉각적으로 처리하는 것이 아닌 일정기간 또는 일정량을 모아뒀다가 한번에 처리하는 방식
대화형 시스템(Interactive System)
- 온라인과 같이 일에 대한 요청에 대해 즉각적으로 처리하여 응답을 받을 수 있는 시스템
시분할 시스템(Time Sharing System)
- 각 프로세스에 CPU에 대한 일정시간을 할당하여 주어진 시간동안 프로그램을 수행할 수 있게하는 시스템
실시간 시스템(Real-time Systen)
- 데이터 발생 즉시, 또는 데이터 처리 요구가 있는 즉시 처리하여 결과를 산출하는 방식

Spring MVC와 Spring Boot HTTP 버전