CPU 스케줄링

이 글은 반효경 저 - "운영체제와 정보기술의 원리"를 공부하고 정리하여 작성하였습니다.

 

1. 프로그램 실행 기계어와 수행 과정

1.1. 기계어 명령의 종류

1. CPU 내에서 실행
   • Add 명령: CPU 내의 레지스터에 있는 두 값을 더해 레지스터에 저장하는 명령
   • 수행 속도가 매우 빠름
2. 메모리 접근
   • Load 명령: 메모리에 있는 데이터를 CPU로 읽어드리는 명령
   • Store 명령: CPU에서 계산된 결괏값을 메모리에 저장하는 명령
   • CPU 내의 명령보다는 느리지만 비교적 짧은 시간에 수행할 수 있는 명령
3. 입출력을 동반
   • 키보드 입력이나 화면 출력
   • 디스크에서 파일 데이터를 읽어오거나 컴퓨터에서 처리된 결과를 디스크에 파일 형태로 저장하는 경우
   • 다른 명령에 비해 오랜 시간이 소요

CPU나 메모리 접근에 필요한 명령은 일반 명령에 해당함
컴퓨터 시스템 내에서 모든 입출력 명령은 특권 명령으로 규정됨

 

1.2. 프로그램 수행 과정

• 사용자 프로그램이 수행되는 과정은 CPU 작업과 I/O 작업의 반복으로 구성
• 프로그램 수행 단계
  1. CPU 버스트: 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 단계
  2. I/O 버스트: I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 단계
• 프로세스 비중에 따른 분류
  • I/O 바운드 프로세스
    • I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스
    • 주로 사용자로부터 인터랙션을 계속 받으며 수행시키는 대화형 프로그램에 사용
    • 짧은 CPU 버스트를 많이 가지고 있음
  • CPU 바운드 프로세스
    • I/O 요청이 많지 않아 CPU 버스트가 길게 나타나는 프로세스
    • CPU 작업에 소모하는 계산 위주의 프로그램에 사용
    • 소수의 긴 CPU 버스트를 가지고 있음
• 프로세스들의 CPU 버스트 분석 결과
  

  

  
  
  • 대부분 짧은 CPU 버스트를 가지고 극히 일부분만 긴 CPU 버스트를 가짐
  • CPU를 짧게 사용하고 I/O 작업을 수행하는 프로세스가 많음
  • 이런 프로세스는 CPU의 빠른 서비스를 필요로 함
• 즉, CPU 스케줄링 시 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 사용할 수 있는 스케줄링이 필요
• I/O 바운드 프로세스의 우선순위를 높이는 것이 좋음

 

 

2. CPU 스케줄러

• 준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제 코드
• 타이머 인터럽트 발생 시 호출되고 준비 큐에서 CPU를 기다리는 프로세스 중 하나를 선택해 CPU를 할당
• CPU 스케줄링이 필요한 상황
  1. 실행 상태에 있던 프로세스가 I/O 요청 등에 의해 봉쇄 상태로 바뀌는 경우 (비선점형)
  2. 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우 (선점형)
  3. I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하여 이 프로세스의 상태가 준비 상태로 바뀌는 경우 (선점형)
  4. CPU에서 실행 상태에 있는 프로세스가 종료되는 경우 (비선점형)
• CPU 스케줄링 방식
  • 비선점형 방식: CPU가 획득한 프로세스가 스스로 CPU를 반납하기 전까지 CPU를 뺏기지 않는 방식
  • 선점형 방식: 프로세스를 강제로 빼앗을 수 있는 스케줄링 방식

 

3. 디스패처

• 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드
• 디스패처를 통한 컨텍스트 스위칭
  1. 현재 수행 중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장
  2. 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원 후 그 프로세스에게 넘기는 과정을 수행
  3. 컨텍스트 스위칭 이후 시스템의 상태를 사용자모드로 전환
  4. 사용자 프로그램은 복원된 문맥 중 프로그램 카운터로부터 현재 수행할 주소를 찾을 수 있음
• 디스패치 지연시간(Dispatch Latency): 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지의 시간, 대부분 문맥교환 오버헤드에 해당

 

4. 스케줄링의 성능 평가

• 시스템 관점 지표
  • CPU 이용률: 전체 시간 중에서 CPU가 일을 한 시간의 비율
  • 처리량: 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 끝마친 프로세스 개수
    (= CPU 버스트를 완료한 프로세스의 개수)
• 사용자 관점 지표
  • 소요시간: (CPU 버스트가 끝난 시점 - CPU를 요청한 시점)의 시간
    ( = 준비 큐 대기 시간 + CPU를 사용한 시간)
  • 대기시간: CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합
  • 응답시간: 프로세스가 준비 큐에 들어온 후 첫번째 CPU를 획득하기까지의 기다린 시간

※ 여기서 기준은 프로그램 종료와는 관계가 없음.

 

5. 스케줄링 알고리즘

5.1. 선입선출 스케줄링

• 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식
• 프로세스가 자발적으로 CPU를 반납할 때까지 빼앗지 않음
• CPU 버스트가 긴 프로세스가 먼저 도착할 경우 평균 대기시간이 길어짐 (콘보이 현상)

 

5.2. 최단작업 우선 스케줄링(SJF)

• CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식
• 평균 대기시간을 가장 짧게 하는 최적 알고리즘
• 비선점형 방식과 선점형 방식으로 나뉠 수 있음
• 선점형의 경우
  • 실행 중인 P의 남은 CPU 버스트 시간 > 나중에 도착한 P의 CPU 버스트 시간 이면 CPU를 빼앗김
  • 이러한 SJF 선점형 구현 방식을 SRTF(Shortest Remaining Time First)라 함.
  • 준비큐 도착시간이 불규칙할 경우, 평균 대기시간을 최소화할 수 있는 알고리즘이 됨
