운영체제 - 프로세스 스케줄링

스케줄링

• 여러가지 작업의 처리순서를 결정하는 것
  • ex) 프로세스 스케줄링, 디스크 스케줄링 등
• 프로세스 스케줄링
  • 주어진 프로세스가 여러 개인 경우, 프로세스 처리순서를 결정하는 것

 

프로세스 스케줄링 단계

• 1. 상위단계 스케줄링: 작업 큐에 쌓여진 작업 들 중 어떤 것을 먼저 처리할 것인가?
  • 작업이 요청이 들어오면, 해당 작업을 프로세스를 만드는 작업
  • 운영체제에 따라 시스템의 자원을 효율적으로 이용 할 수 있도록 한다. 
  • CPU작업이 많은 것들 혹은 입출력장치가 많이 비어있을 경우 등 상황에 맞춰 자원이 효율적으로 운용될 수 있도록 한다. 
  • CPU를 할당받을 시간을 기다린다. 
• 2. 하위단계 스케줄링: 
  • 준비 큐에 있는 프로세스를 선택하여 사용 가능한 CPU를 할당(디스패치)하는 역할
  • 수행주체: 디스패처(dispater)
  • 하위단계 스케줄링을 하는 주체인 디스패처는 어떤 프로세스가 실행되게 해줄 것인가를 고민함.

• 3. 중간단계 스케줄링: 
  • 시스템에 부하가 많이 있을 경우, 단기적인 부하를 조절하도록 한다. 

 

스케줄링 기본 목표 - 스케줄링은 어떤 목표를 두고 할 것인지? 

• 공정성
  • 모든 프로세스가 적정 수준에서 CPU 작업을 할 수 있게 함 (한 프로세스만 CPU에 집중되지 않도록)
• 균형
  • 시스템 자원이 충분히 활용될 수 있게 함

 

운영체제의  유형에 따른 스케줄링의 목표

• 일괄체제 운영체제
  • 처리량의 극대화: 주어진 단위시간에 처리한 프로세스 수
  • 반환시간의 최소화: 특정 프로세스가 생성 시점부터 종료 시점까지의 소요시간
  • CPU 활용의 극대화
• 시분할 운영체제
  • 빠른 응답시간: 요청한 시점부터 반응이 시작되는 시점까지의 소요시간
    • ex) 사용자들이 시스템에 붙어서 질문을 했을 경우 바로바로 응답이 오는 시간
  • 과대한 대기시간 방지: 프로세스가 종료될 때까지 준비 큐에서 기다린 시간의 합
    • 일을 못하고 준비 큐에서 기다리는 시간을 최소화 할 수 있도록 한다. 
• 실시간 운영체제
  • 우선순위가 높은 작업이 들어왔을 때, 해당 작업은 무조건 특정 시간안에 완료되도록 해줘야 한다.
  • 처리기한을 맞춤   

 

 여러가지 스케줄링 목표에 따라 우선적으로 고려해야 할 기본적인 정책

• 선점 스케줄링 정책
  • 실행 중인 프로세스에 인터럽트를 걸고 다른 프로세스에 CPU를 할당할 수 있는 스케줄링 방식
  • 필요한 이유: 높은 우선순위의 프로세스를 우선 처리해야 하는 경우에 운용
    • ex) 실시간 시스템, 시분할 시스템
  • 대신, 문맥 교환에 따른 오버헤드가 발생
    • 운영체제는 문맥 교환이 매우 빠르게 실행도로록 만들어져야 한다.  
    • 문맥(context) : CPU의 모든 레지스터와 기타 운영체제에 따라 요구되는 프로세스 상태
    • 문맥 교환(context switching): CPU가 현재 실행하고 있는 프로세스의 문맥을 PCB에 저장하고 다른 프로세스의 PCB로부터 문맥을 복원하는 작업
    • 레지스터 정보들이 CPU에 활용되고  있을 때 문맥 교환의 상황이 됐다면, PC에 일시 보관이 되고 새롭게 시작될 프로세스의 PCB와 레지스터 정보들이 CPU에 전달된다. 
• 비선점 스케줄링 정책
  • 실행 중인 프로세스를 바로 준비상태로 전이시킬 수 없는 스케줄링 방식
    • 자발적으로 내놓지 않는다. 실행에서 바로 준비상태로 갈 수 없다. 실행중인 프로세스가 자발적으로 CPU를 내놓는다. 이럴경우 대기 상태에서 준비 상태로 간다. 종료 -> 준비는 갈 수 있지만, 실행 -> 준비로 갈 수 없다.
  • CPU를 할당받아 실행이 시작된 프로세스는 대기상태나 종료상태로 전이될 때까지 계속 실행상태에 있게 된다.
  • 강제적인 문맥교환이 없어 오베헤드가 발생하지 않음.
    • 자발적일 경우엔 있을 수 있지만, 비 자발적인 경우에는 없다. 
  • 긴 프로세스가 실행중이라면 짧은 프로세스가 오래 기다리게 되는 경우 발생.
    • 중요하고 짧음에도 불구하고 계속 기다려야하는 문제점이 있다. 

 

