운영체제 (OS) - Chapter 05

● Chapter 05의 목표

- 다중 프로그램 운영 체제기반의 CPU 스케줄링에 대해 설명
- CPU 스케줄링에 사용되는 다양한 알고리즘 대해 설명
- 특정 시스템을 위한 CPU 스케줄링 알고리즘을 선택하는 데 사용되는 기준에 대해 설명명
- 운영체제에서 사용되는 스케줄링 알고리즘에 대해 설
 
 
 
 
 
 
 
 
 
 
 

● Basic Concepts

- CPU 사용성을 최대화하려면 해당 CPU를 필요로 하는 프로세스들이 여러개가 있어야함 (멀티프로그래밍 형태)
- 프로세스 실행은 CPU 실행과 I/O 대기의 처리로 구성됨
- 프로세스의 실행은 CPU 버스트로 시작한 다음 I/O 요청 작업을 실행함
 
 
 
 
 
 
 
 
 
 
 
 
 

 

● Histogram of CPU-burst Times

- burst duration : CPU를 사용한 시간
- frequency: CPU를 사용한 빈도
- 대부분의 프로세스들의 burst는 길지 않다는 것을 알 수 있음
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

● CPU Scheduler

- ready queue안에 있는 프로세스들은 다양한 방법으로 순서가 정해질 수 있음
 
[CPU 스케쥴링 정 타이밍]
 
 
- 프로세스가 실행 상태에서 대기 상태로 전환될 때
- 프로세스가 실행 상태에서 준비 상태로 전환될
- 프로세스가 대기 상태에서 준비 상태로 전환되는 경우
- 프로세스가 종료될 때
 
[스케쥴링 종류]
 
- 실행 상태에서 대기 상태로 전환, 프로세스 종료 시에서의 스케줄링은 비선점형(nonpreemptive)임, 즉, 프로세스에 CPU가 주어지면 자발적으로 제어권을 포기하거나 종료될 때까지 CPU를 빼앗을 수 없음
- 나머지는 선점형(preemptive) 스케쥴링을 사용, 스케줄러가 프로세스가 CPU를 강제로 종료시킬 수 있음
 
- 선점형 스케쥴링은 공유 데이터에 대한 액세스를 신중하게 관리해야 함
- 선점형 스케쥴링은 커널 모드에서 프로세스가 선점되는 경우 어떤 일이 발생하는지 고려하여 설계되어야 함
- 선점형 스케쥴링은  중요한 OS 작업 중에 인터럽트를 효과적으로 처리해야 함
 
 
 
 
 
 
 
 
 

 

● Dispatcher

- 다스패처 모듈은 단기 스케줄러가 선택한 특정 사용자 프로세스에 운영 체제에서 CPU 제어를 넘기는 역할을 해줌
- 컨텍스트 전환: 이전 프로세스의 상태를 저장하고 새 프로세스의 저장된 상태를 로드하여 CPU를 한 프로세스에서 다른 프로세스로 전환하는 것
- 사용자 모드로 전환: 운영 체제가 하드웨어에 대한 모든 액세스 권한을 가지고 특권 명령을 실행할 수 있는 커널 모드에서 애플리케이션 코드가 제한된 권한으로 실행되는 사용자 모드로 작동 모드를 전환하는 것
- 적절한 위치로 이동: 프로세스 실행을 재개하기 위해 CPU를 사용자 프로그램의 올바른 위치로 이동
 
- 디스패치 대기 시간(Dispatch Iatency): 이 용어는 디스패처가 한 프로세스를 중지하고 다른 프로세스를 시작하는 데 걸리는 시간
 
 
 
 
 

 

● Scheduling Criteria

- CPU 사용율 ( CPU Utilization) : CPU를 최대한 바쁘게 유지하는 것
- 처리량 (Throughput) : 시간 단위당 실행을 완료하는 프로세스 수
- 처리시간 (Turnaround time) : 프로세스 실행부터 프로세스 완료까지 걸린 총 시간
- 대기 시간 (Waiting time) : 프로세스가 준비 큐에서 기다린 총 시간
- 응답 시간 (Response time) :  request 이후 첫 번째 응답이 생성될 때까지 걸리는 시간,  출력된 시간은 아님
 
 
 
 
 
 
 
 
 
 
 
 
 
 

● Scheduling Algorithm Optimization Criteria

- CPU사용률을 최대화 했는가
- 처리량을 최대화 했는가
- Turnaround time을 최소화했는가
- Waiting time을 최소화 했는가
- Response time을 최소화 했는가
 
 
 
 
 
 
 
 
 
 
 

● First Come First Service Scheduling(FCFS)

- 가장 먼저 오는 프로세스를 가장 먼저 실행함
- Convoy effect - 긴 프로세스뒤에 짦은 프로세스가 있으면 짧은 프로세스들은 Waiting timing에 영향을 받음
 
 
 
 
 
 
 
 
 
 
 
 

