[OSTEP] Ch3.2. Scheduling: Response time, RR, I/O, Blocked State.

Operating Systems: Three Easy Pieces: Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau
https://pages.cs.wisc.edu/~remzi/OSTEP/
본 글은 위 교재을 주교재로 한 학교 '운영체제(Operating Systems)' 수업을 들으며 공부한 내용을 정리한 글입니다.

해당 글은 개인 공부 및 교육 목적으로 작성하였으며, 일부 교재에 첨부된 사진(또는 교재에서 강의노트로 첨부된 사진)들을 포함하고 있습니다.
교재 출처 사진을 최소화하고자 블로그에는 핵심 사진을 제외하곤 옮기지 않은 사진들도 있습니다. 따라서 고의로 누락한 사진들이 존재하며, 해당 사진들을 언급하는 내용이 있을 수 있습니다. 누락한 사진들은 직접 교재를 참고해 주세요.

혹시 문제가 있다면, 댓글 남겨주시면 빠른 시일 내에 확인 후 적절한 조치를 취하겠습니다.

---

 

새로운 스케쥴링 메트릭: 응답 시간(Response time)

• 작업이 시스템에 도착한 시점부터 작업이 처음으로 스케쥴(실행)되기까지 걸리는 시간.
  • 멀티태스킹의 시작으로 time sharing이 도입되면서, 이젠 작업이 얼마나 빠르게 실행되냐도 중요하게 되었음.
  • 우리가 일상적으로 response time이라고 하면, 내 입력 대비 나한테 뭔가 response가 출력되는 데 걸리는 시간이라고 할 수도 있지만, 이 책의 시스템적인 관점에서의 response time은 저게 정의임.
    • 즉, 실제로는 작업이 처음으로 실행된 순간에도 사용자한테 가시적인 response가 없을 수 있음.

    T_response = t_firstrun - T_arrival

• 예를 들어, 아까의 예시에선 각 작업의 응답 시간은 A는 0, B는 0, C는 10이 됨.
• STCF를 비롯하여 비슷한 류의 폴리시(스케쥴링 방식)들은 응답 시간에서 좋은 평가를 받지 못함.
  • 왜냐하면, 동시에 3개의 작업이 도착했다 치면, 세 번째 작업은 딱 한 번 스케쥴되기 위해 먼저 실행된 두 작업이 완전히 끝날 때까지 기다려야 하기 때문이다.
  • → 우리는 어떻게 스케쥴러를 response time에 민감(sensitive)하게 만들 수 있을까?
• fairness는, 작업들의 response time이 얼추 비슷하게 (짧게) 나오면 fair하다고 생각해볼 수 있음.
  • 그래서, 아까 FIFO 예시(10초씩 순서대로 3번)는 fair하지 않다고 생각해볼 수 있음.
• 엄밀히 말하면, fairness가 응답 시간이랑 비슷하게 간다는 건 엄밀히 따지면 그다지 좋은 설명은 아님.
  • 그냥 RR의 그 time slice 방식이 fairness를 중점에 둔 방식인데, 그러다 보니 응답 시간 또한 어쩌다 줄어들게 된 것뿐임.

Round Robin(RR)(라운드 로빈) 스케쥴링

• Time sclicing Scheduling임.
  • 작업을 time slice로 잘게 나눠 실행시키고, run queue에 있는 다음 작업으로 전환하는 걸 모든 작업들이 끝날 때까지 반복한다.
    • time slice: 작업이 잘게 나눠져 실행되는 그 짧은 시간
      • 이는 때때로 scheduling quantum이라고도 불림.
  • 이는 모든 작업들이 끝날 때까지 계속 반복됨.
  • time slice의 길이는 (정의상) timer-interrupt period(타이머 인터럽트 주기)의 배수여야 한다.
    • 예를 들어, 타이머가 10msec마다 인터럽트를 발생시킨다면 time slice는 10, 20msec등 10msec의 배수가 될 수 있다. 그래야 OS가 인터럽트를 통해 제어권을 가져올 수 있기 때문.
    • 여기서, timer interrupt가 일어났다고 무조건 context switching이 일어나는 게 아니었음을 기억!!
  • time slice가 끝나면 ‘실행 큐’에 있는 다음 작업을 실행하는 건데,
    • 따라서, time slice가 끝난다고 해도, RR과 MLFQ에서는 run queue에 다른 레디 상태 프로세스가 없는 경우에는 context switching이 일어나지 않음.
    • 즉, 현재 실행 중인 프로세스가 유일한 프로세스여서 실행할 다른 프로세스가 없으면 Context Switching이 발생하지 않고 그대로 실행됨.
  • 그리고 뒤에 설명할 MLFQ에서는 time slice가 끝나면 이제 가장 우선순위가 높은 작업을 실행하는데,
    • 내 우선순위를 한 칸 내렸음에도 현재 실행중인 내가 우선순위가 유일하게 가장 높으면, context switching이 일어나지 않음.
    • MLFQ에서의 context switching은 (내려간 우선순위 기준으로) 동일 우선순위의 작업들이 있을 때만 일어남. 그렇지 않으면 계속 우선순위만 낮아짐.
