Dev.log

지금까지 lock의 개념을 살펴보았고, hardware와 OS의 적절한 조합으로 어떻게 구현되는지 살펴보았다. 하지만, concurrent programs을 빌드하기 위한 기본 요소로 lock만이 있는 건 아니다.

특히, 스레드는 종종 실행을 계속하기 전에 condition이 true인지 확인하고 싶어한다. 예를 들어, 상위 스레드는 계속하기 전에 하위 스레드가 완료되었는지 확인하고 싶을 수 있다. 이를 join()이라고도 부른다. 이러한 기다림(wait)은 어떻게 구현할 수 있을 지 살펴보자. 

Spin-based Aproach - inefficient

Shared Variable(공유 변수)를 사용해 볼 수 있다. 이러한 Spin-based Approach라 칭한 이 솔루션은 일반적으로 작동하지만 상위 항목(parent)이 CPU 시간을 낭비(spin and waste)하고 있기 때문에 매우 비효율적이다.

대신에 우리가 원하는 것은 child의 실행이 끝날 때까지, 즉 우리가 기다리고 있는 condition이 실현될 때까지  parent를 sleep하는 것이다.(CPU를 낭비하지 않고).

멀티 스레드 프로그램에서, 스레드를 계속하기 전에 어떤 조건이 참일 때까지 기다리도록 하는 것이 종종 유용하다. condition이 true가 될 때까지 회전(spin)하는 간단한 방법은 매우 비효율적이며 CPU Cycles를 낭비하며, 경우에 따라서는 부정확할 수 있다. 그렇다면, 어떻게 thread를 wait하는 것이 좋을까?

Definition and Routines

조건이 참일 때까지(until the condition becomes true) 기다리기 위해서, 스레드는 조건 변수(conditional variable)라고 하는 것을 사용할 수 있다. 조건 변수는 condition에 따라 실행이 기다려지는 상황에서 적용할 수 있는 명시적 대기열(explicit queue)이다. 다른 스레드는 상태(state)가 변하면 대기 중인 하나 이상의 스레드를 깨울 수 있으며 따라서 스레드가 계속 진행될 수 있도록 허용한다.

이러한 Conditional Variable(조건 변수)는 크게 wait()와 signal() 두 가지 연산과 연관되어 있다. wait() 호출은 스레드가 절전 모드(sleep)로 전환할 때 실행되며, signal() 호출은 스레드가 프로그램에서 무언가를 변경했기 때문에 해당 조건에 대해서 대기 중인 절전 스레드를 깨우려고 할 때 실행된다.

여기서 done은 State Variable(상태 변수)다.

Conditional Variable (조건 변수)란,  Condition Variable은 특정 조건을 만족하기를 기다리는 변수이며, thread간의 신호 전달을 위해 사용한다.

출처 : ju-hy.tistory.com/39

아래는 Conditional Variable(조건 변수)와 State Variable(상태 변수)를 사용하여 thread_join과 thread_exit을 구현한 코드 예제이다.

위 코드의 두 가지 케이스를 살펴보자.

# Case 1.

부모는 자식 스레드를 만들지만 스스로 실행을 계속한다(우리는 하나의 프로세서만 가지고 있다). 따라서 자식 스레드가 완료될 때까지 기다리기 위해 즉시 thr__join()으로 호출한다. 이 경우 lock을 획득하고, child가 완료되었는지(아닌지) 확인한 후 wait()를 호출해 스스로 sleep한다.(따라서 unlock된다).

The child will eventually run, print the message “child”, and call thr exit() to wake the parent thread

하위 스레드가 마침내 실행되며, child메시지를 보내고, thr_exit()를 호출하여 부모에게 신호를 보낸다. 이 과정에서 lock을 걸고, 완료 상태(done=1)를 설정하며, 부모에게 신호를 보내어 깨운다. 마지막으로, 상위 스레드가 실행되며 잠금이 설정된 상태에서 wait()로부터 돌아오고, 잠금을 해제하고, "parent: end" 메시지를 출력한다.

# Case 2.

자식 스레드가 생성 즉시 실행되고 done을 1로 설정하며 signal을 호출하여 절전중(sleeping)인 스레드를 깨우고 완료된다. 그런 다음 상위 스레드가 실행되고  thr_join()을 call하며 done이 1인것을 확인하고 wait()하지 않고 return한다.  

* done이라는 상태 변수(state variable)가 꼭 필요한 지 의문이 들 수 있다. 만약 상태 변수가 없다면 어떻게 될까?

잘못된 접근 방식이다. Case 2의 상황에 대처할 수 없게 된다.

자식 스레드가 즉시 실행되서 thr_exit()를 호출하는 경우 자식 스레드는 signal을 보내지만 해당 condition에 대해서 asleep상태의 스레드가 없다. 부모 스레드가 실행되면, wait를 호출할 것이고 asleep 상태에 갇히게(stuck) 될 것이다. 어떠한 스레드도 해당 스레드를 깨우지 않을 것이다. 해당 예시로부터, 상태 변수 done의 중요성을 깨달을 수 있다. done이라는 상태 변수는 스레드가 알고자 하는 값을 기록한다. sleeping, waking, locking은 해당 변수를 둘러싸고 build된다.

* 만약 lock 기능이 없다면 어떻게 될까?

