• Workload : job descriptions의 집합(걸리는시간, 리소스의 양)
    • Job : 프로세스와 비슷함 but CPU만 연속적으로 쓰는(burst) 프로세스처럼 보인다.
      • 프로세스 : CPU와 입출력작업을 번갈아가면서 하는 프로세스
    • Scheduler : 실행할 job을 선택하는 로직
    • Metric : 스케쥴링 퀄리티를 측정하는 방법
  • 스케쥴링

    • Workload 가정

      1. 각 job은 동일한 시간 동안 수행된다.
      2. 모든 job은 동시에 도착한다.
      3. 모든 작업은 오직 CPU만 사용한다.(I/O작업x)
      4. 각 job의 실행시간은 주어져있다.

    • 스케쥴링 측정방법

      • Performance metric 성능 측정방법 : Turnaround time

        image.png

        • 작업을 완수한 시간 - 작업이 도착한시간을 계산해준 값

      • 다른 metric : fairness

        • 프로세스 여러개를 비슷한 정도로 잘 할당해주는 것
          • 하나에 몰빵해주면 unfair한 스케쥴링이 됌

      • FIFO : first in, First out

        • FCFS : first come, first served (선착순!)

        image.png

        • A, B, C가 동시에 도착함 → 완수한 시간대가 10, 20, 30

      • Convoy 효과

      image.png

      모두 동일한 시간을 작업한다는 조건을 삭제하면 위와 같이됌 A arrived just before B which arrived just before C

      : C가 도착하기 바로 직전에 B가 도착했고 B가 도착하기 바로 직전에 A가 도착함!

      • SJF : shortest job first (짧은 것 먼저!)

        image.png

      Non-preemptive scheduling : 비선점적 → 먼저온게 우선이 아님

      B,C가 늦게 왔어도 짧으니까 먼저 !

      • SJF with B,C Late Arrivals

      image.png

      이 방법도 시간이 너무 커진다!

      • Preemptive 스케쥴링 (선제권이 있는 스케쥴링)

        • 위의 스케줄링 방법(FIFO, FCFS, SJF): 선제권이 없는 방법
          • job이 CPU자원을 자발적으로 포기해야만 스케쥴러가 다른 job을 스케쥴링하는 방법
        • New 스케쥴러
          • 선제권이 있는 방법을 채택

            • 실행중인 job으로 부터 강제로 CPU를 가져와서 다른 job을 스케쥴링 해준다.

            • STCF(shortest time-to-completion first)

              • 짧은게 먼저 완전한 수행이 될 수 있도록
              • 항상 빠르게 전체 job이 수행될 것이다.
              • 그때그때마다 항상 적은 시간이 남은 작업을 우선적으로 스케쥴링
              • 예시

              image.png

      • New 스케쥴링 metric : Response time 반응시간

        • 작업이 도착하고 처음 스케쥴링된(실행된) 시간

        image.png

        • Turnaround time과의 차이 : 끝나는시간을 정확하게 모르기 때문에 실행이 시작된 시간으로 계산

          • 끝나는 시간알면 → 턴어라운드로 !

        • Round Robin(RR) 스케쥴링

          • Time slicing Scheduling
            • 타임슬라이싱된 시간동안 job을 실행하고, job이 끝나고 실행대기열에 있는 다음 job으로 전환된다. → 이과정을 반복
            • 타임슬라이싱의 길이는 timer interrupt 주기의 배수여야 한다.
              • OS는 timer interrupt를 통해 context switch가 일어나므로 배수여야 정확한 타이밍에 다른 job으로 전환가능
            • Time slicing 은 scheduling quantum으로도 불림
          • 턴어라운드 보다는 성과가 좋진 않다.→턴어라운드시간이 성과 측정면에서 good
          • 예시

          image.png

          • 슬라이싱 타임의 길이
            • 짧은 슬라이싱 길이 : 반응속도 빠르고, 비용 크다
            • 긴 슬라이싱 길이 : 반응속도 느리고, 비용 적다
            • 둘을 잘 타협해서 써라!

        • Incorporating I/O (I/O 포함)

          • job의 가정 3번을 없애보자!
            • 모든 프로그램은 I/O가 존재
          • 예시
            • A, B 둘다 CPU 50ms가 필요함
            • A는 10ms 실행후 i/o작업이 무조건 요청됨
              • i/o도 10ms
            • B는 단지 CPU 50ms만 사용하면 됌

          다음과 같이 나올 것이다.

          image.png

          많은 양의 workload를 줄일 수 있다.

          • I/O가 요청되면 job은 blocked 상태가 됨
          • I/O가 완료되면 job은 ready 상태로 전환
          • CPU를 최대로 활용할 수 있다

        • Multi-Level Feedback Queue (MLFQ)

          • 서로 다른 우선순위를 가진 다양한 대기열을 가지고 판단하는 방법

          • MLFQ의 기본적인 룰 (4가지 룰)

            • 1: 더 높은 우선순위의 job → 실행
            • 2: 같은 우선순위의 job → RR 스케쥴링을 사용
            • job의 관측된 행동을 보고 우선순위를 변화한다.
              • job이 IO작업을 기다리는동안 반복적으로 CPU를 포기한다면 → 높은 우선순위를 유지한다.(빨리주고 빨리 끝내!)
              • job이 긴 시간동안 CPU를 사용한다면 → 우선순위를 낮춘다.(길게쓸거면 나중에해!)
              • 추가 룰(우선순위변경하는 3가지 추가룰)
            • 예시

            image.png

            image.png

          I/O예시

          image.png

          • MLFQ는 상호작용하는 (I/O와 CPU를 번갈아가면서 쓰는) 작업들을 높은 우선순위에 둔다.

        • MLFQ의 문제점

        • The Priority Boost

        • Better Acounting

        • 낮은 우선순위는 긴 타임슬라이스

      • Solaris(운영체제 중 하나) MLFQ 수행

      • MLFQ 요약