• RR은:
  • 공정(fair)하기에 response time에서는 훌룡한 성능을 가지나,
  • turnaround time와 같은 메트릭에서는 형편없는 성능을 보인다.
• Example:
  • A, B, C가 동시에 순서대로 시스템에 도착했고, 각각 5초씩의 실행 시간을 가지는 상황이다.
  • SJF 스케쥴링 방식 사용 시:

    

    • Arerage Turnarount Time = (5 + 10 + 15) / 3 = 10초
    • Arerage response Time = (0 + 5 + 10) / 3 = 5초
  • 1초의 time slice를 가지는 RR 스케쥴링 방식 사용시:

    

    • Arerage Turnarount Time = (15 + 15 + 15) / 3 = 15초
    • Arerage response Time = (0 + 1 + 2) / 3 = 1초
  • 앞서 우리가 얘기한 대로,
    • Turnaround Time은 SJF가 더 좋게 나오나,
    • Response Time은 RR가 더 좋기 나오는 걸 볼 수 있다.

Length of a Time slice

• time slice 길이를 더 짧게 하면?
  • response time이 더 좋아짐(짧아짐).
    • → fairness가 높아진다.(performance는 안 좋아진다고 할 수 있음.)
  • 여기서 time slice 길이를 너무 짧게 하면,
    • context switching가 너무 자주 발생하게 되어,
    • context switching cost(overhead)가 전체 성능에 큰 영향을 미치게 되기에
    • 전체적으로 성능(문맥상 turnaround time)이 많이 떨어지게 된다.
• time slice 길이를 더 길게 하면?
  • context switching cost(overhead)의 영향을 여러 작업이 나눠 분할 상환하게 되므로, 그 영향이 비교적 낮아지게 됨.
  • 그러나 response time은 더 안 좋아짐(길어짐).
    • → fairness가 낮아진다.(performance는 좋아진다고 할 수 있음.)
  • 여기서 time slice 길이를 너무 길게 하면,
    • response time이 길어도 너무나도 길어져 버린다.
    • 그러면 SJF/STCF랑 큰 차이가 없어지게 된다.
• 위처럼, time slice의 길이를 결정하는 것은 시스템 디자이너에게 trade-off 상황으로 다가온다.
• 따라서, 우리는 RR을 사용할 때 너무 짧지도, 너무 길지도 않은 적절한 time slice 길이를 선택해야 한다.
  • → 이거 시스템 디자이너가 결정해야 하는데, 실제론 정하기 매우 난감하다.
  • 따라서 default값을 쓰는 것도 좋다.

Break;

• 우리는 두 종류의 스케쥴링 방식을 배웠다.
  • 첫 번째 유형은 SJF, STCF처럼 turnaround time이 좋지만 response time은 나쁜 스케쥴링 방식이다.
    • (일단 앞에 것부터 빠르게 해치움)
  • 두 번째 유형은 RR처럼 response time이 좋지만 turnaround time은 나쁜 스케쥴링 방식이다.
    • (다 같이 손잡고 늦게 끝남)
    • 여기서, 모든 작업이 끝나는 시간이 좋고 나쁘단 게 아님. 당연히 동일한 조건이면 모든 작업이 끝나기까지 걸리는 시간은 동일함. 여기선 average turnaround time이 나쁘다는 것.
• 우리는 가정 1, 2, 3을 완화하긴 했지만, 아직 완화해야 할 가정 두 개가 더 남아 있다.
  • 가정4: 모든 작업은 CPU만을 사용한다.
  • 가정5: 각 작업의 런타임(실행 시간)은 사전에 알려져 있다.

Incorporating I/O(입출력 연산을 포함하여 생각)

• 이제 가정 4를 완화하자.
  • → 이제 모든 프로그램은 CPU뿐만 아니라, I/O(입출력) 작업 또한 수행한다.
