7. CPU Scheduling 1

KOCW 반효경 교수님 운영체제 강의 정리
이 글은 공부한 것을 복습 및 기록하기 위한 게시물입니다.
잘못된 정보가 기입되어 있을 수 있으니 주의해주시기 바랍니다.
강의 링크 : http://www.kocw.net/home/cview.do?lid=5488703b25305c37

1. CPU-burst Time

프로그램의 경로는 CPU만 연속적으로 사용하는 단계와 I/O를 사용하는 단계가 번갈아가면서 실행되는 것이다.
CPU에서 Instruction을 실행하는 단계를 CPU burst라고 하며 I/O를 쓰는 단계를 I/O burst라고 한다.
프로그램의 종류마다 CPU burst와 I/O burst가 나타나는 주기는 다르다.

I/O bound job이란 CPU를 짧게 사용하고 I/O burst가 자주 끼어드는 비중이 높은 것을 말한다.
CPU bound job이란 CPU를 오래 사용하고 I/O burst를 자주 사용하지 않는 것을 말한다.
실제로 CPU는 CPU bound job 비중이 높으며 I/O bound job은 빈도가 많지만 CPU를 사용하는 비중이 낮다.

CPU Scheduling이 필요한 이유는 I/O bound job 때문이다.
사람과 연결된 interative한 job을 우선순위로 두어야 한다.

CPU Scheduling은 2가지의 중요한 이슈가 있다.

1. 누구에게 우선해서 CPU 소유권을 줄 것인가
2. 언제 얼마만큼의 시간을 주고 뺐을 것인가
   
   
   

2. 프로세스의 특성 분류

3. CPU Scheduler & Dispatcher

CPU Scheduler는 누구에게 CPU를 줄 것인지 결정하는 운영체제(kernel) 코드이다.
Dispatcher는 CPU를 누구에게 줄지 결정되었으면 CPU를 전달해주는 역할을 하는 운영체제(kernel) 코드로
CPU에서 돌아가던 프로세스의 Context를 저장하고 새로 CPU를 넘겨주는 프로세스의 Context를 CPU 레지스터에 설정해놓는다.

CPU Scheduling이 필요한 경우는 다음과 같은 상태 변화가 있은 경우이다.

1. Running -> Blocked
   nonpreemptive
   ex) I/O를 요청하는 시스템 콜
2. Running -> Ready
   preemtive
   ex) CPU 소유권 할당시간 만료로 인한 timer Interrupt
3. Blocked -> Ready
   preemtive
   ex) I/O 완료 후 Interrupt
   I/O가 끝났을 때는 Ready로 보내고 CPU를 바로 할당해주지는 않는다.
   그러나 CPU를 바로 넘겨줄 때도 있다.
   (ex. 우선순위 CPU Scheduling에서 I/O를 요청한 프로세스가 우선순위가 가장 높을 경우)
4. Terminate
   nonpreemptive
   
   
   

• nonpreemptive : 비선점형, 강제로 빼앗지 않고 자진 반납
• preemptive : 선점형, 강제로 빼았음, 현대적인 CPU Scheduling
  
  
  

4. Scheduling Criteria

• 시스템 입장에서의 성능 척도 : 이용률, 처리량
• 프로그램 입장에서의 성능 척도 : 소요시간, 대기시간, 응답시간
  
  
  

1. CPU uillization(이용률)
   전체시간에서 CPU가 일한 시간을 뜻한다.
   가능한 CPU를 바쁘게 일을 시켜야 한다.

2. Throughput(처리량)
   주어진 시간동안 몇 개의 작업을 완료하였는지를 뜻한다.

3. Turnaround time(소요시간)
   CPU burst를 다 사용하고 나가는 시간을 뜻한다.
   CPU burst에서 CPU를 쓴 시간과 기다리는 시간의 총합

4. Waiting time(대기시간)
   CPU burst를 기다리는 시간을 뜻한다.
   한번의 CPU burst안에서 CPU를 얻었다가 뺏겨서 기다리는 시간의 총합

