운영체제 - CPU 가상화(스케줄링 & 공유자원 관리)

 

'운영체제 - 아주 쉬운 세 가지 이야기'와 'Computer System - A Programmer's Perspective'를 읽고 작성한 글 입니다. 틀린 부분이 있을 수 있습니다.

 

CPU 가상화

운영체제는 CPU, 메모리, 디스크와 같은 자원들을 가상화시킨다. 

 

Task Manager - Performance창 캡처 (window)

내 컴퓨터의 Task Manager 화면을 살펴보자. Logical processor는 4개인데(코어 수와 차이나는 이유는 하이퍼쓰레딩 때문이다.), Process는 251개가 현재 돌아가고 있다. 심지어 Thread의 개수는 3312개다. 한정된 개수의 Logical processor위에서 이렇게 많은 수의 process와 thread가 동작할 수 있는 이유는 운영체제가 CPU를 가상화시켜주기 때문이다. 한정된 자원인 CPU를 무한개의 CPU가 존재하는 것처럼 변환하여 동시에 많은 수의 프로그램을 실행시키는 것이다.

 

프로세서가 한개인 상황을 가정해보자. 하나의 프로세서에서 multithreaded process가 실행될 때, 프로세서는 시분할을 통해 CPU가 여러개인 듯한 추상화를 제공한다. 스레드간에 context-switching을 하며 번갈아 실행함으로써 동시에 실행되고있는 것 처럼 보이는 것이다.

 

이번 포스팅에서는 운영체제가 병행성을 제공하면서 해결해야하는 문제들 중 두가지를 짚어볼 것이다. 바로, 스케줄링과 공유자원 관리이다.

 

 

스케줄링

운영체제는 CPU를 어느 프로세스에게 할당해주어야 할 지 결정해야 한다. 공정하고 효율적인 스케줄링 정책에 대해 반환시간과 응답시간의 관점에서 알아보자.

 

반환시간은 작업이 도착하는 시점부터 작업이 끝날 때 까지의 시간이며, 응답시간은 작업이 도착하고 최초로 스케줄링되는데까지 걸리는 시간이다. 반환시간이 길다면, 작업이 끝날 때 까지 너무 오랜 시간이 소요될 것이다.(CPU자원을 차지하지 못하고 굶어 죽을 수도 있다. starvation) 응답시간이 길다면, 사용자가 굉장히 답답함을 느낄 것이다. (마우스를 움직였는데 5초후에 커서가 움직인다고 생각해보자.)

 

더 복잡한 알고리즘들이 많지만, 이번 포스팅에서는 반환시간과 응답시간의 관점에서 '선입선출(First In First Out)', '최소 잔여시간 우선(Shortest Time-to-Completion First)', '라운드 로빈(Round Robin)' 그리고 '멀티레벨 피드백 큐(Multi-Level Feedback  Queue)'까지 다뤄볼 예정이다.

 

선입선출 FIFO

가장 기본적인 구현이 쉬운 스케줄링 알고리즘이다. 

말 그대로 먼저 도착한 작업을 먼저 처리하게 된다. 

 

각각 10초를 소비하는 세개의 작업 A,B,C가 순서대로 거의 동시에 도착했다고 가정해보자. 

A 10초 -> B 10초 -> C 10초 

위와 같이 CPU를 점유하고 작업을 진행하게 될 것이다.

이때, 반환시간은 (10+20+30)/3으로 20초이다.

 

다른 상황을 가정해보자.

B,C는 그대로이고 A의 작업시간이 100초로 늘어나면 어떻게 될까?

A 100초 -> B 10초 -> C 10초 

이 순서로 실행되며, B와 C작업은 추가된지 각각 110초, 120초 이후에 끝나게 된다.

반환시간은 (100+110+120)/3으로 110초이다.

 

B와 C는 A에 비해서 상대적으로 빠르게 끝날 수 있는 작업임에도 불구하고 A보다 조금 늦게 도착했다는 이유로 A의 작업이 모두 끝날 때 까지 기다려야 한다...

 