race condition이 발생한다. 만약 부모가 thr_join()을 호출한 다음 done의 값을 확인하면, 그것은 0일 것이고 wait()을 호출하여 sleep 상태빠지려 할 것이다. 이 때 lock 기능의 부재로 인해 parent가 interrupt되며 child가 실행된다면 child는 state variable인 done을 1로 변경하고 signal을 보낼 것이다. 하지만 waiting상태의 잠든 스레드가 없을 것이며, 다음으로 parent가 다시 실행될 때 영원히 sleep상태에 빠진다.

해당 join 예제를 통해서 조건 변수를 올바르게 사용하기 위한 몇 가지 기본 요소를 확인할 수 있었다.

signal()이나 wait() 호출 시 잠금을 유지하라 -Hold the lock when calling signal or wait.

wait()호출 시 lock을 유지하는 것은 선택사항이 아니라, wait() 의미론적으로 보았을 때 강제되어진다(필수사항이다).

왜냐하면,

(a) wait()를 호출할 때 lock이 유지된다고 가정하고,

(b) 호출자를 sleep 상태로 전환할 때 lock을 해제하며,

(c) sleep 상태로부터 돌아오기 직전에 다시 lock을 획득하기 때문이다.

따라서 signal() 또는 wait()를 호출할 때 lock을 유지하자. 

The Producer/Consumer (Bounded Buffer) Problem

이번에 다룰 동기화 문제는 Producer/Consumer Problem(생산자/소비자 문제)로 알려져있고, dijkstra에 의해 처음 제기되었다. 이 문제로부터 잠금 또는 조건 변수로 사용될 수 있는 일반화된 semaphore가 등장하였다.

하나 이상의 생산자 스레드와, 하나 이상의 소비자 스레드가 있다고 상상해보자. 생산자는 데이터 항복을 생성하여 버퍼에 배치하고, 소비자는 버퍼에서 지정된 항목을 가져와 어떠한 방식으로 소비한다.

이러한 방식은 실제 많은 시스템에서 사용되는 방식이다. 예를 들어, 멀티 스레드 웹 서버에서, 생산자는 HTTP 요청을 작업 대기열(the bounded buffer)에 넣고, 소비자 스레드는 이 대기열에서 요청을 꺼내서 처리한다.

Bounded buffer는 하나의 프로그램의 출력을 다른 곳으로 파이프(pipe)할 때도 쓰인다. 예를 들어, "grep foo file.txt | wc -l"이라는 커맨드를 입력하면, 두 프로세스를 동시에 실행한다. 프로세스 grep은 file.txt로부터 standard output에 한줄 한줄 출력하고, 이는 파이프를 통해 리디렉션되어  프로세스 wc의 표준 입력으로 들어온다. wc는 input stream의 라인 개수를 결과로 출력하는 프로세스이다. 그러므로, grep프로새스는 생산자이고, wc 프로세스는 소비자이다. 이들 사이에는 in-kernel bounded buffer가 있다.

bounded buffer는 공유 리소스이기 때문에 race condition을 막기 위해 동기화된 접근(synchronized access)를 필요로 한다.

Producer/Consumer with If statement

위 코드는  if를 사용한 producer/consumer 구현 코드이다. 이는 생산자와 소비자 스레드가 각각 하나일 때는 문제가 없지만, 여러개일 때 문제가 발생한다.

예를 들어, 생산자 스레드 1개, 소비자 스레드 2개가 있다고 생각해보자.

1. Tc1(첫번째 소비자 스레드)가 먼저 실행되고, c2 if문에서 count==0이므로(버퍼에 데이터가 존재하지 않으므로) sleep상태가 된다.

3. Tp1 스레드가 실행되며 count==0이므로 버퍼에 데이터를 넣고, Tc1에 신호를 보내어 sleep상태의 Tc1을 다시 스케줄링한다.

4. 먼저 스케줄링되어있던 Tc2가 버퍼에 있는 데이터를 소비한다.

5. 다음으로 sleep상태에서 깨어난 Tc1가 실행되지만, buffer가 비어있는 문제가 발생한다.

즉, 여기서 볼 수 있는 문제는 Tp1(생산자가) Tc1(소비자)를 깨운 후에, Tc1이 다시 실행되기 전에 bounded buffer의 상태가 변경되었다(Tc2에 의해)는 점이다. 즉, 깨어난 스레드가 실행될 때 원하는 대로 상태(state)가 존재할 것이라는 보장이 없다.

이러한 문제를 해결하기 위해서는 아래처럼 while문을 이용하면 된다.

Producer/Consumer with While statement (with one condition variable)

하지만, while 문을 사용하더라도 해결하지 못하는 문제 하나가 더 있다. 바로 조건 변수가 하나라는 점이다.

이전과 같이 예를 들어, 생산자 스레드 1개, 소비자 스레드 2개가 있다고 생각해보자.

1.Tc1, Tc2가 순서대로 실행되며, 소비할 데이터가 존재하지 않으므로 sleep상태가 된다.

2. Tp1이 데이터를 생산하여 bounded buffer에 데이터를 넣고, Tc1을 깨운다.

3. Tc1이 데이터를 소비하고, Tc2를 깨운 후 sleep 상태에 빠진다. (조건 변수가 하나이므로 다음 대기열에 있는 Tc2를 깨우는 것이다.)

4. Tc2가 실행되지만 buffer에 데이터가 없으므로 sleep상태에 빠진다.

