맨위로가기

다단계 큐 스케줄링

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

다단계 큐 스케줄링은 짧은 작업과 입출력(I/O) 바운드 프로세스에 우선순위를 부여하고, 프로세서 사용량에 따라 프로세스를 분류하는 것을 목표로 하는 CPU 스케줄링 기법이다. 다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링을 개선한 방식으로, 프로세스가 큐를 이동할 수 있도록 하여 작업 유형에 따라 효율적인 관리를 가능하게 한다. 이 방식은 여러 개의 FIFO 큐를 사용하며, 프로세스는 큐의 우선순위에 따라 CPU를 할당받고, 시간 슬라이스 내에 완료되지 않으면 낮은 우선순위 큐로 이동한다. 유닉스 계열 운영체제는 다단계 피드백 큐를 채택하여 자원 대기 상태의 프로세스 큐 배치와 자원 기아 회피를 위한 큐 레벨 조정을 구현했다.

2. 설계 방침

다단계 피드백 큐 스케줄링은 다음과 같은 설계 목표를 충족하도록 의도되었다.


  • 짧은 작업에 우선권을 준다.
  • 입출력 관련 프로세스에 우선권을 준다.
  • 프로세서 사용량에 따라 프로세스를 분류한다.

2. 1. 기본 원칙

1962년 페르난도 J. 코바토가 처음 개발한 다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링에서 한 단계 발전된 방식이다. 다단계 큐 스케줄링에서는 프로세스가 하나의 큐에 영구적으로 할당되지만, 다단계 피드백 큐 스케줄링에서는 프로세스들이 큐를 갈아탈 수 있다. 이는 작업들이 서로 다른 유형의 작업들로 분류될 경우 사용된다.

다단계 피드백 큐 스케줄링은 다음과 같은 설계 목표를 충족하도록 의도되었다.

# 짧은 작업을 우선한다.

# I/O 바운드 프로세스(대화형 프로세스)를 우선한다.

# 프로세스의 성질을 신속하게 파악하고, 그것에 기초하여 스케줄을 수행한다.

2. 2. 목표

페르난도 J. 코바토가 1962년 처음 개발한 다단계 피드백 큐 스케줄링은 다음 목표를 달성하기 위해 설계되었다.

# 짧은 작업을 우선 처리한다.

# 입출력 위주 프로세스(대화형 프로세스)를 우선 처리한다.

# 프로세스의 성격을 빠르게 파악하여 스케줄을 수행한다.

3. 작동 방식

다단계 큐 알고리즘이 프로세스를 초기 큐 할당에 영구적으로 유지하는 반면, 다단계 피드백 큐는 프로세스를 큐 간에 이동시킨다.[4] 이 이동은 이전 시간 할당량의 CPU 버스트에 따라 달라진다.[5]


  • 프로세스가 너무 많은 CPU 시간을 사용하면 우선순위가 낮은 큐로 이동한다.
  • 프로세스가 I/O 바운드이거나 대화형 프로세스인 경우 우선순위가 높은 큐로 이동한다.
  • 프로세스가 우선순위가 낮은 큐에서 너무 오래 대기하여 기아 상태가 되면 우선순위가 높은 큐로 에이징된다.


여러 개의 FIFO 큐로 구성되어 있으며, 맨 앞의 FIFO가 가장 우선순위가 높다. 디스패처는 상위 FIFO 큐에서 실행 가능한 프로세스를 찾아서, 처음 발견된 프로세스를 실행한다.

프로세스가 특정 레벨의 큐에서 실행될 수 있는 기회는 (퀀텀을 다 사용한다면) 단 한 번이며, 즉시 한 단계 아래 레벨의 큐로 이동하게 된다. I/O 바운드 프로세스는 퀀텀을 다 소진하는 경우가 드물기 때문에 높은 레벨의 큐에 계속 존재할 수 있다.

3. 1. 기본 알고리즘

1962년 페르난도 J. 코바토가 처음 개발한 다단계 피드백 큐 스케줄링은 여러 개의 FIFO 큐를 사용하며, 다음과 같은 방식으로 작동한다.

# 새로운 프로세스는 최상위 FIFO 큐의 끝(꼬리)에 삽입된다.

# 어떤 단계에서 프로세스가 큐의 머리에 도달하면 CPU가 할당된다.

# 프로세스가 주어진 큐의 시간 슬라이스 내에 완료되면 시스템을 종료한다.

# 프로세스가 자발적으로 CPU 제어를 포기하면, 큐잉 네트워크를 떠나 다시 준비되었을 때 이전에 제어를 포기했던 동일한 큐의 꼬리에 삽입된다.

# 프로세스가 모든 양자 시간을 사용하면 선점되어 다음 하위 레벨 큐의 끝에 삽입된다. 이 다음 하위 레벨 큐는 이전 상위 레벨 큐보다 더 많은 시간 양자를 가진다.

# 이 방식은 프로세스가 완료되거나 기본 레벨 큐에 도달할 때까지 계속된다.

#:* 기본 레벨 큐에서 프로세스는 완료되어 시스템을 종료할 때까지 라운드 로빈 방식으로 순환한다. 기본 레벨 큐의 프로세스는 선착순 방식으로 스케줄링될 수도 있다.[6]

#:* 선택적으로, 프로세스가 I/O를 위해 차단되면 한 레벨 "승격"되어 다음 상위 큐의 끝에 배치된다. 이를 통해 I/O 바운드 프로세스가 스케줄러에 의해 우선시될 수 있으며, 프로세스가 기본 레벨 큐에서 "탈출"할 수 있다.