● Shortest Job First Scheduling (SJF)

- CPU burst가 적은순으로 프로세스를 실행  
- 프로세스들이실제로 각 CPU burst가 얼만큼씩 필요로 하는지를 정확히 알아내기 힘들기에 구현이 힘듬 ( 사용자에게 물어보는 방법이 있음) 
 
 
 
 
 
 
 
 
 
 
 
 

● Determining Length of Next CPU Burst

- exponential averaging

   Tn = n번쨰의 실제 CPU burst 실행시간
    Tn+1 = 다음 CPU burst의 예측 실행시간

다음 CPU burst 실행시간 = a * 이전의 실행시간 + (1 - a) (이전의 예측했던 CPU burst 실행시간) 
 
대부분의 다음 CPU burst 에측값 = (실제 CPU burst 측정값 + 이전의 CPU burst 예측값) / 2
 
 
 
 
 
 

● Prediction Length of Next CPU Burst 예제

- 다음 CPU burst 예측값 = ( 실제 CPU burst + 이전의 예측값 ) / 2
 
 
 
 
 
 
 
 
 
 
 

● Prediction Length of Next CPU Burst 예제

-  α는 가장 최근의 CPU 버스트가 다음 버스트 추정에 어느 정도 영향을 미치는지 결정하는 가중치임
- α=0: 최근 기록은 예측에 영향을 미치지 않으므로 계속 같은 예측값을 가짐
- α=1: 마지막 실제 CPU 버스트에 의해서만 결정되기에, 가장 최근의 버스트 시간만 고려하고 이전 데이터는 모두 무시됨
 
- 가중치가 올라갈수록 점점 더 큰 거듭제곱으로 제곱되고, 이전 버스트에 주어지는 가중치는 점점 감소합니다
 
 
 
 
 
 
 
 
 
 
 
 
 
 

● Shortest Remaining Time First 예제

burst time이 1인시점에는, 남은 P1의 burst time인 7과 P2의 burst time을 비교, P2가 더 적으니 P2를 실행, P1은 다시 ready queue로 돌아감,

burst time이 2인 시점에는, P3도 추가, P2가 아직 젤 작으므로 P2가 CPU에 그대로 할당, 나머지 P2, P3는 Ready queue에 할당

burst time이 3인 시점에는 P4도 추가, 그대로 P2가 계속 작으니 그대로 실행

burst time이 5인 시점에는 P2 종료, P1, P3, P4 중 P4가 5로 젤 작으므로 P4를 CPU에 할당

burst time이 10인 시점에는 P4가 종료, P1, P3중 7로 더 작은 P1이 다시 CPU에 할당, P3는 ready queue에서 대기

burst time이 17인 시점에는 P1이 종료, 마지막으로 burst time이 0인 P3를 실행후 burst time이 26인 시점에 모든 프로세스가 종료됨

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

● Priority Scheduling

- 우선 순위 수치가 실제로 할당되어, 우선순위 값이 낮은 순으로 우선시하여 CPU를 할당시킴 
- Shortest Job First(SJF)도 우선순위 스케쥴링중 하나로 볼 수 있음 ( 우선순위 값으로 burst time을 사용)
 
Starvation : 우선순위가 뒤로 밀린프로세스는 계속해서 굶주린채로 기다려야 하는 문제가 발생함

Aging : 시간에 지나면 ready queue에 있는 프로세스의 우선순위를 높여주는 방법으로 starvation을 해결할 수 있음
 
 
 
 
 
 
 
 
 
 
 
 
 

● Priority Scheduling의 예

- priority가 가장 낮은 P2가 가장 먼저 CPU에 할당됨, 그다음 우선순위가 낮은 P5가 P2다음으로 CPU에 할당됨, 이후 낮은 순으로 P1,P3,P4순으로 순서대로 할당됨
 
 
 
 
 
 
 
 
 
 
 
 
 

● Round Robin (RR)

- 프로세스가 CPU에 할당된 Run 상태에서 ready queue로 다시 쫒겨나는 경우를 Round Robin이라고 함
- 만약 n개의 프로세스가 있고 CPU time quantum이 동일하다고 할때 할 때, 각 프로세스는 1/n만큼 나눠서 모두 동일하게 실행하게 됨
- ready queue 안에있는 프로세스는 이전 프로세스 작업 시간이 제한되어 있기 때문에 일정시간이 지나면 이전 프로세스는 interrupts 시키고 다음 프로세스를 실행함
 
 
 
 
 
 
 
 
 
 

 

● Round Robin의 예제