작업의 도착순서에 따라, 반환시간이 최악이 될 수 있다.

 

이렇게 CPU를 많이 필요로 하지 않는 프로세스들이, CPU를 오랫동안 사용하는 프로세스가 끝나기를 기다리는 현상을 convoy effect라고 한다.

운영체제 - 아주 쉬운 세 가지 이야기

 

최소 잔여시간 우선 STCF

이 스케줄러는 특정 작업이 도착했을 때, 현재 실행중인 작업의 잔여시간과 새로운 작업의 잔여시간을 비교해 잔여 실행시간이 더 적은 작업을 먼저 실행시킨다.

 

100초가 필요한 작업 A가 실행되다가, 10초 후 10초가 걸리는 작업 B와 C가 도착했다고 가정해보자.

B와 C가 도착했을 때, B가 A보다 잔여 작업시간이 더 적기 때문에 A는 잠시 멈추고 B가 CPU를 선점하게 된다.

A 10초 -> (선점)B 10초 -> C 10초 -> A 90초 

이런 과정을 거쳐 세 작업이 실행되게 된다. 

 

반환시간은 (120+10+20)/3으로 50초이다.

선입선출 알고리즘과 비교했을 때 평균 반환시간이 더 짧아진 것을 확인할 수 있다. (110초 -> 50초)

 

최소 잔여시간 우선 알고리즘은 잔여시간을 알 수 있다는 비현실적인 가정을 하고 있다. 

반환시간의 측면에서 FIFO알고리즘보다 개선이 되었지만, 응답시간의 측면에서는 여전히 성능이 좋지 못하다.

 

라운드 로빈 RR

작업이 종료될 때 까지 기다리지 않고, 일정 시간간격마다 작업을 교체하는 알고리즘이다.

특정 작업이 끝나지 않았더라도, 타임 슬라이스마다 작업을 번갈아가며 실행시킨다. 때문에, 라운드 로빈은 응답시간의 측면에서 최고의 강점을 가진다.

 

각각 10초를 소비하는 세개의 작업 A,B,C가 순서대로 거의 동시에 도착했다고 가정해보자.

아래의 그림과 같이 세 작업 모두 번갈아가며 실행된다. 이때, 응답시간은 1초 미만이다. (타임 슬라이스가 아주 크지 않다면)

운영체제 - 아주 쉬운 세 가지 이야기 [그림 7.7]

반환시간을 살펴보자. 

A,B,C모두 공평하게 번갈아가면서 실행되기 때문에 세 작업 모두 반환시간은 약 30초이다. 따라서, 평균 반환시간도 30초이다.(context-switching비용을 고려한다면 30초 이상의 평균 반환시간을 가질 것이다.)

같은 조건에서 선입선출 알고리즘의 평균 반환시간은 20초였다. 

확실히 반환시간면에서 성능이 좋지 않음을 확인할 수 있다. 

 

또한 타임 슬라이스가 짧을 수록 응답시간은 좋아지겠지만, 그만큼 작업간에 스케줄링이 빈번하게 일어나기 때문에 context-switching 비용이 커지게 된다.

 

멀티레벨 피드백 큐 MLFQ

university of wisconsin-madison, Scheduling: The Multi-Level Feedback Queue [figure8.7]

라운드 로빈 스케줄러는 작업들을 번갈아 실행시키며 응답시간을 최소로 한다. 하지만, 반환시간의 측면에서는 성능이 최악이다.

최소 잔여시간 우선 스케줄러는 남은 작업들 중 진행 시간이 가장 짧은 작업을 수행한다. 평균 반환 시간을 최소로 하지만, 응답시간의 측면에서는 성능이 좋지 못하다. 심지어 잔여시간을 알 수 있다는 비현실적인 가정까지 함께 하고 있다.

 

MLFQ는 응답시간과 반환시간의 절충을 이루어 냈고, 작업을 수행하며 잔여시간에 대해 판단한다.

