[운영체제] Ch5. CPU 스케줄링

공룡책(운영체제)을 읽고 정리한 글입니다.

 

 

 

실질적으로 운영체제는 프로세스가 아니라 커널 수준 스레드를 스케줄한다.
그러나 '프로세스 스케줄링'과 '스레드 스케줄링' 용어는 상호 교환적으로 사용된다.

일반적인 스케줄링 개념이면 '프로세스 스케줄링'을 사용하고, 스레드에 국한된 개념이면 '스레드 스케줄링' 이라는 용어를 사용할 것이다.

 

CPU 스케줄링 기본 개념

 

하나의 프로세스가 I/O요청이 완료되기를 기다리고 있다. 만약 프로세스가 I/O응답을 받기 전까지 다른 프로세스를 실행하지 못하고 기다린다면 시간을 매우 비효율적으로 사용하게 된다.

따라서 어느 프로세스가 대기해야 할 경우, 운영체제는 CPU를 회수해 다른 프로세스에게 할당해야 할 것이다.

결국 CPU는 항상 바빠야 한다는게 중요한 원칙이 된다. 그래서 거의 모든 컴퓨터 자원들은 사용전에 스케줄된다.

 

 

용어, 개념 정리

1. CPU-I/O 버스트 사이클

프로세스의 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다.

프로세스 실행은 CPU 버스트로 시작된다. 이어서 I/O 버스트가 발생하고, 이들이 반복되다가 종료된다.

 

위 그림은 CPU 버스트 지속시간에 따른 빈도수를 나타낸 그래프이다. (컴퓨터마다 많이 다르지만 일반적으로 위와 같다.)

지속시간이 짧을수록 많이 일어나는 것을 볼 수 있다. 

CPU 지향 프로그램은 다수의 긴 CPU 버스트를 가질 수 있고, I/O지향 프로그램은 짧은 CPU 버스트를 많이 가질 것이다.

버스트
는 정보기술의 여러 가지 상황에서 사용되는 용어로서, 간헐적으로 특정 량의 데이터를 주고받는 것을 의미한다. 이 용어는 "스트림", "연속적인" 등의 용어와 대비될 수 있다.

 

---

2. CPU 스케줄러

CPU가 유휴 상태가 될 때마다, 운영체제는 준비 큐에서 다음 프로세스를 선택해서 실행해야 한다.

선택 절차는 CPU 스케줄러에 의해 수행된다. 

 

준비 큐는 반드시 FIFO 방식의 Queue가 아니어도 된다. 우선순위 큐, 트리, 연결리스트 등의 다양한 자료구조를 사용할 수 있다. 하지만 개념적으로는 준비 큐에 있는 프로세스는 CPU에서 실행될 기회를 기다리며 대기한다.

이때 큐에 있는 정보들은 일반적으로 PCB(프로세스 제어 블록)들이다.

 

---

3. 선점 및 비선점 스케줄링

 

선점형 스케줄링

현재 CPU가 프로세스를 실행하고 있음에도 불구하고, 다른 프로세스가 현재 프로세스를 중지시키고 CPU의 사용을 빼앗을 수 있는 방식이다.

일반적으로 Windows, Linux, macOS를 포함한 최신 운영체제들은 대부분 선점 스케줄링 알고리즘을 사용한다.

 

장점  

긴급하게 처리해야 할 높은 우선순위를 가진 프로세서들을 빠르게 처리할 수 있다.

 

단점

데이터가 다수의 프로세스에 의해 공유될 때 경쟁 조건(race condition)을 초래할 수 있다.

A, B 프로세스가 데이터를 공유하고 있다고 가정하자.

A 프로세스가 자료를 갱신하는 도중에 B가 CPU를 선점하여 B 프로세스가 실행이 되어버렸다.

이런 경우에 A가 작업하던 데이터의 일관성이 깨지는 문제가 생기게 된다.

프로세스 간 문맥 교환이 자주 발생하므로 운영 체제의 오버헤드가 증가한다.

 

 

비선점형 스케줄링

