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

• 프로그램이 시작되면 PC(프로그램 카운터)라는 이름의 레지스터가 현재 CPU가 수행할 코드의 메모리 주소값을 갖고 있음
  그러면 CPU는 프로그램 카운터가 가리키는 주소의 기계어 명령을 하나씩 수행하게 됨

• CPU를 사용하는 것(CPU내의 레지스터에 값을 기반으로 연산, 메모리에서 불러와서 연산)은 일반명령

1. CPU 버스트 : 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계
2. I/O 버스트 : 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계

I/O 바운드 프로세스: I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스
CPU 바운드 프로세스: I/O 작업을 거의 수행하지 않아 CPU버스트가 길게 나타나는 프로세스

• 대화형 프로그램 -> CPU 연산이 짧게 여러번 있음 -> CPU를 우선적으로 줘서 자주 빨리 처리하게 해야함
  즉 CPU 스케줄링 시 I/O 바운드 프로세스의 우선순위를 높여주는게 바람직하다

🦊 1. CPU 스케줄러

• CPU 스케줄러 : 준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제의 코드
• CPU 스케줄링이 필요한 상황
  1 실행 상태에 있던 프로세스가 I/O 요청 등에 의해 봉쇄 상태로 바뀌는 경우
  2 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우
  3 I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 그 결과 이 프로세스의 상태가 준비 상태로 바뀌는 경우
  4 CPU에서 실행 상태에 있는 프로세스가 종료되는 경우
• CPU 스케줄링 방식 = 비선점형(nonpreemptive)방식 + 선점형(preemptive) 방식
  • 비선점형 방식 : CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지 CPU를 빼앗기지 않는 방법
  • 선점형 방식: CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법

    CPU를 빼앗는 방법으로
    는 할당시간(time quantum)을 부여한 후 타이 머 인터 럽트를 발생시키는 방
    법이 대표적이다. 위의 네 가지 경우중에서는@과@가비선점형 스케줄
    링의 예가 되며， æ와 @은 선점형 스케줄링 방식에 해당한다.0)은 이번에
    1/0 작업이 완료된 프로세스가 인터럽트 당한 프로세스보다 우선순위가
    높아， 인터럽트처리 후 직전에 수행되던 프로세스에게 CPU를다시 할당
    하는 것이 아니라 문맥교환을 통해 I!O가 완료된 프로세스에게 CPU를 할
    당하는 경우가 해당된다.

🦊 2. 디스패처

• 디스패처: CPU 스케줄러에 의해 새로운 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드
  • 현제 수행 중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장하고 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에게 CPU를 넘김
  • 새로운 프로세스의 문맥을 복원시킨 후에는 시스템의 상태를 사용자모드로 전황해 사용자 프로그램에게 CPU의 제어권을 넘기게 된다.

    새로운 프로세스의 문맥을 복원시킨 후에는 시스댐의 상태를 사용자모드로 전환해 사용자 프로그
    램에게 CPU의 제어권을 넘기게 된다. 그러면 시용자 프로그램은 복원된 문맥 중 프로그램 카운터로부터 현재 수행할 주소를 찾을 수 있게 된다. 디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간을 디스패치 지 연시간(dispatch l ate n cy) 이라고 하며 , 디스패치 지연시간의 대부분은 문맥교환 오버헤드에 해당된다.

🦊 3. 스케줄링의 성능 평가

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

🦊 4. 스케줄링 알고리즘

1) 선입선출 스케줄링

• 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식
• 대표적인 현상으로 콘보이 현상이 있음
  • 콘보이 현상: CPU 버스트가 긴 프로세스가 먼저 도착하면 오래 기다려야 하는 현상

2) 최단작업 우선 스케줄링(Shortedst-job First)

CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식

• 평균 대기시간을 가장 짧게 하는 최적 알고리즘
• SJF에는 2가지 방식이 있음(선점형, 비선점형)
  • 비선점형 프로세스가 CPU를 획득하면 CPU 버스트가 더 짧은 프로세스가 오더라도 끝날때까지 기다림
  • 선점형은 CPU 버스트가 더 짧은 프로세스가 오면 현 프로세스에서 CPU를 빼앗아 더 짧은 프로세스에게 이양함
    SJF의 선점형 구현 방식 = SRTF(Shortest Remaining Time First)
