프로세서 스케줄링 알고리즘.md

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

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)
  • 데이터 발생 즉시, 또는 데이터 처리 요구가 있는 즉시 처리하여 결과를 산출하는 방식