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

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/ 

Virtual Memory : Demand Paging

하드디스크의 일부를 마치 메인 메모리처럼 사용할 수 있도록 하는 기술이다. 이는 물리적 메모리(Physical Memory)의 한계를 극복하기 위한 기술이다. 이 기법은 하나의 프로그램을 실행할 때 프로그램 전체가 메모리로 올라와 실행되는 것이 아닌, 필요한 부분만을 불러와 실행하는 것을 기본으로 한다.

즉, 커널은 실제 메모리(RAM)에 올라와 있는 블록들 중에, 쓰이지 않는 것을 디스크에 저장한다. 이를 통해서 사용 가능한 메모리 영역을 늘린다. 만일 디스크에 저장되었던 메모리 블록이 다시 필요하게 되면 실제 메모리 안으로 올려지며 대신에 다른 블록이 메모리로 내려간다. 이런 과정이 일어나고 있다는 것은 사용자가 알 수 없고, 그저 많은 양의 메모리가 있는 것처럼 보일 뿐이어서 점유하고 있는 메모리가 디스크에 있는 실제 메모리에 있는 지는 신경쓰지 않아도 된다.

다만, 디스크를 읽고 쓰는 시간은 메모리를 읽고 쓰는 시간보다 훨씬 느리기 때문에 프로그램의 실행은 그만큼 느려지게 된다. 이렇게 가상메모리로 쓰이는 하드디스크 영역을 스왑 영역(Swap Space)이라고 한다.

출처 : attiadmin.guyweb.co.kr/linux/swap.html

Swap Space

먼저, 페이지를 이동할 수 있도록 디스크의 공간을 확보해야 한다. 운영체제에서는 이를 위해 스왑 공간(Swap Space)를 참조하는데, 이는 메모리에서 페이지를 스왑 공간(디스크)으로 옮기고 스왑 공간으로부터 페이지를 메모리로 옮기기 위해서다. 따라서, 운영체제가 스왑 공간에서 페이지 크기의 단위로 읽고 쓴다고 가정했을 때, 운영체제는 지정된 페이지의 디스크 주소를 기억해야 한다.

스왑 공간의 크기는 궁극적으로 특정 시간에 시스템에서 사용할 수 있는 최대 메모리 페이지의 수를 결정하기 때문에 중요하다.

The Present Bit

이처럼 디스크에 공간을 확보했으니, 디스크와 페이지를 스왑(swap)하는 것을 지원하기 위해 시스템위에 기계(machinery)를 추가해야 한다.

Without Swap Space

먼저, 하드웨어 기반으로 관리되는 TLB가 있다고 가정했을 때, 메모리를 참조할 때 어떠한 일이 벌어지는지 떠올려보자. 실행 중인 프로세스는 가상 메모리 참조(Virtual Memory References)를 생성하며, 하드웨어는 원하는 데이터를 메모리에서 가져오기 전에 해당 참조를 물리적 주소로 변환한다.

하드웨어는 먼저 가상 주소에서 VPN을 추출하고 TLB에서 일치(TLB Hit)를 확인하고, 적중 시 해당하는 물리적 주소를 가져와 메모리로부터 데이터를 가져온다. 이 경우에는 추가적인 메모리 액세스가 필요하지 않으므로 속도가 빠르며 일반적인 경우다.

TLB에서 메모리를 찾을 수 없을 때 (TLB Miss), 하드웨어는 메모리에 있는 페이지 테이블로부터 VPN을 인덱스로 사용하여 해당 페이지에 대한 페이지 테이블 항목(PTE)을 조회한다. 페이지가 유효하고 물리적 메모리에 있는 경우 하드웨어는 PTE에서 PFN(Page Frame Number)을 추출하여 TLB에 설치한 후 해당 명령을 다시 시도한다. 이번에는 TLB Hit가 발생한다.

With Swap Space