• 비선점형의 경우
  • CPU를 점유하고 있는 프로세스가 CPU 버스트를 모두 수행할 때까지 기다려줌.
• 기아 현상(starvation): CPU 버스트가 긴 프로세스는 준비 큐에서 무한정 기다리는 문제가 발생함

 

5.3. 우선순위 스케줄링

• 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당
• 우선순위 값을 통해 결정하며 우선순위 값이 작을수록 우선순위가 높음
• 우선순위 스케줄링도 선점형 방식과 비선점형 방식으로 각각 구현할 수 있음
• 우선순위가 낮은 프로세스는 기아 현상을 겪을 수 있음
• 이를 해결하기 위해 기다리는 시간이 길어지면 우선순위를 높이는 노화(aging) 기법을 사용

 

5.4. 라운드 로빈 스케줄링

• 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한하는 방식
• 한 번에 연속적으로 사용할 수 있는 최대 시간을 할당시간이라 하고 일반적으로 수십 밀리초 정도로 설정.
• 여러 종류의 이질적인 프로세스가 같이 실행되는 환경에서 효과적
• 타이머 인터럽트를 사용하여 CPU를 회수함.
• 가장 공정한 스케줄링 방식이라 할 수 있고 대기시간도 CPU 버스트 시간에 비례해 증가함
• 할당시간을 너무 짧게 설정할 경우 문맥교환의 오버헤드가 증가해 시스템 성능이 저하됨.

 

5.5. 멀티레벨 큐

• 준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법
• 일반적으로 성격이 다른 프로세스들을 별도로 관리
• 프로세스의 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 별도로 둠
• 대화형 작업을 담는 전위 큐(foreground queue)와 계산 위주의 작업을 담는 후위 큐(background queue)로 분할하여 운영
  • 전위 큐 → 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링 활용
  • 후위 큐 → 응답시간이 큰 의미가 없기 때문에 FCFS 스케줄링 기법을 사용하여 문법교환 오버헤드를 줄임
• 어느 큐에 먼저 CPU를 할당할 것인지에 대한 스케줄링이 필요함
  • 고정 우선순위 방식
    • 큐에 고정적인 우선순위를 부여하여 운영하는 방식
    • 전위 큐에 우선순위를 높게 잡고 후위 큐를 낮게 잡음
  • 타임 슬라이스 방식
    • 큐에 대한 기아 현상을 해소할 수 있음
    • 큐에 CPU 시간을 적절한 비율로 할당

 

5.6. 멀티레벨 피드백 큐

• 프로세스를 여러 큐에 줄 세우면서, 큐 간 프로세스 이동이 가능함.
• 프로세스의 다양한 성격을 반영해 구현할 수 있음
• 멀티레벨 피드백 큐 정의 요소
  • 큐의 수
  • 각 큐의 스케줄링 알고리즘
  • 프로세스를 승격/강등시키는 기준
  • 프로세스가 도착했을 때 들어갈 큐를 결정하는 기준 등

ex) 예시

• 상위에 있는 큐일수록 우선순위가 높음 
• CPU 사용시간이 짧은 대화형 프로세스들은 우선순위가 가장 높은 큐에서 서비스를 받고 완료
• CPU 버스트 시간이 긴 프로세스는 할당시간이 10인 하위 큐로 내려가서 대기
• 그래도 다 안되면 계산 작업으로 간주되어 최하위 큐로 이동하고 FCFS 스케줄링을 적용

 

5.7. 다중처리기 스케줄링

• CPU가 여러 개인 시스템을 다중처리기 시스템이라 부름
• CPU가 여러 개인 경우, 프로세스를 준비 큐에 한 줄로 세워서 각 CPU가 알아서 다음 프로세스를 꺼내도록 할 수 있음
• 특정 CPU에서만 수행되야 하는 프로세스도 있기 때문에 이 경우, 각 CPU 별로 줄 세우기를 할 수 있음
• 일부 CPU에 작업이 편중되는 현상을 막기 위해 부하균형 메커니즘이 필요함.
• 대칭형 다중처리: 각 CPU가 알아서 스케줄링을 결정하는 방식
• 비대칭형 다중처리: 하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임지는 방식

 

5.8. 실시간 스케줄링

• 실시간 시스템에서는 정해진 데드라인 안에 작업을 처리해야 함
• 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 EDF(Earlist Deadline First) 스케줄링을 사용

 

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

• 스케줄링 알고리즘의 성능을 평가하는 방법
  • 큐잉모델
    • 주로 이론가들이 수행하는 방식
    • 확률분포를 통해 프로세스들의 도착률과 CPU의 처리율을 입력값으로 삼음
    • 복잡한 수학적 계산을 통해 CPU 처리량, 프로세스 평균 대기시간 등을 계산
  • 시뮬레이션
    • 가상으로 CPU 스케줄링 프로그램을 작성한 후 프로그램 CPU 요청을 입력하여 결과를 보는 방식
    • 입력값은 실제 CPU 요청 내역(트레이스, trace)을 추출해 쓰거나 가상으로 생성할 수 있음
  • 구현 및 실측
    • 구현가들이 수행하는 방식
    • 운영체제 커널의 소스 코드 중 CPU 스케줄링을 수행하는 코드를 수정하여 커널을 컴파일 한 후 시스템 설치 과정을 수행함
    • 이후 동일한 프로그램을 원래 커널과 CPU 스케줄러를 수정한 커널에서 수행하고 실행시간을 측정하여 알고리즘 성능을 평가

 

자료

• 운영체제와 정보기술의 원리 (반효경 저, 2020.5)