이름에서도 알 수 있듯이 MLFQ는 여러 개의 큐로 이루어져 있으며, 각각의 큐들은 다른 우선순위를 가진다.

높은 우선순위를 가진 작업이 낮은 우선순위를 가지는 작업보다 먼저 실행되게 되며, 우선순위가 동일한 작업의 경우 라운드 로빈으로 번갈아가며 실행되게 된다.

 

그렇다면, 우선순위는 어떻게 결정되는 것일까?

작업의 순서를 결정하는 스케줄러는 특정 작업의 잔여시간을 판단할 수 없기 때문에, 우선 짧게 끝나는 작업이라는 가정을 하고, 최고의 우선순위를 부여한다. 이후, 일정한 시간이 지나면 해당 작업의 우선순위를 서서히 낮추게 된다. 짧은 작업시간을 가지는 대화형 작업의 경우 우선순위가 낮아지기 전에 작업이 끝날 것이고, 자동으로 우선순위가 낮아진 작업들은 긴 작업시간을 요구하는 작업이라는 것을 알 수 있게 된다.

 

이렇게 우선순위를 활용해서 응답시간을 단축시키는데 성공했다.

 

oslab.kaist - pintos project [multilevelfeedback.pptx]

MLFQ는 일정 시간이 지나면 작업의 우선순위를 상향조정한다. 그 이유는 아래와 같다.

 

oslab.kaist - pintos project [multilevelfeedback.pptx]

그림에서 볼 수 있다 싶이, 대화형 작업이 계속 발생한다면, 상대적으로 우선순위가 낮은 작업은 CPU를 얻을 기회를 얻지 못할 것이다. 이렇게 되면 반환시간의 측면에서 악영향을 미칠 수 밖에 없다. 따라서, 대화형 작업이 꾸준히 발생할 때, 긴 배치형 작업에게도 기회를 주기 위해서 주기적으로 우선순위를 상향조정하는 것이다. 이렇게 되면, 긴 작업시간을 필요로 하는 작업도 꾸준히 실행될 기회를 얻을 수 있다.

 

그림에서는 큐가 세개 정도로 나타나지만, 실제로는 더 많을 수 있다. 또, 같은 우선순위를 가지는 작업간에 라운드 로빈 방식으로 스케줄링 되는데, 이때 time slice를 큐 별로 변경할 수도있다. 우선순위가 높은 작업들은 주로 대화형 작업들임으로, 빠르게 교체해 줌으로써 응답성을 높이고, 우선순위가 낮은 CPU 중심의 작업들은 context-switching 부담을 줄이기 위해 time slice를 상대적으로 길게 유지한다.

 

kaist oslab ppt를 살피던 중 Solaris MLFQ implementation을 가져와 보았다. 참고하자.

 For the Time-Sharing scheduling class (TS)
 60 Queues
 Slowly increasing time-slice length
 The highest priority: 20msec
 The lowest priority: A few hundred milliseconds
 Priorities boosted around every 1 second or so.

- oslab.kaist pintos project [multilevelfeedback.pptx]

 

MLFQ는 멀티 레벨 큐를 가지고 있으며, 지정된 작업의 우선순위를 정하기 위하여 피드백을 사용한다. 과거에 보여준 행동이 우선순위 지정의 지침이 된다. 작업이 시간이 지남에 따라 어떻게 행동하고 그에 맞게 어떻게 처리하는지에 대해 주의를 기울여라.

운영체제 - 아주 쉬운 세 가지 이야기

---

공유자원 관리

왜 공유자원을 관리할 필요가 있는지 알아보자. 

아래의 코드는 스레드 두개를 생성한 후, 두 스레드간에 공유되는 전역 변수인 counter 변수를 1 증가시키는 행위를 각각 10,000,000번 수행한다. 

