[OS] 6. CPU 스케줄링

[이화여자대학교 반효경 교수님의 강의를 듣고 정리한 글입니다.]

운영체제

운영체제 운영체제는 컴퓨터 하드웨어 바로 위에 설치되는 소프트웨어 계층으로서 모든 컴퓨터 시스템의 필수적인 부분이다. 본 강좌에서는 이와 같은 운영체제의 개념과 역할, 운영체제를 구성하는 각 www.kocw.net

운영체제

---

[그림과 함께 편하게 보려면 여기로]

https://adorable-aspen-d23.notion.site/OS-6-CPU-71b6941e5fc94583a08abe780b6ddda3

[OS] 6. CPU 스케줄링

1. CPU 스케줄링

1. 기본 용어

1. CPU bound job, I/O bound job

• CPU burst
  • CPU 할당 후 입출력 요구시까지의 시간
  • CPU에서 기계어를 사용하는 단계, 계산 위주
• CPU bound job
  • CPU burst가 길게 일어나는 작업
• I/O bound job
  • CPU burst가 짧으며, 자주 일어나는 작업
  • 입출력 요청이 자주 일어나는 사용자와의 interaction이 많은 job

2. CPU 스케줄링이 필요한 이유

• 시스템 자원을 효율적으로 사용하기 위해 필요하다.
  • 여러 종류의 job(process)들이 존재하는데, CPU bound job이 CPU를 장시간 가지게 되면
    • I/O bound job의 응답속도가 늦어지고, 사용자들은 답답함을 느끼게 된다.
  • 어떻게 하면 효율적으로 job들을 스케줄링 할 수 있을까?
    • interactive한 job들이 너무 오래 기다리지 않게!

3. CPU Scheduler & Dispatcher

• CPU Scheduler
  • Ready큐에서 어떤 프로세스에게 CPU를 줄지 결정한다.
• Dispatcher
  • CPU를 누구에게 줄지 결정한 후, 그 프로세스에게 CPU를 넘겨주는 운영체제 커널 코드
  • 문맥교환을 수행하는 애
    • 현재 실행 중인 프로세스의 Context를 저장하고,
    • 새로 실행할 프로세스의 Context를 받아와 세팅한다. (CPU register, PC 등등..)
• CPU 스케줄링이 일어나는 경우
  • 1. Running → Blocked (I/O시스템콜)
  • 1. Running → Ready (Timer interrupt)
  • 1. Blocked → Ready (I/O 완료 후 인터럽트)
  • 1. Terminated
• 1,4는 nonpreemptive(비선점 - 자진반납)
• 2,3은 preemptive(선점 - 강제로 빼앗음) 스케줄링이다.

2. CPU Scheduling

1. 성능 척도

• 시스템 입장
  • CPU Utilization (이용률)
    • 전체 시간 중에서 CPU를 놀리지 않고 일한 시간의 비율
  • Throughput(처리양)
    • 주어진 시간 동안에 몇 개의 작업을 완료했는가
• 프로세스 입장
  • TurnAround Time (소요시간,반환시간)
    • CPU를 처음 쓰러 들어와서, 다 쓰고 나갈 때까지 걸린 시간
    • 쓴시간 + 대기시간 총합
  • Waiting Time (대기시간)
    • CPU를 대기하는 시간
  • Response Time (응답시간)
    • Ready Queue에 들어와서 처음으로 CPU를 얻기까지 걸린 시간
    • 처음으로 얻는 시간이 사용자 입장에서 굉장히 중요
• 중국집 예시
  • 사장님 입장
    • Utilization
      • 주방장이 노는 시간을 줄이고 일하는 시간을 늘리면 좋다
    • Throughput
      • 주어진 시간 동안 많은 요리가 완성되면 좋다
      • 짜장면,코스요리,짬뽕의 주문이 들어왔을 때 요리 순서를 어떻게 하느냐에 따라 주어진 시간 동안 더 많은 요리를 완성할 수 있다.
  • 손님 입장
    • TurnAround Time
      • 손님 입장에서 코스 요리를 주문했으면 처음 주문한 후, 코스 요리 다 기다리고 다 먹고 나갈 때까지 걸린 시간
    • Waiting Time
      • 손님 입장에서 코스 요리 중간중간 대기한 시간들의 합
    • Response Time
      • 주문하고 첫 음식이 나올 때까지 걸린 시간

