스케줄링 정리

스케줄링이란?

• 다중 프로그래밍을가능 하게 하는 것.
• CPU는 한번에 한가지의 작업만을 처리 가능 -> 따라서 여러 프로그램이 번갈아 수행되도록 스케줄링을 사용한다.
• 스케줄링을 사용함으로써 CPU 이용률을 극대화

❗ 즉, 시스템의 자원을 효율적으로 사용하기 위해 한 프로세스가 CPU를 언제 얼마나 차지할 것인가에 대한 순서 또는 방법을 결정짓는 작업

스케줄링은 왜 하는가?

1. 공정성 : 모든 프로세스에 공정하게 할당한다.
2. *처리율[각주:1] 증가 : 단위 시간당 프로세스를 처리하는 비율을 증가시킨다.
3. *CPU 이용률 증가 : 프로세스 실행 과정에서 주기억장치에 접근이나 입출력 명령 실행 등의 원인에 의해 발생할 수 있는 CPU의 낭비 시간을 줄이고, CPU가 순수하게 프로세스를 실행하는 데 사용되는 시간 비율을 증가시킨다.
4. 우선순위 제도 : 우선순위가 높은 프로세스를 먼저 실행한다.
5. 오버헤드 최소화 : 오버헤드를 최소화한다.
6. 응답시간 최소화 : 작업을 지시하고, 반응하기 시작하는 시간을 최소화한다.
7. 반환시간 최소화 : 프로세스를 제출한 시간부터 실행이 완료될 때까지 걸리는 시간을 최소화한다.
8. 대기시간 최소화 : 프로세스가 준비상태 큐에서 대기하는 시간을 최소화한다.
9. 균형 있는 자원의 사용 : 메모리, 입출력 장치 등의 자원을 균형있게 사용한다.
10. 무한 연기 회피 : 자원을 사용하기 위해 무한정 연기되는 상태를 회피한다.

❗ 처리율, CPU이용률, 응답시간, 반환시간, 대기시간은 스케줄링의 성능을 비교하는 기준이 된다.

스케줄링 성능 평가

시스템 관점의 지표

• CPU 이용률

  : 전체 시간 중에서 CPU 가 일을 한 시간이 비율을 나타낸다. CPU 대부분의 시스템에 하나만 존재하는 고비용 자원이므로 CPU 의 이용률은 시스템 전체의 성능과 밀접하게 관련된다. 따라서 CPU 가 일을 하지않는 시간 즉, 휴먼(idle) 상태에 머무르는 시간을 최소로 만드는 것이 중요한 목표이다.

• 처리량

  : 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇개를 끝마쳤는지 (CPU 버스트를 완료한 프로세스의 개수) 를 나타낸다. 즉 CPU 의 서비스를 원하는 프로세스 중 몇 개가 원하는 만큼의 CPU를 사용하고 이번 CPU 버스트를 끝내어 준비큐를 떠났는지 측정한 것이 처리량의 개념이다. ( 한정적인 자원에서 더 많은 프로세스들이 CPU 작업을 완료하기 위해서는 CPU 버스트가 짧은 프로세스에세 우선적으로 할당하는 것이 유리하다.

사용자 관점의 지표

• 소요시간

  : 프로세스가 CPU 를 요청한 시점부터 자신이 원하는 만큼 CPU 를 다 쓰고 CPU 버스트가 끝날 때까지 걸린 시간, 즉 준비 큐에서 기다린 시간과 실제로 CPU를 사용한 시간의 합을 뜻한다. 이는 해당 CPU 버스트가 완료될 때까지 소요된 시간으로, 프로그램이 시작해 종료하는 데까지 걸리는 시간이 아님을 주의해야한다.

• 대기시간

  : CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU 를 얻기 위해 기다린 시간의 합

• 응답시간

  : 프로세스가 준비 큐에 들어온 후 첫 번째 CPU 를 획득하기까지 기다린 시간, 대기시간은 준비 큐에 들어온 직후부터 이번 CPU 버스트가 끝날 때까지 준비 큐에서 기다린 시간의 합을 나타내는 반면, 응답시간은 준비 큐에 들어온 직후부터 첫 번째 CPU 를 얻기까지 걸린 시간만을 나타내어 두 척도는 다소 차이가 있다. 타이머 인터럽트가 빈번히 발생할수록 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 짧아지므로 처음 CPU를 얻기까지 걸리는 시간은 줄어들게 되어 응답시간이 향상된다. 응답시간은 대화형 시스템에 적합한 성능 척도로서 사용자 입장에서 가장 중요한 성능 척도라 할 수 있다.

스케줄링 알고리즘

• 선입선출 알고리즘(First-Come First-Served : FCFS)
  : 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식. 이 방식에서는 CPU 를 먼저 요청한 프로세스에게 CPU를 먼저할당하고, 그 프로세스가 자발적으로 CPU를 반납할 때까지 빼앗지 않는다. 먼저 온 요청을 먼저 처리하기 때문에 대단히 합리적인 스케줄링 방식인 것 같지만 경우에 따라 비효율적인 결과를 초래하기도 한다.
  Ex ) 다수의 프로세스 앞에 긴 작업 하나 때문에 기다려야 하는 상황이 생겨 평균 대기시간이 길어진다. 또한 CPU 버스트가 짧은 프로세스들이 앞의 긴 작업 하나 때문에 대기시간은 물론 I/O 장치들의 이용률까지도 동반 하락하게 된다.