코드가 제대로 동작한다면, 20,000,000이 결과로 print되어야할 것이다.
onlinegdb사이트에서 컴파일하고, 실행시켜볼 수 있다. 직접 결과를 확인해보자. 운이 좋아 20,000,000이 결과로 나올 수도 있지만, 두세번 더 실행시켜본다면, 결과가 달라져있을 것이다.

www.onlinegdb.com/online_c_compiler

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

// volatile [https://ko.wikipedia.org/wiki/Volatile_%EB%B3%80%EC%88%98]
volatile int cnt = 0;
long loops;

void *worker(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        cnt++;
    }
    return NULL;
}

int main(int argc, char *argv[])
{
    loops = 10000000;
    pthread_t p1, p2;
    printf("Initial value : %d\n", cnt);
    
    pthread_create(&p1, NULL, worker, NULL);
    pthread_create(&p2, NULL, worker, NULL);
    pthread_join(p1, NULL);
    pthread_join(p2, NULL);
    
    printf("Final value : %d\n", cnt);    
    return 0;
}

 

20,000,000이 아닌 다른 숫자가 출력되는 것을 확인할 수 있다.

12292776이라는 결과를 얻었다. 왜 20,000,000이 아닌 다른 숫자가 출력되는 것일까? 

 

바로, 공유자원이 제대로 관리되지 않았기 때문이다.

 

단순해 보이는 덧셈 연산이지만, counter 변수를 1 증가시키는 `counter++;`부분은 아래 그림과 같이 Load, Update, Store 세 개의 명려어로 이루어진다.

Computer System - A Programmer's Perspective 그림 12.17

* 어셈블리어를 읽는데 뭔가 이상해서 찾아보니 책이 잘못된듯 하다. (stackoverflow참고) cnt++;이 원자적인 연산이 아님을 알아보기 위한 예시였음으로, 별도로 다루지는 않겠다.

 

이렇게 cnt를 증가시키는 부분은 cnt값을 레지스터로 탑재하는 명령어, 레지스터를 1 증가시키는 명령어 그리고 레지스터의 값을 다시 메모리에 저장하는 명령어로 이루어져 있다. 우리가 실행한 코드에서는 이 세 개의 명령어가 원자적으로 실행되지 않았기 때문에, 제대로된 값을 얻을 수 없었던 것이다.

 

더 자세하게 얘기해보자. 

Load, Update, Store를 L, U, S라 하고, i번 Thread가 수행하는 명령어를 Li, Ui, Si라고 하자. 최초에 cnt는 0이다.

 

 

L1, U1 - 1번 Thread가 cnt의 값을 register로 읽어들이고(L1), register에 저장된 변수를 1 증가시켰다.(U1)

 

Context Switching - 이때, 1번 Thread가 scheduling당하고, 2번 Thread로 문맥 전환이 일어났다.

 

U2, L2, S2 - 아직 1번 Thread가 update한 변수를 register에서 memory로 저장하지 않았기 때문에, 2번 Thread가 읽은 cnt값은 여전히 0이다. 2번 Thread가 이 cnt값을 reigster로 읽어들이고(L2), register에 저장된 변수를 1 증가시켰다.(U2) 2번 Thread는 register에 저장된 변수를 메모리로 옮기고(S2), scheduling 당한다. 메모리에는 1이 저장된다.

 

S1 - 1번 Thread가 다시 실행되고, 다음 인스트럭션을 수행하기 시작한다. register에 남아있던 변수값을 메모리로 옮긴다.(S1) 1번 Thread의 register에 저장된 cnt값은 1임으로, 메모리에는 다시 1이 저장된다.

 

 

위의 예시에서 L1, U1, S1이 실행된 이후 L2, U2, S2가 실행되면, cnt가 정상적으로 2로 증가할 것이다. 이처럼 명령어의 실행 순서에 따라 결과가 달라지는 상황을 race condition이라고 한다. 이러한 상황에서 필요한 것이 mutual exclusion이다. mutual exclusion은 하나의 Thread가 임계 영역 내의 코드를 실행 중일 때는 다른 쓰레드가 실행할 수 없도록 보장해준다.

 