• SJF의 단점 : 기아현상
• 기아현상: CPU버스트 시간이 긴 프로세스는 오랜시간 CPU배정을 못받을 수 있음

3) 우선순위 스케줄링

• 어떤 기준으로 우선순위를 잡던 우선순위가 낮은 프로세스는 CPU를 할당받지 못함
• 노화(aging) 기법: 프로세스가 기다린 시간에 비례해서 우선순위를 높임

4) 라운드 로빈 스케줄링

각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간을 특정하게 제한함

• 이때 할당시간(time quantum)이 너무 길면 FCFS와 같아짐

• 너무 짧은면 CPU를 사용하는 프로세스가 빈번하게 교체되어 문맥교환의 오버헤드가 커짐

• 일반적으로 할당시간을 수십 밀리초로 설정

  • 이는 여러 프로세스가 동시에 수행되는 환경에서 대화형 프로세스가 CPU를 한 번 할당받기까지 지
    나치게 오래 기다리지 않을 정도의 시간 규모에 해당한다. 이는 사람이 느리지 않다고 체감할 정도의 시간 규모에 한 번씩은 CPU를 할당받을 수 있도록 정한 시간 규모라 할 수 있다.

• 할당시간이 만료되어 CPU를 회수하는 방법으로 타이머 인터럽트를 사용

5) 멀티레벨 큐

• 속성이 같은 프로세스낄 모아서 큐를 여러개 만듬
• 대화형 작업을 담기 위한 전위큐(foreground queue)
  • 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링 사용
• 계산 위주의 작업을 담기 위한 후위큐(background queue)
  • 응답시간이 큰 의미 없기에 FCFS 스케줄링으로 문맥교환 오버헤드를 줄임
• 큐 자체에 대한 스케줄링이 필요함
  • 고정 우선순위 방식으로 전위큐에 우선순위를 두어 먼저 할당함
  • 타임 슬라이스 방식도 있음
    • CPU 시간중 80% 전위, 20% 후위 이런식으로 배당

6) 멀티레벨 피드백 큐

• 프로세스가 큐를 이동할 수 있음
  • 오래기다렸을 때 우선순위가 높은 큐로 이동시킴
• 멀티레벨 피드백 큐를 정의하기 위한 요소
  • 큐의 수
  • 각 큐의 스케줄링 알고리즘
  • 프로세스를 상위 큐로 승격시키는 기준
  • 프로세스를 하위 큐로 강등시키는 기준
  • 프로세스가 도착했을 때 들어갈 큐를 결정하는 기준
    
• 상위가 우선순위가 높음
  첫번째로 5만큼의 시간을 할당받고, 그뒤로 10을 할당받고, 그뒤로는 FCFS로 끝날때까지 할당받음

7) 다중처리기 스케줄링

• 한쪽 프로세서에 몰리는 것을 방지하기 위해 부하균형 메커니즘이 필요함
• 대칭형 다중처리와 비대칭형 다중처리 방식이 있음
• 대칭형 다중처리 방식
  각 CPU가 각자 알아서 스케줄링을 결정
• 비대칭형 다중처리
  하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임지고 나머지 CPU는 거기에 따름

8) 실시간 스케줄링

• 우리가 흔히 사용하는 프로세스는 작업에 '데드라인'이 존재하지 않음

• 하지만 '실시간' 시스템에서는 작업마다 데드라인이 존재함

• hard real-time system(경성 실시간 시스템) : 반드시 시간을 지켜야함

• soft real-time system(연성 실시간 시스템) : 반드시 지킬 필요까지는 없음

• DEF(Earlist Deadline First) : 데드라인이 얼마 남지 않은거부터 먼저 처리
  일반작업과 VOD작업이 혼합되어있는 환경에서는 VOD등 데드라인이 존재하는 프로세스에게 높은 우선순위를 할당함