본문 바로가기

CS/운영체제

운영체제(6) - CPU 스케줄링

반응형

CPU bound job

  • CPU를 길게 쓰는 프로그램들

I / O bound job

  • 입출력이 많은 작업들, 키보드 입력같은거

여러 종류의 JOB( = process)이 섞여 있기 때문에 CPU 스케줄링이 필요하다

 

CPU Scheduler

  • Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.

Dispactcher

  • CPU의 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘긴다
  • 이 과정을 context switch(문맥교환)라고 한다

CPU스케줄링이 필요할 때

  1. Running  - > Blocked ( 예 : I / O 요청을 위한 시스템 콜) - > 자진 반납
  2. Running - > Ready ( 예 : 할당시간만료로 timer interrupt) - > 강제
  3. Blocked - > Ready ( 예 : I / O 완료 후 인터럽트) - > 강제
  4. Terminate - > 자진 반납

Scheduling Criteria( 성능 척도 )

  • Cpu utilization ( 이용률)
  • Throughput( 처리량 )
  • Turnaround time( 소요시간, 반환시간)
  • Waiting time( 대기 시간)
  • Response time( 응답 시간)

다양한 스케줄링 알고리즘

 

1. FCFS ( First - Come First - served)

단순하게 먼저오는 것부터 처리하는 알고리즘, 비선점 스케줄링 방법 중 하나이다

 

Convey effect ( 호위 효과 ) : 긴 시간을 잡아먹는 프로세스가 먼저오게 되면 뒤에 있는 프로세스들이 오랜시간 기다려야 하는 현상

 

2. SJF ( Shortest - Job - First)

  •  CPU burst time이 가장 짧은 프로세스를 제일 먼저 실행
  • SJF is optimal, 주어진 프로세스들에 대해 minimum average waiting time을 보장
  • 두가지 방식이 존재한다
    • Nonpreemptive : 수행중인 CPU는 계속 실행...
    • Preemptive : 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김. Shortest - Remaining - Time - First ( SRTF ) 
  • 단점 : 다음번 CPU burst time을 어떻게 알 수 있는가? 추정(estimate)만이 가능하다. 과거의 CPU burst time을 이용해서 추정

3. Priority Scheduling

  • highest priority를 가진 프로세스에게 CPU 할당
  • SJF는 일종의 Priority Scheduling이다. 왜냐하면 CPU burst time이 짧은 일에 우선순위를 주기 때문이다
  • Starvation 현상이 발생가능하다, ( Starvation : 우선순위가 낮은 프로세스가 계속 실행되지 않는 현상)
    • 해결책으로는 Aging이 있다 ( Aging : 오래기다리면 우선순위를 높여준다 )

4. Round Robin ( RR )

  • Preemtive 방식
  • 각 프로세스는 동일한 크기의 할당시간( time quantum )을 가짐
  • 할당시간이 너무 크면 FCFS, 너무 작으면 Context Switch 오버헤드가 너무 커진다
  • 제일 많이 사용하는 CPU 스케줄링의 근간이 됨
  • response time은 더 짧다
  • 일반적으로 SJF보다 average turnaround time이 길다

5. Multilevel Queue

  • ReadyQueue를 여러 개로 분할
    • foreground ( interactive ) 
    • background ( batch - no human interaction)
  • 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  • 큐에 대한 스케줄링이 필요
    1. Fixed Priority Scheduling
      • 무조건 foreground 먼저, background는 나중에...
      • Starvation 발생 가능....
    2. Time Slice, 각 큐에 CPU time을 적절한 비율로 할당

6. Multilevel Feedback Queue

  • 여러개의 줄이 있는데( 큐가 존재 ), 프로세스가 다른 큐로 이동 가능
  • 에이징을 이 방식으로 구현 가능
  • Multilevel - Feedback - queue scheduler를 정의하는 파라미터들
    1. Queue의 수
    2. 각 큐의 Scheduling algorithm
    3. Process를 상위 큐로 보내는 기준
    4. Process를 하위 큐로 내쫓는 기준
    5. 프로세스가 CPU 서비스를 받으러 할 때 들어간 큐를 결정하는 기준

 

7. Multiple - Processor Scheduling

  • CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
  • Homogeneous processor인 경우
    • 큐에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다
    • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐...
    • Load Sharing( Load balancing) 
      • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
      • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
    • Symmetric Multiprocessing ( SMP )
      • 각 프로세서가 각자 알아서 스케줄링 결정
    • Asymmetric Multiprocessing
      • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

8. Real - Time Scheduling

  • Hard real - time systems
    • Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링 해야함
  • Soft real - time systems
    • Soft real-time task는 일반 프로세스에 비해 높은 Priority를 갖도록 해야함 ex) 동영상

9. Thread Scheduling

  • Local scheduling
    • User level thread의 경우 사용자 수준의 Thread library에 의해 어떤 Thread를 스케줄할지 결정 ( = 프로세스 내부에서 결정)
  • Global scheduling
    • Kernal level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 Thread를 스케줄할지 결정

Algorithm Evaluation

  • Queueing models
    • 확률분포로 주어지는 arrival rate와 service rate등을통해 각종 Performance index 값을 계산
  • Implementation ( 구현 ) & measurement ( 성능 측정 ) 
    • 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 비교
  • Simulation ( 모의 실험 ) 
    • 알고리즘을 모의 프로그램로 작성 후 trace를 입력으로 하여 결과 비교

 

이 포스팅은 이화여대에서 무료로제공하는 반효경님의 운영체제강의를 수강하며 정리한 내용입니다.

필자가 잘 이해하지 못해서 잘못된 내용이 있을 수 있으므로 주의바라며, 발견되면 알려주시면 감사하겠습니다.

http://www.kocw.net/home/search/kemView.do?kemId=1046323 

 

운영체제

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

www.kocw.net

 

반응형