CPU 스케줄링

CPU 스케줄링

프로그램이 메모리에 올라가면 PC(프로그램 카운터)라는 이름의 레지스터가 현재 CPU에서 수행할 메모리의 주소값을 가지고 있는다. 그러면 CPU는 PC가 가진 메모리 주소를 하나씩 실행 시킨다.

프로그램 실행과 관련한 기계어 명령

• CPU 내에서 수행되는 명령

  • ADD - CPU내의 레지스터에 있는 2개의 값을 더해 레지스터에 저장하는 명령이다. 수행속도가 매우 빠르다.

• 메모리 접근을 필요로 하는 명령

  • LOAD - 메모리의 데이터를 CPU로 읽어 들이는 명령이다.

  • Store - CPU에서 계산된 값을 메모리에 저장하는 명령이다.

  • 비교적 빠르다.

• 입출력을 동반한 명령

  • 시간이 오래걸린다.

CPU burst - 사용자 프로그램이 CPU를 직접 가지고 빠른명령을 수행하는 단계

I/O burst - I/O요청이 발생해 커널에 의해 입출력을 진행하는 느린 단계

왜 CPU 스케줄링이 필요한가?

CPU 스케줄링이란 CPU burst가 균일하지 않는 다양한 프로그램이 존재하므로 효율적인 관리를 위해서 필요하다. 프로그램들은 CPU burst, I/O burst가 반복적으로 cycle을 이루며 구성되어 있다. 그 중 하나의 프로세스가 I/O burst를 위해 사용자의 입력을 기다리고 있다. 그러고 있는 사이 다른 CPU burst를 수행할 수 있다. 그때 효율적인 관리를 위해서 CPU스케줄링이 필요하다.

CPU 스케줄러

준비상태에 있는 프로세스들 중 어떤 프로세스에게 CPU를 할당할 지를 결정하는 운영체제의 코드이다.

• 선점형 - CPU를 강제로 뺏는 방식이다.

• 비선점형 - CPU를 획득한 프로세스가 스스로 CPU를 반남하기 전까지 CPU를 빼앗지 않는 방식이다.

디스패처

스케줄러가 어떤 프로세스가 CPU를 사용할지 결정하면 그 프로세서에게 CPU를 이양하는 일을 디스패처가 담당한다. 수행중인 프로세스의 문맥을 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로 부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정을 수행한다.

스케줄링 알고리즘

1. FCFS(First-Come First-Served)

• 먼저 온 순서대로 CPU를 할당하는 방식이다.

• 비선점형 방식

• 콘보이 현상 - CPU burst가 긴 프로세스가 짧은 프로세스 보다 먼저 도작해 오랜시간을 기다려야 하는 현상. FCFS의 대표적인 단점이다.

2. SJF(Shortest-Job First)

• CPU burst가 가장 짧은 프로세스에게 먼저 할당하는 방식이다.

• 비선점형, 선점형 두 가지 방식이 있다.

• 선점형 구현방식을 SRTF(Shortest Remaining Time First)라고 한다.

• CPU burst가 짧은 프로세스에게만 CPU를 할당하는 경우 CPU burst가 긴 프로세스는 계속 기다리게 되는 문제가 발생한다.

3. 우선순위 스케줄링(priority scheduling)

• 우선 순위가 높은 프로세스에게 먼저 할당하는 방식이다.

• 숫자가 낮을 수록 높은 우선순위를 가진다.

• 비선점형, 선점형 두 가지 방식이 있다.

• starvation(기아) 현상이 문제가 된다. 계속 우선순위가 높은 프로세스가 들어오면 우선순위가 낮은 프로세스는 한없이 기다리게 된다. aging 기법으로 문제를 해결한다. Aging 기법은 기다리는 시간이 길어지면 우선순위를 조금씩 높히는 방식이다.

4. 라운드 로빈 스케줄링

• CPU를 사용할 수 있는 시간이 정해지며 그 시간이 지나면 프로세스로 부터 CPU를 회수해서 준비큐에 있는 다른 프로세스에게 CPU를 할당한다.

• 이 시간을 할당시간이라고 부르는데 할당시간이 너무 길면 FCFS 스케줄링처럼 되며, 너무 짧으면 문맥교환의 오버헤드가 커지게 된다.

• 오버헤드 - 어떤 처리를 하기위해 들어가는 간접적인 시간, 메모리를 말한다.

5. 멀티 레벨 큐

• 준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법

• 일반적으로 성격이 다른 프로세스들을 별도로 관리하고 그레 맞는 스케줄링을 적용하기 위해 준비큐를 별도로 두게 된다. 예를 들어 빠른 응답을 필요로하는 대화형 작업과 그렇지 않은 작업을 다른 준비큐에 두는 것이다.

• 전위큐 - 대화형 작업을 담는다. 빠른 응답시간이 요구되므로 라운드 로빈 스케줄링을 이용한다.

• 후위큐 -계산위주의 작업을 담는다. 응답시간은 별 의미가 없으므로 FCFS를 이용한다.

  어떤 준비큐에 먼저 CPU를 할당할 것인지 스케줄링이 필요하다.

• 고정 우선순위 방식 - 전위큐, 후위큐를 두어 전위큐에 우선적으로 CPU를 할당한다. starvation문제가 발생할 수 있다.

• 타임 슬라이스 방식 - CPU 시간을 적절한 비율로 할당하게 된다. 예를 들어 전위큐 80%, 후위큐 20% 이렇게 할당한다.

6. 멀티 레벨 피드백 큐

• 프로세스를 여러 큐에 세우는 것은 멀티 레벨 큐와 비슷하다.

• 프로세스가 하나의 큐에서 다른 큐로 이동이 가능하다는 점에서 다르다.

• 라운드로빈 -> 라운드로빈(할당시간 10) -> FCFS 스케쥴링을 따르는 큐를 순차적으로 이동한다.

7. 다중 처리기 스케줄링(multi-processor system)

• CPU가 여러개인 시스템을 다중 처리기 시스템이라고 부른다.

• 프로세스를 준비 큐에 한줄로 세워 놓고 각 CPU가 다음 프로세스를 꺼내어 가도록 할 수 있다.(은행원 알고리즘)

• 하지만 특정 CPU에서만 처리해야하는 프로세스가 있을 경우 준비큐를 한줄이 아니라 각 CPU별로 줄세우기를 할 필요가 있다.

• 여러줄로 줄세우기를 하는경우 한 CPU에만 작업이 편중되는 현상이 발생할 수 있다. 이와 같은 현상을 방지하기 위해 load balancing 매커니즘이 필요하다.

8. 실시간 스케줄링

• 실시간 스케줄링에는 시분할 시스템과는 다르게 각 작업마다 데드라인이 있다.

  • 경성 실시간 시스템 - 미사일 발사, 원자로 제어

  • 연성 실시간 시스템 - 멀티미디어 스트리밍