5. Tp1, Tc1, Tc2 모두가 sleep 상태에 빠지는 문제가 발생한다.

이 문제를 해결할 수 있는 단순한 방법은 조건 변수를 2개 사용해서 생산자는 소비자만 깨우도록, 그리고 소비자는 생산자만 깨우도록 만드는 것이다.

Producer/Consumer with While statement (with two condition variable)

위처럼 조건 변수 2개를 사용하여 생산자는 소비자만 깨우고, 소비자는 생산자만 깨우도록 바꾸어 문제를 해결할 수 있다.

Producer/Consumer with While statement (with two condition variable and multiple buffer size)

이번엔, buffer size가 1 이상 일때의 구현을 살펴보자.

이전과 달라진 점은 buffer의 크기가 1이 아닌 다수라는 점이다. 이에 따라 put()과 get()코드가 수정되고, 생산자는 버퍼가 가득찬 경우에만 wait()을 수행하며, 소비자는 버퍼가 비어있을 경우에만 wait()를 사용한다.

Covering Conditions

이번엔 다른 문제 상황을 살펴보자.

위 코드는 멀티 스레드에서 메모리를 할당하고 해제하는 일부 라이브러리의 코드이다. 메모리를 할당받는 allocate() 코드는 소비자(메모리 할당받는) 스레드가 원하는 size만큼의 메모리를 할당받을 수 있을 때까지 wait하고, 메모리를 해제하는 스레드는 사용중인 메모리를 할당 해제한 후 신호를 보내 메모리를 할당받으려하는 스레드를 깨운다.

여기서 문제는 어떠한 스레드에 신호를 보내야 하는 가이다. 예를 들어, free()를 통해서 여유 메모리가 100이 되었는데, 메모리를 할당받으려하는 두 스레드(첫번째 스레드는 150만큼의 메모리를, 두번째 스레드는 50만큼의 메모리를 필요로한다.) 중 첫번째 스레드를 깨운다면 여유 메모리가 부족하여 할당받을 수 없으므로 다시 sleep상태가 되고 할당받을 수 있던 두번째 스레드에게는 기회가 가지 않는 문제가 발생한다. 즉, 수행할 수 있는 스레드가 있음에도 아무것도 수행하지 않는 상태가 된다.

이러한 문제를 해결하기 위해서 signal() 대신 broadcast()를 사용하여 sleep상태의 모든 스레드를 깨우는 방법이 있다. 물론 성능 면에서 부정적인 영향을 줄 수는 있지만, 위와 같은 이슈를 해결할 수 있다. 이러한 trade-off를 잘 고려해야 한다.

pages.cs.wisc.edu/~remzi/OSTEP/

+) 참고한 블로그 : icksw.tistory.com/164?category=878876

Design Pattern?

소프트웨어 공학론에서, 좋은 코드를 설계하기 위한 일종의 설계 디자인 방법론이다.

실무적으로 프로그래머들 사이에서 대중적으로 인정받는 일반화된 효율적인 설계 방식이다.

좋은 코드

좋은 코드란, 프로그램 개발 시에 맞닥뜨리는 여러 문제나 애로 사항들을 해결하고 만족할 수 있는 적절하게 짜여진 코드라고 볼 수 있다.

확장과 수정에 용이하며, 설계 이후 추가적인 유지 보수에 비용이 적게 들어가며

코드가 명확하고 단순하며

재사용성이 높고

리소스의 낭비가 없는 효율적인.

객체지향적 관점에서 이러한 부분을 구체적으로 명시하여 5가지 원칙으로 제시한 것이 SOLID이다.

SOLID

SOLID 원칙은 워낙에 유명하고, 알고 있으면 처음엔 와닿지 않더라도 개발하다보면 체감이 확 되는 내용이라 객체지향적 개발을 하는 프로그래머라면 두고두고 봐야하는 내용같다.

S

Single Responsibility Principle (SRP) : 단일 책임 원칙. 하나의 클래스는 하나의 책임만 가져야 한다.

O

Open/Closed PRinciple (OCP) : 개방 폐쇄 원칙. 소프트웨어 요소는 확장에는 열려 있으나 변경에는 닫혀 있어야 한다.

L

Liskov Substitution Principle(LSP) : 프로그램의 객체는 프로그램의 정확성을 깨뜨리지 않으면서 하위 타입의 인스턴스로 바꿀 수 있어야 한다.

I

Interface segregation Principle(ISP) : 특정 클라이언트를 위한 인터페이스 여러 개가 범용 인터페이스 하나보다 낫다.

D

Dependency Inversion Principle(DIP) : 프로그래머는 추상화에 의존하며 구체화에 의존하면 안된다.

GoF 디자인 패턴

Gang of Fout는 유명한 개발자 4명인데, 디자인 패턴을 체계화한 사람들이다.

GoF 디자인 패턴은 생성(Creational) 패턴, 구조(Structural) 패턴, 행위(Behavioral) 패턴으로 구분된다.

SOLID 철학이 녹아있다.

생성 패턴

객체 생성과 관련한다.

추상 팩토리, 빌더, 팩토리 메소드, 프로토타입, 싱글턴

구조 패턴

클래스 및 객체를 조합해 더 큰 구조를 만드는 것과 관련한다.

어댑터, 브리지, 컴포지트, 데코레이터, 퍼사드, 플라이웨이트, 프록시

행위 패턴

클래스 및 객체 간의 알고리즘이나 책임 분배와 관련한다.