2. 선점/비선점

• 선점형 스케줄링 (Preemptive)
  • CPU를 빼앗을 수 있다.
  • 장점
    • 프로세스의 우선순위가 높은 프로세스를 먼저 처리할 수 있고, 응답시간이 빠르다.
  • 단점
    • 많은 오버헤드를 초래한다. (문맥교환 많음)
• 비선점형 스케줄링 (nonpreemptive)
  • 이미 할당된 CPU를 빼앗을 수 없고, 모든 프로세스들의 요구를 공정하게 처리한다.
  • 장점
    • 문맥교환 횟수가 적고, 응답 시간 예측이 쉽다
    • I/O bound작업의 경우 CPU bound 작업을 기다려야 하는 일이 생긴다.

2. CPU Scheduling Algorithm

1. 스케줄링 알고리즘

1. FCFS(First-Come First Served)

• 우선순위 : 프로세스 도착 순으로 처리
  • ex) 은행 번호표, 화장실 줄 선 순서대로, 끝날 때까지 보장
• 선점형
• 단점
  • CPU bound 프로세스가 먼저 선점된다면, 뒤에 도착한 프로세스들은 기다려야 한다.
    • 대화형 프로세스의 경우 응답시간이 매우 늦어질 수 있다.(답답)
  • Conboy Effect : 먼저 도착한 프로세스의 종류에 따라 waiting time이 천차만별이다.

2. SJF (Shortest -Job-First)

• 우선순위 : CPU burst Time이 짧은 작업 순으로 처리
  • ex) 화장실 빨리 처리하는 애 먼저, 변비는 나중
• 선점형, (비선점형)
  • Preemptive(선점)
    • 더 짧은 애가 들어오면 CPU를 넘겨줌
    • Shortest-Remaining-Time-first
    • Average waiting time을 보장 (최적화)
  • Nonpreemptive(비선점)
    • 더 짧은 애가 들어오더라도 CPU사용을 보장
• 장점
  • Waiting time의 평균이 가장 짧아진다. (평균 대기 시간 최적 알고리즘)
• 단점
  • Starvation
    • CPU 사용시간이 긴 프로세스는 영원히 사용이 안될 수도 있음
  • CPU burst time을 미리 알 수 없음
    • 장기 스케줄링의 경우는 과거를 보고 예측해서 사용할 수 있지만 (exponential averaging - 지수적 평균), 단기 스케줄링의 경우 불가하다.

3. Priority Scheduling

• 우선순위 : 우선순위가 높은 작업
  • 내부적 우선순위 고려 : 제한시간, 메모리 요구량, 사용하는 파일 수, 평균 CPU 버스트에 대한 평균 입출력 버스트의 비율 등
  • 외부적 우선순위 고려 : 사용료, 정책적인 변수 등
• 선점형, (비선점형)
• 장점
  • CPU bound 프로세스 < IO bound 프로세스 ⇒ 대화성을 증진시킬 수 있다.
• 단점
  • Starvation(기아)
    • 우선순위가 낮은 프로세스가 지나치게 많이 기다리는 문제
    ⇒ Aging(노화) 기법 도입
    • 시스템에 머무는 시간이 증가함에 따라 우선 순위를 올려주자

4. Round Robin (RR)

• 현대 선점형 운영체제의 근간이 되는 스케줄링
  • Timer가 존재하여 timer의 시간을 세팅하고 프로세스에게 넘기며 timer interrupt로 프로세스의 CPU 독점을 막는다.
• 선점형
• 각 프로세스는 Time Quantum(타임슬라이스) 만큼씩 CPU가 할당된다.
  • 할당 시간이 끝나면 프로세스는 선점당하고, Ready Queue의 제일 뒤에 가서 다시 줄을 선다.
  • 어떤 프로세스도 (n-1)*q 시간 이상 기다리지 않는다. (n:프로세스 개수, q:타임슬라이스)
• 장점
  • 공정한 기회 (기아상태X)
  • 응답 시간이 빨라진다.
  • SJF보다 turn-aroung time이나 waiting time의 평균값은 길어질 수 있지만, 응답 시간은 짧다.
