운영체제(5) - CPU Scheduling(1)

‘운영체제’를 공부하여 정리한 내용입니다.

1. Basic Concepts

Single processing system

• 한 순간에 오직 하나의 프로세스만이 실행
  • 나머지 프로세스는 CPU가 자유 상태가 되어 다시 스케쥴될 수 있을 때까지 기다려야 한다.
• Multi programming의 목적은 CPU 이용률을 최대화하기 위한 것
  • 실행 되고 있던 프로세스가 I/O등을 기다리는 대기 상태가 되면 CPU가 놀게 된다.
  • 우리는 이런 상황을 피하고 CPU가 계속 일을 할 수 있도록 해야한다.

CPU-I/O Burst Cycle

• 프로세스가 실행될 때 교차되는 형태
  • 프로세스가 시작될 때는 무조건 CPU Burst로 시작
  • 그 이후 부터는 I/O Burst와 CPU Burst를 교차하여 계속 실행시킨다.
  • 프로세스가 종료될 때는 CPU Burst

CPU Scheduler

• CPU가 Idle할 때마다 OS는 ready queue에 있는 프로세스들 중에서 실행될 프로세스를 선택해야 한다.

  • 이는 CPU Scheduler가 해준다.

• 이 Queue의 움직임은 기존의 Queue처럼 FIFO일 필요는 없다.

  • OS에 따라 FIFO, Priority, SJF, HRN 등의 형태들 중에서 하나를 선택한다.
  • Queue에서 대기하고 있는 레코드 정보는 PCB이다.

Preemptive Scheduling $ Non-Preemptive Scheduling

• CPU 스케쥴링은 다음의 4가지 상황에서 발생한다.

  1. running -> waiting: I/O 요청 혹은 부모 Process가 자식 Process를 기다릴 때 부르는 wait()
  2. running -> ready: by interrupt, running 중이었던 프로세스가 CPU 점유를 뺐긴다.
  3. waiting -> ready: 요청한 I/O 처리 등이 마쳤을 때
     • 프로세스가 ready로 돌아왔을 때, 이 프로세스가 현재 running 중인 프로세스보다 우선순위가 높다고 가정해보자.
     • 이 상황에서는 지금 running 하고 있는 것을 후퇴 시키고 이 프로세스를 running으로 만들 것인지 선택해야 한다.
  4. running -> terminated: 이제 이 프로세스는 전체 queue에서 빠져나온다.
     • 남은 프로세스들 가운데서 다시 스케쥴링 해야 한다.

• Non-Preemptive Scheduling

  • 1, 4번의 상황처럼 프로세스가 스스로 CPU 제어를 반납하는 경우만 프로세스 스케쥴링이 일어난다.
  • 2번의 경우는 인터럽트로 인해 지금 돌아가던 프로세스가 원치도 않았는데 CPU 제어를 반납하기를 원하는 것이기에 이 스케쥴링은 허락하지 않는 상황이다.
  • 3번의 경우는 waiting에 있던 프로세스가 ready queue로 돌아와서 CPU 제어를 가져가려고 하는 것이기 때문에 마찬가지로 Non-Preemptive Scheduling에서는 허락하지 않는 상황이다.

• Preemptive Scheduling

  • 2, 3 번의 상황에 대해서도 running 중이었던 프로세스가 CPU 제어를 반납할 수 있다는 것을 생각해야 한다.
  • Race condition(경쟁 상태)
    • 공유 자료를 수정 중이었다고 생각해보자. (메인 메모리에 존재하는 공유데이터: data == b_0000) (b는 이진수라는 것을 의미한다.)
    • p1이 data의 0번 비트를 1로 수정하려고 자신의 레지스터로 데이터를 꺼내서 수정하다가 다시 메인 메모리로 저장하지 못하고 제어를 뺐긴다. (data == b_0000)
    • p2가 data의 1번 비트를 1로 수정하려고 자신의 레지스터로 데이터를 꺼내고 수정하고 다시 저장까지 마친다. 그리고 p1이 다시 CPU 제어를 가져간다. (data == b_0010)
    • p1은 수정을 완료하고 메인 메모리에 저장한다. (data == b_0001)
    • 결과적으로 data는 b_0001이 되고 우리는 p2의 결과를 잃게 된다. 둘이 동시에 접근하길 원하게 되면 이런 상황이 발생한다. 사실 원래 우리가 원했던 결과는 b_0011이었다.
  • 커널의 작업은 선점 당할 수 있는가?
    • 대부분의 OS는 커널의 작업은 선점시키지 않고 기다린다.
    • 커널은 주로 시스템에 영향을 많이주기에 선점 당하게 되면 위험한 상황이 발생할 수 있기 때문이다.
    • 이는 오버헤드가 존재한다. 그래도 커널의 구조는 단순화시킬 수 있다.

