밸~하

밸로그 여러분 안녕하세요.

오늘은 스케줄의 종류 2번째로 지난시간에 이어서
스케줄링에 대해서 알아보도록 하겠습니다.

프로세스의 스케줄링 방식에는 다양한 스케줄링 방식이 존재합니다.

오늘은 2개의 스케줄링 방식에 대해서 추가로 설명을 드리고 스케줄링이라는 주제를 마무리 해보려고 합니다.

그럼 바로 알아보겠습니다.

첫번째로 소개드릴 스케줄링은 바로
Round-Robin 스케줄링입니다.

OS 그리고 스케줄링에 대해서 조금이라도 공부하신분은 한번쯤은 들어보셨을 정도로 유명한 스케줄링 방식입니다.

그럼 바로 알아보겠습니다.

1. Round-Robin Scheduling

이 Round-robin scheduling의 정의에 대해서 알아보겠습니다.

Round-Robin 스케줄링이란?

• Round-Robin알고리즘은 Round-Robin원칙에서 유래되었습니다.

• Round-Robin원칙은 체스나 기타 경기에서 사용됩니다. 원칙은 참가자들이 순환하면서 각자 모든 상대와 경기를 치르는 형식으로 경기를 진행하는 방식입니다. 이러한 방식으로 공정성과 각 참가자가 모든상대와 경기를 할 수 있게됩니다.

• Round-Robin스케줄링은 멀티테스킹에서 가장 흔히 사용되는 스케줄링이자 가장 오래되고 구현하기 쉬운 스케줄링입니다.

• Round-Robin스케줄링은 Ready상태에 있는 각 작업이 제한된 시간(time slice)동안 순환 대기열에서만 차례로 실행됩니다.

• Round-Robin스케줄링은 Starvation현상이 발생하지 않고 모든 프로세스가 실행될수 있게 해줍니다.

이렇게 라운드 로빈 스케줄링에 대해서 간단히 알아보았습니다.

그럼 이 라운드 로빈 스케줄링은 어떤 주요한 특징을 가지고 있는지 알아보겠습니다.

Round-Robin 스케줄링의 특징

• Round-Robin은 선점형 알고리즘입니다.
• CPU는 사전에 정의된 time-slice/time-quantum이라고 불리는 시간만큼의 프로세스를 수행하고 다음 Ready상태에 있는 프로세스에 Resource를 할당해 줍니다.
• 이미 실행됬지만 주어진 시간안에 프로세스를 끝내지 못한 프로세스의 경우 다시 대기큐의 마지막에 추가가 됩니다.
• process별 time-slice는 최소여야합니다. 그러나 OS 마다 다르게 적용될 수 있습니다.
• 특정시간내에 이벤트에 반응하는 실시간 알고리즘 입니다.
• Round-Robin은 가장 오래되고, 공정하게 자원을 할당하고, 간단하게 구현할수있는 알고리즘입니다.
• 가장 전통적으로 OS에서 사용되는 스케줄링입니다.

Round-Robin 스케줄링은 이러한 특징들을 가지고있습니다.

가장 오래되고 폭넓게 사용되고 자주 사용된 스케줄링인 만큼 많은 refer들과 다양한 구현 방식이 존재합니다.

이번엔 Round-Robin Scheduling을 도입했을때의 장점과 단점에 대해서 설명을 드리겠습니다 .

Round-Robin Scheduling의 장점

• Starvation이나 Convoy효과를 방지할 수 있습니다.
• 모든 프로세스가 공정하게 CPU의 자원을 할당받아 사용할 수 있습니다.
• 모든 프로세스가 Priority에 구애받지 않고 실행됩니다.
• 실행 큐에 있는 전체 프로세스의 숫자를 알고 있다면, 같은 프로세스를 실행할때 Worst-case response time을 추정할 수 있습니다.
• 이 스케줄링 메소드는 burst time에 의존하지 않기에, Round-Robin스케줄링은 확장성이 용이합니다.
• 일단 한 프로세스가 특정 time-slice동안 실행되고 프로세스가 끝나지 않으면 대기큐의 가장 마지막에 들어가게 되고 다음 프로세스를 실행시킵니다(convoy effect방지)
• 선점된 프로세스들의 상태를 보관하여 OS가 Context Switching메서드를 사용하더라도 상태를 유지할 수 있습니다.
• 평균응답시간에서는 최고의 performance를 보여줍니다

Round-Robin Scheduling의 단점

• Time slicing이 너무 낮으면 프로세스의 결과물도 많이 줄어듭니다.
• Context switching시에 더많은 시간을 소모합니다.
• time Quantum에 높은 의존성을 가지고 있습니다.
• Priority를 설정할 수 없습니다.
• 중요한 작업에 Priority를 줄 수 없습니다.
• time slice가 낮을 수록 context switching시에 오버헤드가 높아집니다.
• 효율적인 time quantum을 찾는것은 매우 어려운 일입니다.

요약을 하면
라운드 로빈 알고리즘은 장점으로 time slice를 가지고 있지만 아이러니 하게도 timeslice에 높은 의존성을 가지고 있고 Priority를 설정할 수 없어 중요한 프로세스를 우선적으로 실행해야 할때에 효율적이지 않을수도 있습니다.

그렇기에 어떠한 작업을 할지에 따라서 적절한 스케줄링을 적용시키는것이 중요합니다.

두번째로 볼 것은 Backfill scheduling입니다.