한 프로세스가 CPU를 할당받아 실행중이라면 다른 프로세스들이 CPU를 강제적으로 뺏을 수 없는 스케줄링 방식이다.

 

장점

모든 프로세스에 대한 공정한 처리가 가능하다.

프로세스 간의 오버헤드가 적어 효율적이다.

 

단점

긴 작업이 짧게 끝나는 작업을 오랫동안 기다리게 되는 경우가 발생한다.

 

---

4. 디스패처

 

CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스로 넘겨주는 작업을 도와주는 모듈이다.

디스패처는 다음과 같은 작업을 포함한다.

• 한 프로세스에서 다른 프로세스로 문맥을 교환하는 일
• 사용자 모드로 전환하는 일
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일

 

디스패처는 모든 프로세스의 문맥 교환 시 호출되므로, 가능한 한 최고로 빨리 수행되어야 한다.

(문맥 교환은 초당 수십~수백번이 일어나기 때문에 디스패처의 속도가 빨라야 한다.)

디스패처가 하나의 프로세스를 정지하고, 새로운 프로세스를 시작하는데까지 소용되는 시간을 디스패처 지연이라고 한다.

 

---

스케줄링 기준

CPU 스케줄링 알고리즘은 정말 많고 각각의 특성이 존재한다.

따라서 특정 상황에서 어떠한 알고리즘을 선택하려면, 스케줄링에 대한 기준이 필요하다. 비교하는데 사용되는 특성에 따라서 최선의 알고리즘을 결정하는 데 큰 차이가 발생한다.

 

1. CPU 이용률(utilization)
   가능한 CPU를 바쁘게 유지해야 한다.
   실제 시스템은 주로 40% ~ 90% 범위를 가져야 한다.
   
   
2. 처리량(throughput)
   CPU가 프로세스의 수행때문에 바쁘다면, 작업이 진행중인 것이다.
   단위 시간당 처리한 프로세스의 개수를 처리량이라고 한다.
   긴 프로세스를 처리한 경우 이 비율을 몇 초동안 하나의 프로세스가 될 수 있고, 짧은 트랜잭션(짧은 일의 단위)인 경우 초당 수십 개의 프로세스가 될 수 있다.
   
   
3. 총처리 시간(turnaround time)
   특정한 프로세스의 입장에서 보면, 중요한 기준은 그 프로세스를 실행하는 데 소요된 시간일 것이다.
   프로세스의 제출 시간과 완료 시간의 간격을 총 처리 시간이라고 한다.
   준비 큐에서 대기한 시간, CPU에서 실행하는 시간, I/O시간을 합한 것이다.
   
   
4. 대기 시간(waiting time)
   스케줄링 알고리즘은 프로세스의 실행, I/O를 하는 시간의 양에 영향을 미치지는 않는다.
   단지 프로세스가 준비 큐에서 대기하는 시간의 양에만 영향을 준다.
   대기 시간은 준비 큐에서 대기하면서 보낸 시간의 합이다.
   
   
5. 응답 시간(response time)
   대화식 시스템에서 총처리 시간은 최선의 기준이 아닐 수 있다.
   프로세스가 어떤 출력을 매우 일찍 생성하고, 이전의 결과가 사용자에게 출력되는 사이에 새로운 결과를 얻으려고 연산을 게속하는 경우가 종종 있다. 따라서 하나의 요청을 보낸 후 첫 번째 응답이 나올 때까지의 시간이 기준이 될 수 있다.
   응답 시간은 응답이 시간되는 데까지 걸리는 시간이다.(출력 미포함)
   
   

결국 CPU 이용률 최대화, 총처리 시간, 대기 시간, 응답 시간을 최소화 하는것이 바람직하다.

대부분 평균 측정 시간을 최적화하려고 한다.

하지만 평균 보다는 최솟값 또는 최댓값을 최적화하는것이 더 바람직할 수도 있다.

 

우리가 사용하는 PC의 경우에는 평균 응답 시간을 최소화하기보다는 응답 시간의 편차(variable)를 최소화하는 것이 중요하다고 한다.

---

스케줄링 알고리즘

 