만약 페이지(pages)가 disk와 스왑(swap) 되기를 원한다면, 즉 가상 메모리를 사용한다면 더 많은 기계를 추가해야 한다. 특히, 하드웨어 및 운영체제가 PTE를 확인할 때 페이지가 물리적 메모리에 존재하지 않는다는 것을 발견할 수 있다. 이처럼 하드웨어 및 운영체제가 페이지의 물리적 메모리 상의 존재 여부를 판단하기 위해 사용하는 새로운 정보는 각각의 PTE 항목에 존재하는 present bit이다.

Present bit이 1이라면, 페이지가 물리적 메모리에 존재한다는 것을 의미하고, 위와 같이 진행하면 된다.

Present bit이 0이라면, 페이지는 메모리가 아닌 디스크에 존재한다는 것을 의미한다. 물리적 메모리(physical memory)에 존재하지 않는 페이지에 접근하는 상황을 page fault라고 한다. 

페이지 폴트가 발생하면 OS가 호출되어 페이지 폴트를 처리한다. Page fault Handler가 실행되고 페이지 폴트를 해결한다.

The Page Fault

페이지가 메모리에 존재하지 않고 디스크로 스왑되어 있을 경우 운영체제는 page fault를 해결하기 위해 해당 페이지를 메모리로 스왑해야 한다. 그렇다면, 운영체제는 어떻게 해당 페이지의 위치를 디스크로부터 찾을까? 보통, 이러한 정보는 페이지 테이블에 저장되어 있다. 따라서, 운영체제는 PTE의 일부 비트에 해당하는 데이터를 해당 페이지 disk address의 PFN처럼 사용한다. 운영체제는 페이지에 대한 page fault를 수신하면 PTE를 조회하여 disk address를 찾고 디스크에 해당 페이지를 메모리에 불러오도록 요청을 전송한다.

Disk I/O(디스크 입출력)가 완료되면, 운영체제는 페이지 테이블을 업데이트하여 해당 페이지의 present bit을 1로 변경하고 PTE의 PFN에 새롭게 가져온 페이지의 in-memoroy location을 기록한다. 그리고 해당 명령을 재시도한다.

이번 재시도에서는 TLB miss가 발생할 수 있다. 발생 시 위의 변환된 정보로 TLB를 업데이트하고, 서비스할 것이다. 이와 같은 단계를 피하기 위해서 page fault를 해결할 때 TLB를 업데이트할 수도 있다.

최종적으로, 변환 정보를 TLB에서 찾아 변환된 물리적 주소(physical address)에 존재하는 원하는 데이터 또는 명령을 메모리로부터 가져온다(fetch). 

I/O가 발생한 동안에 해당 프로세스는 block상태가 된다. 따라서 운영체제는 page fault를 처리하는 동안에 다른 ready상태의 프로세스를 실행할 수 있다. I/O는 고비용 작업이기 때문에 다른 프로세스와 실행을 overlap(겹침)하는 것은 멀티프로그래밍 시스템이 하드웨어를 가장 효과적으로 사용할 수 있는 방법 중 하나이다.

What if Memory is Full?

위에서 설명한 절차는 페이지를 Swap Space(스왑 공간)으로부터 메모리로 가져오기에 충분한 사용 가능 메모리 용량이 확보되었다는 것을 가정한다. 물론 그렇지 않은 경우도 있다. 메모리가 꽉 찬(full) 상태 또는 거의 꽉 찬 상태일 때이다. 이 때, 운영체제는 가져오려는 새 페이지의 공간을 확보하기 위해 하나 이상의 페이지를 내보낼 수 있다. 내보내거나 교체할 페이지를 선정하는 절차를 Page-Replacement Policy라고 한다.

메모리에 존재하는 페이지를 잘못 내보낼 경우 프로그램 성능에 있어 엄청난 비용이 발생하기 때문에 좋은 페이지 교체 정책을 만드는 것이 중요하다. 잘못된 결정을 내린다면 프로그램이 메모리 기반 실행 속도가 아닌 디스크 기반 실행 속도로 실행하게 되며 이는 프로그램이 10,000배 또는 100,000배 느려질 수 있다는 것을 의미한다.

Page Fault Control Flow

