프로세스 스케줄링

https://chichoon.tistory.com/121

[Rank 3] Philosophers - 프로세스와 스레드

앞선 포스팅 (좀 오래된 포스팅이긴 하지만…) 에서 프로세스와 스레드의 차이를 알아보았다

오늘은 프로세스 스케줄링에 대해 공부해보도록 하자

프로세스 스케줄링이란?

프로세스가 생성되고 실행될 때 필요한 자원들을 해당 프로세스에게 할당하는 작업

앞 포스팅에도 적었듯 프로그램이 메인 메모리에 적재된 상태가 프로세스이므로 메인 메모리에는 많은 프로세스들이 존재한다

하지만 프로세스를 처리할 수 있는 CPU는 단 하나밖에 없다 (서버용 컴퓨터 등 특수한 컴퓨터는 CPU가 여러 개 있기도 하지만, 이러나저러나 CPU 수가 프로세스 수에 비해 제한적인 것은 맞다)

게다가 사람도 두 가지 생각을 한번에 하면 과부하걸리듯이… CPU도 한 번에 하나의 작업밖에 처리할 수 없다

따라서 어떤 프로세스에 먼저 자원을 할당하고 실행시켜 줄 지, 쉽게 말하면 어느 프로세스가 CPU를 차지할 것인지 결정하는 것이 프로세스 스케줄링이다

프로세스 스케줄링 덕에 여러 프로그램 (프로세스) 을 동시에 실행시키고 있는 것처럼 보이는 것이다

왜 하는가요

• 프로세스 처리율 (시간 당 작업량) 을 늘릴 수 있다
• CPU를 최대한으로 활용할 수 있다 (노는 CPU가 없도록 한다)
• 프로세스간 공평하게 자원을 배분해줄 수 있다
• 중요한 프로세스들에겐 우선권을 주고, 프로세스가 여러 개 돌아도 안정적으로 동작하도록 하며, 프로세스가 무한 대기 상태에 빠지지 않게 한다
• 시스템 자원이 늘어나거나 줄어들면 이를 적극 반영해야 한다

프로세스들을 최대한 최적의 순서로 배정해주고, 시스템의 자원을 효율적으로 배분하고 사용하게 하기 때문에 그만큼 효율이 올라간다

프로세스 스케줄링 용어

Burst

어떤 현상이 짧은 시간동안 집중적으로 발생하는 현상

• CPU Burst
  • 프로세스 내에서 CPU 명령 작업이 연속으로 발생하는 것
• I/O Burst
  • 프로세스 내에서 입출력 작업이 연속으로 발생하는 것

CPU Burst와 I/O Burst는 교대로 나타나며, 프로세스의 종류에 따라 Burst 발생 시간이 달라진다

Bounds

• CPU Bound
  • CPU Burst가 많이 일어나는 프로세스
  • I/O (입출력 요구) 빈도가 낮다
  • 연산 처리가 많은 작업 (채굴, 머신러닝 등) 이 CPU Bound에 속함
  • 프로세스 진행 속도가 CPU 속도와 연관이 깊음
• I/O Bound
  • I/O Busrt가 많이 일어나는 프로세스
  • I/O 하위 시스템 수행 빈도가 더 높다
  • 프로세스 진행 속도가 CPU 속도와 연관이 낮음
• Memory Bound
  • 프로세스 진행 속도가 사용가능한 메모리 양과 액세스 속도에 의해 제한됨
  • 많은 양의 메모리를 사용하는 작업이 Memory Bound에 속함

프로세스 스케줄링 종류

장기 스케줄링 (Long term Scheduling)

• 어떤 프로세스가 얼마만큼의 시스템의 자원 (메모리 영역) 을 차지하도록 할 것인지 결정하고, 준비 상태 큐 (Ready Queue) 로 보낸다
  • Pool에서 프로세스들을 선별하여 메모리에 적재한다
    • 메모리와 디스크 사이의 스케줄링을 담당한다고 볼 수 있다
  • 이때 CPU Bound 프로세스와 I/O Bound 프로세스를 적절히 섞어 적재해준다
    • CPU Bound 프로세스는 연산량이 많아 CPU의 비중이 크다
    • I/O Bound 프로세스는 I/O 작업 위주로 하기 때문에 CPU 비중이 비교적 적다
  • CPU Bound 프로세스가 많이 적재되면 CPU의 부담이 커지고 사용자와의 상호작용 (입/출력) 이 적어진다
  • I/O Bound 프로세스가 많이 적재되면 입출력을 기다리느라 CPU의 대기 시간이 커진다