• First In, First Out (FIFO) : 우리가 알고있는 Queue의 작동방식과 동일하다.
  • 먼저 도착한 프로세스가 CPU를 먼저 사용한다.
  • 가장 먼저 도착한 프로세스의 작업시간이 길어질 수록 뒤에 도착한 프로세스가 작업을 완료하기까지의 시간이 매우 오래 걸린다. 다른 프로세스의 Turnaround time이 매우 길어지게 된다.
  • 위와 같은 현상을 Convoy Effect라고 한다.

 

• Shortest Job First (SJF) | Shortest-Remaining-Time-First
  • 작업시간이 짧은 프로세스먼저 처리하는 방식이다.
  • 여기서 선점형 방식과 비선점형 방식을 나눌 수 있다.
    • 선점형 방식 
      1. A라는 작업이 100시간이 걸리는데 현재 10시간을 해서 90시간이 남은 상태라고 하자
      2. B라는 작업은 15시간이 걸리고 지금 준비상태에 들어와있다.
      3. 이때 A의 남은시간(90시간)보다 B의 남은시간(15시간)이 더 짧으므로 A를 중단하고 B를 먼저 실행한다.
    • 비선점형 방식
      1. 동시에 들어온 경우가 아니라면 FIFO와 동일하다.
• Round Robin (RR) Scheduling
  • 임의의 time slice만큼 프로세스를 수행하고, 다음 프로세스로 CPU권한을 넘겨주는 방식이다.
  • time slice가 10ms이고 A, B, C 프로세스가 대기중이라면 10ms간격으로 프로세스를 실행하게 된다.
  • 선점형 방식이고 공정하다. -> CPU를 받지 못하는 프로세스가 없다.(No starvation)
  • 단점 : 빨리 끝날 수 있는 프로세스도 RR방식으로 time slice만큼만 실행이 반복된다면 turnaround time이 증가하는 경향이 있다.
  • 장점 : 모든 프로세스의 response time이 매우 빨라질 수 있다.
  • 주의사항 : time slice의 길이가 매우 중요함을 알 수 있다.
    • 짧은 time slice : 더 좋은 response time | context switching overhead가 퍼포먼스에 큰 영향을 끼침
    • 긴 time slice : 좋지 못한 response time | context switching 비용의 감소

 

 

[운영체제] 스케줄링 알고리즘 (Scheduling Algorithms)

 

 

Basic MLFQ(MultiLevel Feedback Queue)

[OS] Scheduling #2

 

 

Basic MLFQ의 문제점 해결

[OS] Scheduling #3

 

 

---

스레드 스케줄링

 

스레드는 사용자 수준 스레드와 커널 수준 스레드로 나뉘게 된다.

사용자 수준과 커널 수준 스레드의 차이 중 하나는 이들이 어떻게 스케줄 되느냐에 있다.

 

다대일, 다대다 모델 시스템에서 스레드 라이브러리는 사용자 수준 스레드를 LWP(Light Weight Process == Thread) 상에서 스케줄 한다. 이 모델 시스템에서는 동일한 프로세스에 속한 스레드 간에 CPU를 경쟁하기 때문에 프로세스-경쟁-범위(process-contention scpop, PCS)로 알려져있다. (LWP도 마찬가지로 PCS에 속한다고 생각한다.)

 

'스레드 라이브러리는 사용자 수준 스레드를 LWP(Light Weight Process) 상에서 스케줄 한다.' <- 이 말은 스레드가 실제로 CPU 상에서 실행 중이라는 것을 의미하지 않는다. 실제로 CPU 상에서 실행되기 위해서는 운영체제가 LWP의 커널 스레드를 물리적인 CPU 코어로 스케줄 하는 것을 필요로 한다.(스케줄 한다고 해서 바로 실행과 연관되지 않는다는 뜻)

 

CPU 상에 어느 커널 스레드를 스케줄 할 것인지 결정하기 위해서 커널은 시스템-경쟁-범위(system-contention scope, SCS)를 사용한다.

