운영체제 강의 5강

5-1강, CPU Scheduling 1

CPU and I/O Bursts in Program Execution

• 어떤 프로그래이든 위와 같은 경로를 거친다.
  • CPU 실행하는 단계(CPU burst)와 I/O 작업(I/O burst)을 실행하는 단계를 반복한다.
  • 사람이 많이 개입하는 프로그램은 더욱 많이 반복하게 된다.(I/O burst가 자주 끼어들게 된다)
  • 반면 그냥 행렬 곱셈을 계산하는 프로그램은 사람의 개입이 거의 없이(I/O busrt가 거의 없다) 결과값을 반환해준다.

CPU-burst Time의 분포

• x축은 CPU-burst Time이다.
  • CPU-burst Time이 짧은 경우, 즉 I/O burst Time이 많이 개입된 경우의 빈도가 많다.
    • I/O bound job이라고 부른다.
  • CPU-burst Time이 긴 경우, 즉 I/O burst Time이 적게 개입된 경우의 빈도가 적다
    • CPU bound job이라고 부른다.
  • Interactive job에게(사용자가 기다리는) 적절한 response를 제공할 수 있어야 한다. 오래 기다리지 않도록
• 공평하면서도 효율적인 메커니즘이 필요하다.

프로세스의 특성 분류

• I/O bound process
  • CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
• CPU-bound process
  • 계산 위주의 job

CPU Scheduler & Dispatcher

• 운영체제에 있는 특정한 기능을 하는, 코드로 이루어진 소프트웨어
• CPU Scehduler
  • Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.
• Dispatcher(실제로 CPU를 주는 과정)
  • CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다.
  • 이 과정이 context switching
• CPU 스케줄링이 필요한 경우
  1. running -> block ex. I/O 요청 시스템 콜
  2. running -> ready ex. timer interrupt
  3. block -> ready ex. I/O 완료 후 interrupt(CPU만 얻으면 작업이 가능한 프로세스)
  4. terminate
• 1, 4의 스케줄링은 nonpreemptive(= 자진 반납)
  • 비선점형, 일단 줬으면 뺏지 않는 방법
  • CPU를 가지고 있어도 별다른 실행을 할 수 없을 때
• All other scheduling(2, 3) preemptive(= 강제로 빼앗김)
  • 선점형, 줬지만 언제든지 뺏어올 수 있는 방법
  • 나는 CPU를 쓰고 싶은데 우선순위가 떨어지거나 할당된 시간이 다 되어 빼앗길 때
  • 현대 CPU 제어 매커니즘이다.

Scheduling Criteria

• CPU 스케줄링 성능을 평가하는 척도
  • 시스템 입장에서의 성능 척도, 가장 많이 일을 시킬 수 있는 것
    • CPU utilization(이용률) : 쉬지 않게 계속 CPU를 돌리는 것.(중국집, 주방장이 얼마나 놀지 않고 요리하는가)
    • Throughout : 주어진 시간 동안 몇 개의 작업을 완료했는가.(중국집, 몇 개의 요리를 처리했는가)
  • 프로그램 입장에서의 성능 척도, 내가 빨리 CPU를 얻어 빨리 끝내는, 얼마나 빨리 끝낼 수 있는지 시간 관련 척도
    • Turnaround time(소요 시간, 반환 시간) : CPU를 쓰려고 들어와서, 기다리다가 CPU를 다 쓰고 나갈 때까지 걸린 시간. 프로세스를 실행하는 데에 쓴 총 시간.(손님, 코스 요리, 먹고 기다리고 하는 시간들)
    • Waiting time(대기 시간) : ready queue에서 기다리는 시간. 처음으로 CPU를 얻더라도 timer에 의해 모든 프로세스 과정을 실행하지 못하고 ready queue에 들어갈 수 있다. 그렇게 ready queue에 있는 모든 시간을 합한 것이다.(손님, 손님이 기다리는 시간)
    • Response time(응답 시간) : 처음으로 CPU를 얻기 위해 걸린 시간.(손님, 첫 번째 음식을 기다리는 시간)
  • ready queue에 들어온 건에 대해서 기다린 시간이 얼마고, 단위 시간 당 몇 개를 처리했고, 이러한 것들이 관심의 대상이다. 특정 프로세스가 시작되어서 종료될 때까지의 시간이 아니라, 프로세스가 CPU를 쓰러 들어와서, I/O하러 나갈 때까지의 시간이다.