• 상위 스케줄링이라고도 하며, 작업 스케줄러에 의해 수행된다
• 수행 빈도가 적고 (수십 초 ~ 수 분에 한번), 느리게 동작한다
• 요즘은 가상 메모리 관리 시스템이 상당히 발전하여 메모리를 거의 무한대처럼 사용할 수 있기 때문에 (진짜로 무한대인건 아님) 장기 스케줄링은 생략되는 경우가 많다고 한다
  • 장기 스케줄링이 생략되면, 실행시킨 프로세스는 전부 메모리에 올라오고 준비 상태 큐에 적재된다

중기 스케줄링 (Middle Term Scheduling)

• 장기 스케줄러, 단기 스케줄러 사이에서 부하를 조절하는 역할을 맡는다
• 어떤 프로세스들이 메모리 공간을 할당받을 지 결정하며, 이를 통해 CPU 부하를 해결한다
  • CPU를 할당받으려는 프로세스가 많다는 것은 그만큼 메모리를 할당받은 프로세스가 많다는 뜻이다 (장기 스케줄러에 의해 메모리에 적재됨)
  • 메모리를 할당받은 프로세스가 과하게 많아질 경우, 각 프로세스별로 할당받을 수 있는 메모리 양도 극도로 줄어들게 되며, 시스템이 과부하된다
  • 시스템에 과부하가 걸리면 단기 스케줄러에게 CPU를 할당받은 프로세스마저도 주소 공간이 부족해 실행에 지장이 생기고, 시스템의 성능이 심각하게 저하된다
• CPU 부하를 해결하기 위해 프로세스를 봉쇄 (suspended) 상태로 만든다
  • 프로세스를 일시 대기 상태로 만들면, 해당 프로세스가 할당받은 메모리를 통째로 디스크의 스왑 영역에 보내버린다 (swap out)
  • 우선순위가 가장 낮거나, 일정 시간동안 활성화되지 않은 프로세스가 여기에 들어간다
• 메모리 공간에 여유가 생기면, 봉쇄 상태의 프로세스는 봉쇄 준비 (ready) 상태로 변한다
  • 이때 디스크의 스왑 영역에 보내진 메모리는 중지 대기 상태가 풀릴 때 다시 시스템 메모리로 돌아온다 (swap in)
• 시스템에서의 작업 승인 여부와 작업들에 대한 CPU 할당 과정 사이에서 버퍼 역할을 해준다

단기 스케줄링 (Short Term Scheduling)

• 프로세스가 실행되기 위해 CPU를 할당받는 시기와, 특정 프로세스를 지정하는 작업을 의미한다
• 장기 스케줄러에 의해 준비 상태 큐에 적재된 프로세스들 중 하나를 선별해 CPU에게 할당하고, 실제 작업을 시킨다
  • 이때 프로세스 하나를 선별하기 위해 사용되는 것이 스케줄링 알고리즘이다
• 프로세서 스케줄링, 하위 스케줄링이라고도 다며, 프로세스 스케줄러에 의해 수행된다
• 자주 수행되고 (밀리세컨드 이하의 단위마다 한 번씩 수행), 빠르다
• 스케줄러, 스케줄링이라는 단어는 보통 단기 스케줄러를 가리킨다

프로세스 스케줄링 큐 종류

작업 큐 (Job Queue)

상태 불문, 모든 프로세스가 관리되는 큐

여기에 있는 큐는 메모리를 할당받지 않은 프로세스일 수도 있다

준비 큐 (Ready Queue)

CPU 할당을 기다리는 프로세스들이 관리되는 큐

여기에 적재된 프로세스들은 전부 준비 상태이다

이 큐에 프로세스들을 적절히 줄세우기 위해 스케줄링 알고리즘을 사용한다

장치 큐

대기 상태로 시스템 또는 장치 입출력을 기다리는 프로세스들이 이곳에 적재된다

장치 컨트롤러가 관리하며, 프로세스의 장치 입출력 처리가 끝나면 장치 컨트롤러가 인터럽트를 발생시키며 프로세스를 준비 큐로 보낸다

프로세스의 상태

생성됨 (new)

프로세스가 생성되는 단계

커널 공간에 PCB (Process Control Block) 이 생성되었다

PCB는 운영체제가 특정 프로세스를 관리하기 위한 정보가 들어있다

