[운영체제와 정보기술의 원리] 6장 CPU 스케줄링

cpu : 프로그램의 기계어 명령을 실제로 수행하는 컴퓨터 내의 중앙처리장치. 프로그램이 시작되면 프로그램 카운터가 가리키는 주소의 기계어 명령을 하나씩 수행함

program counter(pc) : 프로그램 카운터라는 이름의 레지스터는 프로그램이 시작되어 메모리에 올라가면 현재 CPU에서 수행할 코드의 메모리 주소값을 가짐

 

기계어 명령

• CPU 내에서 수행되는 명령 (주로 일반명령)
  • Add : 레지스터에 있는 두 값을 더해 레지스터에 저장하는 명령
  • 수행 속도 빠름. CPU에서만 실행돼서
• 메모리 접근을 필요로 하는 명령 (주로 일반명령)
  • Load : 메모리에 있는 데이터를 CPU로 읽어 들이는 명령
  • Store : CPU에서 계산된 결괏값을 메모리에 저장하는 명령
  • 수행 속도 비교적 빠름
• 입출력을 동반하는 명령 (특권명령, 사용자 프로그램이 직접 수행 X, 운영체제가 대신 수행)
  • 키보드 입력
  • 처리된 결과 화면 출력
  • 디스크 파일 데이터 읽기/저장하기
  • 수행 속도 느림

프로세스

• I/O 바운드 프로세스 : I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스
  
  • 사용자로부터 인터랙션을 계속 받아가며 프로그램을 수행시키는 대화형 프로그램 (interactive program)
• CPU 바운드 프로세스 : I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스
  • 프로세스 수행의 상방 시간을 입출력 작업 없이 CPU 작업에 소모하는 계산 위주의 프로그램

 

1. CPU 스케줄러

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

 

CPU 스케줄링이 필요한 경우

• 실행 상태에 있던 프로세스가 I/O 요청 등에 의해 봉쇄(blocked) 상태로 바뀌는 경우 (비선점형)
• 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우 (선점형)
• I/O 요청으로 봉쇄 상태에 있는 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 그 결과 이 프로세스의 상태가 준비 상태로 바뀌는 경우 (선점형)
• CPU에서 실행 상태에 있는 프로세스가 종료되는 경우 (비선점형)

CPU 스케줄링의 방식

• 비선점형(nonpreemptive) : CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법
• 선점형(preemptive) : 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법
  • CPU를 빼앗는 방법으로는 할당시간(time quatum)을 부여한 후 타이머 인터럽트를 발생시키는 방법이 대표적이다.

 

2. 디스패처

• 새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드
• 현재 수행 중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정을 수행
• 디스패치 지연시간 (dispatch latency) : 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간, 이 시간의 대부분은 문맥교환 오버헤드에 해당된다. 

 

3. 스케줄링의 성능 평가

스케줄링 기법의 성능을 평가하기 위한 지표

 

• 시스템 관점의 지표
  • CPU 이용률  (utilization) : 전체 시간 중에서 CPU가 일을 한 시간의 비율
  • CPU 처리량 (throughput) : 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지(CPU 버스트를 완료한 프로세스의 개수)
• 사용자 관점의 지표
  • 소요시간 (turnaround time) : 프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼 CPU를 다 쓰고 CPU 버스트가 끝날 때까지 걸린 시간 (준비 큐에서 기다린 시간 + 실제로 CPU를 사용한 시간)
  • 대기시간 (waiting time) : CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합
  • 응답시간 (response time) : 프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간

❗ CPU 버스트란? 

• 프로그램의 수행 중 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계를 의미한다. 즉, 프로그램이 I/O를 한 번 수행한 후 다음번 I/O를 수행하기까지 직접 CPU를 가지고 명령을 수행하는 일련의 작업이다. 

 

4. 스케줄링 알고리즘

1) 선입선출 스케줄링 (First-Come First-Served: FCFS)

• 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식
• 단점 : 콘보이 현상(Convoy effect)
  • CPU 버스트가 짧은 프로세스가 CPU 버스트가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다려야 하는 현상을 말한다. 

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

• CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식
• 평균 대기시간을 가장 짧게 하는 최적 알고리즘(optimal algorithm)으로 알려진다
• 비선점형 방식으로 구현될 경우, 일단 CPU를 획득하면 그 프로세스가 CPU를 자진 반납하기 전까지는 CPU를 빼앗지 않는다. 
• 선점형 방식으로 구현될 경우, 준비 큐에서 CPU 버스트가 가장 짧은 프로세스에게 CPU를 할당했다 하더라도, CPU버스트가 더 짧은 프로세스가 도착할 경우 CPU를 빼앗아 더 짧은 프로세스에게 부여한다. -> SRTF (shortest remaining time)이라고도 불림.
• 단점 : 기아 현상(starvation)
  • CPU 버스트가 짧은 프로세스가 계속 도착할 경우 CPU 버스트가 긴 프로세스는 영원히 CPU를 할당받지 못하게 되는 경우를 말한다.

3) 우선순위 스케줄링 (Priority Scheduling)

• 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식
• 우선순위 값 (priority number)이 작을수록 높은 우선순위를 가지는 것으로 가정한다.
• 비선점형/선점형 두 가지의 경우로 구현 가능
• 우선순위 스케줄링 또한 기아 현상이 생길 수도 있다. 이걸 해결하기 위해 노화(aging) 기법을 사용할 수 있는데, 노화기법이란 기다리는 시간이 길어지면 우선순위를 조금씩 높여, 언젠가는 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 해주는 방법이다. 

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

• 시분할 시스템의 성질을 가장 잘 활용함
• 각 프로세스가 CPU를 연속으로 사용할 수 있는 시간을 특정 시간으로 제한해 이 시간이 경과하면 해당 프로세스로부터 CPU를 회수해 준비 큐에 줄 서 있는 다른 프로세스에게 CPU를 할당한다
• 각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간을 할당시간(time quantum)이라고 부른다
• 각 프로세스의 대기시간은 그 프로세스의 CPU 버스트 시간에 비례한다. -> 공정한 스케줄링 방식

5) 멀티레벨 큐 (multi-level queue)

• 준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법
• 멀티레벨 큐에서 준비 큐는
  • 대화형 작업을 담기 위한 전위 큐(foreground queue)와 -> 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링 사용
  • 계산 위주의 작업을 담기 위한 후위 큐(background queue)로 분할하여 운영된다. -> 응답시간이 큰 의미가 없어 FCFS 스케줄링 기법을 사용해 문맥교환 오버헤드를 줄임

6) 멀티레벨 피드백 큐 (multi-level feedback queue)

• CPU를 기다리는 프로세스를 여러 큐에 줄 세운다는 측면에서 멀티레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다.

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

• CPU가 여러 개인 시스템을 다중처리기 시스템이라고 하고 이러한 환경에서는 프로세스를 준비 큐에 한 줄로 세워서 각 CPU가 알아서 다음 프로세스를 꺼내어가도록 한다
• 다중처리기 스케줄링의 방식
  • 대칭형 다중처리 : 각 CPU가 각자 알아서 스케줄링을 결정하는 방식
  • 비대칭형 다중처리 : 하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임지고 나머지 CPU는 그에 따라 움직이는 방식

8) 실시간 스케줄링 (real-time scheduling)

• 실시간 시스템에서는 각 작업마다 주어진 데드라인이 있어 정해진 데드라인 안에 반드시 작업을 처리해야 한다.
• 경성 실시간 시스템(hard real-time system) : 시간을 정확히 지켜야 하는 시스템(미사일 발사, 원자로 제어 등)
• 연성 실시간 시스템(soft real-time system) : 데드라인이 있지만 못 지켰다고 해서 위험한 상황이 발생하지는 않는 시스템(멀티미디어 스트리밍 시스템)
• 데드라인을 지키는 것이 중요하기 때문에 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 EDF(Earliest Deadline First) 스케줄링을 많이 사용한다.

 

5. 스케줄링 알고리즘의 평가

• 스케줄링 알고리즘 성능을 평가하는 방법으로는 큐잉모델, 시뮬레이션, 구현 및 실측 방식이 있다.