임계 영역(critical section)은 보통 변수나 자료 구조와 같은 공유 자원을 접근하는 코드의 일부분을 말한다.
경쟁 조건(race condition) 혹은 데이터 경쟁(data race)는 멀티 쓰레드가 거의 동시에 임계 영역을 실행하려고 할 때 발생하며 공유 자료 구조를 모두가 갱신하려고 시도한다면 깜짝 놀랄 의도하지 않은 결과를 만든다.
비결정적(interminate) 프로그램은 하나 또는 그 이상의 경쟁 조건을 포함하여 그 실행 결과가 각 쓰레드가 실행된 시점에 의존하기 때문에, 프로그램의 결과가 실행할 때마다 다르다. 결과는 컴퓨터 시스템에서 일반적으로 기대하는 바와 달리 결정적이지 않다.
이와 같은 문제들을 회피하려면 쓰레드는 상호 배제(mutual exclusion)라는 기법의 일종을 사용하여서 하나의 쓰레드만이 임계 영역에 진입할 수 있도록 보장한다. 그 결과로 경쟁을 피할 수 있고 프로그램 실행 결과를 결정론적으로 얻을 수 있다.

운영체제 - 아주 쉬운 세 가지 이야기

 

락 Lock

프로세스를 실행하는 도중 인터럽트로 인해 명령어가 원자적으로 실행될 수 없는 경우 락을 이용해 임계영역 내의 변수들을 다루는 명령어들이 원자 단위의 명령어인 것 처럼 실행되게할 수 있다.

 

 

위에서 다루었던 코드에 락을 추가해 cnt++;코드가 원자적으로 실행되도록 처리했다. 실행시켜보면, 실제로 20,000,000이 결과로 도출되는 것을 확인해볼 수 있다.

* Thread 간에 상호 배제(mutual exclusion) 기능을 제공하기 때문에 POSIX 라이브러리는 락을 mutex라고 부른다. - 운영체제 - 아주 쉬운 세 가지 이야기

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

// volatile [https://ko.wikipedia.org/wiki/Volatile_%EB%B3%80%EC%88%98]
volatile int cnt = 0;
long loops;
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