생성된 프로세스는 장기 스케줄러에 의해 준비 큐에 적재되고, 준비 상태에 들어간다

준비 상태 (Ready)

프로세스가 CPU 사용을 기다리는 상태

장기 스케줄러에 의해 프로세스가 메모리에 적재된 상태로, 아직 CPU 사용권을 받지는 않았지만 CPU를 할당받으면 바로 사용할 수 있는 대기 상태이다

준비 큐에 있는 모든 프로세스가 이 상태이다

• 준비 큐는 연결 리스트로 이루어져 있으며, 각각의 노드가 프로세스를 하나씩 가리킨다
• Ready 상태인 프로세스들은 무조건 이 큐에 적재되고, 다른 상태로 바뀌면 큐에서 빠져나간다

실행 상태 (Running)

프로세스가 CPU를 할당받아 명령들을 실행중인 상태

각 시스템당 CPU는 일반적으로 한 개이기 때문에 Running 상태의 프로세스는 단 하나밖에 없다

대기 상태 (Waiting / Blocked)

프로세스가 I/O 작업 처리 또는 특정한 이벤트가 발생하여 대기중인 상태

입출력을 받고 처리가 끝날 때까지 이 상태에 머무르며, 처리가 끝나면 준비 큐에 다시 적재되고 Ready 상태로 변한다

Running 상태의 프로세스가 입출력 처리 단계에 들어가면 처리 완료까지의 시간이 상당히 걸리기 때문에 다른 프로세스들이 CPU를 할당받지 못하고 그대로 CPU 낭비가 발생하게 된다

이를 방지하기 위해 존재하는 상태로, 입출력 처리를 하는 프로세스는 CPU를 반납하고 해당 처리가 끝날 때까지 장치 큐에 올라간다

장치 큐에 있는 프로세스가 끝나면, 디스크 컨트롤러가 인터럽트를 발생시키고 프로세스는 다시 준비 큐로 이동한다

실행 종료 (terminated)

프로세스가 실행이 완료되어 모든 자원을 반납하였다

커널 공간 안에 PCB는 남아있다

봉쇄 중단 (Suspended Block)

중기 스케줄러에 의해 프로세스의 수행이 중지된 상태

대기 상태에 있던 프로세스가 이 상태로 바뀔 수 있다

이 상태의 프로세스는 자신이 할당받은 자원을 디스크로 스왑 아웃한다

대개 메모리 부족 때문에 봉쇄 중단 상태에 들어가며, 우선순위가 낮거나 오랫동안 실행되지 않은 프로세스가 먼저 봉쇄 중단되는 경향이 있다

봉쇄 준비 (Suspended Ready)

봉쇄 중단과 마찬가지로, 중기 스케줄러에 의해 프로세스의 수행이 중지된 상태

준비 상태에 있던 프로세스나 생성된 프로세스가 이 상태로 바뀔 수 있다

또는 봉쇄 중단 상태의 프로세스가 메모리 여유가 생기면 이 상태로 바뀔 수도 있다

여전히 자원은 디스크에 스왑 아웃 되어있는 상태로, 메모리 여유가 생기면 준비 상태로 돌아간다

스케줄링 기법

선점 스케줄링 (Pre-emptive)

운영체제가 CPU 분배 권한을 들고 있으며, 가장 자원을 필요로 하는 프로세스에게 요청이 올 때마다 CPU를 분배하고, 필요에 따라 CPU 사용 권한을 뺏을 수도 있다

하나의 프로세스가 이미 CPU를 차지하고 수행되고 있더라도, 다른 프로세스가 현재 프로세스를 쫒아내고 자신이 CPU를 차지할 가능성이 있는 스케줄링 방식이다

쉽게 말해 맥도날드에서 햄버거 살 때 빨리 받고 싶은 사람이 새치기해서 먼저 주문할 수도 있다

• 빠른 응답시간을 요하는 시스템 (대화형 시스템) 에게 적합하다
• 스케줄러 호출 빈도가 높고, Context Switching 때문에 오버헤드 (추가적인 시간과 메모리 소요) 가 발생한다
• 언제 어떤 요청이 발생할 지 예측할 수 없다
• 비슷한 우선순위의 프로세스들 끼리 경쟁 상태에 돌입할 수도 있다
• 한 프로세스가 데이터를 수정하는 중에 다른 프로세스에게 CPU 주도권이 넘어간다면, 해당 데이터의 정보가 이상해질 수 있다 (일관성 없어짐)