스케줄링 평가 기준

• 평가 기준 
  
  •  평균대기시간
    • 각 프로세스가 만들어지고 나서 준비되지 않고 대기되는 상태, 각 프로세스가 수행이 완료 될 때까지 준비 큐에서 기다리는 시간의 합의 평균 값 
  • 평균 반환 시간
    • 각 프로세스가 생성된 시점부터 수행이 완료된 시점까지의 소요시간의 평균 값
  • 예시
    • 시각 0에 프로세스 A는 준비 큐에 들어감 > CPU에 할당되어 동작 
    • 처음 만들어진 시간부터 CPU에서 실행되는 시간 
    • 대기시간의 의미와 반환시간의 의미를 잘 파악해야 한다. 

 

스케줄링 알고리즘

 

• FCFS 스케줄링 (First-Come First-Served)
  • 비선점 방식
  • 준비 큐에 도착한 순서에 따라 디스패치
  • 장점
    • 가장 간단한 스케줄링 기법
  • 단점
    • 짧은 프로세스가 긴 프로세스를 기다리거나 중요한 프로세스가 나중에 수행될 수도 있음
      • 시분할 운영체제나 실시간 운영체제에는 부적합
    • 프로세스들의 도착순서에 따라 평균반환시간이 크게 변함

 

• SJF 스케줄링 (Shortest Job First)
  • 비선점 방식
  • 준비 큐에서 기다리는 프로세스 중 실행시간이 가장 짧다고 예상되는 것을 먼저 디스패치
  • 장점
    • 일괄 처리 환경에서 구현하기 쉬움
  • 단점
    • 실제로는 먼저 처리할 프로세스의 CPU시간을 예상할 수 없음
    • 새로 들어온 짧은 프로세스가 긴 프로세스를 기다리거나 중요한 프로세스가 나중에 수행될 수도 있음
      • 시분할 운영체제나 실시간 운영체제에는 부적합

 

• SRT 스케줄링 (Shortest Remaining Time)
  • SJF 알고리즘 선점 방식
  • 준비 큐에서 기다리는 프로세스 중 남은 실행시간이 가장 짧다고 예상되는 것을 먼저 디스패치
  • 장점: SJF 보다 평균대기시간이나 평균반환시간에서 효율적임
  • 단점
    • 실제로는 프로세스의 CPU시간을 예상할 수 없음
    • 각 프로세스의 실행시간 추적, 선점을 위한 문맥교환 등 SJF보다 오버헤드가 큼 
    • ex) 실행 중이였던 레지스터 값을 PCB에 넣고 다시 꺼내고 하는 문맥교환. 

 

 

• RR 스케줄링 (Round Robin)
  • 선점 방식
  • 준비 큐에 도착한 순서대로 디스패치하지만 정해진 시간 할당량에 의해 실행이 제한된다.
  • 시간 할당량 안에 종료하지 못한 프로세스는 준비 큐의 마지막에 배치된다.
  • 장점
    • CPU를 독점하지 않고 공평하게 이용
      • 시분할 운영체제에 적합
  • 단점
    • 시간 할당량이 너무 크면 FCFS 스케줄링과 동일
    • 시간 할당량이 너무 적으면 너무 많은 문맥 교환 발생으로 오버헤드가 커짐
• HRN(Highest Response Ratio Next) 스케줄링
  • 비선점 방식
  • 준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치
    • 예상실행시간이 짧을 수록, 대기시간이 길수록 응답비율이 커짐
    • 응답비율 = 대기시간 + 예상 실행시간/ 예상 실행시간 = 대기시간 / 예상 실행시간 + 1 
  • 장점
    • SFJ 스케줄링의 단점을 보완
      • 예상실행시간이 긴 프로세스도 오래 대기하면 응답비율이 커져 나중에 들어오는 짧은 프로세스 보다 먼저 디스패치 가능
  • 단점
    • 실제로는 프로세스의 CPU 시간을 예상할 수 없음.
• 다단계 피드백 큐 스케줄링
  • 선점방식
  • 라운드로빈 스케줄링 확대형
  • I/O 중심 프로세스와 연산 중심 프로세스의 특성에 따라 서로 다른 시간 할당량 부여
  • 단계 1부터 단계 n까지 하나씩 준비 큐 존재
  • 단계 k는 단계 k+1에 피드백
  • 단계가 커질수록 시간 할당량도 커짐
  • 디스패치 후 대기상태로 갔다가 준비상태가 될 때까지는 현재와 동일한 단계의 준비 큐에 배치
  • 시간 할당량을 다 썼으면 다음 단계의 준비 큐로 이동 배치
  • 단계 k의 준비 큐에 있는 프로세스가 디스패치 되려면 단계 1부터 단계 k-1까지 모든 준비 큐가 비어 있어야만 함
  • 특징
    • I/O 위주 프로세스는 높은 우선권 유지
    • 연산 위주의 프로세는 낮은 우선권이지만 긴 시간 할당량

 

스케줄링 알고리즘

비선점: FCFS, SJF, HRN

선점: RR, 다단계 피드백 큐, SRT