책임 연쇄, 커맨드, 인터프리터, 반복자, 메멘토, 옵서버, 상태, 전략, 템플릿 메소드, 비지터

static 변수 및 메소드는 언제 메모리에 할당되고 해제될까?

본 궁금증을 해결하기 위해 static 메모리 영역에 좀 더 관심을 갖고 공부해보자!

메모리 영역 살펴보기

Static 메모리에는 클래스, static 변수 및 메소드가 존재한다. Static 변수 및 메소드는 객체(인스턴스)를 생성하지 않고도 접근이 가능하며, 여러 객체(인스턴스)들이 공유한다. JVM이 프로그램을 시작할 때 할당되고, 프로그램을 종료할 때 할당 해제된다. GC에 의해 관리되지 않으며 생명주기가 프로그램의 시작부터 종료까지이므로 프로그램 실행 내내 메모리에 할당된 채 존재한다. 따라서 과용하게 되면 시스템의 성능에 악영향을 미칠 수 있다는 점을 생각해야 한다.

Heap 메모리에는 new 연산자에 의해서 생성된 객체(인스턴스)들이 존재하는 영역이다. GC에 의해 관리된다.

Static 변수 및 메소드의 특별함

일반적인(non-static) 클래스의 변수 및 메소드는 해당 클래스가 인스턴스화(new 연산자를 통한 생성)되기 전까지는 사용할 수 없다. 하지만 static 변수나 메소드는 인스턴스의 생성과 상관없이(즉, 객체를 생성하지 않고도) 접근하여 사용할 수 있다. 즉, 프로그램 시작 시 메모리에 고정적으로 할당되며 프로그램이 종료될 때 해제된다.

그래서, Static 변수와 메소드는

JVM의 실행과정에서 필요한 클래스의 정보를 메모리에 로딩한다. 이 로딩 시점에서 static 변수가 초기화된다.

따라서, 프로그램 시작 시 static 메모리에 할당되며 프로그램이 종료될 때 해제된다.

[출처]

kim-daeyong.github.io/2019-07-09-static/

mangkyu.tistory.com/m/47

Stack 2개로 Queue 만들기

개발 관련 정보들을 구글링하던 도중 면접에서 Stack 2개로 Queue 1개를 만들어보라는 질문을 받았다는 글을 보았다.

Stack 2개로 Queue를 만든다라는 아이디어를 보고 어떻게 구현하면 좋을지 구글링해보았고, 그러한 정보를 이 글에 담아보려 한다.

Stack(스택)은

Stack은 LIFO(Last-In First-Out) 구조다. 나중에 들어온 것이 먼저 나간다.

Queue(큐)는

Queue는 FIFO(First-In First-Out) 구조다. 먼저 들어온 것이 먼저 나간다.

Stack 2개로 Queue 1개 만들기

아래와 같이 Stack 2개를 둔다. 하나의 스택은 Inbox, 그리고 나머지 한 스택은 Outbox다.

Inbox로 원소가 들어오고, Outbox로부터 원소가 나간다. 즉, 사용자는 Inbox로 데이터를 push()하고, Outbox로부터 데이터를 pop() 한다.

한번 데이터를 넣어보자. 1이라는 데이터를 push하고 2라는 데이터를 순차적으로 push한다. 사용자가 데이터를 push()할 경우 Inbox로 들어온다.

이번엔, pop()을 해보자. pop()을 할 경우, Outbox로부터 pop()을 하는데 여기서 핵심적인 부분이 있다.

** Outbox로부터 pop을 할 때는 두 가지 케이스에 대해서 다른 코드를 수행한다. **

만약, Outbox Stack이 empty()==true일 경우

1. Inbox로부터 모든 데이터를 순차적으로 pop하여  Outbox로 push한다

2. Outbox로부터 데이터를 pop한다.

만약, Outbox Stack이 empty()==false일 경우

1. Outbox로부터 데이터를 pop한다.

현재 Outbox가 empty하므로 아래와 같이 수행된다.

왜 이렇게 해야만 할까?

Outbox에 원소가 남아있는 상태에서 Inbox로부터 pop and push를 수행하면 원소의 순서가 꼬인다.

Outbox에 남아있는 원소가 Inbox에 있는 원소보다 먼저 사용자로부터 push되었으므로, 순서 상 먼저 사용자로부터 pop되어야하는데, Outbox에 아직 pop되어야할 데이터가 남아있는 상태에서 Inbox로부터 pop and push를 진행할 경우 Outbox의 기존 원소 위에 쌓이므로 스택의 LIFO Rule에 의해서 순서가 꼬이게 된다. 즉, FIFO도, LIFO도 아닌 엉망인 자료구조가 만들어진다.

따라서 위의 룰을 지키도록 하자!

Classic vs Multi-threaded

Classic View - Single Point of Execution within a program, 하나의 프로그램에는  단일 실행 포인트.

-> 즉 하나의 프로그램 안에는 명령어를 가져오고 실행하는 Single Program Counter(단일 PC)만이 존재했다.

Multi-threaded program - 멀티 스레드 프로그램은 하나 이상의 실행 포인트가 존재한다.

스레드들은 같은 주소공간을 공유한다. (same Page Table) -> 같은 데이터에 접근할 수 있다.

하지만, 각각의 스레드는 own private set of registers(including PC) 레지스터 set을 스레드별로 각자 가지고 있다.