지금까지 배운 지식들을 총집합하여 메모리 액세스의 전체 제어 흐름(comple control flow of memory access)을 스케치할 수 있다. 누군가가 메모리에서 어떠한 데이터를 가져오고자 할 때 무슨 일이 발생하는가?라는 질문을 한다면 발생할 수 있는 모든 다른 가능성들에 대해서 숙지하고 있어야 한다.

위 Hardware Control Flow Algorithm을 통해서 알아둬야 할 대표적인 세 가지 사례가 있다.

첫 번째는, 페이지가 존재하고 유효한 경우다(valid and present, 18-21). 이 경우 TLB Miss Handler는 PTE로부터 PFN을 획득하여 명령을 다시 시도하면 TLB hit가 발생하고 여러번 계속할 수 있다.

두 번째는,  Page fault handler를 실행해야 하는 경우다(Valid but not present, 22-23). 페이지가 프로세스가 접근할 수 있는 유효한 상태이지만 물리적 메모리에 존재하지 않는 상황이다. Page fault handling(스왑공간에서 페이지 읽도록 I/O요청 및 페이지 테이블 업데이트) -> 재시도(TLB Miss) -> 재시도(TLB Hit) 순서다.

세 번째는 프로그램의 버그로 인해 유효하지 않은 페이지에 접근한 경우다(not valid, 22-23). 이 경우 PTE의 나머지 비트들은 관여하지 않고, 하드웨어가 invalid access를 trap하고 운영체제는 trap handler를 실행하여 해당 프로세스가 종료될 수 있다.

When Replacements Really Occur

지금까지 설명한 대체 방법은 운영체제가 메모리가 완전히 가득 찰 때까지 기다렸다가 다른 페이지를 위한 공간을 확보하기 위해 페이지를 교체하는 것으로 가정했다. 이는 다소 비현실적이며, 이보다는 운영체제가 메모리의 일정 작은 부분을 능동적으로 사용가능한 상태로 유지하는 것이 여러 측면에서 유리하다.

메모리의 일부 작은 공간을 확보(free)하기 위해서 대부분의 운영체제는 일종의 high watermark(HW)와 low watermark(LW)를 가지고 있다. 사용가능한 페이지 수가 LW보다 적어질 때 메모리 확보를 담당하는 백그라운드 스레드가 실행된다. 해당 스레드는 사용가능한 페이지 수가 HW에 다다를 때 까지 페이지를 제거한다. Swap daemon 또는 page daemon1이라고 불리는 해당 스레드는 운영체제가 프로세스를 실행하는동안 사용할 여유 메모리를 확보한 후 sleep상태가 된다.

여러 교체 작업을 한번에 수행하여 성능 최적화를 할 수 있다. 예를 들어, 많은 시스템은 여러 페이지를 클러스터링하거나 그룹화하여 한 번에 스왑 파티션에 기록하므로 디스크의 효율성이 향상된다. 이러한 클러스터링은 disk의 검색 및 회전 오버헤드를 줄여 성능을 현저하게 향상시킨다.

백그라운드 페이징 스레드를 이용하면 직접 교체를 수행하는 대신 사용 가능한 여유 페이지 공간이 있는지 확인할 수 있다. 여유 페이지 공간이 존재하지 않을 경우 백그라운드 페이징 스레드에 페이지가 필요함을 알린다. 사용 가능한 페이지가 존재하게 되면 백그라운드 페이징 스레드는 원래 스레드를 깨워 원하는 페이지로 이동할 수 있다.

해야할 일이 있을 때, 작업의 그룹화를 허용하고 효율성을 높이기 위해서 백그라운드에서 수행하는 것이 종종 좋다. 운영체제는 때때로 백그라운드에서 일을 수행한다. 예를 들어, 실제로 디스크에 데이터를 쓸 때(write), 많은 시스템 버퍼 파일이 메모리에 쓰인다(write). 이렇게 하면 디스크에 한 번에 많은 쓰기(write)를 수행할 수 있어 디스크 효율 향상, 쓰기 지연 시간 단축(improved latency of writes)이 가능하다. 또한 백그라운드 작업은 시스템이 idle 상태일 때도 수행될 수 있어 하드웨어를 더 효과적으로 사용할 수 있다.

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