대표적인 선점 스케줄링 기법 알고리즘으로 라운드로빈, Shortest Remaining Time, 선점 우선순위 등이 있다

비선점 스케줄링 (Non-Preemptive)

모든 프로세스가 스케줄된 순서대로만 CPU를 점유하며, 한 프로세스가 CPU를 사용하고 있다면 다른 프로세스는 이를 건드릴 수 없다

맥도날드에서 새치기 못하게 줄 양 옆에 총 든 경찰이 있다고 생각해 보자

나는 아무리 배가 고파도 절대로 새치기를 할 수 없다

나는 10초만에 주문할 수 있다고 해도, 앞 사람이 10분 넘게 주문이 걸린다고 해서 밀어낼 수가 없는 것이다

• 모든 프로세스에게 공정하게 돌아간다
• 스케줄러 호출 빈도가 낮기 때문에, 오버헤드가 적다
• 응답 시간을 예측할 수 있다
• 우선순위가 높은 프로세스는 마냥 기다릴 수밖에 없기 때문에, 비효율적이다
• 수행시간이 짧은 프로세스들이 수행시간이 긴 프로세스들을 기다려야 하는 상황 때문에 처리율이 떨어질 수 있다

대표적인 비선점 스케줄링 기법 알고리즘으로 FCFS (선입선출), Shortest Job First, Highest Response Next 등이 있다

스케줄링 알고리즘

평가 기준

• CPU 이용률: 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율
• 처리량: CPU가 단위시간당 처리하는 프로세스의 개수
• 총 처리 시간: 프로세스가 시작해서 끝날 때까지 걸린 시간
• 대기시간: 프로세스가 준비완료 큐에서 대기하는 시간의 총 합
• 응답시간: 대화식 시스템에서 요청 후 첫 응답이 오기까지 걸린 시간

선입선처리 스케줄링 (First Come First Served = FCFS)

CPU에 먼저 도착한 순서대로 (먼저 요청한 순서대로) 자원을 제공받는다

비선점 방식으로, 한 프로세스가 자원을 사용하고 있다면, 다른 프로세스는 대기한다

구현이 아주 쉽고, 모든 프로세스가 언젠가는 무조건 실행된다

다만 프로세스 수행 시간이 길든 짧든, 우선순위가 어떻든 무조건 먼저 요청한 프로세스가 CPU를 먼저 점유하기 때문에, 수행 시간이 짧은 프로세스들이 마냥 기다리게 될 수 있다

이러한 문제점을 호위효과 (Convoy Effect) 라고 부른다

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

Shortest Process Next = SPN 이라고도 한다

대기 작업들 중 CPU Burst Time (CPU 요구량, 실행시간) 이 제일 적은 작업에 CPU를 할당한다

비선점 SJF와 선점 SJF가 있다

• 선점 SJF는 한 프로세스가 실행중일 때, 다른 더 짧은 실행시간을 갖는 프로세스가 들어올 경우 해당 프로세스로 교체하므로, 평균 대기 시간이 더 짧다
• 비선점 SJF는 현재 실행중인 프로세스를 교체하진 않는다

평균 응답 시간이 최소화되지만, 실행시간이 짧은 프로세스들 때문에 실행시간이 긴 프로세스의 우선순위가 계속 밀려나 무한 대기에 빠질 가능성이 있다

이러한 현상을 기아 (Starvation) 이라고 한다

그 외에도 실행 시간을 예측할 수 없거나, 짧은 작업에 우선순위를 높게 부여한다는 점에서 공정하지 않은 방식이라는 단점이 있다

최상 응답 비율 순서 스케줄링 (Highest Response Ratio Next = HRRN)

대기 시간과 실행 시간을 모두 고려하여 우선순위를 결정한다

이때 대기 시간과 실행 시간을 이용하여 ((대기 + 실행) / 실행) 최상 응답 비율을 구하기 때문에 최상 응답 비율 순서 스케줄링이라는 이름이 붙었다

FCFS와 SJF의 단점을 보완한 느낌의 알고리즘으로, 실행 시간이 긴 프로세스에게도 공평하게 작업 시간이 돌아간다

또한 FCFS, SJF와 비슷하게 비선점 스케줄링이다

기한부 스케줄링 (Deadline)

작업을 반드시 명시된 시간이나 기한 내에 완료하도록 계획하는 스케줄링

