스케줄링

스케줄링

스케줄러

• 시스템이 실행하고자 할 때 프로세서(CPU)를 프로그램들에게 할당하는 과정을 스케줄링이라한다
• 어떤 프로세스에게 자원을 할당할지 결정하는 커널 모듈
  • 프로세스는 자신의 임무를 모두 수행하고 사라질 때 까지 많은 큐를 돌아다니는데 이때 프로그램들은 제한된 프로세서(CPU)를 서로 사용하려고 한다. 운영체제(OS)는 이러한 프로세스중 하나를 택하는 데, 스케줄러가 이러한 역할을 담당한다.

장기 스케줄러(Long Term Scheduler)

• 작업 스케줄러(Job Scheduler), 승인 스케줄러 라고도 한다.
• 디스크내의 작업을 어떤 순서로 가져올지 결정하는 프로그램
• 디스크와 같은 저장장치에 작업들을 저장해놓고, 필요할 때 실행할 작업을 작업 큐에서 꺼내 준비 큐(Ready Queue)를 통해 메인 메모리에 적재
  • new -> ready 상태로 전이를 승인
• 현대의 시분할 시스템에서는 사용되지 않음

중기 스케줄러

• ready 큐 관리
• 메모리에 적재된 프로세스의 수를 동적으로 조절하기 위한 스케줄러
• 메모리에 수많은 프로세스가 적재되어 프로세스당 보유하고있는 메모리량이 극도로 적어지게 됨 -> 디스크 I/O가 수시로 발생하게 되어 시스템 성능이 크게 저하
• 이 경우 메모리에 올라와 있는 프로세스 중 일부로 부터 메모리를 통째로부터 빼앗아 그내용을 디스크의 스왑 영역에 저장 >스왑아웃(swap out)
  • 디스크로 스왑아웃 시켜야할 경우 봉쇄상태의 프로세스를 첫번째로 스왑아웃 시킴 (봉쇄상태의 프로세스는 당장 cpu를 획득할 가능성이 없기 때문)
  • 봉쇄상태의 프로세스들을 스왑아웃 시켜도 해결이 안될경우 준비 큐로 이동하는 프로세스를 추가적으로 스왑아웃 시킴

단기 스케줄러

• 프로세스 스케줄러, CPU스케줄러 라고도 함
• CPU를 할당할 프로세스를 선택하는 스케줄러
  • 준비 큐에있는 프로세스를 스케줄링 알고리즘을 통해 선택
• 준비 상태의 프로세스중에서 어떤 프로세스를 다음 번에 실행 상태로 만들 것인지를 결정함
• ready -> running 상태로 전이
  

	장기 스케줄러		단기스케줄러
new	->	ready	->	running

스케줄링 알고리즘

• CPU는 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행해야 합니다. 이때 어떤 프로세스를 다음에 처리할 지 선택하는 알고리즘을 스케줄링 알고리즘이라함
  

비선점 스케줄링

• 프로세스가 CPU를 점유하고 있으면 다른 프로세스가 뺴앗을 수 없는 방식
• 모든 프로세스에 대한 요구가 공정하게 처리가능하지만, 짧은 작업이 긴작업을 수행하는 프로세스 종료 시까지 대기 해야할 경우도 발생
• 응답시간을 예측 가능하고 일괄처리에 적합함

FCFS(First-Come-First-Served)

• 먼저 들어온 프로세스가 먼저 처리되는 알고리즘
• 장점
  • 가장 간단한 스케줄링 알고리즘
  • 오버헤드가 낮다 (프로세스 종료까지 대기 하기 때문에)
• 단점
  • 비선점식 알고리즘이기 때문에 대화식 프로세스에 적합하지 않음
  • 긴 수행시간을 가지고있는 프로세스가 자원을 점유하고 있을 경우, 다른 프로세스들이 그만큼 대기시간을 갖게된다. 이러한 현상을 Convey Effect라 한다

SJF(Shortest Job First)

• 각 작업의 프로세서 실행 시간을 이용하여 프로세서가 사용 가능할 때 실행 시간이 가장 짧은 작업에 할당
• 장점
  • Convey Effect를 해결 (실행시간이 짧은 작업을 먼저 실행하여 평균 대기시간이 다른 알고리즘에 비해 짧아짐)