Intro

CPU 가상화를 위해서, 운영체제는 physical CPU를 여러 작업 간에 공유하여 마치 동시에 실행되는 것처럼 만들어야 한다. 기본 아이디어는 간단하다. 하나의 프로세스를 잠시 실행했다가 다른 프로세스를 실행하는 방식으로 진행한다. 이와 같은 방식으로 CPU를 공유하면 가상화가 이루어지며 이를 time sharing of CPU라고 한다.

그러나 이러한 가상화 머신을 구축하는데는 몇 가지 과제가 있다.

첫 번째는 성능(performance)이다. 시스템에 과도한 오버헤드를 부가하지 않고 어떻게 가상화를 구현할 수 있을까?

두 번째는 제어(control)다. 운영체제가 CPU에 대한 제어를 유지하면서 프로세스를 효율적으로 실행하는 방법은 무엇이 있을까?

Basic Technique: Limited Direct Execution

프로그램을 기대하는 만큼 빠르게 실행하기 위해서 OS 개발자는 Limited Direct Execution을 고안해냈다.

Direct Execution은 프로그램을 CPU에서 직접 실행한다는 것이다. 그러므로, 운영체제가 프로그램을 실행하고자 할 때, Process list에 Process Entry를 생성하고, 메모리를 할당하고, 프로그램 코드를 디스크에서 메모리로 로드하고, 진입점(entry point)을 찾아서 jump하여 사용자의 코드를 실행하기 시작한다. 보다 정확한 direct execution protocol은 아래와 같다.

Direct Execution 만으로 해결할 수 없는 문제들이 있다.

첫 번째로, 프로그램을 실행하기만 한다면 OS가 어떻게 프로그램을 효율적으로 실행하면서 동시에 원하지 않는 작업을 수행하지 않도록 할 수 있을까?

두 번째로, 프로그램을 실행할 때 OS는 어떻게 프로세스를 중지하고 다른 프로세스로 전환하는 time sharing(CPU 가상화)을 구현할 수 있을까?

해당 질문들을 풀어나가는 과정에서, 우리는 CPU 가상화를 위한 필요 사항들을 더 잘 이해할 수 있다.

OS는 이러한 문제들을 해결하기 위해 프로그램 실행(direct execution)을 통제 및 제한(limited)한다.

Problem #1 : Restricted Operations

direct execution 은 분명 빠르다는 장점이 있지만 만약 프로그램이 CPU에서 실행 도중에 disk I/O을 요청하거나 CPU나 Memory의 시스템 리소스에 대한 추가적인 액세스를 요청하는 등 제한된 작업(restricted operations)에 대해서 어떻게 처리해야할까?

한 가지 접근법은 제한된 작업들(restricted operations)에 대해서 프로세스가 원하는 것을 모두 허용하는 것이다. 물론 이는 바람직하지 못하다. 예를 들어 I/O(입출력)의 경우, 프로세스가 전체 디스크를 읽거나 쓸 수 있다면 모든 보호(protection) 기능이 손실된다.

따라서, 일반적으로 취하는 접근법은 user mode(사용자 모드)라고 불리는 새로운 프로세서 모드를 도입하는 것이다. 사용자 모드에서 실행하는 코드는 할 수 있는 것이 제한적이다. 예를 들어, 사용자 모드에서 실행할 때 프로세스는 I/O request를 할 수 없으며 요청 시 프로세스가 exception을 던지고 운영체제는 프로세스를 종료(kill)할 것이다.

사용자 모드와 달리, 운영체제가 실행되는 kernel mode(커널 모드)에서 실행하는 코드는 I/O 요청 및 restricted operations을 포함하여 권한이 필요한 모든 작업을 수행할 수 있다.