void *worker(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        pthread_mutex_lock(&lock);
        cnt++;
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

int main(int argc, char *argv[])
{
    loops = 10000000;
    pthread_t p1, p2;
    printf("Initial value : %d\n", cnt);
    
    pthread_create(&p1, NULL, worker, NULL);
    pthread_create(&p2, NULL, worker, NULL);
    pthread_join(p1, NULL);
    pthread_join(p2, NULL);
    
    printf("Final value : %d\n", cnt);    
    return 0;
}

 

락은 어떻게 만들까?

 

1. 인터럽트 제어

 

임계영역 내에서 인터럽트를 비활성화한다면, 임계영역 내의 코드를 실행할 때는 인터럽트가 발생할 수 없고, 명령어들이 원자적으로 처리될 수 있다. 

void lock() {
	DisableInterrupts();
}

void unlock() {
	EnableInterrupts();
}

단순하게 해결된 것처럼 보이지만, 이 방법에는 많은 문제점들이 존재한다.

 

• 인터럽트를 비활성화시키기 위해서는 유저모드에서 실행되고 있는 프로그램의 권한을 높여주어야 한다.
• 어플리케이션이 인터럽트를 비활성화시킨 후 인터럽트를 다시 활성화하지 않는다면, 운영체제가 제어권을 다시 얻을 수 없다.
• 멀티프로세서에서는 적용할 수 없다. 특정 프로세서에서 인터럽트를 비활성화 하더라도, 다른 프로세서에서 실행 중인 프로그램은 영향을 받지 않는다. 

 

2. 스핀 락

 

flag를 사용해서 락을 구현할 수는 없을까?

 

임계 영역에 진입하는 쓰레드가 flag를 1로 증가시킨 후 임계 영역의 명령어를 실행하는 중에 스케줄링 당했다고 가정해보자. 다른 쓰레드도 임계 영역으로 진입하려 할 때, mutex의 flag를 확인하게 되고, 이때 flag는 1이기 때문에 계속 while문을 돌며 flag가 1이 되길 기다린다. 그러다가, 다시 타이머 인터럽트가 발생하고 context-switching이 발생해 락을 소유하고 있는 쓰레드가 실행된다. 이 쓰레드는 flag를 0으로 변경한 후 락을 반납한다.

 

typedef struct __lock_t { 
	int flag; 
} lockt_t;

void init (lock_t *mutex) {
	mutex->flag = 0;
}

void lock (lock_t *mutex) {
	while (mutex->flag == 1)
		;
	mutex->flag = 1;
}

void unlock (lockt_t *mutex) {
	mutex->flag = 0;
}

 

잘 작동하는 듯 보이지만, 이 코드에는 두가지 문제점이 존재한다.

 

첫 번째는 flag가 0임을 확인하고 1로 변경하는 연산이 원자적이지 않다는 것이다. flag를 확인하고 변경하는 과정이 원자적이지 않다면, 두개의 쓰레드 모두 flag를 1로 변경해 임계 영역의 변수를 동시에 건드리게 될 수도 있다.

lock함수의 while문을 탈출한 직후에 스케줄링 되고, 다른 쓰레드가 flag를 1로 변경한다면 두개의 쓰레드가 동시에 lock을 획득하게 될 수 있다. 락은 상호 배제가 목적인데, 이 결과는 우리가 원하는 결과가 아니다.

 

두 번째는 flag가 0이 될때까지, 그러니까 다른 쓰레드가 락을 반납할때 까지 while문을 돌며 기다린다는 것이다. 대기하는 와중에도 CPU 자원을 불필요하게 소모한다.

 

먼저 첫 번째 문제를 해결해보자. 

flag를 확인하고, 변경하는 작업이 원자적으로 이루어지지 않는다는 것이 문제였음으로, 이를 개선하자.

하드웨어단에서 지원해주는 TestAndSet 명령어를 사용할 수 있다.

 

* Test-and-set를 지원하는 아키텍처 마다 다른 이름으로 부른다. SPARC에서는 load/store unsigned byte 동작을 하는 ldstub, x86에서는 원자적 교체 명령어인 xchg의 락 버전이다. - 운영체제 - 아주 쉬운 세 가지 이야기

 

TestAndSet 명령어는 변수의 값을 변경하고, 변수의 원래 값을 반환하는데 이를 원자적으로 처리한다. 위의 코드와 아래의 코드에서 lock부분에서 차이점을 확인해볼 수 있다.

typedef struct __lock_t {
	int flag;
} lock_t;

void init (lock_t *lock) {
	lock->flag = 0;
}

void lock (lock_t *lock) {
	while (TestAndSet(&lock->flag, 1) == 1)
		;
}

void unlock (lock_t *lock) {
	lock->flag = 0;
}

 

다음으로 두번째 문제 스핀락이다. 

 

스핀락은 상호 배제를 정확히 수행해준다는 면에서 락의 역할을 충실히 하고 있다.

하지만, 성능이나 공정성 면에서 보았을 때는 형편없는 모습을 보여준다.

 

공정성

여러 쓰레드가 하나의 락을 얻기 위해서 경쟁하고 있는 상황에서 특정 쓰레드가 락을 얻을 수 있다는 보장을 할 수 없다. 해당 쓰레드가 운이 없어서 락이 해제된 즉시 자신의 프로그램을 실행시키지 못하고 계속 다른 쓰레드들이 락을 차지해 버린다면, 해당 쓰레드는 굶게(starvation) 된다.

 

성능

스핀락은 상당히 비효율적이다. 락을 가진 쓰레드와 해당 락을 필요로 하는 두개의 쓰레드가 더 있다고 가정해보자. 현재 락은 첫 번째 쓰레드가 점유하고 있어 나머지 두개의 쓰레드는 임계 영역으로 진입할 수 없지만, 스케줄러는 이들에게도 CPU 자원을 일정부분 할당해준다. 

 

[스핀락이 필요한 경우]

https://www.notion.so/youseop/PS-CS-study-5002e240171f4a5a9ac137987fca7d4d

 

 

3. waiting 큐 사용

 

쓰레드는 실행되다가 스케줄러에 의해 ready큐로 들어간다. 이후 자기 차례가 돌아오면 다시 running 상태가 되어 명령어를 실행한다. 스핀락은 락을 필요로 하는 쓰레드들을 다시 ready큐에 삽입하고, 락이 아직 반환되지 않았는데 running 상태가 되면 while문을 실행하다가 다시 ready큐에 삽입되도록 하는 방식이다.

ready큐에서 대기를 시키면, 해당 쓰레드의 차례가 돌아왔을 때 아직 락을 얻을 수 있는 상태가 아닌데도, CPU 자원을 소모한다. 이를 waiting 큐를 활용해 해결할 수 있다.

 

각각의 락 별로 waiting 큐를 운영한다. 락이 현재 가용상태가 아니지만, 락을 필요로 하는 쓰레드의 경우 해당 락의 waiting 큐에 push 시킨다. 이후, 락이 가용가능한 상태가 되었을 때 큐의 제일 앞에 있는 쓰레드를 pop시켜 ready 큐에 삽입하면, 락이 가용가능해진 시점에 쓰레드가 실행되도록 할 수 있다.

 

아래 그림을 보며 이해해보자.

(0번 쓰레드가 락을 쥐고 있고, 1번 쓰레드와 2번 쓰레드는 락을 필요로 한다.)

1. 0번 쓰레드가 lock을 획득하고 명령어를 실행시키다가 락을 반납하지 못한채로, 스케줄링 당했다.

2. 1번 쓰레드의 차례가 돌아와 실행되는데, 1번 쓰레드는 락을 필요로 한다. 현재 락은 0번 쓰레드가 소유하고 있음으로, 해당 락의 waiting 큐에 1번 쓰레드를 추가해 놓는다.

 

3. 1번 쓰레드가 waiting 큐에 추가되며 running 상태에서 waiting 상태로 변했다. ready 큐의 제일 앞에 있던 2번 쓰레드가 실행된다. 2번 쓰레드도 락이 필요하기 때문에 1번 쓰레드와 같은 과정을 거쳐 waiting 큐에 추가되게 된다.

4. 0번 쓰레드의 차례가 돌아오고, 작업을 끝낸 0번 쓰레드가 lock을 반납했다. 락이 반납되었음으로, waiting 큐에서 가장 앞에 위치하는 1번 쓰레드를 pop한 후에 ready 큐에 추가한다.

 

이 방식을 통해 스핀락에서 문제가 되었었던 공정성과 성능 부분을 모두 해결할 수 있다.

 

락이 점유당한 상태에서 다른 쓰레드가 락을 얻으려고 시도하면, 해당 쓰레드들은 waiting 큐에 차례대로 push되고, 락이 가용가능해졌을 때, 차례대로 pop되면서 공정하게 락을 사용할 수 있다.(우선순위가 모두 같을 경우)

 

락을 필요로 하지만, 아직 얻지 못한 경우 해당 쓰레드를 ready 큐에 방치하는 것이 아닌 waiting 큐에 추가해 락이 반납되기 전 까진 scheduling되지 않는다. 따라서, 불필요하게 CPU자원을 낭비하지 않는다.

 

 

 

 

 

 

 

 

참고한 자료

• Computer System - A Programmer's Perspective
• 운영체제 - 아주 쉬운 세 가지 이야기
• oslab.kaist - multilevelfeedbackque link
• University of Wisconsin-Madison link
• Oracle - multithreaded programming guid link
• MIT - reading 17: Concurrency link
• 테크 스케치 블로그 link
• onlinegdb link
• stackoverflow(mistake in Computer System figure 12.17) link