• 단점
  • 잦은 문맥교환으로 오버헤드가 발생할 수 있다. (처리율 감소 가능)
  • 타임슬라이스에 의해 성능이 큰 영향을 받는다.
  • CPU burst타임이 거의 동일한 프로세스가 들어온다면, 마지막에 한번에 다 끝날 수 있다.
    • But, 일반적으로는 짧은 프로세스, 긴 프로세스들이 섞여있기 때문에 괜춘
• Time quantum
  • q large → FCFS와 유사
  • q small → 오버헤드 커짐
  • 10-100 millisecond정도가 적당하다.
    • CPU busrt의 80%가 타임퀀텀보다 짧도록 조정
• CPU burst time이 긴 프로세스는 waiting time이 길어지고, 짧은 프로세스는 짧아진다.

5. Multilevel Queue (다단계 큐 스케줄링)

• 우선순위 마다의 준비큐를 형성
  • 큐에 한 줄 서기가 아니라, 여러 줄로 줄서기
• 항상 가장 높은 우선순위 큐의 프로세스에 CPU를 할당한다.
  • 각 큐는 독립적인 스케줄링 알고리즘을 가진다.
    • Foreground(interactive) → RR
    • Background(batch, no human interaction) → FCFS
• Fixed priority Scheduling
  • 철저한 계급주의, 신분 상승이 불가능하다.
  • starvation 발생이 가능하다.
• Time Slice Scheduling
  • ex) 80%는 우선순위 높은 큐에, 20%는 낮은 큐에

2. 추가 스케줄링 알고리즘

1. Multilevel Feedback Queue (다단계 피드백 큐 스케줄링)

• 타임슬라이스 소진 시 하위 큐의 뒤로 삽입한다.
• Aging 기법 사용 (기아 상태 예방)
  • 하위 큐에서 너무 오래 대기하면 대기 상위큐로 이동한다.
• 단점
  • 너무 복잡한 판단이 필요하다.
  • 

2. Multiple-Processor Scheduling

: 한 시스템 내에서 여러 처리기 사용이 가능하면 부하를 공유가 가능하다.

• CPU가 Homogeneous(동종의) 프로세서인 경우
  • Queue에 프로세스를 줄세워 놓고 프로세서가 알아서 꺼내갈 수 있게 한다.
  • 단점
    • 반드시 특정한 프로세서에서 수행되어야 하는 프로세스가 있으면 복잡
• Load Sharing
  • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요하다.
    • 놀고있는 CPU를 줄이자
  • 별개의 큐를 두는 방법 VS 공동 큐를 사용하는 방법

왼쪽 : 비대칭 다중처리, 오른쪽 : 대칭 다중처리

1. Symmetric Multiprocessing(SMP) - 대칭 다중처리

• CPU가 다 대등해서 알아서 하는 것
• 각 프로세서가 각자 알아서 스케줄링 결정

1. Asymmetric Multiprocessing - 비대칭 다중처리

• 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고, 나머지 프로세서들은 거기에 따른다.
• 자료 공유의 필요성이 없다.

3. Real-Time Scheduling

: Deadline이 존재하고, 반드시 이 시간안에 처리되어야 하는 것

• 실시간 시스템
  • Hard real-time systems
    • 정해진 시간 안에 반드시 끝내도록 스케줄링해야함
  • Soft real-time computing
    • 일반 프로세스에 비해 높은 priority를 갖도록 해야 함
• 정적 우선순위 스케줄링 (RM - Rate Monotonic)
  • 우선순위 : 더 짧은 주기의 태스크
  • 장점
    • 구현이 상대적으로 단순하다.
    • 우선순위 예측성이 좋다. (우선순위가 고정되어 있기 때문)
  • 단점
    • 처리기 이용률이 높지 않다.
  • 실시간 태스크 수가 정해져있고, 주기와 수행시간이 파악될 경우 사용하기에 좋다.
• 
• 동적 우선순위 스케줄링 (EOF - Earliest deadline first)
  • 우선순위 : Deadline까지 남은 시간이 짧은 태스크의 작업 (선점형)
  • 장점
    • 처리기 이용률이 이론적으로 100%이다.
  • 단점
    • 과부하시 Domino Effect가 발생할 수 있다. (연달아서 프로세스들이 데드라인을 미스함)
• 

4. Thread scheduling

• Local Scheduling
  • User level Thread의 경우 사용자 수준의 Thread library에 의해 어떤 쓰레드를 스케줄할 지 결정
• Global Scheduling
  • Kernel level Thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 쓰레드를 스케줄할 지 결정