여전히 문제가 남아있다. 만약 유저 프로세스가 디스크 입출력과 같은 권한이 필요한 작업을 수행하고자 한다면 어떻게 할까? 이를 위해 현대의 거의 모든 최신 하드웨어는 유저 프로그램이 시스템 호출(system call)을 수행할 수 있는 기능을 제공한다. 시스템 호출은 커널이 파일 시스템(file system)에 액세스하고, 프로세스를 생성 및 파괴하고, 다른 프로세스와 통신하고, 더 많은 메모리를 할당하는 것과 같은 특정한 핵심 기능들을 사용자 프로그램(user program)에 노출한다.

system call을 수행하기 위해 프로그램은 special trap instruction을 실행한다. 해당 명령과 동시에 커널로 jump하고 privilege level(권한 수준)을 kernel mode로 올린다. system call의 목적이었던 권한이 필요한 작업을 수행하고 완료되면 OS에서 return-from-trap 명령을 호출하며 호출된 사용자 프로그램을 다시 user mode로 privvilege level을 낮춘다. 

trap 명령을 실행할 때,  확실하게 호출자의 레지스터들을 저장해야 한다. OS가 return-from-trap 명령을 실행 후 호출자의 레지스터들(caller's registers)이 올바르게 return(반환)되게 하기 위해서다. 예를 들어 x86 프로세서는 Program Counter, flags, 그리고 다른 레지스터들을 프로세스당 커널 스택에 push한다. return-from-trap 명령은 그 스택으로부터 values을 pop하여 사용자 모드 프로그램 실행을 재개한다.

운영체제 내부(커널 모드)에서 실행할 코드를 트랩이 알게 하기 위해서 커널은 시스템 부팅 시 트랩 테이블(trap table)을 구성한다. 시스템은 커널 모드로 부팅되므로 필요에 따라 시스템 하드웨어를 자유롭게 구성할 수 있다. OS가 가장 먼저 수행하는 작업 중 하나가 특정 예외 이벤트 발생 시 실행할 코드를 하드웨어에 알려주는 것이다. 운영체제는 이러한 트랩 핸들러(특수 명령)의 위치를 하드웨어에 알려준다. 하드웨어에 정보가 입력되면 이러한 핸들러의 위치는 다음 재부팅 전까지 기억하므로 시스템 호출 및 기타 예외 이벤트 발생 시 무엇을 해야 하는 지 알고 있다.

시스템 호출(system call)을 특정하기 위해 각 시스템 호출마다 번호를 할당한다. OS는 트랩 핸들러 내부에서 시스템 호출을 처리할 때 이 번호를 검사하고 유효한지 확인하고, 만약 그렇다면 해당 코드를 실행한다. 이러한 indirection(트랩 핸들러를 거쳐서 간접 실행)은 일종의 보호(protection) 기능을 한다. 사용자 코드(user code)는 jump할 exact address를 specify할 수 없다. 대신에 번호를 통해 특정 서비스를 요청해야 한다. 하드웨어에 trap table의 위치를 지정하는 명령의 실행도 강력한 기능이자 특권화된 작업이므로 사용자 모드에서 허용하지 않는다.

요약해보면 LDE(Limited Direct Execution) Protocol의 두 단계는 아래와 같다.

1 단계 - (부팅 시) 커널은 트랩 테이블을 초기화하며 CPU는 이후 사용하기 위해 위치를 기억한다. 이러한 과정은 커널의 privileged instruction을 통해 이루어진다.

2 단계 - (프로세스 실행 시) 커널은 프로세스를 실행하기 전 몇 가지(이전 내용 참고) 사항을 설정하고, CPU를 사용자 모드로 전환하여 프로세스를 실행하기 시작한다. 프로세스가 시스템 호출을 하면 운영체제는 trap에 걸려들어 이를 처리하고 return-from-trap을 통해 프로세스 제어 권환을 반환한다. 그 후 프로세스가 작업을 완료하면 main()에서 return(반환)된다. 이를 통해 프로그램이 정상적으로 종료(exit)되고운영체제가 정리한 후(clean up) 최종적으로 완료된다.

Problem #2: Switching Between Processes

Direct Execution에 있어서 다음 문제는 어떻게 OS가 CPU에 대한 제어권을 가지고 switch between processes를 수행할 수 있는 가이다. Switching Process는 겉보기에는 그저 OS가 실행 중인 프로세스를 멈추고 다음 프로세스를 실행하면 되는 간단한 문제처럼 보이지만 실제로는 그렇게 단순하지 않다. 왜냐하면, 프로세스를 수행하는 주체는 CPU이지 OS가 아니기 때문이다. 따라서 OS는 switch between process(프로세스 간 전환)을 수행하기 위해 CPU에 대한 제어권을 얻어야(regain control) 한다.

A Cooperative Approach: Wait For System Calls

과거에 일부 시스템에서 취했던 한 가지 접근 방식은 협력 접근 방식이다. 이와 같은 방식에서 운영체제는 시스템의 프로세스들이 합리적으로 동작할 것이라고 신뢰한다. 너무 오래 실행되는 프로세스는 주기적으로 CPU를 포기하며 OS가 다른 작업을 수행할 수 있도록 한다고 가정한다. 따라서 프로세스는 종종 시스템 호출을 통해서 CPU의 제어 권한을 OS에 전송한다. 예를 들어, 파일을 열고 읽거나, 다른 컴퓨터에 메시지를 보내거나 새로운 프로세스를 만들 때, 허용되지 않는 불법적인 작업을 할 때 OS가 CPU에 대한 제어 권한을 얻게 되며 이러한 사안에 관해 처리할 수 있게 된다.

따라서, 협력적 스케줄링 시스템에선 OS가 시스템 호출이나  불법적인 작동(illegal operation) 발생 시 CPU의 제어권을 얻는 수동적인 방식이다. 만약, 프로세스에 문제가 생겨 무한 루프(infinite loop) 상태에 빠지거나, 시스템 호출을 하지 않는다면 운영체제는 할 수 있는 것이 없다는 문제가 발생한다.

A Non-Cooperative Approach: The OS Takes Control

위와 같은 방식은 프로세스가 시스템 호출을 하지 않고 CPU에 대한 제어권을 운영체제에 전달하기를 거부할 때 추가적인 하드웨어의 도움 없이는 운영체제가 할 수 있는 것이 별로 없다. 프로세스가 무한 루프에 빠졌을 때 우리가 할 수 있는 유일한 방법은 재부팅이다. 따라서, 협력적 접근 방식은 우리가 해결하고자 하는 문제를 명확히 해결하긴 힘들다.

이를 위한 다른 해답은 timer interrupt 이다. 타이머 장치는 milliseconds 단위로 interrupt를 발생시킨다. 인터럽트가 발생하면 현재 실행 중인 프로세스가 중지되고 OS에서 미리 구성한 인터럽트 핸들러가 실행된다. 해당 시점에서 OS는 CPU를 제어할 수 있고 현재 프로세스를 중지하고 다른 프로세스를 실행할 수 있다.

앞서 시스템 호출에서 논의했듯이, OS는 타이머 인터럽트가 발생할 때 실행할 코드를 하드웨어에 미리 알려주어야 한다. 따라서 부팅시 OS는 하드웨어에 알려준다. 다음으로 부팅 작업 중에도 OS는 해당 타이머 장치를 실행하며 타이머가 시작되면 OS는 제어에 대한 안전성을 확보하며 자유롭게 사용자 프로그램을 실행할 수 있다. 타이머를 끌 수도 있으며 이는 동시성(concurrency)에 대한 이해와 함께 추후에 자세히 논의한다. 하드웨어는 시스템 호출 트랩 시 동작과 유사하게 인터럽트가 발생했을 때도 실행 중인 프로그램의 상태(state)를 충분히 저장하고 return-from-trap 명령이 실행될 때 실행중이었던 프로그램을 올바르게 재개할 수 있도록 해야하는 책임이 있다.

Saving and Restoring Context

이제 OS가 시스템 호출 또는 타이머 인터럽트를 통해서 제어권을 되찾았으므로 프로세스를 계속 실행할 지 아니면 다르 프로세스로 전환할지 결정해야 한다. 해당 결정은 OS의 일부분인 스케줄러에 의해 내려진다. 이에 대한 자세한 내용은 추후에 논의한다.

전환하도록 결정이 내려지면 OS는 Context Switch라고 하는 low-level code를 실행한다. Context switch 시  OS는 현재 실행중인 프로세스의 몇몇 레지스터 값들을 저장하고 전환할 프로세스의 몇몇 레지스터 값들을 복원한다. 따라서 OS는 실행중이던 프로세스로 돌아가는 대신 return-from-trap 명령이 실행될 때 시스템이 다른 프로세스를 실행하도록 보장한다.

현재 실행중인 프로세스의 컨텍스트(context)를 저장하기 위해서 OS는 현재 실행 중인 프로세스의 범용 레지스터, PC 및 커널 스택 포인터를 저장한 다음 실행할 프로세스의 레지스터, PC를 복원하고 실행할 프로세스의 커널 스택으로 전환한다. 스택을 전환함으로써 커널은 인터럽트된 실행중이었던 프로세스의 컨텍스트에서 switch 코드에 대한 호출을 입력하고 곧 실행 될 프로세스의 컨텍스트에서 반환한다. 그런 다음 OS가 최종적으로 Return-from-trap 명령을 실행할 때, 곧 실행될 프로세스가 현재 실행 중인 프로세스가 되며 컨텍스트 전환이 완료된다.

이 프로토콜 중 발생하는 레지스터 저장/복원에는 두 가지 유형이 있다.

첫 번째는 타이머 인터럽트가 발생할 때이다. 이 경우엔 실행중인 프로세스의 사용자 레지스터는 해당 프로세스의 커널 스택을 사용하여, 하드웨어에 의해 암시적으로(implicitly) 저장된다.

두 번째는 OS가 A에서 B로 Context Switch 할 때이다. 이 경우 커널 레지스터들은 소프트웨어(OS)에 의해 명시적으로(explicitly) 저장되는데, 이번에는 해당 프로세스의 프로세스 구조에서 메모리에 저장된다. 해당 동작은 시스템 커널이 A를 트랩한 상태에서 B를 트랩한 상태로 이동시킨다.

Worried About Concurrency?

그렇다면, 이런 의문이 생길 수도 있다. 

만약 시스템 호출중에 타이머 인터럽트가 발생한다면 어떻게 되는가?

하나의 인터럽트를 처리 중일 때 또 다른 인터럽트가 발생하면 어떻게 되는가?

실제로, OS는 인터럽트나 트랩 핸들링 도중에 또 다른 인터럽트가 발생할 때를 주의 깊게 고려할 필요가 있다. 해당 이슈에 대한 논의는 추후에 Concurrency 파트에서 하도록 한다.

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

프로세스 API란?

운영체제가 프로세스의 생성 및 제어를 위해서 제공하는 API다.

fork() System Call

fork() System Call(시스템 호출)은 새로운 프로세스를 생성하기 위해 사용된다.

동일 프로그램에서 부모 프로세스로부터 자식 프로세스가 생성된다.

wait() System Call

wait() System Call은 부모 프로세스가 자식 프로세스의 종료까지 기다리도록 하기 위해 사용된다.

exec() System Call

이 시스템 호출은 호출자 프로그램(the calling program)으로부터 다른 프로그램을 실행할 때 사용된다.

fork()의 경우는 동일 프로그램의 복제 프로세스를 생성하는데 반해, 다른 프로그램을 실행하고자 한다면 exec()를 사용할 수 있다. 

exec()(+ execvp())를 실행할 경우, executable(실행 가능한 파일)의 이름과 몇몇 arguments(인자)를 고려하여 코드 및 정적 데이터를 로드하고, 현재 코드 세그먼트에 덮어쓴다. 또한 힙과 스택 및 프로그램의 메모리 공간의 다른 부분들은 다시 초기화된다(re-initialized). 그런다음 운영체제는 해당 프로그램을 실행하면 해당 프로세스의 argv로 모든 인수를 전달한다.

따라서, 새로운 프로세스를 생성한다기보다는 현재 실행중인 프로그램을 해당 프로그램으로 변환한다고 볼 수 있다. exec()가 성공적으로 실행된다면, 이전 프로그램은 거의 실행되지 않는다고 볼 수 있으며, 성공적인 exec() 호출은 반환되지 않는다. (a successful call to exec() never returns)

Unix Shell 과 Process API

프로세스를 생성하는 단순한 메커니즘과 다르게 이렇게 이상한 exec()와 fork()와 같은 인터페이스를 만든 것일까?

왜냐하면, 이와 같은 fork()와 exec()의 분리가 Unix 쉘을 만드는 데 필수적이기 때문이다.

쉘에 적용하였을 때, fork()는 exec()와는 다르게 호출 후에 계속 코드를 실행하는 것이 가능하다. 그리고 이를 통해서 실행되는 프로그램의 환경을 변경하는 것이 가능하다.

쉘은 사용자 프로그램(user program)에 불과하며, 사용자에게 프롬프트를 출력하고 다음 입력을 기다린다. 사용자가 명령을 입력하면, 쉘은 실행 파일이 있는 파일 시스템의 위치를 파악하고, fork()를 호출하여 커맨드(명령)를 실행하기 위한 새로운 프로세스를 생성한 뒤에, 일부 변형된 exec()를 호출하여 커맨드를 실행한다. 그리고 wait()를 호출하여 명령이 완료되기까지 기다린다. 자식 프로세스가 완료되면, 쉘은 wait()로부터 return(반환)되고, 프롬프트에 다시 출력한 뒤, 유저의 다음 명령(커맨드)를 기다린다.

이처럼, fork()와 exec()의 분리는 쉘이 유용한 여러 가지 작업을 쉽게 수행할 수 있도록 한다.

Process Control and Users

fork(), exec(), wait() 외에도 유닉스 시스템의 프로세스와 상호 작용하기 위한 많은 인터페이스들이 있다. 예를 들어, kill() 호출은 프로세스에 pause, die, 그리고 기타 유용한 명령들에 대한 신호를 보내는데 사용된다. 대부분의 UNIX Shell에서 특정 키 스트로크 조합은 현재 실행 중인 프로세스에 특정 신호를 전달하기 위해서 쓰인다. 예를 들어 control+c는 SIGINT(인터럽트)를 프로세스(일반적으로 종료)로 보내고 control+z는 SIGTSTP(중지) 신호를 전송하여 프로세스의 실행 중간에 일시 중지할 수 있다.(나중에 재개할 수 있다.)

The entire signals subsystem(전체 시그널 하위 시스템)은 개별 프로세스 내에서 신호를 수신 및 처리하는 방법, 개별 프로세스 및 전체 프로세스 그룹에 신호를 보내는 방법 등 외부 이벤트를 프로세스에 전달하는 풍부한 인프라를 제공한다. 이러한 형태의 통신을 사용하려면, 프로세스가 signal() 시스템 호출을 사용하여 다양한 신호를 캐치(catch)해야 한다. 이렇게 하면 특정 신호가 프로세스에 전달되었을 때 해당 프로세스가 정상적인 실행을 미루고(suspend) 신호에 응답하여 특정 코드들을 실행하도록 할 수 있다.

그렇다면, 누가 프로세스에 신호를 보낼 수 있고, 누가 신호를 보내지 못하도록 해야할까? 일반적으로, 우리가 사용하는 시스템은 동시에 여러 사용자가 사용할 수 있다. 만약 아무나 SIGINT와 같은 신호를 임의로 전송할 수 있다면 시스템의 사용성(usability)과 보안성(security)이 손상될 것이다.

따라서, 현대 시스템은 유저에 대한 강력한 개념을 포함한다. 사용자는 자격 증명을 설정하기 위해서 암호를 입력한 후 로그인하여 시스템 리소스에 액세스할 수 있다. 그런 다음에 사용자는 하나 이상의 프로세스를 실행하고 프로세스를 제어할 수 있다.

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