• 최단작업 우선 스케줄링 (Shortest-Job First : SJF)

  : CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식. 이와 같은 할당 방식을 통해 CPU 버스트가 짧은 프로세스가 CPU를 먼저 사용하고 준비 큐를 빠져나가게 되면 프로세스들이 준비 큐에서 기다리는 전체적인 시간이 줄어들게 된다. ( SJF 스케줄링 알고리즘은 평균 대기시간을 가장 짧게 하는 최적 알고리즘으로 알려져 있다.) 


• 비선점형(nonpreemptive) 방식

  : 일단 CPU를 획득하면 그 프로세스가 CPU를 자진 반납하기 전까지는 CPU를 빼앗지 않는 방식. 프로세스가 수행 중 일 때, 짧은 CPU 버스트를 가진 프로세스가 도착할 경우 현재 수행중이던 프로세스를 수행 후 CPU 버스터가 짧은 프로세스 먼저 수행한다.


• 선점형 (preemptive) 방식

  : 준비 큐에서 CPU 버스트가 더 짧은 프로세스가 도착할 경우 CPU를 뺴앗아 더 짧은 프로세스에게 부여하는 방식 -> SJF의 선점형 구현 방식에서는 현재 CPU에서 실행 중인 프로세스의 남은 CPU 버스트 시간보다 더 짧은 CPU 버스트 시간을 가지는 프로세스가 도착할 경우 CPU를 빼앗게 된다. 이러한 SJF의 선점형 구현 방식을 SRTF(Shortest Remaining Time First) 라고 부른다. 프로세스가 수행 중 일 때, 짧은 CPU 버스트를 가진 프로세스가 도착한 경우 도착 시점에 CPU 버스터가 짧은 프로세스 먼저 수행한다.

• 우선순위 스케줄링

  : 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식. 이때 우선순위는 우선순위 값을 통해 표시하며 우선순위 값이 작을수록 높은 우선순위를 가지는 것으로 가정한다. 우선 순위를 결정하는 방식에는 여러가지가 있을 수 있다.
  EX) CPU 버스트 시간을 우선 순위 값으로 정의 - SJF 알고리즘과 동일한 의미를 가지게 된다.