• Example:
  • 현 상황:
    • A와 B는 각 50ms씩의 CPU 시간을 필요로 하고,
    • A는 10ms동안 실행된 후에 I/O request를 발생시킨다.
      • 이때, I/O 작업은 10ms의 시간이 걸린다.
    • 반면에, B는 I/O 작업 없이 그냥 CPU만 50ms동안 사용한다.
    • 또한 스케쥴러는 A를 먼저 실행시키고 B를 다음에 실행시킨다고 가정하자.
  • 그리고 우린 STCF 스케쥴링 방식을 사용할 것이다.

  • 

  • 그러면, (현 공부하는 상황에선) A는 위와 같이 10msec 작업으로 분할되는 반면에, B는 하나의 50msec CPU 작업만을 수행하게 된다.
    • 이렇게 어떤 프로세스가 I/O와 같은 작업을 수행 중일 때 CPU의 제어권을 계속 차지하고 있는 방식을 Busy Waiting 방식이라고 함.
    • 이는 blocked 상태를 활용하지 않았다고도 생각할 수 있음.
  • 그러나… 이는 A 프로세스가 I/O 작업을 수행하는 동안 CPU가 놀게 되므로 비효율적임.
• 개선된 접근 방식: blocked 상태를 활용.
  • A를 50msec의 작업 하나로 보지 않고, 각 10msec의 독립적인 작업 5개로 나눠 다루는 것이다.
    • 따라서 시스템이 시작할 때 스케쥴러는 10msec 작업 5개와 50msec 작업 1개를 스케쥴링하게 된다.

    • 

  • 그러면 STCF 알고리즘에 따라, 위처럼 A-B-A-B-… 순서대로, 중간에 B가 제어권을 뺏겨 가며 작업들이 꽉꽉 채워 실행되게 된다(CPU 가동률이 최대로 된다).
  • 사실은, 그냥 A 작업이 입출력을 수행하는 동안, CPU의 제어권을 자발적으로 포기하는 건데, 저자가 설명을 위해 저렇게 나누는 걸로 얘기한 것 같다.
    • 즉, A가 I/O 작업을 수행하는 동안은, blocked 상태로 넣어버리는 것이다.
    • 이는 blocked 상태를 활용했다고도 생각할 수 있음.
      • 위에 5조각으로 나눴다는 건 책의 표현인데, 솔직히 별로 맘에 들진 않다…
  • 아까보다 훨씬 더 효율적인 걸 알 수 있다!!

블락드(blocked) 상태를 활용

• 어떤 프로세스가 입출력 작업을 요청한 경우,
  • 해당 프로세스는 입출력이 완료될 때까지 CPU를 사용하지 않을 것이기 때문에,
  • 입출력 완료를 기다리며 블락드(blocked) 상태가 된다.
  • 만약 그 입출력이 하드 디스크 드라이브에 보내졌다면,
    • 프로세스는 드라이브의 현재 입출력 워크로드에 따라 몇 초 또는 좀 더 긴 시간 동안 블록될 수도 있다.
    • 스케쥴러는 그 시간 동안 실행될 수 있는 다른 작업들을 스케쥴해야 한다.
• 프로세스가 그 입출력 작업을 완료했으면:
  • I/O device controller는 CPU에 인터럽트를 발생시키고,
  • OS는 해당 프로세스를 블락드(blocked) 상태에서 레디(ready) 상태로 변경한다.
    • 또는, 해당 프로세스를 그냥 즉시 실행시킬 수도 있다.

만병통치약은 없다(No More Oracle)

• 우리는 가정5를 통해 각 작업의 런타임(실행 길이)을 OS(스케쥴러)가 미리 알고 있다고 가정하였으나,
  • 사실 범용 운영체제에서 각 작업의 런타임을 미리 알 수 있는 방법은 없다.
• 그럼, 우리(OS)는 프로세스의 예상 런타임을 예측하는 방법밖에 없다.
  • 이를 어떻게 예측하는지는 다음 시간에 알아보자.

여담) 바이너리 서치

• 교수는 바이너리 서치 하면, tree보단 array가 먼저 생각난다.
• 디버깅할 때 바이너리 서치를 쓸 수 있음.
  • printf()를 middle line에 넣고,
    • 그 line이 실행됐으면: 거기까지는 OK다. 그니까 그 이후 middle line에서 다시 printf() 실행.
    • 그 line이 실행되지 않았으면: 그니까 그 이전 middle line에서 다시 printf() 실행.
• 이런 바이너리 서치를 실제 개발에 사용할 기회가 있을 수 있으니, 알고 있으라 함.