스레드를 T1에서 T2로 전환할 때 TCB(Thread Control block)을 switch하지만, address space는 그대로 남는다.(즉, page table을 전환할 필요가 없다.)

스레드를 왜 쓸까?

1. parallelism : 병렬성 때문에 쓴다. 병렬적 실행이 가능해진다. 예를 들어, CPU 하나당 하나의 스레드를 갖고, 멀티 프로세서 시스템에서 여러 프로세서가 동시에 프로그램을 실행한다면 프로그램의 실행 속도가 더 향상될 것이다.

2. I/O overlapping : 느린 I/O 때문에 프로그램의 진행이 block되는 것을 피할 수 있다.

While one thread in your program waits (blocked waiting for I/O). 즉, 프로그램에서 하나의 스레드가 I/O를 기다리며 blocked상태인 동안 CPU 스케줄러는 다른 스레드로 전환하여 그동안 프로그램에서 무언가를 실행할 수 있다.

3. 스레드 대신에 멀티 프로세스를 사용할 수도 있지만, 스레드들은 address space를 공유하므로 데이터를 공유하기가 쉽다. 다만, 논리적으로 분리된 task에 관해서는 multi process를 사용하는 것이 더 나은 선택이다.

오늘날 멀티 스레드 프로그램의 예시

오늘날 대부분의 어플리케이션은 멀티스레드이다. 스레드들은 어플리케이션 내에서 실행된다. 어플리케이션 내의 여러 개의 tasks(작업들)은 분리된 스레드들에 의해서 구현될 수 있다.

-디스플레이 업데이트

-데이터 가져오기

-맞춤법 체크

-네트워크 요청에 응답

등등

프로세스 생성보다 스레드를 생성하는 것이 더 가볍다(비용이 적게 든다.)

코드를 단순화해 효율을 높일 수 있다.

커널은 일반적으로 멀티스레드화되어있다.

멀티 스레드(multi-threaded)의 장점 4가지

뛰어난 반응성/응답성(Responsiveness)

프로세스의 일부가 blocked상태여도 실행을 계속하는 것이 가능하다. 이는 특히 유저 인터페이스에 있어 중요하다.

자원 공유(Resource Sharing)

스레드들은 프로세스의 리소스들을 공유하므로, 이는 메시지를 전달하거나 메모리를 공유하는 것보다 쉽다.

경제성(Economy)

스레드를 생성하는 것이 프로세스를 생성하는 것보다 비용이 적게 들며, thread switching(스레드 전환)이 context switching(컨텍스트 전환, 즉 프로세스 전환)보다 오버헤드가 적다.

확장성(Scalability)

프로세스가 멀티 프로세서 구조의 이점을 적극적으로 활용할 수 있다. 즉, 다중 CPU 구조에서는 각각의 스레드가 다른 프로세서에서 병렬로 수행될 수 있으므로 병렬성이 증가한다.

MLFQ에서 다루고자 하는 근본적인 문제는 두 가지이다.

첫 번째는 짧은 작업을 먼저 실행하여 turnaround time을 최적화(optimize)하는 것이다. 문제는, SJF(또는 STCF)와 같은 알고리즘이 필요로하는 정보인 작업의 실행 시간을 모른다는 것이다.

두 번째로, 시스템이 대화형 사용자(interactive user)에 반응하도록 하여 응답 시간을 최소화하는 것이다. 저번에 배웠던 Round Robin 알고리즘은 response time(응답 시간)은 짧지만 turnaround time이 길다.

우리가 프로세스에 대해서 아는 정보가 없을 때 어떻게 이러한 목표를 달성하기 위한 스케줄러를 만들 수 있을까? 스케줄러가 시스템이 실행될 때 실행 중인 작업의 특성을 학습하여 더 나은 스케줄링 결정을 내릴 수 있는 방법은 무엇일까?

MLFQ : Basic Rules

MLFQ에서  각기 다른 Priority Level(우선 순위 레벨)을 할당한 여러 개의 고유한 queue(대기열)을 가지고 있다. 언제든지 실행 가능한 작업은 단일 대기열에 존재한다. MLFQ는 우선 순위를 사용하여 주어진 시간에 실행할 작업을 결정한다. 우선 순위가 높은 작업이 실행되도록 선택된다. 둘 이상의 작업들이 지정된 대기열에 있을 경우 우선 순위가 같고, 이럴 땐 이들은 라운드 로빈 스케줄링을 사용한다.

따라서 MLFQ의 두 가지 규칙을 말할 수 있다.

규칙 1. 작업 A, B에 대해서 우선순위가 A > B이면 A가 실행된다.

규칙 2. 우선순위가 같은 작업들에 대해서는 라운드 로빈 스케줄링을 실행한다.

MLFQ 스케줄링의 핵심은 스케줄러가 우선순위를 설정하는 방법인데, MLFQ는 각 작업에 대해 고정된 우선순위를 부여하기보다는 관찰된 동작에 따라 우선순위를 변화시킨다. 예를 들어, 작업이 키보드 입력을 기다리는 동안 CPU를 반복적으로 포기하면 MLFQ는 interactive process의 행동이라고 판단하여 우선순위를 높게 유지시킨다. 대신 작업이 CPU를 장시간 집중적으로 사용하는 경우 MLFQ는 우선순위를 줄인다. 이처럼, MLFQ는 프로세스를 실행하며 프로세스에 대해 배우고, 작업의 이력(history)을 사용하여 작업의 미래 동작을 예측한다.