우선순위 스케줄링도 SJF 와 마찬가지로 비선점형과 선점형 방식 으로 구현할 수있다.
우선순위 스케줄링 방식에서의 문제점 중 하나는 기아 현상이 발생할 수 있다는 점이다. (우선순위가 높은 프로세스가 계속 도착하는 상황에서 우선 순위가 낮은 프로세스는 CPU를 얻지 못한 채 계속 기다려야 할 수 있기 때문이다. 이러한 문제점을 해결하기 위해 노화(aging) 기법을 사용할 수 있다.
  ❗ 노화 기법 이란 ?
  : 기다리는 시간이 길어지면 우선순위를 조금씩 높여, 언젠가는 가장 높은 우선순위가 되어 CPU 를 할당받을 수 있게 해주는 방법


• 라운드 로빈 스케줄링
  : 시분할 시스템의 성질을 가장 잘 활용한 새로운 의미의 스케줄링 방식. 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되며, 이 시간이 경과하면 해당 프로세스로부터 CPU를 회수해 준비 큐에 줄 서 있는 다른 프로세스에게 할당한다. 그러면 이 프로세스는 준비 큐의 제일 뒤에 가서 줄을 서 다음번 차례가 오기를 기다리게 된다. 이때 각 프로세스마다 한 번에 CPU 를 연속적으로 사용할 수 있는 최대시간을 할당시간(time quantum) 이라고 부른다. 할당 시간이 너무 길면 FCFS와 같은 결과를 나타내게 되고, 너무 짧으면 CPU 를 사용하는 프로세스가 빈번하게 교체되어 문맥교환의 오버헤드가 발생한다. 라운드 로빈 스케줄링은 여러 종류의 이질적인 프로세스가 같이 실행되는 환경에서 효과적이다. SJF 스케줄링의 경우 평균 대기시간 측면에서는 가장 우수한 결과를 보장하지만, CPU 버스트 시간이 짧은 프로세스에게만 유리하고 CPU 버스트 시간이 긴 프로세스들을 전체 시스템의 성능을 취해 희생해야한다. 이에 비해 라운드 로빈 스케줄링은 공정한 스케줄링 방식이라 할수 있다. CPU 버스트 시간을 매우 작은 단위로 나누어 실행하기 때문에 자신이 CPU를 쓰고자 하는 양이 적으면 소요시간이 짧이지고, 자신이 CPU 를 쓰고자 하는 양이 많으면 소요시간도 거기에 비례해 길어진다.

• 멀티레벨 큐
  : 준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법을 말한다. 프로세스들이 CPU를 기다리기 위해 한 줄로 서는 것이 아니라 여러 줄로 서는 것이다. CPU 는 하나밖에 없으므로 이 경우 어떤 줄에 서 있는 프로세스를 우선적으로 스케줄링할 것인가 하는 문제가 발생한다. 또한 프로세스가 도착했을 때 어느 줄에 세워야 할지 결정하는 메커니즘도 필요하다. 일반적으로 멀티레벨 큐에서 준비 큐는 대화형 작업을 담기 위한 전위 큐(foreground queue)와 계산 위주의 작업을 담기 위한 후위 큐(background queue)로 분할하여 운영된다. 전위 큐에서는 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용하는 반면, 계산 위주의 작업을 위한 후위 큐에서는 응답시간이 큰 의미를 가지지 않기 때문에 FCFS 스케줄링 기법을 사용해 문맥교환 오버헤드를 줄이도록 한다. 멀티레벨 큐에서는 또 다른 스케줄링이 필요한데, 이는 큐 자체에 대한 스케줄링이다. 즉 여러 개의 준비큐에 대해서 어느 큐에 먼저 CPU를 할당할 것인지 결정하는 스케줄링이 필요한 것이다. 큐에 대한 스케줄링으로 가장 쉽게 생각할 수 있는 방식은 고정 우선순위 방식(fixed priority scheduling) 이다. 이 방식에는 큐에 고정적인 우선순위를 부여해 우선순위가 높은 큐를 먼저 서비스하고 우선순위가 낮은 큐는 우선순위가 높은 큐가 비이 있을 때에만 서비스하게 된다. 고정 우선순위 방식 외에 타임 슬라이스(time slice) 방식을 사용할 수 고 있는데, 이는 큐에 대한 기아 현상을 해소할 수 있는 방식으로, 각 큐에 CPU 시간을 적절한 비율로 할당한다. EX) 전체 CPU 시간 중 전위 큐 80%, 후위 큐 20%를 할당해 스케줄링하는 방식


• 멀티레벨 피드백 큐

  : CPU 를 기다리는 프로세스를 여러 큐에 줄 세운다는 측면에서 멀티레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다. 멀티 레벨 피드백 큐는 프로세스들의 다양한 성격을 반영해 구현할 수 있다. 예를 들면 우선순위 스케줄링에서 기아 현상을 해결하기 위해 등장했던 노화 기법을 멀티레벨 피드백 큐 방식으로 구현할 수 있다. 우선순위가 낮은 큐에서 오래 기다렸으면 우선순위가 높은 큐로 승격시키는 방식을 이라 할수 있다.