스케줄링 알고리즘

FCFS(First-Come First-Served)

• 먼저 온 것을 먼저 처리한다.(비선점형)
• 굉장히 CPU를 오래 쓰는 프로세스이 먼저 도착하면, 짧게 쓰는 프로세스들이 기다려야 한다. 비효율적이다.
• 기다리는 시간인 Average waiting time이 상당히 길다.
• 작업 시간이 긴 프로세스로 인해 짧은 프로세스가 기다려야 하는 현상을 convoy effect라고 한다.
  • 좋은 현상은 아니다.

• 기다리는 시간이 상당히 짧아진다.

SJF(Shortest-Job-First)

• CPU를 쓰는 시간이 짧은 프로세스한테 CPU 제어권을 먼저 주는 메커니즘이다.
• Average waiting time이 가장 짧다.
• SJF도 2가지로 나뉜다.
  • Nonpreemptive : 더 짧은 프로세스가 도착해도 원래 작업 중인 프로세스가 끝날 때까지 내놓지 않는다.
  • Preemptive : 더 짧은 프로세스가 도착하면, 앞으로 남은 시간이 짧은 프로세스에게 CPU 제어권을 빼앗긴다.
  • Preemptive의 Average waiting time이 더 짧다.

• Preemptive에서 P2의 경우, 2초에 도착하여 7초에 끝났다. 원래라면 6초에 끝나는 것이 기댓값이므로 기다린 시간은 1초이다.
• 0초에는 P1이 가장 먼저 도착하기에 항상 P1이 먼저 실행된다.
• Preemptive의 경우가 1초 정도 덜 기다리는 것을 확인할 수 있다. 어떤 알고리즘도 3초 보다 적을 수 없다. SJF Preemptive가 가장 짧은 알고리즘이라서.

SJF의 문제점

• Starvation(기아)
  • burst time이 긴 프로세스는 서비스를 받는 데에 너무 오래 걸릴 수 있다.
• 실제론 각 프로세스들이 얼머나 작업을 할지 알기 어렵다.
  • 실제 시스템에서 SJF를 사용하기 어렵다.
  • 하지만 추정은 할 수 있다. I/O Bound, CPU Bound 등에 따라.
  • 과거에 얼마나 썼는가를 보고 정확하진 않지만 어느정도 예측은 가능하다.
    • 과거의 CPU burst time을 이용해서 추정
      • exponential averaging
        1. tn : 실제 CPU 사용 시간
        2. 타우n+1 : 예측한 CPU 사용 시간
        3. a, 0 <= a <= 1
        4. define : 타우n+1 = a * tn + (1 - a)타우n
        • t와 타우를 일정 비율로 활용한다.

• 타우자리가 모두 t로 바뀌었다. 타우 초기값(최초로 예측했던) 빼고.
• (1 - a)는 0보다 작으므로 후속 term들은 가중치가 적어진다.
• 이렇듯 현재(타우n+1) 얼마나 CPU를 사용할지는 알 수 없지만 과거의 값들로 예측을 해본다.

Priority Scheduling

• 우선순위가 높은 프로세스에게 CPU를 주겠다.
  • Preemptive : 우선순위가 더 높은 프로세스가 들어오면 CPU를 빼앗기는 것.
  • Non-Preemptive : 우선순위가 더 높은 프로세스가 들어와도 일단 현재 프로세스를 완료하고 CPU를 내놓는 것.