그러나, 때로는 우선 순위가 낮은 작업이 우선 순위가 높은 작업들에 의해 아예 실행이 되지 못하는 상황이 생기는 것을 막기 위해 우선순위가 낮은 작업의 순위를 올리는 판단도 필요하다. 이처럼, MLFQ 스케줄러가 작업의 우선순위를 어떻게 변화하는지를 아는 것이 핵심이다. 이에 대해서 배워보자. 

Attempt #1: How To Change Priority

이제, 작업의 생명주기동안 MLFQ가 우선 순위 레벨을 어떻게 변경할 것인지를 결정해야 한다. 이 때, 짧은 실행(키보드나 마우스에서 사용자 입력을 기다리며 많은 I/O를 수행하며 CPU를 자주 포기하는 경우)을 하는 대화형 작업과, 많은 CPU 시간이 필요하지만 반응 시간이 중요하지 않은 오래 실행하는 CPU-bound 작업이 혼합되어 있다는 점을 명심해야 한다.

규칙 3. 시스템에 들어가면 작업은 가장 높은 우선 순위에 배정된다.

규칙 4a. 작업을 실행하는 동안 전체 time slice를 모두 사용하는 경우 우선 순위 레벨이 감소한다.(대기열 하나 아래로 이동)

규칙 4b. 작업이 time slice를 전부 사용하기 전에 CPU를 포기하면 동일한 우선 순위 레벨을 유지한다.

Problems With Our Current MLFQ

문제점 1. 시스템에 너무 많은 대화형 작업이 있을 경우 그들이 모든 CPU time을 소모하므로 장기간 실행되는 작업은 CPU time을 전혀 할당받지 못하는 Starvation 문제가 발생할 수 있다.

문제점 2. 사용자가 그들의 프로그램을 재작성하여 공정한 시스템 리소스 점유율 그 이상을 할당받도록 스케줄러를 속일 수 있다. 즉, time slice가 끝나기 전에 I/O 작업을 실행하여 고의적으로 CPU를 포기하며 동일한 대기열에 남아 더 많은 CPU time을 확보할 수 있다. 예를 들어, time slice의 99%만큼 작업을 실행하고 포기하는 방식이 있다. 이를 통해 CPU를 독점할 수 있다는 문제가 생긴다.

문제점 3. 프로그램이 시간이 지남에 따라 동작을 변경할 수 있다. 작업의 동작 Phase가 CPU-bound -> Interactive로 전환되었을 때 현재의 접근 방식에서는 해당 작업은 시스템에서 다른 대화형 작업들처럼 다루어지지 않을 것이다.

Attempt #2: The Priority Boost

starvation 문제를 피하기 위해 새로운 규칙을 추가하자. 시스템 내 모든 작업의 우선 순위를 주기적으로 향상시킨다.

규칙 5. 일정 시간이 지나면(일정 주기마다) 시스템의 모든 작업을 대기열의 맨 위로 이동한다.

새 규칙은 두 가지 문제를 동시에 해결한다. 첫째, 프로세스가 중단되지 않도록 보장된다다(starvation 해결). 즉, 맨 위 대기열로 이동하여 CPU를 다른 우선 순위가 높은 작업과 라운드 로빈 방식으로 공유하여 결국 서비스를 받게 된다. 둘째, CPU-bound 작업이 대화형 작업이 된 경우 우선 순위 부스트를 받은 후 스케줄러가 해당 작업을 적절하게 처리한다.
 

Attempt #3: Better Accounting

고의적으로 time slice가 만료되기 전에 CPU를 포기하여 작업의 우선 순위를 유지하는 프로그램의 스케줄러 악용으로부터의 문제를 해결하기 위해 규칙 4를 수정한다. 이를 위해 스케줄러는 지정된 우선 순위 레벨에서 프로세스가 사용한 시간 할당의 양을 추적한다.

규칙 4: CPU를 포기한 횟수와 상관없이 해당 우선 순위 레벨에서 주어진 시간 할당을 모두 사용하면 우선 순위가 감소한다.

이를 통해 프로세스의 CPU 부당 점유를 막는다.

Tuning MLFQ And Other Issues

MLFQ 스케줄링에서 아직 몇 가지 다른 이슈가 존재한다. 한 가지 큰 이슈는 위에서 고려한 스케줄러를 어떻게 매개 변수화하느냐이다. 예를 들어 대기열이 몇 개여야 하는지, 대기열당 time slice가 얼마나 커야 하는지, starvation을 피하고 작업의 동작 변화(cpu-bound -> interactive)를 고려하기 위해 우선 순위를 얼마나 자주 올려야 하는지 등이다. 이러한 질문에 쉽게 대답할 수 없기 때문에 workload 기반 경험과 이후의 스케줄러 튜닝만이 만족스러운 균형을 이룰 수 있다.

마지막으로, 많은 스케줄러에는 사용자가 사용할 수 있는 몇 가지 다른 기능이 있다. 예를 들어 일부 스케줄러는 운영 체제 작업에 대해 가장 높은 우선 순위 수준을 예약하므로 일반적인 사용자 작업은 시스템에서 가장 높은 우선 순위를 얻을 수 없다. 또한 일부 시스템은 우선 순위를 설정하는 데 사용자의 개입을 허용하기도 한다. 예를 들어 명령줄 인터페이스를 사용하면 작업의 우선 순위를 늘리거나 줄일 수 있으므로 특정 시간에 작업이 실행될 가능성을 늘리거나 줄일 수 있다. 자세한 내용은 man 페이지를 참조하도록 하자.