• 다중처리기 스케줄링
  : CPU가 여러 개인 시스템을 다중처리기 시스템이라고 부른다. 다중처리기 환경에서의 CPU 스케줄링은 CPU가 하나인 시스템에서보다 더욱 복잡한 문제가 있다. 이러한 환경에서는 프로세스를 준비 큐에 한 줄로 세워서 각 CPU가 알아서 다음 프로세스를 꺼내어가도록 할 수 있다. 예를 들어, 은행창구에서 번호표를 통해 순서를 정해 놓고 한 고객에 대한 처리가 끝나면 다음 번호의 고객을 부르는 방식이다. 그러나 반드시 특정 CPU 에서 수행 되어야 하는 프로세스가 있는 경우에는 문제가 더욱 복잡해진다. 이런 상황에서는 한 줄이 아니라 각 CPU 별로 줄 세우기를 할 수도 있다. 한편 여러 줄로 줄 세우기를 하는 경우 일부 CPU 에 작업이 편중되는 현상이 발생할 수 있다. 이와 같은 현상을 방지하기 위해 각 CPU별 부하가 적절히 분산되도록 하는 부하균형(load balancing) 메커니즘을 필요로 한다. 다중처리기 스케줄링의 방식은 대칭형 다중처리(symmetric multi-processing) 와 비대칭형 다중처리(asymmetric multi-processing) 로 나누어 볼수 있다.
  대칭형은 각 CPU 가 각자 알아서 스케줄링을 결정하는 방식이고, 비대칭형은 하나의 CPU 가 다른 모든 CPU 의 스케줄링 및 데이터 접근을 책임지고 나머지 CPU 는 거기에 따라 움직이는 방식을 말한다.

• 실시간 스케줄링(real-time system)
  : 우리가 흔히 사용하는 시분할 시스템에서는 작업의 처리가 빠를수록 좋지만 특정 시간 이내에 처리하지 못했다고 해서 심각한 상황이 발생하는 것은 아니다. 즉 작업에 데드라인이 존재하지 않는다. 이와 달리 실시간 시스템에서는 각 작업마다 주어진 데드라인이 있어 정해진 데드라인 안에 반드시 작업을 처리해야한다.

• 경성 실시간 시스템(hard real-time system)
  : 미사일 발사, 원자로 제어 등 시간을 정확히 지켜야 하는 시스템을 만한다. 이러한 시스템에서는 정해진 시간 안에 반드시 작업이 완료되도록 스케줄링해야 한다.

• 연성 실시간 시스템(soft real-time system)
  : 데드라인이 존재하기는 하지만 데드라인을 지키지 못했다고 해서 위험한 상환이 발생하지는 않는다. 멀티미디어 스트리밍 시스템이 연성 실시간 시스템의 대표적인 예이다.

스케줄링 알고리즘 평가 :

방법으로는 큐잉모델((que-ueing model), 시뮬레이션(simulation), 구현 및 실측(implementation & measurement) 방식이 있다.

• 큐잉모델((que-ueing model)
  : 주로 이론가들이 수행하는 방식으로, 확률분포를 통해 프로세스들의 도착률과 CPU의 처리율을 입력값으로 주면 복잡한 수학적 계산을 통해 각종 성능지표(performance index) 인 CPU의 처리량, 프로세스의 평균 대기시간 등을 구하게 된다.

• 시뮬레이션(simulation)
  : 실제 시스템에 구현해 수행시켜보는 것이 아니라 가상으로 CPU 스케줄링 프로그램을 작성한 후 프로그램의 CPU 요청을 입력값으로 넣어 어떠한 결과가 나오는지를 확인하는 방법. 입력값은 가상으로 생성할 수 도 있고 실제 시스템에서의 CPU 요청 내역을 추출해 사용할 수도 있다. 이때 실제 시스템에서 추출한 입력값을 트레이스(trace) 라고 부른다. 트레이스는 몇 초에 어떤 프로세스가 도착하고, 각각 CPU 버스트 시간을 얼마로 하는지에 대한 정보를 시간 순서대로 적어놓은 파일

• 구현 및 실측(implementation & measurement)
  : 이온가와 정반대인 구현가들이 수행할 수 있는 방식으로, 운영체제 커널의 소스 코드 중 CPU 스케줄링을 수행하는 코드를 수정해서 커널의 컴파일한 후 시스템에 설치하는 과정을 필요로 한다. 그런 다음 동일한 프로그램을 원래 커널과 CPU 스케줄러를 수정한 커널에서 수행시켜보고 실행 시간을 측정하여 알고리즘의 성능을 평가한다.

참고 : https://s1107.tistory.com/6