• 정수값으로 Priority Number가 주어진다.
  • 이 때 가장 작은 숫자가, 가장 높은 우선순위를 가지게 된다.
• SJF는 예측한 CPU 제어 시간을 바탕으로 우선순위를 매겨 스케줄링하는 기업이라고 볼 수 있다.
• 문제점
  • starvation : 우선순위가 낮은 프로세스가 실행되지 못할 수 있다.
  • 해결법
    • aging
      • 오래 기다릴수록 우선순위를 조금씩 높여주는 것.

Round Robin(RR)

• 현대 컴퓨터에서 사용하고 있는 CPU 스케줄링은 라운드 로빈에 기반하고 있다.
• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가진다.
  • 일반적으로 10 ~ 100ms
• 할당 시간이 지나면 CPU를 빼앗기고 ready queue에 들어간다.
• n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다. (1/n q time unit만큼 CPU 시간을 얻게 된다. 여러번 반복되어야 하면 1/n q time unit단위로 CPU 시간을 얻게 된다)
  • 어떤 프로세스도 (n - 1) * q time unit 이상을 기다리지 않는다.
  • 응답 시간이 빠른다.
• 할당시간, 즉 q를 아주 크게 잡으면 FCFS(먼저 들어온 것을 먼저 처리하는)와 가까워진다.
• q를 작게 잡으면, 라운드 로빈에서는 이상적이라고 볼 수 있지만 context switching 오버헤드로 성능이 나빠질 수 있다.
• 따라서 적당한 q(10 ~ 100ms)를 주는 것이 좋다.
  
• SJF보다, 각 프로세스마다 Average turnaround time(혹은 waiting time)은 길지만 response time은 더 짧다.

---

5-2강, CPU Scheduling 2 / Process Synchronization 1

Multilevel Queue

• 위로 갈수록 우선순위가 높아진다.
• interactive processes : 사용자와 상호작용하는 프로세스
• batch processes : CPU 연산을 주로 하는 프로세스
• 고려사항
  • 어느 큐에 넣을 것인가
  • 그 큐에 들어가 있을 때, 그 큐에만 우선권을 주느냐
    • 우선순위가 낮은 큐는 starvation을 겪을 수도 있다.

• Ready Queue를 여러 개로 분할
• 프로세스를 어느 Queue에 넣을 것인가
  • foreground(전경, interactive)
  • background(후경, batch - no human interaction, 사용자와 상호작용이 없는, 즉 CPU 연산이 주로 필요한)
• 각 Queue마다 어떤 스케줄링 알고리즘을 쓸 것인가
  • foreground : Round Robin(응답 시간을 줄이기 위해, 우선 순위가 떨어지는 프로세스도 응답 시간을 줄이기 위해)
  • background : FCFS(오버헤드를 줄이기 위해)
• Queue 마다 스케줄링도 필요하다.
  • Fixed priority scheduling
    • 어떤 큐를 먼저 처리해야 할지, 즉 큐에 대한 우선순위가 정해져 있는 경우
    • foreground 먼저 처리하고 background를 처리한다.
    • starvation의 우려가 있다.
      • 우선순위가 높은 foreground에 계속해서 프로세스가 차면, background의 프로세스를 처리할 수 없다.
  • Time slice
    • 각 큐에 대해 CPU time을 적절한 비율로 할당
    • ex.
      • 라운드로빈을 사용하는 foreground에게 80%
      • FCFS를 사용하는 background에게 20%

Multilevel Feedback Queue