MLFQ: Summary

• 규칙 1: 우선 순위(A) > 우선 순위(B)이면 A가 실행된다(B는 실행하지 않는다).
• 규칙 2: 우선 순위(A) = 우선 순위(B)인 경우, A와 B는 주어진 대기열의 Time slice를 사용하여 Round Robin 방식으로 실행된다.
• 규칙 3: 작업이 시스템에 진입할 때 가장 높은 우선 순위(맨 위 대기열)에 배치된다.
• 규칙 4: 주어진 우선 순위 수준에서 시간 할당을 모두 사용하면(CPU를 포기한 횟수에 관계없이), 우선 순위가 감소한다(즉, 대기열 하나 아래로 이동).
• 규칙 5: 일정 시간이 지나면 시스템의 모든 작업을 맨 위 대기열로 이동한다.

출처 : pages.cs.wisc.edu/~remzi/OSTEP/ 

Workload Assumptions

글을 들어가기 전에, 시스템에서 실행중인 프로세스(작업)에 대해 이와 같은 가정을 한다.

가정 1. 각각의 작업은 동일한 시간동안 실행된다.

가정 2. 모든 작업들은 동시에 도착한다.

가정 3. 시작하면 각 작업은 완료될 때까지 실행된다.

가정 4. 모든 작업은 CPU만 사용한다. (I/O를 수행하지 않는다.)

가정 5. 각 작업의 실행 시간을 알고 있다.

Scheduling Metrics

Turnaround Time을 위와 같이 단순하게 가정한다.

First In, First Out (FIFO)

FCFS라고도 불린다.

FIFO는 위 두 그림으로 설명이 가능하다.

First In, First Out은 먼저 온 사람에게 먼저 제공한다는 뜻으로, 먼저 할당 요청을 한 프로세스에게 CPU를 할당한다.

비선점형 스케줄링이며 효율적이지 않다. 여기서 비선점적이라는 것(Non-Preemptive)은 CPU를 할당받으면 자신의 작업을 모두 마치기 전까지, CPU를 반환하지 않는다는 의미이다.

FIFO의 치명적인 단점은 Convoy Effect이다. 이는 상대적으로 짧은 다수의 리소스 잠재적 소비자(수행 시간이 짧은)가 헤비급 리소스 소비자(수행 시간이 긴) 뒤에 대기하는 현상이다.

Shortest Job First (SJF)

이름 그대로 최단 작업을 우선적으로 실행한다. FIFO와 동일하게 비선점형 스케줄링이다.

모든 작업이 동시에 도착한다는 가정이 있다면 가장 효율적인 알고리즘이라고 볼 수 있다. 그러나, 모든 작업들이 한꺼번에 도착하는 것이 아니라 언제든지 도착할 수 있다고, 위의 가정 2를 제거한다면 SJF 알고리즘 또한 문제가 많다.

Shortest Time-to-Completion First (STCF)

위에서의 문제를 해결하기 위해, 가정 3을 제거하고 스케줄러에 타이머 인터럽트(timer interrupt)와 컨텍스트 전환(context switching)을 적용한다면 비선점형 스케줄러(non-preemptive scheduler)인 SJF의 문제를 선점형 스케줄러인 STCF로 어느정도 해결할 수 있다. 즉, SJF에 preemption(선점)을 추가한 Shortest Time-to-Completion First (STCF)  또는 Preemptive Shortest Job First (PSJF)이 그것이다.

새 작업이 시스템에 들어갈 때마다 STCF 스케줄러는 새 작업을 포함하여 남은 작업 중 가장 적은 시간이 남아 있는 작업을 결정하고 이 작업을 예약한다.

SJF가 모든 작업이 동시에 도착한다는 위의 가정하에서 최적의 알고리즘이었다는 것을 기반으로, 해당 가정만을 제거했을 때는 현재까지  STCF가 최적의 알고리즘이라는 것을 알 수 있다.

A New Metric: Response Time

따라서, 우리가 모든 작업의 길이를 알고, 그 작업은 오로지 CPU만을 사용하며, 유일한 metric인 turnaround time(소요 시간)만을 고려했다면 STCF는 훌륭한 정책이다. 실제로, 배치 컴퓨팅 시스템(batch computing system)에서는 이러한 방식의 스케줄링 알고리즘이 타당할 수 있다. 하지만 Time-shared machine(시분할 머신)의 등장으로 모든 것을 바꾸어 놓았다. 이제 사용자는 터미널을 사용하며 시스템에 대화형 성능(interactive performance from system)을 필요로 한다.

이제 우리는 응답 시간을 작업이 시스템에 도착하는 시간부터 작업이 예약된 첫 번째 시간까지로 정의한다.

응답 시간을 충분히 고려한 스케줄러를 생각해보자.

Round Robin

라운드 로빈(RR) 스케줄링의 기본적인 아이디어는 간단하다. RR은 작업을 완료하기 위해 실행하는 대신에 Time Slice(Scheduling Quantum)에 대한 작업을 실행한 다음 실행 대기열의 다음 작업으로 전환한다. 작업들이 마무리될 때까지 해당 방식을 반복한다. 이러한 이유로, RR은 때때로 Time-Slicing이라고 불린다. Time slice의 길이는 타이머 인터럽트 주기의 배수여야 하므로 타이머가 10밀리초마다 중단되는 경우 시간 조각은 10, 20 또는 10ms의 다른 배수가 될 수 있다.

