프로세스 스케줄링

프로세스 스케줄링

• 프로세스 스케줄러는 CPU에서 실행 가능한 여러 프로세스 중 하나의 프로세스를 선택한다.
• 그 프로세스는 CPU의 자원을 할당받고 실행된다.

스케줄링 큐

• 프로세스 스케줄링은 큐잉 도표로 나타낸다.

1. Job Queue

   • 프로세스가 시스템에 들어오면 잡 큐에 놓인다. 잡 큐는 시스템 안의 모든 프로세스로 구성된다.

2. Ready Queue

   • 준비 완료 상태이며 주 메모리에서 실행 대기 중인 프로세스가 위치하는 장소이다.
     • CPU를 할당(dispatch)받으면 Ready Queue에서 제거한다.
   • Ready Queue는 일반적으로 연결 리스트이다.
     • 각 노드는 PCB이다.
   • Ready Queue의 헤더는 리스트의 첫번째와 마지막 PCB를 가리키는 포인터를 갖는다.
   • 각 PCB는 Ready Queue에 있는 다음 프로세스를 가리킨다.

3. Device Queue

   • 특정 입출력 장치를 대기하는 프로세스들의 리스트이다.
   • 각 장치는 자신만의 디바이스 큐를 갖는다.

스케줄러

• 프로세스는 생성된 순간부터 제거될 때까지 다양한 스케줄링 큐를 방문하고 빠져나간다.
• 이 절차는 적절한 스케줄러에 의해 수행된다.

1. 장기 스케줄러(Job 스케줄러)

   • 장기 스케줄러는 프로세스를 선택하여 실행하기 위해 메모리로 적재한다.
   • 실행 빈도수가 적다.
     • 실행 간격이 크다.
   • 다중 프로그램의 정도를 제어한다
     • 메모리에 있는 프로세스의 수를 의미한다.

2. 단기 스케줄러(CPU 스케줄러)

   • 실행 준비가 완료된 프로세스에게 CPU를 할당한다.
   • 실행 빈도수가 많다. CPU를 위해 지속적으로 새로운 프로세스를 선택해야 한다.

3. 중기 스케줄러

   • 경쟁이 심할 때 우선순위가 낮은 프로세스를 제거한다.
     • 다중 프로그래밍의 정도가 완화된다.
   • 여유가 생기면 제거했던 프로세스를 디스크에서 불러와 메모리에 다시 적재시키고 실행을 재개한다.
     • 이 기법을 스와핑(swapping)이라고 한다.

문맥 교환(Context switch)

• CPU를 다른 프로세스로 교환하려면 이전 프로세스의 상태를 보관하고 새 프로세스의 보관된 상태를 복구하는 작업이 필요하다. 이 작업을 문맥 교환이라고 한다.
• 문맥 교환이 일어나면 커널은 전 프로세스의 문맥을 PCB에 저장한다. 그리고 스케줄 상 실행되기로 한 프로세스의 저장된 문맥을 복구한다.
• 문맥 교환이 진행되는 동안 시스템은 아무런 일을 하지 못한다. 그렇기 때문에 문맥 교환 시간은 순수한 오버헤드이다.

스케줄링 기법

비선점형 기법

• 모든 작업을 한 번에 처리하는 일괄 처리 기법에서 적합하다.
• 모든 프로세스에 대한 요구가 공정하다.
• 프로세스가 CPU를 할당받으면 작업이 완료되기 전까지 CPU를 계속 사용한다.
• 응답시간을 예측하기 쉽다.

1. FCFS(First Come, First Served)

   • 먼저 들어오면 먼저 CPU를 할당받는다.
   • 구현이 간단하다.
   • 우선순위를 고려하지 않는다.
   • 먼저 들어온 작업이 끝나기 전까진 다른 작업이 실행되지 않아 비효율적이다.

2. SJF(Shotest Job First)

   • 레디 큐에서 대기중인 프로세스 중 실행 시간이 가장 짧을 것으로 예측되는 프로세스에게 CPU를 할당하는 기법
   • 실행 시간은 추정치이기 때문에 실제로 먼저 수행해야 하는 작업이 늦게 실행될 수 있음.
   • 또한 실행 시간이 길 것으로 예상되는 작업은 무한정 대기하는 기아 현상이 발생할 수 있음.

3. HRN(Highest Response-ratio Next)

   • SJF에서 실행시간이 긴 프로세스가 불리한 요소를 해결하는 방법
   • 우선 순위를 대기 시간과 서비스 시간으로 계산한다.
     • 우선 순위 = (대기 시간 + 서비스 시간) / 서비스 시간
     • 대기 시간이 길면 우선 순위도 높아진다. 이를 Aging 기법이라고 한다.
   • 우선 순위가 높은 프로세스에게 CPU를 할당한다.

4. 기한부(Deadline)

   • 명시된 시간 내에서 작업이 종료되도록 계획한다.
   • 사전에 정확한 자원 및 수행 시간을 예측하기 어렵다.

선점형 기법

• 프로세스가 CPU를 할당받아 실행하고 있어도 우선순위가 높은 다른 프로세스가 있다면 실행 중이던 CPU 자원을 뺏어 새 프로세스에게 할당한다.
• 우선순위가 높은 프로세스를 빠르게 처리할 수 있다.
• 빠른 응답 시간을 요구하는 대화식시분할 시스템에서 유리하다.
• 선점으로 인해 오버헤드가 발생한다.
• 프로세스 당 시간 배당을 위한 인터럽트용 타이머 클럭이 필요하다.

1. SRT(Shortest Remaining Time)

   • SJF를 선점형으로 바꾼 기법
   • SJF처럼 실행 시간이 짧은 프로세스에 CPU를 먼저 할당한다.
   • 우선순위가 더 높은 프로세스가 있다면 CPU 자원을 넘겨준다.

2. RR(Round Robin)

   • 각 프로세스가 CPU를 할당받을 수 있는 시간을 정한다.
   • 우선순위는 정하지 않는다.
   • 각 프로세스는 허용된 시간만큼만 CPU를 사용하고 다음 프로세스에게 CPU 자원을 넘긴다.
   • 평균적인 응답 시간이 짧아진다.
   • 문맥 교환이 많이 발생하여 오버헤드가 크다.
   • 할당 시간이 크면 FCFS와 똑같이 작동한다.

3. Multi Level Queue

   • 프로세스를 그룹으로 분류하고, 그룹 당 다른 레디 큐를 사용한다.
   • 우선순위에 따라 시스템/대화형/편집/일괄처리 등으로 나누어 상, 중, 하위 단계로 배치한다.
   • 그룹의 특성에 따라 다른 우선순위 기법을 사용한다.
   • 특정 그룹의 레디 큐에 들어간 프로세스는 다른 그룹의 레디 큐로 이동할 수 없다.
   • 하위 단계의 레디 큐에 있는 프로세스를 실행하던 중 상위 단계 레디 큐의 프로세스에서 CPU 할당 요청이 들어오면 자원을 넘겨준다.
     • 우선순위는 상위 > 중위 > 하위 순이다.

4. Multi Level Feedback Queue

   • Multi Level Queue의 그룹 별 레디 큐에 CPU 시간 할당량을 부여한다.
     • 주어진 시간 동안 작업을 완료하지 못하면 다음 단계의 레디 큐로 이동한다.
       • Multi Level Queue에서는 다른 단계로 이동하지 못했던 문제를 해결한 것이다.
   • 상위 단계의 레디 큐일수록 우선순위가 높고 시간 할당량은 낮다.
   • 마지막 단계는 Round Robin 스케줄링 기법을 사용한다.