Adavanced Scheduling Schemes

• 비율 공유 스케쥴러 Propotional
  • 공정하게 공유하는 스케쥴러
    • CPU 시간의 일정 비율을 job이 보장받는다.
    • Turnaround time or response time에 최적화되지 x
• 복권 스케쥴링 Lottery

  • 티켓 Tickets

    • 프로세스가 받아야하는 CPU(시스템) 자원의 비율을 나타낸다.
    • 예시

    

    • 스케줄러는 winning ticket을 선택한다!

    

    더 길게 경쟁할수록, 원하는 비율을 달성할 확률이 높다.

  • 티켓 메커니즘

    • 티켓의 통화(currency)
      • 사용자는 자신들이 원하는 통화로 job에 티켓을 할당할 수 있다.
        • 시스템이 알아서 올바른 글로벌 가치(원과 달러가 1장의 가치가 다르듯이 맞춰줘야됌)로 변환시켜준다.
      • 예시

    

    • 티켓의 전송&인플레이션(몰아주기)
      • 프로세스는 일시적인 해결방안으로 다른 프로세스에게 티켓양도가능
        • 소유한 티켓 늘리거나 낮출 수 있다.
        • 믿을만한 프로세스에 한해 OS가 허용할 때만 가능
      • 예를 들어, AB둘다 프린터를 쓰고 싶음 but A가 쓰고있다 → B가 티켓 스케쥴링에서 이기더라도 B는 기다려야함 → 그럴바엔 B가 티켓을 A한테 양도해서 A가 빨리 끝내버리고 B가 사용하는게 더 낫다!
• U : 불공평한 metric

  • 첫번째 job이 완료된 시간을 두번째 job이 완료된 시간으로 나눈 값

    • 예시

    

    • 1에 가까울수록 공평, 0에 가까울수록 불공평!

  • 티켓과 연결지어 생각해보자

    

    • 시행횟수가 많을 수록 공평해질 것이고, 적을수록 불공평해질 것이다.

  • Stirde 스케쥴링 (Stried : 보폭)

    • 각 프로세스의 보폭(티켓 수에 따른)을 계산해 그 순간마다 각 프로세스들의 보폭누적합(pass value)이 가장 작은 프로세스를 판단하여 측정하는 방법

    

    • 보폭은 어떤 큰 수를 티켓수로 나누면 된다. (예시에선 A : 100장, B : 50장, C : 250장)
    • 만일 pass value가 0인 프로세스가 들어오면 다른 프로세스의 pass value를 따라잡을때까지 CPU 독점!
• Multiprocessor 스케쥴링
  • 멀티코어 프로세서의 증가는 확산하는 멀티프로세서 스케쥴링의 자원이다.
    • 멀티코어란? 하나의 칩에 여러개의 CPU가 들어있는 상태
  • CPU를 더 추가하는 것은 단일 어플리케이션을 더 빨리 실행되게 하지 않는다.
    • 스레드를 사용하여 병렬로 실행하면 더 빨리 실행될 것이다!
  • 캐시 / 메인 메모리

    • CPU안에 있는 Cache는 작고, 빠르다.

      • 주요한 데이터를 가지고 있다. 시간적 및 공간적 지역성을 활용할 수 있다.

    • 메인 메모리는 느리다.

      • 모든 데이터를 가지고 있다.
      • Cache에 데이터를 보관함으로써, 시스템은 느린 메모리를 빠른 메모리처럼 보이게 만들 수 있음

    • Multicore issue 3가지는 다음과 같다.

    • Cache Coherence 캐쉬 통일성 문제

      

      

      • 한 CPU에서 값을 업데이트 해도 다른 CPU에서 불렀을 때 값이 바뀌지 않음
        • 같은 어플리케이션 (값이 갱신되어야하는)은 같은 CPU에서 실행하는게 Cache를 효율적으로 쓸 수 있다.
      • 이 문제의 해결책 : Bus snooping (하드웨어적 솔루션)
        • 각 Cache는 bus를 관찰하여 메모리 업데이트에 주의를 기울여야한다.
          • 캐시에 보유한 데이터 항목이 업데이트되면, 그 데이터의 변경사항을 업데이트하거나 데이터 사본을 무효화해야한다.

    • Dont forget Synchronization 동기화

      • 서로 다른 CPU간의 공유되는 데이터를 접근할 때는, 상호 배제 기본요소(mutual exclusion)가 정확성을 보장하기 위해 사용되어야 한다.

    • Cache Affinity 캐시 선호도

      • 가능한 동일한 CPU에서 프로세스가 실행(유지)되는 것이 좋다.
        • 프로세스가 실행될 때, 해당 CPU캐시의 일부상태가 있는 경우에 더 빠르게 실행

    • Single Queue Multiprocessor Scheduling (SQMS) 단일 대기열 멀티프로세서 스케쥴링

      • 모든 job들을 하나의 대기열에 스케쥴링 되기위해 넣는다.
        • 각 CPU는 하나의 글로벌적으로 공유된 대기열에서 다음 job을 선택하면 된다.
        • 단점 : 어떤 형태의 잠금장치 필요함 (동기화 작업의 필요성으로 인한 확장성의 한계가 존재, Lack of scalability)
        • job이 여러 CPU에서 수행했다 말았다 하는 것은 Cache 의 장점을 이용하기 어렵다. job이 다른 cpu로 갈때마다 이전cpu의 cache에 있는 내용은 무용지물이 돼서!

      

      • Cache affinity를 고려해서 다시 스케쥴링해보면

      

      대부분 선호도를 유지하는 방법을 택한다면 → A,B,C,D는 cpu하나씩 잡고 실행

      But. E는 cpu들을 계속 번갈아가면서 선택하여 실행됨 → 구현하기 복잡할수도?

    • Multi-queue Multiprocessor Scheduling (MQMS) 다중 대기열 멀티프로세서 스케쥴링

      • 여러개의 대기열이 있고, 각 대기열은 특정 스케쥴링 규칙을 따른다.
      • job이 시스템에 들어오면, 정확히 하나의 스케쥴링 대기열에만 배치된다.
        • 정보공유 or 동기화 문제를 방지하기 위해서 (like 각cpu에os따로 있는거처럼)
      • 예시

      

      • 할당 불균형 문제 Load Imbalance 문제

        • C가 다 끝나거나 A가 다 끝난 경우에 발생할 수 있는 문제

        

        • 이러한 문제의 해결방안

          • Migration 이주

            • Q0 대기열에 job이 없다면, B나 D를 Q0로 옮겨서 실행

            • Q0에 A만 남은 경우에도 이주를 할 수 있는데 이런 식의 패턴도 가능!

              

        • Work Stealing 작업 도둑질

  • Linux Multiprocessor Schedulers 리눅스 멀티프로세서 스케쥴러