2. Backfill scheduling

backfill scheduling이 무엇인지에 대해서 알아보겠습니다.

backfill scheduling이란?

• backfill scheduling은 순서에 관계없이 사용가능한 리소스를 더 잘 활용할수 있게하는 스케줄링 입니다.

• backfill scheduling은 다른 job의 실행이 늦춰지지 않는 선에서 다른 작업에 예약된 작업 슬롯을 사용할 수 있습니다.

• backfill을 사용하면 리소스를 과도하게 사용하지 않아도 대규모 병렬작업을 실행시킬 수 있습니다.

• busy cluster에서는, 프로세서 예약기능은 대규모 병렬작업을 더 빨리 예약하는데 도움을 줍니다. 그러나 기본적으로, 예약된 프로세서들은 대규모 작업이 시작되기 전까지는 유휴 상태 즉 실행되지 않고 대기상태로 남아있게 됩니다.

• 이러한 현상은 예약된 작업에 할당된 자원들이 대기큐에 있는상태로 실행상태로 바뀔때까지 기다리게 됨으로, LSF스케줄링의 작업수행능력을 감소시키게됩니다.

• backfill scheduling은 이러한 문제를 해결하기위해서 나왔습니다.

• backfill scheduling은 예약된 작업 슬롯들을 큰 작업이 실행되기 전에 실행되고 종료될수 있는 작업들을 실행시킬수 있습니다. 이러한 도입으로 인해 LSF의 자원사용 효율을 증가시킬수 있습니다.

그럼 이러한 backfill scheduling은 어떻게 동작하는지 알아보겠습니다.

backfill의 동작방식

• backfill scheduling의 경우, LSF scheduling은 실행 제한이 만료될때까지 작업이 실행 될 수 있다고 가정합니다.

• backfill scheduling은 클러스터의 모든 작업에 실행 제한이 있을때 가장 효율적으로 작동합니다.

• 실행 제한이 짧은 작업은 backfill작업으로 예약될 가능성이 높기 때문에, backfill 큐에 적절한 실행제한을 지정하는 사용자들은 향상된 처리시간을 얻을수 있습니다.

• 일단 큰 병렬 작업이 충분한 job slot들에 예약된다면, LSF 스케줄링은 예약된 슬롯에서 현재 실행중인 작업의 run limit를 기반으로, 앞서 이야기한 큰 병렬 작업의 시작시간을 계산합니다.

• 하지만 LSF스케줄링은 큰작업이 run limit가 정의되지 않은 작업을 기다리는 경우에는 backfill을 사용할 수 없습니다.

• 만약 LSF가 유휴작업슬롯을 backfill할수 있다면, 오직 대규모 작업의 시작시간전에 만료되는 run limit가 있는 작업만 예약된 작업슬롯을 사용할 수 있습니다.

• 즉, LSF는 run limit이 없는 작업에는 backfill을 사용할 수 없다는 것입니다.

이렇게만 보면 조금 어려우니 한 자료를 봐보겠습니다 .

출처 : IBM backfill

이 시나리오에서는, 4-CPU멀티 프로세서 host가 있다고 가정하겠습니다.

1. job1의 run limit이 2시간으로 예약되고 오전 8시에 실행됩니다.

2. 병렬작업 job2 는 모든 4개의 CPU를 필요로합니다. 그러나 이 작업은 바로 실행될수가 없습니다. 그이유는 job1이 1개의 CPU를 사용하고 있고 3개의 프로세서가 남아있기 때문입니다.

3. 8:30에는 오직 2개의 프로세스와 1시간의 timelimit 만 필요로하는 또다른 작업 job3가
   있습니다. 일단 job2는 10시까지 실행될수 없기에, 남은 CPU프로세서들은 job3에 의해 backfill되게 됩니다. 따라서 job3는 job2의 시작시간전에 작업을 완료할수 있고, 유휴 프로세서를 사용할 수 있게됩니다.

4. job3가 9:30,job1 이 10시에 끝나게 되면, job2가 10시 이후에 실행되게 됩니다.

위의 예시에서 만약 job3의 run limit이 2시간 이었다면 job2 의 예약된 유휴 자원을 backfill할 수 없었을 것입니다. 그리고 job2가 실행되고 종료된 이후에 실행될수 있을것입니다.

그럼 이러한 backfill은 어떤 한계를 가지고 있을까요?

backfill의 한계

• mbatchd가 재구성된 직후에는 작업 예상시작시간 이없습니다.

backfill과 job 유휴 한계

backfill작업은 다른작업이 이미 사용하고 있는 작업슬롯을 빌려서 사용하게 됩니다.
backfil작업은 작업슬롯을 먼저 예약한 작업과 동시에 실행되지 않습니다.
backfill은 host또는 프로세서에 대한 작업슬롯 제한에 도달한경우에도 backfill이 발생할 수 있습니다.
backfill은 사용자 또는 대기열의 작업 슬롯 제한에 도달한 경우 backfill이 실행될 수없습니다.

이렇게 backfill에 대해서도 알아봤습니다.

오늘 소개해드린 두가지 scheduling은 둘다 매력적인 scheduling인것은 분명합니다.

하지만 각각에 목표로하는 자원관리 방식에 따라서 적절한 스케줄링을 채용하는것이 중요한것 같습니다.

오늘의 포스팅은 여기까지입니다.

다음 시간에는 새로운 주제로 다시 오겠습니다.

감사합니다.