• Dispatcher

  • CPU의 제어를 스케쥴러가 선택한 프로세스에게 건네주는 모듈
  • 작업 목록
    • Context Switch
    • User mode로 전환
    • 프로스램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일
  • 디스패처는 최대한 빨라야 한다.
  • 디스패처가 작업하는 시간에 걸리는 지연시간을 dispatch latency라고 부른다.

2. 스케쥴링 기준 (Scheduling Criteria)

• 기준 목록
  • CPU 이용률: CPU가 얼마나 바쁘게 움직이는가
  • 처리량: CPU가 단위시간당 얼마나 많은 프로세스를 처리하는가
  • 총처리 시간: 프로세스를 실행하는데에 소요된 시간
  • 대기 시간: ready queue에서 총 얼마나 대기했는가?
  • 응답 시간: 사용자가 응답을 제출하고 얼마나 빨리 그 응답에 대해서 대응을 시작했는가
    • 대응을 끝낸 시간을 측정하는 것이 아니다. 대응에 걸리는 시간을 프로그램의 특성에 따라 많이 달라진다.

3. Scheduling Algorithm

• Scheduling 방법은 선택될 수 있다.

  • 앞에서 말한 스케쥴링 기준에 따라 필요한 기준을 선정하여 가장 적절한 알고리즘을 고르면 된다.

• 목록

  • 여기에서 Process의 움직임은 CPU Burst의 길이를 기준으로 계산된다.
    • 참고로 CPU Burst가 끝났다고 무조건 프로세스가 종료되는 것이 아니다
    • I/O Burst 등으로 넘어갔을 가능성도 있다.
  • FCFS (Non-Preemptive Scheduling)
    • 구현은 매우 쉽다.
    • 너무 단순해서 각 프로세스의 특징이 고려되지 않는다는 단점이 있다.
  • SJF (Non-Preemptive Scheduling)
    • CPU Burst를 우리가 미리 알 수는 없다.
      • 그래서 이전의 CPU Burst 시간을 기준으로 예상하는 알고리즘을 추가한다.
  • Priority (Non-Preemptive Scheduling)
    • 우선순위는 내재적으로나 외부에서 설정한다.
    • 같은 우선순위일 경우는, 약속된 방식으로 처리한다.
      • FCFS: 같은 우선 순위 중에서는 먼저 온 프로세스 선택
      • SJF: 같은 우선 순위 중에서는 CPU Burst가 작은(혹은 작을 것이라고 예상되는) 프로세스 선택

  • Round-Robin (Preemptive Scheduling)

    • Time quantum에 따라서 인터럽트가 걸리고 dispatch가 동작한다.
      • 타이머가 동작하면서 인터럽트를 건다.
      • Time Quantum에 따라서 Context Switch가 자주 일어날 수도, 아닐 수도 있다. (영향을 많이 받는다)
        • 너무 작게 잡으면 Context Switch가 너무 자주 일어난다.
        • 너무 크게 잡으면 FCFS와 비슷해지고, 그 의미가 퇴색 된다.
    • 시분할 시스템을 위해 고안된 방법이다.

  • Multilevel Queue

    • 우선순위에 따른 큐 버퍼가 나뉘어져 있다. (queue 단위의 우선순위가 있다.)
      1. 우선 순위가 높은 큐가 비워져 있지 않으면 낮은 우선 순위의 큐에 있는 프로세스는 스케쥴링 되지 않도록 한다.
      2. Queue마다 CPU 할당 퍼센테이지를 주고 이를 기준으로 스케쥴링한다.
         • 아예 할당이 되지 않는 문제를 어느정도 해결한다.
  • Multilevel Feedback Queue
    • 위의 Multilevel Queue에서는 프로세스가 자신이 속하는 Queue를 바꾸지는 않았다.
    • 이 Multilevel Feedback Queue에서는 프로세스가 최상위 우선 순위의 큐에 있다가 프로세스가 CPU Burst를 많이 차지한다고 판단하면 한단계씩 낮은 우선순위의 Queue로 넘어가도록 한다. (queue마다 정해진 time quantum이 있어서 이를 기준으로 CPU Burst가 길다는 것을 판단한다.)
    • 이를 통해서 동적으로 프로세스의 스케쥴을 관리하게 된다.