SCS 스케줄링에서의 CPU에 대한 경쟁은 시스템 상의 모든 스레드 사이에서 일어난다. Windows와 Linux 같은 일대일 모델을 사용하는 시스템은 오직 SCS만을 사용하여 스케줄 한다.

 

전형적으로, PCS는 우선순위에 따라 행해진다. 즉, 스케줄러는 가장 높은 우선순위를 가진 실행가능 프로세스를 선택한다. 그리고 더 높은 우선순위 스레드를 위하여 현재 실행중인 스레드를 선점할 수 있다.

사용자 수준 스레드의 우선순위는 프로그래머에 의해 지정되고, 스레드 라이브러리에 의해 조정되지 않는다.

 

 

#include < pthread.h > 
#include < stdio.h > #define NUM THREADS 5

int main(int argc, char * argv[]) {
    int i,
    scope;
    pthread t tid[NUM THREADS];
    pthread attr t attr;
    
    /* get the default attributes */
    pthread attr init(& attr);
    
    /* first inquire on the current scope */
    if (pthread attr getscope(& attr, & scope) != 0) 
        fprintf(stderr, "Unable to get scheduling scope∖n");
     else {
        if (scope == PTHREAD SCOPE PROCESS) 
            printf("PTHREAD SCOPE PROCESS");
         else if (scope == PTHREAD SCOPE SYSTEM) 
            printf("PTHREAD SCOPE SYSTEM");
         else 
            fprintf(stderr, "Illegal scope value.∖n");
    }
    
    /* set the scheduling algorithm to PCS or SCS */
    pthread attr setscope(& attr, PTHREAD SCOPE SYSTEM);
    
    /* create the threads */
    for (i = 0; i < NUM THREADS; i ++) 
        pthread create(& tid[i], & attr, runner, NULL);
    
    /* now join on each thread */
    for (i = 0; i < NUM THREADS; i ++) 
        pthread join(tid[i], NULL);
    
}

/* Each thread will begin control in this function */
void * runner(void * param) { /* do some work ... */
    pthread exit(0);
}

 

 

pthread_attr_setscope(pthread_attr_t *attr, int scope)

pthread_attr_getscope(pthread_attr_t *attr, int *scope)

두 함수의 첫 번째 매개변수 attr 는 스레드를 위한 속성 집합을 가지키는 포인터를 저장한다.

setscope의 두 번째 매개변수 scope 는 경쟁 범위가 어떻게 지정되는가를 가리키는 PTHREAD_SCOPE_SYSTEM 또는 PTHREAD_SCOPE_PROCESS 값이 전달된다.

getscope의 두 번째 매개변수 *scope 는 경쟁 범위의 현재 값을 저장할 int 값을 가리키는 포인터를 저장한다.

 

만일 오류가 발생하면 각 함수는 0이 아닌 값을 반환한다.

 

int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void *), void *arg);

스레드를 생성한다.

첫번째 매개변수 thread 는 스레드가 성공적으로 생성되었을때 생성된 스레드를 식별하기 위해서 사용되는 스레드 식별자이다. 

두번째 매개변수 attr 은 스레드 특성을 지정하기 위해서 사용하며, 기본 스레드 특성을 이용하고자 할 경우에 NULL 을 사용한다. 

세번째 매개변수 start_routine는 분기시켜서 실행할 스레드 함수이다. (runner)

네번째 매개변수 arg는 위 start_routine 스레드 함수의 매개변수로 넘겨진다.

 

 

int pthread_join(pthread_t th, void **thread_return);

특정 스레드가 종료하기를 기다렸다가, 스레드가 종료된 이후 다음을 진행한다.

첫번째 매개변수 th 는 기다릴 스레드의 식별자이다.
두번째 매개변수 thread_return 은 스레드의 리턴값이다.

(thread_return 이 NULL이 아닌 경우 해당 포인터로 스레드의 리턴 값을 받아올수 있다.)

join된 스레드 (종료된 스레드)는 모든 자원을 반납하게 된다.

 

성공적으로 실행된 경우 0을 리턴한다.

---

다중 처리기 스케줄링

 

 

---

실시간 CPU 스케줄링