5. Response time(응답시간)
   처음으로 CPU를 얻기까지의 시간을 뜻한다.
   CPU burst에서 처음으로 CPU를 얻기까지의 시간
   time-sharing을 사용하는 환경에서는 처음으로 CPU를 얻는 시간은 사용자 응답과 관련하여 굉장히 중요한 시간이다.
   
   
   

preemptive Scheduling은 CPU를 얻었다고 해서 끝까지 사용할 수 있는 것은 아니다.
시간의 개념과 프로세스의 개수는 프로세스가 시작돼서 종료되는 것이 아닌 매 CPU burst건에 한해서
CPU Scheduling의 대상이 되는 것이다.

5. Scheduling Algorithms

5-1. FCFS(First-Come First-Served)

 

먼저 들어온 순서대로 처리하는 것을 말한다.
nonpreemptive Scheduling으로 효율성이 떨어진다.
맨 처음 어떤 프로세스가 선점하느냐에 따라서 대기시간이 천차만별이다.
긴 프로세스가 도착해서 짧은 프로세스들이 오래기다리는 것을 Convoy effect라고 한다.

5-2.SJF(Shortest-Job-First)

CPU를 짧게 쓰는 프로세스에게 먼저 CPU를 한당하는 것을 말한다.(CPU burst가 제일 짧은 것)
preemptive 기준으로 대기시간이 줄어들게 되고 제일 짧은 average 대기시간을 보장한다.
preemptive 버전은 SRTF라고도 부른다.

기존에 CPU를 사용하고 있는 프로세스보다 더 짧게 사용하는 프로세스가 들어올 때
CPU를 넘겨주는 것이기 때문에 기존에 CPU를 사용한 프로세스들 중에서도 제일 짧은 프로세스에게 CPU를 넘겨주게 된다.

 

SJF는 극단적으로 CPU 사용이 짧은 JOB을 선호하기 때문에 CPU 사용이 긴 프로세스는 영원히 CPU를 사용하지 못할 수 있다.
이러한 현상을 Starvation(기아) 현상이라 한다.
프로세스가 CPU 사용시간을 미리 알 수 없다.
과거의 데이터를 통해 사용시간을 예측할 수 있다.

• 1. 실제 CPU 사용시간.
• 2. CPU 사용시간을 예측한 시간
     
     
     

5-3. Priority Scheduling

우선순위 Scheduling을 뜻한다.
우선순위가 제일 높은 프로세스에게 CPU를 넘겨주게 된다.



이 Scheduling은 preemptive 버전과 nonpreemptive 버전으로 나눌 수 있다.

• preemptvie : 현재 실행되고 있는 프로세스보다 우선순위가 더 높은 순위의 프로세스가 있다면 바로 CPU를 넘겨줌
• nonpreemptive : 현재 실행되고 있는 프로세스는 다 실행할 동안 CPU를 보장해주고 완료가 되면 우선순위에 따라 CPU를 넘겨줌
  
  
  
  우선순위가 높지않은 프로세스는 Starvation 현상을 겪을 수 있다.
  이러한 해결법으로는 Aging(노화)이 있다.
• Aging : 아무리 우선수위가 낮더라도 대기시간만큼 우선순위를 높여줌
  
  
  

5-4. Round Robin(RR)

현대적인 CPU Scheduling으로 preemptive Scheduling이다.
CPU 응답시간(response time)이 빨라진다.
대기시간이 CPU를 사용하려는 시간에 비례하게 된다.
할당시간이 길게 되면 FCFS와 같아지게 되고
할당시간이 짧게 되면 Context Switch overhead가 커지게 된다. 즉, 시스템 전체 성능이 낮아지게 된다.

 

CPU 사용시간이 모두 동일한 프로그램이 있을 때 FCFS는 적어도 1개의 프로세스만이라도 빨리 사용하고
나갈 수 있지만 Round Robin일 경우 동일한 대기시간을 가지고 동시에 프로세스가 나가게 된다.
이럴 경우 Round Robin 방식이 더 안좋을 수 있다.
그러나 일반적으로는 CPU 사용시간이 동일하지 않기 때문에 Round Robin이 효율적이다.
Round Robin은 Turnaround Time보다 Response Time이 짧아진다는 것에 장점이 있다.