[OS] CPU Scheduling (2) - CPU 스케줄링

• 간단히 Ready Queue가 여러 개
  • Interactive를 위한 작업은 foreground - RR Algorithm
  • Batch를 위한 작업은 background - FCFS Algorithm
• Queue에는 두 가지 Scheduling 방식이 할당된다.
  • 우선순위 스케줄링 : stavation 문제 발생 가능
  • Time slice : 각 CPU Time을 할당 예를 들어 RR에는 80% 시간, FCFS에는 20% 시간 할당

 

 

• 우선순위에 따라 process 할당

 

 

• 지금까지 설명했던 우선순위 스캐줄링은 starvation문제가 발생할 가능성이 있었음, 그래서 본 문제를 해결하기 위해 시간이 지남에 따라 우선순위를 좀 더 높게 하는 방식이 있었다.
• 이를 Feedback형태로 다양한 queue에서 process가 움직임을 가능하게 하여 우선순위를 좀 더 높게 하는 방식
• Multilevel-feedback-queue schedular를 구현하기 위해 정의해야하는 파라미터가 존재
  • queue 개수
  • 각 queue가 사용하는 scheduling algorithm
  • process가 하위단으로 내려가는 방식 결정
  • process가 상위단으로 올라가는 방식 결정
  • CPU를 작업을 하다 발생하는 새로운 작업들을 어느 queue 저장하여 CPU 이용율을 높일지

 

 

• Q(0) - RR algorithm : quantum 8 ms
• Q(1) - RR algorithm : quantum 16 ms
• Q(2) - FCFS algorithm

 

• 그럼 어떤 알고리즘을 사용하는 Multi queue라고 할 수 있을까?
• 상황에 따라 매번 다르기 때문에 특정할 수 없음

 

 

• Multiple-Processor Scheduling - 여러 개의 CPU(Processor)의 Scheduling
• Asymmetirc Multiprocessing(비대칭적 : Push) : 여러 개의 process 중 하나만 주가 된 주인 process가 되고 나머지는 slave가 되는 형식. 주인 process가 하위 process에게 작업을 할당해주는 방식. 따라서 오직 하나의 process만 작업 구조(형식)을 확인하면 됨
• Homogeneous(대칭적 : Pull) : 작업을 진행할 수 있을 때 Queue에서 Scheduling을 한 후 작업을 할당
• Processor affinity : 모든 CPU는 자기 자신의 Cache를 가지고 있다. 만약 어떤 특정 CPU를 이용하여 작업을 처리하던 중 I/O Interrupt가 발생하면 작업을 멈추고 I/O 작업을 수행한다. 그리고 다시 전에 작업하던 process를 처리하기 위해 CPU를 할당받고자 하는데 전에 사용하던 CPU에 다시 할당되면 당시 작업하던 유용한 데이터가 CPU Cache에 저장되어있어 사용할 수 있다.
  
  • Hard affinity : 위처럼 작업을 하다가 다른 작업을 하게 되면 다시 돌아왔을 때는 사용하던 CPU를 그대로 사용할 수 있게 보장 하는 기법
  • Soft affinity : 전에 사용하던 CPU를 다시 사용하는 것을 보장해주지는 않음

 

 

 

• CPU가 볼 수 있는 Thread는 User-Level Thread가 아닌 Kernel-Level Thread이다.
• 특정 User-Thread가 LWP or Virtual Process에 할당되는 것 : Local Scheduling
• LWP에 있는 작업은 Kernel-Lebel Thread에게 전달되고 CPU는 어떤 Kernel-Thread를 할당하여 작업을 처리할 지 선택하는 것 을 Global Scheduling이라고 하는 것이다.
• 정리하자면 User-level(or LWP)에서 발생하는 것을 Local Scheduling이라고 함. LWP도 User-level Library에서 제공하는 것이므로
• Kernel-Level은 Global Scheduling

 

 

 

• Hard real-time : 주어진 시간 내에 작업이 끝난다는 것을 보장
• Soft real-time : 우선순위를 높여 최대한 정해진 시간 내 끝내는 것을 목표 (보장은 못함)

 

 

• global priority와 scheduling order는 특별히 다른 것은 없고 우선순위만 따짐
• class-specific priorities는 [real-time / system / interactive&time sharing] 세 가지 class로 나뉘어 우선순위 부여
• 그리고 각각의 class 내에서도 우선순위가 존재한다. → schedular classes
• Run queue : 서로 다른 class 내에서 존재할 수 있는 queue

 

 

[Solaris Dispatch Table]

• 보통 Interactive(사용자와 상호작용을 해야하는)작업과 Time Sharing 작업에 대한 Dispatch Table
• 여기서의 Dispatch는 우선순위를 주고(Prioirty) 그 우선순위의 Time quantum은 얼마를 줄 것이며(Time Quantum) 그 Time Quantum값에서 안끝나면(Time Quantum expired) 그 다음 우선순위는 얼마를 줄거고 I/O 작업이 끝난 다음에 우선순위(Return from sleep)
• 위 표를 분석하자면 우선순위가 높으면 → Time Quantum 값을 적게 줌.

 

ex) 우선순위가 30인 작업이 있는데 Time Quantum은 80이다. 만약 할당된 시간 내 작업을 끝내지 못하면 다음 우선순위는 20이 된다. 그럼 다시 작업을 하게 되었을 때 Time Quantum은 120이 된다. 이렇게 우선순위와 Time Quantum이 반비례 관계를 가지도록 하고 작업을 진행해봤더니 Interactive Process들 대상으로 response가 좋았고 CPU bound  Process는 Throughput이 좋았다. 그리고 Solaris Dispatch 특징 중 하나가 I/O 작업을 끝낸 작업들은 다시 우선순위를 높게 준다.

 

 

 

• 우선순위 class를 6가지로 두었다. real-time이 가장 높고  → 방향으로 갈 수록 낮아짐
• 그리고 하나의 class를 다시 7단계로 나눔. 아래로 갈 수록 낮아짐

 

 

 

• Linux에서는 2가지 알고리즘 존재

 

• Time-Sharing
  • 신용도를 기반으로 신용도가 높은 작업이 가장 높은 우선순위
  • 작업을 진행할수록 신용도 값이 낮아짐. 낮아지다가 신용도 값이 0이 되면 다른 process를 선택하게 됨
  • 위 과정을 반복하면 모든 process가 0이 될 수 있는데 그 때 신용도를 재할당하게 됨 재할당 할 때는 우선순위와 전에 사용하던 CPU이용율을 토대로 재할당하게 됨
• Real-Time
  • Soft Real-Time
    • FCFS와 RR Algorithm 사용
    • 우선순위가 높은 작업을 항상 먼저 실행

 

 

 

• 우선순위가 높은 작업은 Time Quantum값을 크게 주어 시간 내 모두 처리할 수 있는 방향으로 유도 (=Soft real time)

 

 

• active array에서 다 못끝낸 작업들은 expired array에서 대기

 

• 평가 방법 3가지 소개
• Deterministic modeling - Process가 주어지고 그 process들의 Arrival Time, Burst Time에 대한 정보가 주어지고 Gantt Chart 내에서 성능을 계산하는 방식
• Queuing model : 공식을 이용하여 계산하는 방식
• Simulation model : 아래에서 설명

 

• 왼쪽부터 Process를 실행 시킴 → 그 Process에서 일어나는 작업들을 모두 측정하고 기록(Trace tape) → trace tape을 각각의 Algorithm으로 Simulation함 → 성능적 통계치 추출 → 비교 분석하여 최종 선택