실시간 운영체제에서 사용되며, 실시간 운영체제에서는 입력된 모든 작업을 반드시 주어진 기한 (데드라인) 내에 마쳐야 하기 때문에 이를 이용하여 우선순위를 지정하고 작업을 수행한다

명시된 시간 내로 작업이 끝나지 않을 경우, 작업을 삭제하고 준비 큐의 맨 뒤로 보내버리기 때문에 위험부담이 크다

그렇기 때문에 작업 시간을 정할 때 프로세스의 정보 등을 조합하여 책정하며, 사용자는 시스템에게 각 프로세스에 관한 정확한 정보를 제공해야 한다

비선점형 스케줄링이다

우선순위 스케줄링 (Priority)

프로세스에 우선순위를 정적 또는 동적으로 부여하고, 우선순위가 높은 순서대로 처리한다

• 정적 우선순위 (Static Priority)
  • 고정 우선순위
  • 한번 고정한 우선순위는 바뀌지 않는다
  • 오버헤드가 적음
  • 주위 환경의 변화를 무시하기 때문에 효율이 낮아질 수도 있다
• 동적 우선순위 (Dynamic Priority)
  • 유동 우선순위
  • 우선순위를 중간에 재조정할 수 있다
  • 중간중간 우선순위 재조정 단계에서 오버헤드가 발생하고, 구현이 복잡하다
  • 환경에 따라 우선순위가 변동할 수 있으므로, 효율이 높아진다

SJF와 마찬가지로 선점 우선순위와 비선점 우선순위 방식이 있다

• 선점 우선순위는 한 프로세스가 실행중일 때, 다른 더 높은 우선순위를 갖는 프로세스가 들어올 경우 해당 프로세스로 교체한다
• 비선점 우선순위는 현재 프로세스를 교체하지 않는다

라운드로빈 스케줄링 (Round Robin)

각 프로세스가 작은 단위의 시간 할당량을 부여받고, 그 시간동안만 자원을 할당받아 번갈아가면서 동작한다

만약 할당 시간동안 작업을 다 끝내지 못했다면 강제로 다음 프로세스가 자원을 할당받아 사용하기 시작하고, 선점당한 프로세스는 준비 큐의 맨 뒤로 돌아간다

이미지의 간트 차트를 보면 모든 프로세스가 같은 시간동안만 동작하는 것을 볼 수 있다

당연히 할당 시간보다 프로세스가 빨리 작업을 끝내면, 바로 다음 프로세스로 작업 텀이 넘어간다

모든 프로세스에 공평하게 시간이 배정되고, 어떠한 프로세스도 오래 대기할 일이 없어 기아 현상이 발생하지 않는다

다만 할당받는 시간이 너무 길 경우, FCFS와 다를 바가 없어지므로 라운드 로빈의 의미가 없어지고, 할당받는 시간이 너무 짧을 경우 컨텍스트 스위칭에 의한 오버헤드가 커지므로 적절한 할당 시간 분배가 중요하다

다단계 큐 스케줄링 (Multi-level Queue)

준비 큐 (Ready Queue) 를 여러 개 사용한다

각각의 큐는 서로 다른 독립적인 스케줄링 알고리즘을 사용하며, 큐 간에도 우선순위가 있다

선점 방식으로, 우선순위가 낮은 큐가 우선순위가 높은 큐에게 CPU 할당을 빼앗길 수 있다

다단계 피드백 큐 스케줄링 (Multi-level Feedback Queue = MLFQ)

위의 ‘다단계 큐 스케줄링' 에서 프로세스가 큐들 사이를 이동할 수 있다는 성질을 추가한 방식이다

우선순위를 결정할 때 해당 프로세스의 과거 이력 (과거 CPU Burst time) 을 이용하며 미래를 예측한다

---

참고자료

[운영체제] 스케줄러의 종류 : 단기, 중기, 장기

[운영체제(OS)] CPU 스케줄링 - (1) CPU 스케줄링의 개념

프로세스 스케줄링(Process Scheduling)

[운영체제(OS)] 5. 프로세스 스케줄링(Process Scheduling)

CPU Bound vs I/O Bound

[운영체제] 스케줄링(Scheduling) 알고리즘(FIFO, SJF, 우선순위, Round-robin)

[운영체제 OS] 스케줄링 알고리즘 - FCFS, RR, SJF, SRT, Priority, MLQ, MFQ 스케줄링

[운영체제] 비선점 스케줄링

프로세스 스케줄링