• 필요에 따라 Queue를 왔다갔다 할 수 있는 스케줄링
• 프로세스가 경우에 따라서는 다른 Queue로 이동할 수 있다.
• 에이징(Aging, 시간이 흐름에 따라 우선순위가 높아지게 하는)을 multilevel feedback queue로 구현이 가능하다.
• multilevel feedback queue를 정의하는 파라미터
  • 큐의 수
  • 각 큐마다 적용할 스케줄링 알고리즘
  • 프로세스를 하위 큐로 내쫓는 기준
  • 프로세스를 상위 큐로 올리는 기준
  • 프로세스가 CPU 서비스를 받으려 할 때, 처음 들어갈 큐(ready queue임을 잊지 말자)를 결정하는 기준
• 우선순위가 가장 높은 큐는 타임 퀀텀을 가장 짧게 준다. 밑으로 갈수록 길게 주고, 제일 아래는 FCFS 방식을 쓴다.
  • 즉 밑으로 갈수록 자기 차례가 오면 되도록 끝날 수 있게 한다.
  • 할당 시간 내에 프로세스가 안 끝나면 아래로 강등이 되고, 아래에서도 할당 시간이 지나도 안 끝나면 더 아래로 내려가게 된다.
  • CPU 사용 시간이 짧은 프로세스가 우선순위가 높은 셈이다.(빨리 처리되고 나가니) 긴 프로세스는 계속 강등된다.
• 라운드로빈만으로는, CPU 사용 시간이 짧은 프로세스가 빨리 CPU 서비스를 받는 것이 잘 구현되지 않기 때문에, 이와 같이 멀티레벨 피드백 큐로 보완한다.
• 처음에 들어오면 무조건 짧은 시간의 CPU 사용시간을 주니, 이미 정해져 있으니 SJF와 달리 CPU 사용시간을 예측할 필요가 없다.

특이한 케이스의 CPU 스케줄링

Multiple-Processor Scheduling

• Homogeneous(동종의) Processor
  • 큐에 한줄로 세워놓고 CPU가 알아서 프로세스를 꺼내갈 수 있게 한다.
  • 특정 CPU가 필요한 프로세스
    • ex. 꼭 찾는 이발사가 있는 경우
• Load sharing
  • 특정 CPU만 일하고 나머지 CPU는 놀고 있으면 안된다.
  • CPU마다 별개의 큐를 사용하는 방법 vs CPU들이 공통으로 사용하는 공동 큐를 사용하는 방법
• Symmetric(대칭적인) Multiprocessing(SMP)
  • 모든 CPU들이 대등한 경우
  • 각 CPU가 알아서 스케줄링을 결정한다.
• Asymmetric(비대칭적인) Multiprocessing
  • 하나의 CPU가 너는 일로가, 너는 일로가 분배하는 역할을 하고 나머지 CPU는 그것을 따른다.
  • CPU 하나가 총괄하는 것.

Real-Time Scheduling

• 정해진 시간 내에 작업을 완료해야 하는, 데드라인이 있는 업무를 처리할 수 있도록 하는 스케줄링
• 먼저 CPU를 주고 이런 것이 중요한 게 아니라, CPU에서 데드라인 안에 끝나는 것을 보장해줘야 한다.
• Hard real-time systems
  • 정해진 시간 안에 반드시 끝내도록 스케줄링
• soft real-time systems
  • 조금은 어겨도 된다.
  • 일반 프로세스에 비해 우선순위만 높여준다.

Thread Scheduling

• 구현 방법
  • Local Scheduling
    • User level thread의 경우로, 사용자 프로세스가 직접 쓰레드를 관리하고, 운영체제는 그 쓰레드의 존재를 모르는 경우이다.
    • 운영체제는 그저 프로세스한테 CPU를 줄지 안줄지를 결정하고, 프로세스한테 CPU가 갔을 때 어떤 쓰레드한테 CPU를 줄지는 프로세스가 결정한다.
  • Global Scheduling
    • Kernel level thread의 경우로 , 운영체제가 쓰레드의 존재를 이미 알고 있는 경우이다.

조 스터디하며 얻은 지식

• 프로세스 우선순위는 PCB에 저장되어 있다.