• 단점
  • 초기의 긴 작업을 종료할 때 까지 대기시켜 기아 문제 발생 : 우선순위가 낮은 프로세스가 순서가 계속밀려 공평성에 위배
    • 에이징 기법으로 해결 ; 오래 기다린 프로세스는 에이징 카운트롤 올려 우선순위를 높임
  • 우선순위 측정이 어려움 : 사용자와 상호작용이 빈번할 경우 작업시간의 판단이 어려움

HRN (Highest Response Ratio Next)

• SJF에서 발생할 수 있는 기아현상을 해결하기 위해 만들어짐
• 서비스를 받기 위해 기다린 시간(대기 시간)과 CPU 사용 시간을 고려하여 스케줄링을 하는 방식
• 우선순위 = (대기 시간 + CPU 사용 시간) / CPU 사용시간
  • 응답을 주기까지 가장 오래 걸리는 시간을 비율로 환산
• 장점
  • SJF의 기아현상 완화
• 단점
  • 공평성 위배
  • 우선순위를 계속 계산해야하므로 오버헤드 증가

선점 스케줄링

• 현재 CPU를 점유한 프로세스의 작업이 종료 되지 않아도 다른 프로세스가 CPU를 점유 할수 있는 방식
• 우선 순위가 높은 프로세스를 빠르게 처리할수 있어 실시간 응답을 요구하는 시스템에 적합

RR(Round Robin)

• 현대적인 CPU 스케줄링 방식
• 각 프로세스는 동일한 할당시간(Time Slice)을 가지며 할당시간이 지나면 준비큐 맨끝으로 가서 CPU할당을 기다림
• 장점
  • 모든 프로세스가 공정하게 시간을 할당받음
  • 프로세스 최악의 응답시간을 아는데 유리
  • Convey Effect를 해결
• 단점
  • 하드웨어 타이머가 필요
  • Time Slice을 너무 짧게하면 잦은 Context Switching 으로 오버헤드가 발생
  • Time Slice을 너무 길게 하면 FCFS와 동일하게 동작

SRT(Shortest Remaining Time)

• SJF 와 RR 을 혼합한 방식
• 기본적으로 RR 스케줄링을 사용하지만, CPU 할당받을 프로세스를 선택 할때 남아있는 작업시간이 가장 적은 프로세스를 선택 (RR 스케줄링이 큐에 있는 순서대로 CPU 할당한다면 , SRT는 남은 시간이 가정 적은 프로세스를 선택, 남은 시간이 동일하다면 RR 순서대로 돌아가면서 실행)
• 장점
  • RR보다 Convoy Effect를 좀 더 해결가능
• 단점
  • 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 context switching을 해야 하므로 SFT 스케줄링에는 없는 작업이 추가
  • 운영체제가 프로세스의 종료 시간을 예측하기 어렵고 기아 현상이 일어남
    
    

Priority scheduling ; 우선순위 스케줄링

• 프로세스는 중요도에 따라 우선순위를 갖는데 이러한 우선순위를 반영한 스케줄링

• 비선점형 방식

  • SJF 스케줄링 : 작업 시간이 짧은 프로세스에 높은 우선순위를 부여한다.
  • HRN 스케줄링 : 작업 시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순위를 부여한다.

• 선점형 방식

  • SRT 스케줄링 : 남은 시간이 짧은 프로세스에 높은 우선순위를 부여

Multilevel Queue ; 다단계 큐 스케줄링

• 우선순위에 따라 준비 큐를 여러개 사용하는 방식
• 우선순위에 따라 다양한 스케줄링이 가능한 선점형 방식
• 각 큐는 절대적인 우선순위를 가지며 우선순위가 높은 큐가 모두 비어있기 전에는 낮은 우선순위 큐에 있는 프로세스를 실행 불가능
• 하나의 큐에서는 선점형 방식으로 프로세스들이 타임 슬라이스를 할당받아 작업이 진행되지만, 큐들 끼리는 비선점형 방식으로 상위 큐에서 프로세스들이 실행이 완료되기 전까지는 하위가 실행될 수 없다.

Multilevel Feedback Queue ; 다단계 피드백 큐 스케줄링

• 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완하는 방식
• CPU를 사용하고 난뒤, 프로세스의 우선순위가 낮아짐
• CPU를 사용한 프로세스는 원래 큐로 되돌아 가지 않고 우선순위가 낮은 큐의 끝으로 들어감