- Time Quantum = 4 
- P1, P2, P3 순으로 선택된다고 가정, P1이 선택되면 4만큼 CPU Time을 실행후 ready queue로 돌아감
- 다음 프로세스인 P2가 다음으로 Time Quantum을 4만큼 할당받고 실행후 ready queue로 다시 돌아가는데 burst time이 3뿐이므로 3만큼만 실행후 종료되었으니 ready queue로 넘어감
- 다음 프로세스인 P3도 P2와 동일하게 4를 할당받지만 3만 실행하고 종료되기에 3만큼 실행후 ready queue로 다시 쫒겨나며, 남은 P1을 4만큼씩 5번을 추가로 할당하여 작업을 마침
 
- Turn-around Time (프로세스가 종료된 시간) : P1 -> 30, P2 -> 7, P3 -> 10
- Response Time (프로세스가 처음 할당된 시간) : P1 -> 0. P2 -> 4, P3 -> 7 
 
 
 
 
 
 
 
 
 
 
 
 

● Time Quantum and Context Switxh Time

- Time Quantum값에 따라 CPU 사용방식이 다름
- Time Quantum이 10일때는 context switxh 횟수가 0번임
- Time Quantum이 6일때는 context switxh 횟수가 1번임
- Time Quantum이 1일때는 context switxh 횟수가 9번임
- Time Quantum 값이 크면 클수록 Context Swith가 줄어들고 , Time Quantum 값이 작아질수록 Context Swith가 늘어남
 
 
 
 
 
 
 
 
 
 

● Trunaround Time Varies With The Time Quantum

- 80%정도의 프로세스 CPU bursts는 q보다 짧아야 함
- 위의 필기는 turnaround time이 5일때를 가정한 것
 
 
 
 
 
 
 
 
 
 
 
 

● Multilevel Queue

- ready queue는 foreground queue와 background queue로 나뉨
- 알고리즘은 foreground 는 Round Robin(RR), background는 First Come First Service (FCFS)를 각각 사용함
- 전체 CPU Time을 100으로봤을 때 80%는 RR을 활용한 foreground를 사용하고 20%는 FCFS를 활용하는 background를 사용함
 
 
 
 
 
 
 
 
 
 
 
 

 

● Multilevel Queue Scheduling

- 어느 프로세스로 실행할 건지 선택하는 스케쥴링이 필요
- 우선순위는 System Processes - Interactive Processses - Interactive Editing Processes - Batch Processes - Student Processes 순으로 높음
 
 
 
 
 
 
 
 
 
 
 
 

 

● Multilevel Feedback Queue

- 낮은 우선순위의 Queue에서 높은 우선순위의 Queue로 이동했다면 Aging방식을 사용하겠다는 것과 같음
- Queue의 개수는 몇개로 할지를 정의해야함
- 각 Queue에 대해 어떤 스켈쥴링 알고리즘을 사용할 지를 정의해야함
- 언제 프로세스를 업그레이드를 시킬지 (낮은 우선순위 Queue에서 높은 우선순위 Queue로 언제 올릴지)를 정의 해야함
- 언제 프로세스를 강등시킬지를 정의 해야함
- 프로세스가 처음 ready queue로 들어왔을 때 어떤 프로세스로 할당시켜야하는지를 정의 해야함
 
 
 
 
 
 
 
 
 
 
 
 

● Multilevel Feedback Queue의 예제

- Q0 : RR을 사용하며 Quantum은 8밀리초임
- Q1 : RR을 사용하며 Quantum은 16밀리초임
- Q2 : FCFS를 사용함 
 
 
- 새로운 작업은 Q0 큐에 들어가며 FCFS 방식으로 처리됨
- CPU를 등록하면 작업은 8밀리초 동안 실행됨
- 8밀리초 안에 작업이 끝나지 않으면 Q1로 이동함
- Q1에서는 작업이 다시 FCFS 방식으로 처리되고 16밀리초 동안 추가로 실행
- 이 시간이 늦어지면 작업이 Q2 큐로 이동함
- Q2에서는 FCFS 방식으로 처리됨
 
 
 
 
 
 
 
 
 
 
 

● Thread Scheduling

- 사용자 영역에서의 쓰레드와 커널영역에서의 쓰레드로 구분됨
- Many-to-One : 여러 사용자 영역의 쓰레드가 하나의 작은 프로세스(LWP)에서 실행되는 모델
- Many-to-Many : 쓰레드 서버가 사용자 영역의 쓰레드를 여러 LWP에 처리하는 모델
 
- Process-Contention Scope (PCS) : 프로세스 내에서 충돌이 발생하는 범위
- System-Contention Scope (SCS) : 시스템 전체에서 모든 스레드가 경쟁이 발생하는 범위
 
 
 
 
 
 
 
 
 
 
 
 
 
 

● Pthread Scheduling

- API는 쓰레드 생성 시 PCS(Process-Contention Scope)나 SCS(System-Contention Scope)를 활용함- - -
- PTHREAD_SCOPE_PROCESS : 스레드를 PCS로 처리함
- PTHREAD_SCOPE_SYSTEM : 스레드를 SCS로 처리함
- Linux와 Mac OS X는 PTHREAD_SCOPE_SYSTEM로 제한됨