RR에 있어 Time Slice의 길이는 매우 중요하다. 짧을수록 응답 시간 측면에서 RR의 성능이 우수하다. 그러나 Time Slice를 너무 짧게 만드는 것은 문제가 된다. Context Switching(컨텍스트 전환) 비용이 과도하게 증가해 전체 성능을 저하시킬 것이다. 따라서 time slice의 길이를 결정하는 것은 시스템 설계자에게 Trade-Off이며, 시스템이 반응하지 않을 정도로 길게 만들지 않고 Context Switching 비용을 감당할 수 있을 만큼 충분히 길어야 한다. Context Switching(컨텍스트 전환) 비용은 일부 레지스터를 저장하고 복원하는 OS 작업으로부터의 발생 뿐만 아니라, 프로그램이 실행될 때 CPU 캐시, TLB, Branch Predictors(분기 예측 변수) 및 하드웨어에서 많은 상태를 구축하며 발생합니다. 다른 작업으로 전환하면 현재 실행 중인 작업과 관련된 이 상태가 flush되고 현재 실행할 작업을 가져오기 위한 새 상태가 발생하므로, 상당한 성능 비용이 발생할 수 있다.

따라서 Response Time(응답 시간)이 유일한 Metric(메트릭)인 경우, 합리적인 Time Slice를 가진 RR은 우수한 스케줄러이다. 하지만 Turnaround time(소요 시간) 측면에서는 최악의 스케줄링 정책 중 하나다. Turnaround Time 측면에서 RR은 단순한 FIFO보다 훨씬 더 심각하다. 일반적으로, 작은 Time Scale로 활성 프로세스 간에 CPU를 균등하게 분배하는 모든 정책(RR 등)은 Turnaround Time과 같은 메트릭에서 저조한 성능을 보일 것이다. 실제로, 이것은 내재적인 Trade-off다. 만약 불공평한 스케줄링을 감수한다면, 더 짧은 작업의 실행을 먼저 완료할 수 있지만, Response Time을 희생해야 한다. 대신에 공정성을 중시한다면, Response Time은 짧아지지만, Turnaround Time을 희생해야 한다. 이런 종류의 Trade-off는 시스템에서 흔히 볼 수 있다.

우리는 두 가지 유형의 스케줄러를 살펴보았다. 첫 번째 유형(SJF, STCF)은 Turnaround Time을 최적화하지만 Response Time에는 좋지 않다. 두 번째 유형(RR)은 Response Time을 최적화하지만 Turnaround Time에 좋지 않다. 그리고 우리는 여전히 고려해보아야할 필요가 있는 두 가지 가정을 다루지 못했다. 가정 4(작업에 I/O가 없다는 가정)와 가정 5(각 작업의 런타임이 알려져 있다는 가정). 그 가정들을 다음에 다루자.

Incorporating I/O

가정 4를 제거해보자. 모든 프로그램은 물론 I/O를 수행한다. 어떠한 입력도 받지 않는다면, 프로그램은 늘 동일한 출력을 생성할 것이다. 출력이 없다면, 아무도 프로그램의 산출물을 볼 수 없으며 실행하는 의미가 없어진다.

작업이 I/O를 요청(request)하면 현재 실행중인 해당 작업은 I/O 도중 CPU를 사용하지 않을 것이며 I/O가 완료되길 기다리며 Blocked 상태가 될 것이다. I/O가 Hard disk drive로 보내지는 경우 I/O load에 따라 몇 밀리초 이상 걸릴 수 있고, 따라서 스케줄러는 그 시간 동안 다른 작업을 CPU에 할당하도록(schedule) 결정할 수 있다.

I/O가 완료되면 인터럽트가 발생하고 OS가 실행되어 I/O를 실행한 프로세스를 Blocked 상태에서 Ready 상태로 다시 이동합니다. 그리고, 스케줄러는 그 시점에서 그 작업을 언제 할당할 지를 결정할 수 있다.

이를 통해 스케줄러가 I/O를 어떻게 통합하는지 확인할 수 있다. 스케줄러는 각각의 CPU Burst를 작업으로 처리하여 대화형(interactive) 프로세스가 자주 실행되도록 한다. 이러한 대화형 작업이 I/O를 수행하는 동안 다른 CPU-Intesive(CPU 집약적) 작업이 실행되므로 프로세서를 더 잘 활용할 수 있다.

No More Oracle

I/O에 대한 기본적인 접근 방식을 배웠고, 이제 우리는 스케줄러가 각 작업의 길이를 알고 있다는 최종 가정을 제거해야 한다. 실제로, 범용적인 OS에서 OS는 일반적으로 각 작업의 길이에 대해 거의 알지 못합니다. 따라서, 그러한 사전 지식 없이 어떻게 SJF/STCF와 같은 방식을 구축할 수 있을까? 또한 RR 스케줄러와 함께 본 몇 가지 아이디어를 통합하여 Response Time 측면에서도 높은 성능을 내려면 어떻게 해야 할까? 다음 장에서 배우도록 하자.

출처 : pages.cs.wisc.edu/~remzi/OSTEP/