스케줄링을 위해, 스케줄러는 항상 최고 레벨 큐의 머리에서 프로세스를 선택하기 시작한다. 최고 레벨 큐가 비어 있는 경우에만 스케줄러는 다음 하위 레벨 큐에서 프로세스를 가져온다. 동일한 정책이 후속 하위 레벨 큐에서 선택하는 데 적용된다. 한편, 프로세스가 상위 레벨 큐에 들어오면 하위 레벨 큐의 프로세스를 선점한다.

또한, 새로운 프로세스는 짧은 시간 안에 완료될 것으로 예상하여 항상 최상위 큐의 꼬리에 삽입된다. 긴 프로세스는 시간 소비 및 상호 작용 수준에 따라 자동으로 하위 레벨 큐로 이동한다. 다단계 피드백 큐에서 프로세스는 주어진 큐 레벨에서 한 번만 완료될 기회를 가지며, 그렇지 않으면 하위 레벨 큐로 강제 이동된다.

3. 2. 우선순위 조정

다단계 피드백 큐 스케줄링에서는 프로세스가 CPU 시간을 너무 많이 사용하면 우선순위가 낮은 큐로 이동한다. 반대로, 프로세스가 I/O 바운드이거나 대화형 프로세스인 경우, 또는 우선순위가 낮은 큐에서 너무 오래 대기하여 기아 상태가 되면 우선순위가 높은 큐로 에이징된다.[4] 이러한 이동은 이전 시간 할당량의 CPU 버스트에 따라 달라진다.[5]

여러 개의 FIFO 큐가 사용되며, 작동 방식은 다음과 같다.

  • 새로운 프로세스는 최상위 FIFO 큐의 끝에 삽입된다.
  • 어떤 단계에서 프로세스가 큐의 머리에 도달하면 CPU가 할당된다.
  • 프로세스가 주어진 큐의 시간 슬라이스 내에 완료되면 시스템을 종료한다.
  • 프로세스가 자발적으로 CPU 제어를 포기하면, 큐잉 네트워크를 떠나 다시 준비되었을 때 이전에 제어를 포기했던 동일한 큐의 꼬리에 삽입된다.
  • 프로세스가 모든 양자 시간을 사용하면 선점되어 다음 하위 레벨 큐의 끝에 삽입된다. 이 다음 하위 레벨 큐는 이전 상위 레벨 큐보다 더 많은 시간 양자를 가진다.
  • 이 방식은 프로세스가 완료되거나 기본 레벨 큐에 도달할 때까지 계속된다.
  • 기본 레벨 큐에서 프로세스는 완료되어 시스템을 종료할 때까지 라운드 로빈 방식으로 순환한다. 기본 레벨 큐의 프로세스는 선착순 방식으로 스케줄링될 수도 있다.[6]
  • 선택적으로, 프로세스가 I/O를 위해 차단되면 한 레벨 "승격"되어 다음 상위 큐의 끝에 배치된다. 이를 통해 I/O 바운드 프로세스가 스케줄러에 의해 우선시될 수 있으며, 프로세스가 기본 레벨 큐에서 "탈출"할 수 있다.


다단계 피드백 큐에서 프로세스는 주어진 큐 레벨에서 한 번만 완료될 기회를 가지며, 그렇지 않으면 하위 레벨 큐로 강제 이동된다.

4. 스케줄링 매개변수

일반적으로 다단계 피드백 큐 스케줄러는 다음 매개변수로 정의된다.[6]


  • 큐의 개수
  • 각 큐의 스케줄링 알고리즘 (FIFO와 다를 수 있음)
  • 프로세스를 더 높은 우선순위 큐로 승격시키는 시기를 결정하는 방법
  • 프로세스를 더 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
  • 프로세스가 서비스를 필요로 할 때, 프로세스가 어떤 큐에 들어갈지를 결정하는 방법

5. UNIX 계열 운영체제의 구현

유닉스 계열 운영 체제는 다단계 피드백 큐를 채택했으며, 일반적으로 다음과 같은 개선 사항을 적용했다.


  • 자원이 대기 중 블록된 프로세스가 깨어났을 때, 이전과 동일한 레벨의 큐가 아닌 다른 큐에 배치한다. 예를 들어, 자원의 종류(디스크 I/O, 메모리, 통신 등)에 따라 반환할 큐의 레벨을 결정한다. 이를 통해 CPU 바운드였던 프로세스가 I/O 바운드로 변화하는 가능성에 대응한다(예: 대화형으로 계산 지시를 내리고, 계산이 끝나면 다음 지시를 기다리는 프로그램).
  • 낮은 레벨의 큐에 있으면서 실행 가능하지만 장기간 실행되지 않은 프로세스를 점차 높은 레벨의 큐로 이동시킨다. 이를 통해 자원 기아를 회피한다.

6. 비판적 관점

(이전 출력이 없으므로, 수정할 내용이 없습니다. 원본 소스와 함께 다시 요청해주세요.)

참조

[1] 서적 Operating System Concepts, Fourth Edition Addison-Wesley
[2] 서적 Proceedings of the May 1-3, 1962, spring joint computer conference on - AIEE-IRE '62 (Spring) 1962
[3] 서적 Operating Systems: Three Easy Pieces https://pages.cs.wis[...] Arpaci-Dusseau Books 2014
[4] 서적 Operating System Concepts, Fourth Edition Addison-Wesley
[5] 서적 Operating System Concepts, Fourth Edition Addison-Wesley
[6] 서적 Operating system concepts Wiley 2008
[7] 간행물 An Experimental Time-Sharing System http://larch-www.lcs[...] IFIPS 1962


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com