이전편 : 가상 메모리

지역성

페이지 교체 알고리즘에 대해 언급하기 전에 먼저 지역성이라는 것에 대해서 알아야 한다.

• 시간 지역성 (Temporal Locality ) : 현재 참조된 메모리가 가까운 미래내에 참조될 가능성이 높음
  • loop,subroutine,stack
• 공간 지역성 (Spatial Locality) : 하나의 메모리가 참조되면 주변의 메모리가 참조될 가능성이 높음
  • Array 순회, 명령어의 순차실행

프로그램의 메모리 참조는 고도의 지역성을 가진다. 임의의 시간 Δt 내에 프로그램의 일부분만을 집중적으로 참조한다는 것이다.
이러한 지역성이 있기 때문에 적절한 페이지 교체 알고리즘이 중요하다.

왜 중요할까?

예를 들어서 주기적으로 두개의 페이지만 참조하는 로직이 있다고 해보자.

만약 그 두개의 페이지를 번갈아가면서 교체를 한다면, 페이지 폴트는 두 개의 페이지에 대해서 접근할때마다 계속 일어날 것이다.

이게 왜 위험하냐면, 불필요한 I/O 작업의 오버헤드도 있고, 그때마다 컨텍스트 스위칭이 계속 일어나기 때문이다.

페이지 교체 알고리즘

페이지 폴트가 났을때, 메모리에 빈공간이 있으면 올리면 되는 일이다. 물론 I/O가 들어가긴 하지만.

근데 만약 모든 메모리가 사용중이라면 교체될 페이지를 골라야하는데, 이걸 잘 고르는게 성능에 큰 영향을 미친다.

그러므로 원하는 것은 가장 낮은 페이지 폴트 확률이다. 모든 예시에서 [1,2,3,4,1,2,5,1,2,3,4,5] 의 순서로 페이지가 필요로 한다고 해보자.

일반적으로 프레임의 개수가 많으면, 페이지 폴트의 빈도도 줄어든다.

다만 정비례 하는것은 아니다. 이는 '벨라디의 모순'과 연관되어 있다.

FIFO

• 단순하게 페이지 교체를 할 때 가장 오래된 페이지를 선택해 교체한다.
  

  

• 근데 프레임이 3개일때와 4개일때를 비교해보면, 프레임이 늘었는데도 오히려 페이지 폴트가 증가했다. → 이것을 '벨라디의 모순'현상이라 한다.
• 즉 투입한 리소스와 효과가 비례하지 않음을 알 수 있고, 적절한 교체 알고리즘을 선택하는것이 중요함을 보인다.

Optimal

• 가장 오랫동안 사용되지 않을 (페이지 교체가 필요한 시점으로부터) 페이지를 선택한다.
  

  

• 가장 이상적인 알고리즘이기 때문에 가장 낮은 페이지 폴트를 보여준다.
• 그렇지만, 다음에 무엇을 사용할지 알 수 없기 때문에 구현이 어렵고 Optimal은 다른 알고리즘과의 성능비교의 기준으로 사용된다.
• 만약, 같은 행동을 반복하는 Bot의 형태고, 메모리 예측을 완벽하게 알 수 있다면 적용할 수 있다.

LRU

LRU는 Least Recently Used의 약자로 페이지 교체를 하는 시점에서
가장 덜 최근에 사용된것, 다시 말해 가장 오래전에 사용한 것 페이지를 선택해 교체하는 알고리즘이다.

• Optimal을 제외하고 굉장히 좋은 성능을 보이는데, 그 이유는 LRU가 Temporal Locality를 전제로 하고 있기 때문이다. 최근에 사용된것은 다시 참조될 가능성이 크니, 반대로 가장 오래전에 사용한것을 지우면서 페이지 교체 자체를 줄이려는 것이다.
  • 그런데 문제점은 LRU를 실제로 구현하는데에 있다.
    • 예를 들어 모든 페이지에 참조된 시간을 적어놓는다면, 페이지 테이블에 추가적인 메모리가 들것이고 (min heap으로 컷해도 될듯) 참조될때마다 이것을 계속 수정하는 오버헤드가 있다.
    • 만약 Linear하게 가장 오래전에 사용된 것을 찾는다고 해보자.
    • 이때의 시간복잡도는 n개의 페이지에 대해서 O(n)인데, 이 N 값이 의미하는 것은 프로세스의 개수이고 보통 너무 크다는데 있다.
  • 그러므로 커널에 구현하기는 시간적/공간적 오버헤드가 너무 크다. 따라서 근사치 모델이 필요하다.

LRU 근사

• 카운터 구현
  • 메모리 참조가 일어날때마다 CPU counter를 올리고, 페이지 A가 참조되면 페이지에 카운터를 덮어씌운다.
  • O(n)의 조회방식, 심지어 그때마다 메모리 액세스가 한번 더 일어남.
• 스택 구현
  • 페이지 번호로 Doubly Linked List 형태로 스택을 구현한다.
  • 페이지 A가 참조되면, A를 헤드로 옮긴다.
    • 이때 6번의 포인터 움직임이 필요하다.
  • 찾는데 드는 오버헤드는 없지만, 매번의 페이지 참조마다 6번의 메모리 액세스가 있다.
  • 교체가 일어나지 않아도 평소 오버헤드가 너무 크다.
• 두번째 기회 (Second Chance)
  • 기본적으로 FIFO다.
  • 페이지를 원형의 큐로 구성한다.
  • 페이지 테이블 내의 모든 페이지의 Ref bit를 초기값 0으로 할당하고, 참조가 되면 1로 바꾼다.
  • 참조비트가 0인 페이지를 찾으면, 그 페이지를 교체한다.
  • 만약 1이라면, 그 페이지는 0으로 바꾸고 한번 더 돈다. 한번의 기회를 더 주는것이다.
  • 한번 더 돌았을때도, 0이면 교환한다.
  • 그런데 모든 bit가 1인 경우를 생각해보면, FIFO의 알고리즘처럼 동작한다.

LFU

• 전제는 많이 사용되는 페이지는 더 많이 사용될 것이라는 전제
• 페이지에 참조된 횟수를 나타내는 카운터를 넣는다.
• 가장 카운터가 적은 페이지를 교체한다.
• 하지만 어떠한 페이지가 집중적으로 참조되다가 그 뒤에도 사용되지 않으면 어느정도까지 계속 머무르는 경향이 일어난다. 즉 전제와 어긋나게 된다.

MFU

• 전제는 카운터가 작은 페이지는 이제 막 들어왔고, 사용되지 않았다는 전제.
• 페이지에 참조된 횟수를 나타내는 카운터를 넣는다.
• 가장 카운터가 큰 페이지를 교체한다.
• Locality가 자주 변하는 시스템에서 유용하다.

프리페이징(Prepaging)

프로세스가 시작될때는 항상 initial page fault가 난다. 아무것도 안올라와 있기 때문에..

이것을 방지하기 위해서, 프로세스가 필요로 하는 페이지의 전부 혹은 일부를 참조되기전에 미리 메모리에 올리는것이다.

물론, 페이지가 사용되지 않으면 낭비가 있다.

Swap의 어떤 이점이 있는가?

• 장점
  • 가상 메모리를 만들고 유지하는데 도움이 된다. 그렇기에 더 많은 프로세스가 구동될 수 있다.
  • 실제 필요한 메모리용량만큼만 디스크에서 메모리로 올릴 수 있게 해주니, 물리메모리보다 더 큰 용량의 프로세스가 구동될 수 있다.
• 단점
  • 디스크에 접근하는 I/O → 디스크가 입출력을 할때 기다리지 않고 컨텍스트 스위칭

난 운영체제가 제일 재밌고 좋다. 최고👍

세마포어와 뮤텍스를 본격적으로 얘기하기에 앞서서 두 방법이 나오게 된 문제상황인 Race Condition과 Critical-Section을 먼저 소개한다.

Race condition

두 개 이상의 프로세스가 공유 데이터에 대해서 동시에 접근하고 조작하려하는 상황을 의미한다. 즉 Race라는 뜻 그대로 하나의 자원을 놓고 서로 경쟁하려는 상태이다.

이 공유된 데이터의 마지막 값은 어느 프로세스가 마지막으로 끝내는지에 따라 달려있다. 만약 interleaved execution(서로 번갈가면서 명령어 수행시) 데이터의 무결성이 침해받는다. → 불확실성

이것을 예방하기 위해서, 동시에 진행되는 프로세스는 반드시 동기화가 되어야 한다.

Critical-Section

이러한 문제를 임계구역(Critical-Section) 문제라고 한다. 임계구역이란 동일한 자원에 대해서 접근하는 영역을 의미한다.
해결하기 위해서는, 한 프로세스가 임계구역에 진입해 작업을 진행할때, 다른 프로세스들은 임계구역에 진입하는 것을 허락하지 않는것이다.

동기화를 해결하는 방법은 세가지 필수적인 조건을 맞춰야 한다.

1. 상호배제(Mutual Exclusion)
   • 어떠한 프로세스 혹은 스레드가 임계구역에서 작업을 진행하면, 다른 프로세스 혹은 스레드는 임계구역에 진입할 수 없다.
2. 진행(Progess)
   • 무기한으로 연기되는것을 막기 위해서 필요하다.
   • 만약, 다른 프로세스가 임계구역에서 작업을 하고 있지 않다면, 다른 진입을 원하는 프로세스의 진입은 지체되어서는 안된다.
3. 한계가 있는 대기 (Bounded Waiting)
   • 과도한 방지를 막기 위해서 필요하다.
   • 프로세스가 임계구역에 들어가기 위해서 요청하고 대기하는 시간은 한정되어 있어야 한다. 즉, 무기한적으로 대기되는것을 막기 위해서 필요하다.

문제에 대한 개괄적인 해결방식

두 개의 프로세스만 있다고 가정했을때, 임계구역에 진입가능했는지 체크하고, 임계구역을 빠져나올때는 진입가능성을 열어준다.
이 때 프로세스들은 동기화를 위한 데이터를 공유해야 한다.

뮤텍스

CS를 가진 스레드 혹은 프로세스들의 실행시간(Running Time)이 서로 겹치지 않고 각각 단독으로 실행될 수 있게끔 하는 기술이다.
일반적으로 한 프로세스에 의해 소유될 수 있는 Key 객체를 기반으로 작동되며, 이 객체를 소유한 스레드 혹은 프로세스만이 공유자원에 접근할 수 있다.

뮤텍스를 구현하는 방식에는 세가지 정도가 있는데, 모두 각각의 장단점이 존재한다.

Swap turn

• 첫번째 해결방식, Swap turn
  • 공유 변수 turn 을 두고, 서로 입장 가능한지 while로 체크한다.
  • 상호배제는 만족하지만, 진행도는 만족하지 못한다.
  • 두 프로세스는 무조건 in-turn 방식(왔다갔다)으로만 진입할 수 있다.
    • 만약 P0→P1 순서대로 들어갔다고 해보자. 이때 P1이 추가적인 진입을 원하더라도 P0의 차례이기 때문에 P1은 진입 할 수 없고, 진행도를 만족하지 못한다.
  • 즉, P1이 CS에 더 자주 접근해야하는 시스템이라고 해보자. 그럴때는 P0에 의존적이다. 두번 연속으로 CS 진입이 불가능하기 때문이다.Dekker's Algorithm
• // P0 **do { while (turn != 0) ; /* My turn? */ critical section turn = 1; /* Now it’s your turn */ remainder section } while (1);** // P1 **do { while (turn != 1) ; /* My turn? */ critical section turn = 0; /* Now it’s your turn */ remainder section } while (1);**
• 두번째 해결방식,데커 알고리즘
  • 만약 flag[i]==true 이면, Pi는 CS에 진입할 수 있다.
  • 첫번째 Swap turn 방식의 문제점인, 연속적인 진입이 불가능한 점을 해결한다.
  • 상호배제는 만족하지만, 진행도는 만족하지 못한다.
  • 만약 flag[i]=true 일때 컨텍스트 스위칭이 일어나면, Pj가 생각하기에 Pi가 들어가있다고 생각할것이다. 실제로는 그렇지 않은데.
    • 그러면 둘다 CS에 진입하지 못하고 기다려야 한다. 다음 컨텍스트 스위칭이 일어날때(선점식일때)까지 기다려야 한다.
    • flag[i]=true 로 바꾸는 저 부분이 유저 코드이기 때문에 중간에 인터럽트의 방해를 받을 수 있는 non-atomic이기 때문이다.Peterson's algorithm
• boolean flag[2] 초기에는 flag[i]=flag[j]=flase // 아무도 CS안에 있지 않다. // Pi do { flag[i] = true; /* Pretend I am in */ while (flag[j]) ; /* Is he also in? then wait*/ critical section flag [i] = false; /* I am out now*/ remainder section } while (1);
• 세번째 해결방식 (피터슨 알고리즘)
  • 1번과 2번의 공유 변수를 조합한 방식이다.
  • flag[j] 변수를 활용해서, swap-turn은 해결했다. 또 turn 문제를 이용해서 무조건 둘 중 하나는 CS에 들어갈 수 있음을 보장한다.
  • 상호배제,진행도,한정된 대기시간이라는 두 프로세스간의 해결책에서의 조건을 모두 만족한다.
  • 여러 프로세스로 확장가능하다. 하지만, while loop에서 CPU는 계속 체크해줘야 하는 busy waiting 문제가 여전히 남아있다. CPU cycle을 낭비하고 있는것이다.
• do { flag [i]= true; /* My intention is to enter …. */ turn = j; /* Set to his turn */ while (flag [j] and turn == j) ; /* wait only if …*/ critical section flag [i] = false; remainder section } while (1);

HW 지원

이렇게 해결책에도 여전히 문제점이 남아있기 때문에, 많은 시스템들은 하드웨어의 지원을 받는다.

• I/O가 없을때 CS 진입 후 선점적인 스케쥴링을 방지.
• 유니프로세서 시스템에선 인터럽트를 꺼버린다. 왜냐면 timeout이 있기 때문에. 하지만 대부분의 멀티프로세서 관점에서는 불리하다.
• 현대의 대부분의 시스템들은 원자적인(atomic) 하드웨어 명령어를 지원받는다.
  • TAS(test and set)
  • 
  • CAS(compare and swap)
    • 원자적으로 두 변수를 바꾼다.
    • 
    • key=true일때 lock이 false면, 진입해버린다. key=true인데 lock이 true면 계속 기다린다.
    • 이때 key는 lock과 달리 지역변수라 컨텍스트스위칭에 안전하다.

세마포어

뮤텍스와 비슷하게 동기화 기법이지만, 뮤텍스는 동시접근을 막으려는 측면이 강하고,
세마포어는 접근 순서 동기화에 조금 더 관련이 있다.

근본적으로 wait() 와 signal() 을 이용해서 제어를 하는 방식으로 세마포어를 여러개를 둠으로써 CS에 접근 가능한 task의 개수를 조절한다.
개수가 1개이면 binary semaphore로 mutex 처럼 작동을 한다.

P(s) // atmoic 해야함
func {
    while S<=0 do nothing;
    S--;
}
V(s) // atomic 해야함
func {
    S++;
}

이렇게 구현하면 세마포어를 이용한 뮤텍스가 된다.물론 busy waiting 문제가 여전히 발생을 한다.
즉, 특정 프로세스가 CS를 많이 차지하면 다른 프로세스는 P에서 계속 기다려야 한다.

이런 방식은 여전히 싱글프로세서 시스템에서 자원의 낭비라는 관점에서 치명적이다.

Block/Wakeup 방식

Block/Wakeup 방식은 busy waiting의 방식처럼 계속 기다리는 것이 아니라,
기다려야 할때만 대기줄에 줄만 세워놓고 block을 당하게 한다. 그 후 자리가 생기면, 즉 순서가 돌아오면 block 당한것들부터 차례로 깨운다.

typedef struct {
int value; /* semaphore */
struct process *L; /*process wait queue*/
} semaphore;

void P(S){
    S.value--;
    if (S.value<0){
        add this into S.L
        block()
    }
}

void V(S){
    S.value++;
    if S.value<=0 {
        remove P from S.L
        wakeup(P)
    }
}

이런식으로 세마포어에 링크드 리스트를 구현해서 세마포어를 완성한다.
process wait queue는 링크드 리스트로 프로세스의 PCB에 대한 정보를 가지고 있다.

• block() : 커널이 현재 프로세스를 중지시키고, 그 프로세스의 PCB를 세마포어 안에 있는 대기 큐에 넣는다.
• wakeup(p) : block되었던 프로세스 P의 작업을 다시 하게 한다.

이 때 S.value 의 절댓값은 현재 block 되어 있는 프로세스의 개수와 동일하다.

이전의 busy waiting과 block wakeup 방식을 비교해보자.

• CS 파트가 작으면
  • 기다리는데 드는 시간보다, block-wakeup하는데 드는 오버헤드가 더 클 수 있음.
• CS 파트가 길면
  • busy waiting이 길어지기 때문에 block-wakeup이 더 좋을수 있다.

임계영역이 유저 공유 데이터에서만 생길까?

1. 인터럽트 핸들러와 커널중간에 인터럽트가 와서 인터럽트 핸들러 내에서 count 값을 올리면, 그 뒤의 count 결과는 보장할 수 없다.
2. count 라는 커널 변수가 있다고 해보자. count 의 값을 올리는 과정은 load하고,increase하고,store를 하는 것인데,
3. 커널이 시스템 콜을 수행중일때, 컨텍스트 스위칭이 일어나면아래와 같은 상황일때 count의 값을 보장 할 수 있는가?이 문제에서 중요한 점은 프로세스간의 데이터 공유가 아니더라도 임계영역문제가 커널 단에서 분명히 발생할 수 있다는 점이다.
4. 유닉스에서는 이를 방지하기 위해서 커널이 작업을 수행하고 있다면(시스템 콜 처리) 선점식 스케쥴링이 일어나지 않는다.
5. 
6. 두 프로세스간은 공유되는 데이터가 없다하더라도, 시스템 콜을 수행할때 커널 데이터는 공유될 수 있다.
7. 멀티프로세서 시스템
   • 만약 두개의 CPU에서 한쪽은 count를 내리고, 한쪽은 카운트를 내린다고 해보자. 어느 값을 저장해야 하는가?
     • 각각의 CPU 이기 때문에 인터럽트로 통제할 수 없다.
   • 이럴때는 커널 자체가 하나의 큰 CS가 된다
     • 커널 자체 접근을 한 CPU만 할 수 있게 하거나
     • 커널내의 공유 변수들을 따로 세마포어로 둔다. 그러면, 큰 CS가 여러개의 나뉘어진 CS가 된다.

이진 세마포어 vs 카운팅 세마포어 비교

• 이진 세마포어
  • 정수값이 0과 1를 오가는 세마포어다. lock과 비슷하게 0은 사용중이고 1은 자유로운 상태이다.
  • 같은 시간 안에 오직 한개의 프로세스나 스레드가 CS에 접근하는 것을 허용한다.
  • CS안에 두개의 프로세스나 스레드가 동시접근이 불가능하기 때문에 상호배제는 만족한다.
  • 단지 정수적인 lock에 불과하니, 제한된 대기를 보장할수는 없다.즉, 기아가 발생할 수 있다.
• 카운팅 세마포어
  • 카운터라는 여러개의 값을 가질 수 있는 세마포어다.
  • 값의 범위는 0에서부터 N까지며, N은 CS로 입장을 허용하는 프로세스 혹은 스레드의 개수이다.
  • 한번에 둘 이상이 CS에 접근가능하기 때문에 상호배제를 보장하지는 않는다.
  • 기아현상을 피하기 위해서 큐를 구성하고 있는데, 이 큐가 있기 때문에 언젠가는 접근할 수 있다. 즉 제한된 대기 상태를 보장한다.
  • 특정하고 1보다 큰 개수의 한정된 자원을 배분할때 사용 될 수 있다.
    • 쓰레드 풀 (Thread Pool)
    • DBCP(Database Connection Pool)의 사례
    • 스프링에서의 사례

세마포어와 뮤텍스 차이점은?

• 세마포어는 뮤텍스가 될 수 있지만 뮤텍스는 세마포어가 될 수 없다.
• 예를 들어 Casting을 한다고 보면 (뮤텍스)세마포어 –> 가능하지만 (세마포어)뮤텍스 –> 불가능하다.
• 세마포어는 소유할 수 없는 반면 뮤텍스는 소유할 수 있고 소유자가 이에 책임을 진다.
• 뮤텍스는 1개만 동기화가 되지만 세마포어는 하나 이상을 동기화 할 수 있다. → 즉 임계영역에 접근가능한 수가 원천적으로 1개이냐 , 그 이상이냐의 차이다.

변기가 하나뿐인 화장실에서는
앞의 사람이 볼일을 마치고 나가야 다음 사람이 들어갈 수 있다.
이렇게 한번에 오직 하나만 처리할 수 있는 대상에 사용하는 것이 뮤텍스이다.

변기가 세개인 화장실에서는 동시에 세 사람이 볼일을 볼 수 있고
이 세 사람 중 아무나 한명이 나오면 다음 사람이 볼일을 볼 수 있다.
이렇게 동시에 제한된 수의 여러 처리가 가능하면 세마포어이다.

만약 변기 세개짜리 화장실의 각 변기에 대해 뮤텍스를 사용한다면
대기중인 사람은 각 변기 앞에 줄을 서는 것이고
이렇게 되면 옆 칸이 비어도 들어가지 못하게 된다.

만약 변기 세개를 묶어서 뮤텍스를 사용한다면
변기 수에 관계없이 무조건 한명만 사용할 수 있게 된다.

이 예에서 변기는 동기화 대상, 사람은 그 동기화 대상에 접근하는 쓰레드를 나타낸다.

뮤텍스와 세마포어의 목적은 특정 동기화 대상이 이미 특정 쓰레드에 의해 사용중일 경우
다른 쓰레드가 해당 동기화 대상에 접근하는 것을 제한하는 것으로 동일하지만
관리하는 동기화 대상이 몇개 인가에 따라 차이가 생기게 되는 것이다.

뮤텍스 vs 이진 세마포어

• 뮤텍스
  • 근본적으로 공유하는 자원에 대한 보호의 목적으로 쓰인다.
  • 뮤텍스는 lock을 잠근 task가 보유하는 관점이다.
  • 그렇기에 오직 그 task만이 해제할 수 있다. lock을 보유하지 않은 task가 접근할시 에러가 발생한다.
  • 일반적으로 이진 세마포어보다 더 가볍고 단순하기에 CS에 대한 보호의 용도로 더 많이 사용된다.
• 이진 세마포어
  • 신호를 주는(Signalling) 메커니즘에 더 가깝다. "나는 끝났으니, 이제 너의 작업을 해도 된다"
  • wait를 호출한 프로세스나 스레드가 아니여도 해제할 수 있다.
  • 물론 이것을 이용해서도 공유 자원을 보호하는데 사용할수는 있지만, task의 순서 동기화의 측면이 더 강하다.
  • 일반적으로 뮤텍스에 비해 오버헤드가 크다.

스핀락과 busy waiting의 사용처

do{
    acquire()
    CS
    release()
} while(true)

func acquire(){
    while(!availbale){
        //busy waiting}
    }
    available=false;
}

위의 방식은 available 이라는 변수를 둠으로써 락이 걸려있지 않다면 가져온뒤 CS로 진입하고 그렇지 않으면 계속 시도하는 방식을 쓰고 있다.

이럴때 acquire과 release는 atomic해야한다. 이런 방식의 가장 큰 문제점은 busy waiting을 해야한다는 점이다. 한 프로세스가 CS에 접근하고 다른 프로세스가 acquire 함수를 호출하면, 계속 acquire 안에서 계속적으로 루프를 돌아야 한다. 이런 방식의 구현을 스핀락(spinlock)이라고 하는데 다른 프로레스가 락이 풀리기를 기다리면서 계속 "돌고있기" 때문이다.

이러한 연속적인 루프는 싱글프로세서 시스템에서 명백한 문제인데, busy waiting 방식에서 다른 CPU가 더 잘 사용할 수 있는 자원을 대기하는데만 사용하고 있기 때문이다. 내가 기다리고 있다는 건 다시 말하면 나혼자만 CPU를 할당받고, 다른 프로세스(락을 풀어줄수 있는)는 돌아가고 있지 않기 때문에 기다릴 이유가 없는것이다.

그러면 스핀락을 사용하는 busy-waiting 방식은 전혀 쓸모가 없는것일까?
그렇지 않다.
이에 관해서 Operating System Concepts(공룡책)의 설명을 보자.

Spinlocks do have an advantage, however, in that no context switch is required when a process must wait on a lock, and a
context switch may take considerable time. In certain circumstances on multicore systems, spinlocks are in fact the preferable choice for locking. If a lock is
to be held for a short duration, one thread can “spin” on one processing core while another thread performs its critical section on another core. On modern multicore computing systems, spinlocks are widely used in many operating systems.

야매로 번역을 해보자면,

하지만, 스핀락도 장점이 있다. 락이 빨리 풀릴거라고 예상되는 시스템에서 스핀락은 아주 유용하다.
컨텍스트 스위칭을 하는 비용보다 스핀락으로 busy waiting을 하는게 더 이득일 수 있기 때문이다.
이러한 장점때문에 멀티프로세서 시스템에서 한 쓰레드는 락에 대해서 계속 스핀하고, 다른 쓰레드는 다른 프로세서에서 임계영역에 대한 접근을 할 수 있다.

이게 무슨말이냐면, 원래 락이 빨리 풀리는 시스템에서는, 다른 프로세서에 있는 스레드가 락을 해제한다면, 내 프로세서에서는 컨텍스트 스위칭을 할 필요없이 바로 스핀락 하다가 들어가버리면 되기 때문이다.

만약, 내가 지금 spin 한다고 해서 바로 컨텍스트 스위칭을 해버린다면, 다른 프로세서가 락을 풀어도 내 프로세서는 다시 프로세스로 스케쥴링될때까지 기다리고, 컨텍스트 스위칭을 한 후 접근해야하기 때문이다.
즉, 원래 락이 빨리 풀리는 시스템에선 컨텍스트 스위칭의 비용이 spin lock의 대기시간의 비용보다 더 비쌀수 있기 때문이다.

이전편 : 페이징

가상 메모리 (Virtual Memory)

가상 메모리는 논리적 메모리와 물리 메모리를 분리시켜, 프로세스 전체가 메모리내에 올라오지 않아도 실행가능하도록 하는 기법이다.

물론 프로그램이 실행되기 위해서는 메모리에 프로세스가 올라와야 하는것은 맞다. 하지만 특정 부분을 실행할때는 그 부분만 메모리 위에 올라와있어도 구동이 된다.

그렇기 때문에 논리적 주소공간은 실제 물리적 주소공간보다 훨씬 커도 된다. 왜냐면, 어차피 일부만 실행할때 필요하니까..
그럼 가장 핵심적인 기술은 프로세스를 실행할때, 필요한 메모리를 불러오고(swapped in) 필요하지 않은 부분은 내리는(swapped out) 과정이 필요하다.

가상메모리는 요구 페이징(Demand Paging) 이라는 기술로 구현된다.

특정 페이지에 대한 수요가 있을때, 즉 페이지에 대한 참조 요청이 들어왔을때 페이지를 메모리로 불러오는것이다.

다시 말해서 기존의 방법과는 다르게 가상 메모리 방식을 취하면, 시작할때부터 아무 메모리도 올라와있지 않아도 되고 필요할때만 불러오는 방식이다.

프로그램에서 사용되는 일부분만 메모리에 적재하는 가상 메모리를 통해서 아래와 같은것들이 가능하다.

• 시스템 라이브러리가 여러 프로세스 사이에 공유가 가능하다.
  프로세스 입장에서는 자신의 주소공간에 라이브러리가 올라와있다고 생각하지만, 실제로 라이브러리가 들어 있는 물리 메모리는 하나로 모든 프로세스에 공유되는 방식이다.
• 프로세스가 만들어질때 훨씬 더 효율적이다. 왜냐면, 실제로 프로세스를 만들때 필요한 모든 메모리를 할당해주는것이 아니라 필요할때만 주기 때문에 훨씬 가볍고 효율적이다.
  • 예를 들어서 fork 를 해서 프로세스를 생성한다고 해보자.
    이때 메모리를 직접 주는것이 아니라 기존의 메모리를 그대로 사용하게끔만 하고 프로세스는 이것을 독립적인 메모리 공간으로 인식한다.
• 실제 물리 메모리보다 더 큰 메모리를 요구하는 프로세스를 구동시킬 수 있다.
• 더 많은 프로세스가 구동이 가능하다.

요구 페이징 (Demand Paging)

페이지를 메모리에 올릴때 오직 그것이 필요할때만 수행하는것을 요구 페이징이라고 한다.
이것을 Lazy Swapper이라고도 하는것같다.(그 페이지 필요할때까지 절대 페이지를 메모리에 올리지 않는다)

• 적은 I/O : 전체 코드내에서 접근 안되는 주소공간은 가져올 필요가 없으니.
• 적은 메모리 사용량
• 빠른 응답 : 모든 페이지가 올라와있을 필요가 없으니 시작이 빠르다.
• 더 많은 유저 : "논리적 메모리 >> 물리적 메모리 " 이니 더 많은 프로세스를 수용가능하다.

만약에 특정 페이지가 필요하다고 하자. 그럼 그 페이지를 참조해야하는데, 아래와 같은 분기를 가지게 된다.

• 페이지에 대한 잘못된 참조 → 에러
• 메모리에 올라와있지 않음 → 데이터를 메모리에 적재함

그럼 이 올라와있지 않거나 올라와 있는것을 어떻게 구분할까?

논리주소와 물리주소를 변환할때 쓰였던 페이지 테이블을 이용해 페이지 테이블의 엔트리에 valid-bit를 부착해서 구분한다.

만약 valid-bit가

• True면
  • 현재 그 메모리를 가져온다.
• False면
  • Page Fault 발생
  • Page fault에 대한 처리를 하는데 일반적으로 페이지에 해당하는 프레임을 찾아서 로드시킨다.
    

    

    
    위 그림을 보면 B,D,E,F,G,H는 valid-bit가 invalid로 되어있다.
    만약 이때 B나 F와 같은 페이지를 참조하려 하면 Page Fault가 일어나는 것이다.

그럼 페이지 폴트 (Page Fault)가 뭘까?

페이지 폴트 (Page Fault)

페이지 폴트는 valid-bit가 invalid 인 곳에 MMU가 접근을 할때 HW trap을 발생시키면서 생긴다.

valid-bit가 invalid 하다는 것은 현재 메모리안에 내가 원하는 페이지가 존재하지 않음을 의미하므로, 원하는 페이지에 해당하는 프레임을 메모리로 가져온 후 프로그램이 계속 동작되게끔 해야한다.

이것을 페이지 폴트 핸들링이라고 한다.

페이지 폴트 핸들링

페이지 폴트는 결국에 인터럽트이기 때문에 ISR을 수행하는 처리과정을 거친다.

아래는 프로세스가 특정한 페이지를 참조하려고 했을때의 과정에 Page Fault 핸들링하는 과정이 추가된것이다.

1. 프로세스가 논리주소 (p,d) 를 가지고 메모리에 접근하려고 시도한다.
2. TLB를 먼저 확인해서 p에 해당하는 프레임 번호 f가 있는지 확인한다.
   1. TLB Hit,있다면 바로 메모리로 접근해서 (f,d)를 가져온다.
   2. TLB Miss, 없으니 이제 페이지 테이블을 참조해야 한다.
3. (p,d)를 가지고 페이지 테이블에 접근한다.
   1. 페이지 테이블에 p에 해당하는 f가 valid하면, 메모리에 접근해서 로드한다.
      • 이때 TLB 엔트리도 갱신된다.
   2. 만약 valid하지 않다면 현재 메모리에 올라와있지 않다는 것 → Page Fault
4. 운영체제가 메모리 접근할때의 주소를 확인한다.
   1. 잘못된 접근인가? 그러면 중지시켜야 한다.
   2. 아니라면 진행.
5. 물리 메모리에서 적절히 빈공간을 찾는다.
   1. 만약 이때 없다면, 적절하게 다른 프레임을 교체시켜야 한다. 이 교체의 방식이 매우 중요한데, 잘 골라야 다음에 replace가 일어날 확률을 줄인다.
6. 저장소에서 매치되는 페이지를 프레임에 올린다.
   1. 이때 프로세스는 wait 상태인데, 저장소 접근 자체가 I/O 이기 때문이다. 컨텍스트 스위칭 발생.
   2. I/O가 끝나면, 페이지 테이블 엔트리가 업데이트 되고, valid-bit가 valid로 설정된다. 이때도 컨텍스트 스위칭 발생할것같다.
   3. 프로세스는 레디큐로 옮겨진다. 그리고 일반적으로 스케쥴링되는것처럼 기다려야 한다.
7. CPU를 다시 할당받게 되면 페이지 폴트 트랩 처리가 끝난다.
8. 페이지 폴트를 촉발시켰던 명령어부터 다시 수행한다. (PC를 증가시키지 않기 때문에. 만약 PC 증가시키면 그 명령어는 강제로 건너띄는것이다.)

쓰레싱 (Threshing)

스레싱은 멀티프로그래밍 환경에서 페이지 폴트가 많이 일어나서 시스템이 아무런 작업도 하지 못하고 페이지를 메모리에서 가져오고 빼내는 과정만 반복해 CPU 이용률이 급격하게 떨어지는 현상이다.

더 최악인 점은 CPU 이용률이 떨어지니, 레디큐에 프로세스를 올리는 Long-term scheduler가 판단하기를
”CPU 이용률을 높이기 위해 멀티프로그래밍 정도를 올려야 함"이라고 판단하고 레디큐에 더 많은 프로세스를 올리면서 페이지폴트는 더 늘어간다.

• 여기서 멀티프로그래밍 정도가 느는것과 페이지폴트가 무슨상관일까?
  • 새로운 프로세스가 올라오면, Short-term scheduler가 새로운 프로세스에 CPU를 할당할 것이고, 이때는 initial page fault가 생기기 때문이다.

결국 Swap-in,Swap-out만을 하느라 바쁘고, 프로세스는 Block 되며, CPU는 대부분의 상황에서 IDLE 상태다.

I/O 작업만 하니까..

위의 그림처럼 MPD를 계속 올리다보니 스레싱이 발생하고, 그러면 더 MPD를 올리게되고 페이지폴트는 더 자주일어나면서 CPU 이용률은 급감한다.

결국에 자주 접근되는 페이지가 메모리에 올라와있지 않으면 이런 많은 페이지 폴트가 생기는데,
그렇기 때문에 각 프로세스가 필요로 하는 최소 프레임의 개수만큼은 보장을 해주어야 한다.

운영체제의 핵심 부분인 하나인 메모리 관리에 대해서 적겠다.

대략 3편으로 구성되며 페이징,가상메모리,페이지 교체 알고리즘 순이다.

MMU

CPU는 프로세스를 구동할 때 PC를 참조해서 다음 명령어를 메모리에서 가져온다. 명령어를 참고해 필요한 데이터가 있으면 메모리에서 가져오는데 이때 주소체계가 서로 다르다.

아래의 그림처럼 base와 limit 레지스터 안에 있는 값들을 조합해서 CPU가 사용하는 주소(논리 주소)와 실제 메모리 주소(물리 주소)를 구할 수 있다.

그러면 왜 두 주소를 구분하였을까?

가장 큰 이유는 보안이다. Limit 레지스터를 둠으로써, P1이 P2의 메모리 영역을 참조하는 Memory Illegal Access를 방지하는 Protection의 기능을 수행한다.

MMU는 Memory-Management Unit의 약자로 위에서 말한 논리주소를 물리주소로 대응시켜주는 HW 장치이다.

MMU 방식에서는 relocation 레지스터가 존재하는데, 프로세스가 메모리 주소를 만들때마다 relocation 레지스터 안의 값이 더해지고 이를 통해서 메모리에 접근할 수 있게 된다.

base 레지스터와 역할이 동일하다고 생각하면 된다.

연속적인 할당(Contiguous Allocation)

메모리에 프로그램을 연속적으로 할당하는 방법이다. 간단하게 말해서 아래에서부터 차례차례 채워가는 방식. 메모리를 연속적으로 사용하기 때문에 간단한 MMU만으로 구현할 수 있다.

일반적으로 커널은 낮은 메모리주소에 배치되고, 유저 프로세스는 높아지는 메모리 주소를 가진다.

또 커널을 제외한 메모리 영역을 하나로 보는 방식과 여러개의 파티션으로 보는 방식이 있다.

여러개의 파티션으로 할당하는 방법에서는 다수의 고정된 크기의 파티션으로 나누어져 있고, 2개 이상의 파티션에 할당할때는 합병(merge)해서 할당한다.

그런데 그림에서 마지막 단계를 잘보면 P10과 P2 사이의 빈 공간이 보인다.
이것을 Hole이라고 하는데, 단순히 말해서 할당가능한 메모리의 영역이다.

이 Hole은 크기가 커서 프로세스를 할당받을 정도가 되면 문제가 되지 않지만, 그 크기가 작을때는 파편화 문제가 생길 수 있다.

파편화 (Fragmentation)

파편화 혹은 단편화는 메모리 내에서 할당가능한 영역이 존재하지만, 할당이 불가능한 상태를 의미한다. 두가지 종류가 있다.

• 내부 파편화

  • 할당을 하는 단위가 존재할때 생긴다.

  • 프로그램이 필요한 사이즈보다 더 큰 메모리가 할당되면서 파티션 내부적으로 메모리 공간이 낭비되는 상황

    

• 외부 파편화

  • 남아있는 메모리가 흩어져 있어서 총 메모리 양은 할당할 수 있을 정도인데 실제론 할당할 수 없을때

    

  • 내부 파편화와는 다르게 할당을 하는 단위가 존재해도 생기고, 존재하지 않아도 생길 수 있다.

    • 존재할때는 왜 생길까?
      • B프로세스의 다음 메모리 공간을 보자.
        원래는 프로세스가 들어갈 자리인데도 그 프로세스가 끝나고 D가 끝나지 않았다면 C는 들어가지 못한다.

  • 즉, 사용가능한 메모리 영역은 있는데, 연속적이지 않은것이다.

  • 압축(compaction) 기법을 통해서 해결 할 수 있는데, 오버헤드가 크다. (JVM GC의 mark-and-compaction 생각해보자.)

세그멘테이션 (Segmentation)

페이징 방법에서는 가상 메모리를 서로 같은 크기로 분할했지만, 세그먼테이션 방법에서는 서로 크기가 다른 논리적 단위인 세그먼트로 분할한다.

세그먼트들의 크기가 각각 다르기 때문에(code를 위한것,데이터를 위한것...) 필요할때마다 빈 공간을 찾아서 해결한다.

프로세스가 딱 필요한 만큼만 메모리를 배정해주기 때문에 내부파편화 문제는 없지만, 외부 파편화 문제는 존재한다.

• 아래 그림을 보자. (a)번 상황에서 Segement 1이 빠지고 S7이 들어오면, S7이 더 작기 때문에 공간에는 맞지만 S2와 S7 사이에 빈공간이 생긴다.!
  

  

• 비슷한 상황이 S4가 나가고 S5가 들어오는 상황에서도 생기고 3과 6의 상황에서도 생긴다.
  이런 빈 공간이 생기기 때문에 세그멘테이션은 외부파편화 문제가 여전히 존재한다.

페이징 (Paging)

논리적 메모리 주소 공간이 물리적인 메모리 공간에서 비연속적으로 배치하게끔 허용하는 기법을 의미한다.

물리메모리를 고정된 사이즈의 프레임(Frame) 이라는 크기로 나누고, 동일한 사이즈로 논리메모리를 페이지(Page) 로 나눈다.

즉 , 프로세스가 일정량의 페이지를 요구하면, 같은 양의 충분한 프레임을 찾아서 매치시켜준다. 그렇기 때문에 허용가능한 프레임을 추적해야한다.

또 페이지와 매치되는 프레임을 찾기 위해 페이지 테이블을 관리해야 한다.

하지만 외부 파편화 문제는 해결할 수 있지만(비연속적으로 배치하니) 내부 파편화 문제는 여전히 존재한다.

위의 그림처럼 프로세스의 메모리주소를 같은 크기의 페이지로 나누고 물리 메모리의 프레임과 대응시킨다.

이 대응이라는 것은 논리주소를 단순히 구성할 순 없고, 일반적으로 2^m바이트의 논리 메모리 사이즈와 페이지 사이즈가 2^n바이트일때, 아래와 같이 m 비트를 (m-n)비트,n비트로 구성한다.

페이지 오프셋은 2^n바이트의 페이지 중에서 현재 몇번째 바이트를 지시하는지 알려주고, m-n비트의 페이지 넘버는 페이지 테이블 내에서 몇번째 프레임을 가리키는데 사용된다.

이러한 페이징 방식에서 논리주소 변환은 위의 구조를 가진다.
잘보면 offset인 d는 주소 변환에는 안쓰이고 바로 물리주소에 대응시켜버린다.
반대로 p인 페이지 넘버는 page table내부에서 frame number와 매치시키기 위해서 사용되는데 p→f 의 역할을 하드웨어의 지원을 받아서 수행된다.

페이지 테이블

페이지 번호와 프레임 넘버를 매치시켜주는 구조를 페이지 테이블(Page Table)이라고 하는데 , 메모리 안에 저장된다.

그렇기때문에 실제로 어떠한 메모리에 접근할때는 두 번의 메모리 접근이 필요하다.

1. 메모리에 있는 페이지 테이블 접근
2. 변환된 물리적 주소에 가서 메모리 접근

이 메모리 접근은 꽤 비용이 큰 작업이기 때문에 TLB라는 새로운 하드웨어 캐시가 쓰인다.

TLB

TLB는 Associative Memory라고도 불리는 하드웨어 캐시인데, 논리주소를 물리주소로 변환할때 메모리접근을 줄이기 위해서 사용된다.

페이지테이블과 유사하게 페이지 번호와 프레임 번호가 대응되게 기록되어 있다.
다만, 모든 페이지 번호가 TLB 안에 있는 것은 아니다.

물론 이 레코드들을 다 순차적으로 읽는것은 아니고, 하드웨어의 지원을 받아 병렬적으로 읽기 때문에 매우 빠르다.

이에 관해서 좋은 답변이 있어서 공유한다. How does a TLB lookup compare all keys simultaneously?

요악하자면 단일 CPU 안에서라도 파이프라이닝 기법을 이용해서 병렬적으로 읽는다는 것. (컴퓨터구조 수업을 참고하자.)

TLB가 도입되면서 (p,d)의 논리주소를 물리적 주소로 변환하는 방법이 변했다.

1. TLB를 먼저 확인해서 p에 해당하는 프레임 번호가 있는지 찾는다.
   1. 있다면, 프레임 넘버 f와 오프셋 d를 가지고 바로 메모리에 접근한다.
   2. 없다면 2번으로 간다.
2. 메모리에 있는 페이지 테이블을 확인한다.
3. 페이지 테이블에 적힌 프레임 넘버 f와 오프셋 d를 가지고 메모리에 접근한다.
4. 가장 최근에 사용된 (p,d)→(f,d) 를 TLB에 저장한다.

1,4번 때문에 TLB는 논리적→물리적 주소 변환에서 캐시 역할을 수행한다고 볼 수 있다.

💡 다만 일반적인 CPU 캐시(L1,L2...)와는 목적 자체가 다르다. TLB는 주소 변환 속도 향상을 위한것이어서 MMU에 의한 주소변환시에 생기고 , CPU 캐시는 데이터를 가져올때 메인 메모리 접근을 줄이기 위하여 메인 메모리 접근시점에 참조된다.
물론 둘 다 메인 메모리 접근을 줄이기 위함이라는 점은 비슷하다.

A cache stores a memory location temporarily while a TLB is like a cache that stores address translation (virtual to physical address)

단 이 TLB도 컨텍스트 스위칭이 일어날때 비워진다.

그 이유는 새로운 프로세스가 CPU를 할당받게 되면, 다른 메모리 주소공간을 참조할것이기 때문이다.
이때문에 컨텍스트 스위칭 직후 TLB 미스가 연속적으로 생긴다.

페이지 사이즈

페이지의 크기에 대해서도 얘기해보자.
페이지의 크기를 정하면, 페이지 테이블의 크기도 결정되므로 적절한 페이지 크기 선정이 중요하다.

여기서 말하는 적절한의 기준이 뭘까?

만약 모든 프로세스가 4K만 요구하는데 페이지 사이즈가 8K면?

모든 페이지에 4K만큼의 내부 파편화가 생기는 것이다.

• 만약 페이지 사이즈가 크다면?

  • 페이지 테이블의 크기는 줄어든다.
  • 한 개의 페이지 테이블안에 들어있는 데이터가 많으니 공간 지역성을 잘 만족한다.
  • 한 번에 많은 양의 데이터를 디스크에서 가져오니 I/O 작업이 줄어든다.
  • 내부 파편화 문제가 증가한다.
  • 필요하지 않은 데이터가 메모리에 올라올 수 있다.

• 만약 페이지 사이즈를 작다면?

  • 내부 파편화 문제가 감소한다.
  • 필요한 데이터만 메모리에 가져올 수 있다.
  • 공간 지역성을 지키기 어려워 페이지 폴트 발생 확률이 늘어난다.
  • 페이지 테이블 내의 엔트리가 많아지니 페이지 테이블의 크기가 커진다. 오버헤드가 발생한다.

따라서 여러가지 트레이드 오프를 고려해서 페이지의 크기를 정하는 것이 중요한데,
일반적으로 메모리 크기도 커지고, 프로세스 크기도 커져서 페이지 사이즈의 크기도 커지고 있다.

리눅스 16.04 기준 아래와 같은 명령어로 페이지 사이즈를 알 수 있는데 4096으로 4K다.

$ getconf PAGESIZE
> 4096

일단 프로세스 스케쥴링 알고리즘에 대해서 언급하기 전에, 프로세스의 상태와 Context-Switching에 대해서 알아야 한다.

여러가지 프로세스의 상태를 기반으로 전이(Transition)되며 이를 바탕으로 스케쥴링 알고리즘이 이루어진다.

프로세스의 상태

프로세스의 상태는 OS에 따라서 개수도 다르고, 명칭도 조금 다르지만, 가장 대표적인 그림은 위의 상태와 같다.

• new : 프로세스가 생성된 상태이다. 이때는 Readuy Queue 안에 들어 있지 않기 때문에 CPU를 받을 대상이 아니다.
• ready : 프로세스가 CPU를 할당받기 위해 대기하는 상태이다. 보통 Ready Queue 안에 들어와있는 상태라고 얘기한다. 스케쥴링의 대상이 된다.
• running : 현재 CPU를 할당받아 작업중인 상태다. Single core 시스템에서는 1개다.
• wating : 프로세스가 입출력이나 이벤트가 끝나기를 기다리는 상태이다.
• terminated : 프로세스가 종료된 상태다. 단 프로세스 구조체가 사라진 것은 아니다.

그림에서 프로세스의 상태가 특정 작업들로 인하여 변하는 것을 볼 수 있는데 이것을 프로세스의 상태 전이(Transition) 라고 한다.

• admitted : 생성된 프로세스가 CPU를 받을 준비가 되어서 Long-term Scheduler(Job Scheduler) 에 의해서 선택받아 Reaudy queue로 옮겨지는 작업이다.
  • Long Term Scheduer : 어떠한 프로세스를 레디큐로 옮길지 선택하는 스케쥴러다. 자주 일어나지 않고, 멀티프로그래밍의 정도(DOM) 가 이것에 영향을 받는다.
    • 일반적으로 많은 프로세스가 한꺼번에 메모리에 올라오면, 일부는 디스크에 저장된다.
    • 존재하는 이유는 기존의 프로세스들이 자원을 확보하기 위해서 존재한다. 무턱대고 다 RQ로 올리면 기존의 프로세스는 작업이 진행되지 않는다.
• scheduler dispatch : ready 상태에 있는 프로세스를 Short term Scheduler가 선택해서 자원을 할당한 후 실행시키는 행위다.
  • Short Term Scheduler : RQ에 있는 프로세스 중에서 어떠한 것이 다음으로 실행될지, CPU를 할당할지 선택하는 스케쥴러다.
    • 빈번하게 발생한다. 그렇기에 이 스케쥴러의 오버헤드를를 줄여야 전체 오버헤드를 줄일 수 있다.
    • 스케쥴링 알고리즘과 아주 깊은 연관이 있다.
• interrupt : 인터럽트는 조금 논란이 있는데, 저 그림상에서는 입출력 이벤트는 포함하지 않는다. Context-switching이 일어난다.
  • 선점식(preemptive) 방식에서는 타이머(Timer) 이벤트가 있다. 인터럽트 핸들러가 인터럽트를 일으켜서 STS에게 다른 프로세스를 선택할지, 지금 프로세스를 그대로 둘지 결정하게끔 한다. 만약 바뀐다면 전이가 일어난다.
  • 비선점식(non-preemptive 혹은 cooperative) 방식에서는 양보(Yield)가 있다. 이 방식에서는 OS가 프로세스를 스케쥴링할때 인터럽트를 사용,허용하지 않는다. 대신에 작동중인 프로세스가 자발적으로 양보를 해서 스케쥴러가 다른 프로세스를 스케쥴링할 수 있는 방식을 쓴다.
• I/O or event wait : 실행 중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우, 입출력/이벤트가 끝날때까지 대기 상태로 만드는 것. Context-switching이 일어난다.
  • 여기서 왜 ready로 안보내는지가 중요하다. 왜냐면, 이 프로세스는 ready로 가서 자원을 할당받을 자격이 없다. 이벤트나 입출력이 끝나지 않았으니 자원을 받아도 사용하지 못하기 때문이다.
• I/O or event completion : 입출력/이벤트가 끝난 프로세스를 ready 상태로 만들어 STS에게 선택될수 있게끔 한다. wait 과는 다르게 자원을 할당받기만 하면 작업을 이어나갈 수 있기 때문이다.

Context-switching?

정확한 정의는 "CPU가 다른 프로세스로 스위치할때, 시스템(OS)이 기존의 프로세스의 상태를 저장하고, 다음 진행될 프로세스의 저장된 상태값을 불러오는것"이다.

• 이 때 중요한것이 PCB 등인데, PCB 안에는 CPU 레지스터에 대한 정보, PC,페이지 테이블과 관련된 정보가 있다. 그렇기에 PCB는 프로세스의 문맥을 보관하고 있는 것이다.
• 다시 작업을 수행할때 이것을 참조해서 어디부터 다시 시작할지 참고 할 수 있다. 그렇기에 새로운 프로세스로 선택될때도 PCB를 불러와야하고, ready 상태나 waiting 상태로 프로세스가 전이될때도 PCB를 저장해야한다.

일반적으로 context switch하는 시간은 순전한 오버헤드다. 대부분의 시스템은 이 전환 시간동안 어떤 의미있는 작업을 하지 않는다.

또 가장 중요한 부분이 context-swtichg을 하면서 Cache flushing이 일어난다. 그렇기에 그 다음에는 연속적인 캐시 미스(successive cache misses)가 발생한다. 이 과정이 대부분의 오버헤드를 차지한다.

💡 캐시를 날리는 이유는 새로운 프로세스는 새로운 virtual adrress를 가지는 새로운 메모리 주소다. 그렇기 때문에 기존의 캐시된 메모리의 주소 영역을 사용할 필요가 없기에 기존의 캐시된 메모리를 Flush 하는 것.

참고로 스레드도 컨텍스트스위칭을 한다. 그치만 쓰레드들끼리는 주소공간을 공유하기 때문에 캐시를 flush할 필요가 없다.

Process context switching vs Thread context switching

프로세스만 context switching을 하는 것이 아닌 쓰레드끼리도 context switching을 한다. 다만 아래와 같은 차이점이 있다.

• 프로세스간 context switching
  • 커널 단에서 스위칭이 일어난다.
  • 메모리 주소 공간의 전환이 일어난다.
  • 프로세서의 캐시와 TLB 모두 Flush 된다. → 연속적인 캐시 미스와 TLB 미스가 일어난다.
  • 메모리 주소공간이 전환되고, 캐시미스가 필연적으로 동반되므로 훨씬 비용이 비싸다.
• 쓰레드간 context switching
  • 커널 단에서 스위칭이 마찬가지로 일어난다.
  • 같은 프로세스 내에서 일어나는 스위칭이기에 메모리 주소공간을 그대로 사용한다.
  • 프로세서의 캐시와 TLB 정보가 유지된다.
  • 레지스터의 값과 스택 포인터 전환 정도만 일어나니 훨씬 저렴하다.

CPU 스케쥴링 알고리즘이란?

스케쥴링 알고리즘은 레디 큐에 있는 프로세스들을 대상으로 다음으로 실행할(CPU를 할당받을) 프로세스를 고르는 작업이다.

일단 프로세스의 상태를 다이어그램으로 먼저 보자.

레디큐 뿐만 아니라, 새로 만들어지는 큐를 담는 큐도 있고, block(I/O wait) 큐도 있다. 일반적으로 CPU 스케쥴링 알고리즘은 Short-term scheduling을 얘기한다.

스케쥴링 알고리즘을 얘기하기 전에 멀티 프로그래밍(Multi Programming) 과 시분할(Time sharing) (혹은 멀티 태스킹(Multi Tasking)) 에 대해서 먼저 얘기를 해야한다.

• 멀티 프로그래밍
  • 작업들을 적절히 구성해 항상 CPU가 프로세스를 실행하도록 한다.
  • 어떤 프로세스가 CPU를 할당받아 사용하다 I/O 작업등 CPU를 필요로 하지 않는 순간이 오면,
    다른 프로세스로 교체해서 그 프로세스가 CPU를 계속 사용할 수 있도록 한다.
  • 이것의 목적은 CPU 사용률(CPU Utilization)을 최대화함에 있다.
• 시분할(멀티 태스킹)
  • CPU가 일할때 매우 빈번하게 수행중인 작업을 교체해서 사용자가 상호작용할 수 있는것이다.
  • 반응하는데 걸리는 시간(Response time)이 충분히 작아야 프로그램들이 동시에 진행하는것처럼 보인다.

스케쥴링의 발생과 목적

CPU 스케쥴링은 아래와 같은 상황에서 일어난다.

• running 에서 waiting 으로 갈 때 (I/O Request)
• running 에서 ready 로 갈 때 (timeout), Preemptive
• waiting 에서 ready 로 갈 때 (I/O Finish, 이때 스케쥴링 해주는 이유는, I/O가 끝난 이후에 핸들링을 해줘야 하기 때문이다. 기존의 running 프로세스는 고려하지 않음),Preemptive
• running 에서 terminated 로 갈 때 (프로세스의 종료)

만약 스케쥴링이 1번과 4번에서만 일어난다면 , non-preempitve지만, 그렇지 않다면 preemptive 스케쥴링이다.

스케쥴링 알고리즘에 대한 기준은 몇가지가 있다

• CPU 이용률 : CPU를 가능한 바쁘게 해야 한다. 높을 수록 좋음
• Throughput : 단위시간당 프로세스 처리 수,batch 시스템에선 중요함, 높을 수록 좋음
• Turnaround time : 특정 프로세스가 도착시간에서부터 끝날때까지 걸린 시간, 낮을 수록 좋음
• Waiting time : 레디큐에서 기다린 시간의 합 , 범용적으로 중요하고, 낮을 수록 좋음
• Response time : 요청이 들어왔을때 첫번째 응답까지 걸리는 시간,일반적인 PC에서 중요하다. Throughput과는 반대의 관계이며 낮을수록 좋다.

스케쥴링 알고리즘

• FCFS (First-Come, First-Served)

  • 비선점
  • 먼저 CPU를 요청한 프로세스에게 먼저 CPU가 할당된다. 공평하다.
  • 큐를 이용하면 쉽게 구현이 가능하다
  • 도착순서를 바꿈으로써 전체 waiting time이 바뀐다. CPU bound job을 뒤로 하면 확 줄어든다
  • Convoy Effect : 시간이 짧게 걸리는 프로세스가 시간이 오래 걸리는 프로세스 뒤에 있으면 CPU 전체 사용률이 줄어든다.

• SJF (Shortest Job First)

  • 기본적으로 비선점 방식
  • CPU burst time이 가장 작은 프로세스를 먼저 CPU 할당시킨다.
  • 선점방식으로 구현하는것을 SRTF(Shortest Remaining Time First) 방법은, 현재 프로세스의 남은 시간보다 더 짧은 프로세스가 새로 들어오면, 선점해버리는 방식이다.
    • 컨텍스트 스위칭에 드는 오버헤드를 고려하지 않을시에는 SJF보다 성능이 좋다.
    • 만약 선점방식이라면, CPU burst time이 긴 프로세스는 계속 실행되지 못하는 기아(starvation) 현상이 발생 할 수 있다.
  • 하지만 현실적으로 SJF는 구현하기 어려운데, CPU의 남은 시간을 예측불가하기 때문이다. 그래서 평균 waiting time이 최소인 Optimal한 알고리즘이다.
  • 그나마 유사하게 접근 하는 방식은 이전 CPU burst time을 기반으로 예측하는 것이다.

• Priority Scheduling

  • 각 프로세스에게 우선순위 지시자가 연결되어 있다.
  • 가장 높은 우선순위(일반적으로 가장 낮은 숫자)를 가진 프로세스에게 CPU가 할당된다
  • SJF도 CPU burst time이라는 우선순위를 가지는 우선순위 스케쥴링 방식이다.
  • 선점과 비선점 방식 모두 구현이 가능하다.
    • 선점 : 새로 도착한 프로세스의 우선순위가 기존의 것보다 높으면 CPU 교체 (SRTF)
    • 비선점 : 신경쓰지 않고 새로운 프로세스를 그저 레디큐 맨 앞에 배치
  • 우선순위가 낮은 프로세스는 계속 실행되지 못하는 기아(starvation) 현상이 발생하는데, 시간이 지날때마다 프로세스의 우선순위를 올려주는 에이징(Aging) 방식으로 해결 가능

• RR(Round-Robin) Scheduling

  • 각각의 프로세스는 Time quantum이라 불리는 짧은 시간을 부여받음.
  • 이 시간이 끝나면, 프로세스는 다른 프로세스로 무조건 교체되고(선점) 레디큐의 마지막으로 돌아간다.(FCFS의 측면)
  • q초의 quantum을 가지는 n개의 프로세스가 있으면, q초마다 한번씩은 1/n의 CPU 타임을 보장받는다.
    → 최대 (n-1)*q 초까지만 기다리면 무조건 보장받는다. 이를 통해서 waiting time의 upper bound를 보장받게 된다.
  • q의 사이즈를 적절히 고르는 것이 중요하다.
    • q가 너무 크면 → FCFS랑 다를게 없다.
    • q가 너무 작으면 → 잦은 컨텍스트 스위칭, 그로 인한 오버헤드가 커지기 때문에 throughput이 감소한다.

• Multi-Level Queue

  • 레디큐를 두개 이상으로 구분해 I/O bound job과 CPU bound job으로 구분한다. 그 이유는 I/O bound job은 interaction이 많아서 response를 빨리 얻어야 하기 때문이다. (우선순위를 높여야겠지?)
  • 크게 두 분류로 나누는데 foreground와 background로 나눈다.
    • foreground : interactive하고 , I/O job 위주이며, RR 알고리즘으로 동작하여 response time을 높이는데 주력으로 둔다.
    • background : batch job(CPU bound job)위주이며, FCFS로 동작하며 throughput을 높이는데 집중한다.
  • 각 큐들은 독립적인 스케쥴링을 가지고 있고, foreground가 다 수행되어야 background를 선택한다.
    • 그렇기 때문에 background job들은 기아현상이 발생할 수 있다. (계속 foreground로 들어오면)

• MLFQ

  • 프로세스들은 큐들 사이에서 서로 이동이 가능하다.

    

  • 새로운 프로세스는 q=8인 큐로 진입하고, 큐 내부적으로는 FCFS의 행동을 취한다. Q1과 Q2의 작업이 있으면 선점한다.

  • CPU를 얻으면 8ms동안 수행되고, 그 안에 끝나지 않으면 Q1으로 강등당한다.

  • Q2에서 16ms동안 수행되고, 그 안에 끝나지 않으면, Q2로 강등당한다. 이런 방식을 취함으로써 Convoy Effect를 방지할 수 있다. (CPU bound job은 우선순위가 낮으니)

  • 단, yield와 같이 I/O 작업으로 인해 q가 소진되기전에 CPU를 포기하면 강등당하지 않고 우선순위를 그대로 유지한다.

  • MLFQ는 burst time이 짧은 대화형 작업들을 빨리 처리하려고 해 response time에서 강점을 보이지만 , CPU bound job들은 기아 현상을 겪을수 있다.

    • 주기적으로 모든 작업의 우선순위를 상향조정 할 수 있다. 예를 들어 모두를 Q0로 올려보낸다. 이 과정에서 CPU bound job들도 조금이나마 작업을 진행할 수 있다.

  • 의도적인 I/O 작업 호출로 우선순위를 유지하는 프로세스가 있을 수 있다. 이 프로세스는 예를 들어 7ms가 지난 후 의미 없는 I/O 작업으로 우선순위를 유지한다.

    • 누적적인 CPU 사용 시간을 기록해서 방지한다. PCB 안에 기록하지 않을까..?

선점식 vs 비선점식

• 선점식은 프로세스에게 한번 실행될때 제한된 시간만큼 CPU를 할당한다. 작업 도중에 자원을 반납당하고 ready 상태로 진입한다. 비선점식은 프로세스가 종료되거나, yield를 통해서나 I/O를 위해서 자발적으로 ready에 가지 않는 한 자원을 반납하지 않는다.
• 선점식만 실행 중에 인터럽트를 허용한다.
• 선점식은 프로세스의 우선순위에 따라 스케쥴링을 하는데, 우선순위가 낮은 프로세스가 선택받지 못하는 기아(starvation)현상이 일어날 수 있다. 비선점식은 수행시간이 긴 프로세스(CPU-bound job)이 스케쥴링되면, 그 뒤의 작업들이 오랜 기간동안 선택받지 못한다.
• 선점식은 context-swtiching이 자주 일어나 이로 인한 오버헤드가 크고, 비선점식은 필수적인 context-switching을 제외하면 자주 일어나지 않아 오버헤드가 비교적 적다.
• 선점식은 우선순위에 따른 유연성을 가지지만(예를 들어 우선순위 promotion을 진행하는 MLFQ) 비선점식은 그렇지 않다.

이러한 특징때문에 interactive한 시스템에선 반응성 때문에 선점식을, batch job을 자주 수행하는 시스템에선 비선점식을 사용하곤 한다.

프로세스란, 실행중인 프로그램을 의미한다.
프로그램을 실행하기 위해서는 주소공간,파일,메모리 등이 필요한데 운영체제로부터 이런 것을 할당받은 프로그램을 프로세스라 한다.

프로그램은 어떤 작업을 수행하기 위한 파일로써 정적인 상태이고, 프로세스는 그 작업을 수행하는 동적인 상태다.

프로세스의 메모리 구조

프로세스는 아래 그림과 같은 메모리 구조를 띄고 있다.

프로세스의 메모리 영역은 코드,데이터,힙,스택 영역으로 구성된다.

• 코드 : 사용자가 작성한 프로그램 함수들의 코드가 기계어 명령 형태로 변경되어 저장되는 공간
• 데이터 : 전역 변수 또는 static 변수 등 프로그램이 사용하는 데이터를 저장하는 공간
• 스택 : 함수의 복귀주소와 지역변수,매개변수,반환값을 저장하는 공간. 재귀함수가 반복되거나 지역변수가 너무 많으면 stack overflow 발생. 가변적이다.
• 힙 : 프로세스 실행 중에 런타임에 할당되는 영역. 이곳에 메모리를 할당하는 것을 동적 할당이라고 한다. 가변적이다.
  

  

  
  이처럼 프로세스는 각자의 메모리 영역을 가지기에 프로세스간의 메모리는 서로 침범 할 수 없다.

프로세스 제어 블록 (Process Control Block, PCB)

PCB(Process Control Block)는 특정 프로세스에 대한 중요한 정보를 저장하고 있는 운영체제의 자료구조이다. 그렇기에 PCB는 일반적으로 보호된 메모리 영역,예를 들면 커널 스택등에 위치한다.

OS는 프로세스를 관리하기 위해 프로세스를 생성함과 동시에 고유한 PCB를 생성한다.

프로세스는 CPU를 할당받아 작업하다가도 context-switching이 일어나면, 진행하던 작업을 저장하고 CPU를 반환해야하는데, 이때의 작업 진행상황이 PCB에 저장된다.
그 후 다시 CPU를 할당받게 되면 PCB 안에 있던 정보들을 불러와서 작업이 멈추었던 시점에서부터 다시 시작한다.

• 프로세스 식별자 : PID
• 프로세스 상태 : new,ready,running,waiting,terminated

• 프로그램 카운터,PC : 프로세스가 다음에 실행할 명령어 주소
• CPU 레지스터
• CPU 스케쥴링 정보 : 우선순위, 스케쥴 큐에 대한 포인터 ← 이것을 바탕으로 MLFQ나 RR이 동작한다.
• 메모리 관리 정보 : 페이지 테이블 또는 세그먼트 테이블에 대한 정보 포함
• 입출력 상태 정보 : 프로세스에 할당된 입출력 장치들과 열린 파일 목록
• 어카운팅 정보 : 사용된 CPU 시간, 시간제한, 계정번호

이 PCB들은 커널 스택과 같은 보호된 메모리 영역 내에서 Linked List 형태로 관리된다. PCB List Head에 PCB들이 생성될때 붙는 방식으로 관리가 된다.

스레드(Thread)

스레드는 프로세스가 할당받은 자원을 이용하는 실행 단위다.

한 프로세스 내에서 동작되는 여러 실행 흐름으로 프로세스 내의 주소 공간이나 자원을 공유할 수 있다.

스레드는 스레드 ID,PC,레지스터 집합, 그리고 각자의 스택으로 구성된다(독립적인 메모리는 아니고, 스택 포인터로 표시한다).

이를 통해 멀티 쓰레딩을 달성할 수 있는데 멀티쓰레딩은 하나의 프로세스를 여러개의 실행단위(스레드)로 나누어서 자원을 공유하며 자원의 생성과 관리의 중복을 줄여 수행능력을 높이는 것이다.

• 공유
  • 같은 프로세스에 속하는 스레드들은 힙,데이터,코드 영역을 공유한다. 추가적으로 open된 파일등도 공유한다.
• 공유하지 않는 것
  • 각자의 스택과 레지스터(PC 포함)은 공유하지 않는다.

이렇게 하나의 프로세스 내에서 다수의 실행 단위인 스레드로 구분하여 공유할 자원은 공유하고, 독립적인것은 따로 두어 수행 능력을 향상시키는 것을 멀티스레딩이라 한다.

스레드에서의 메모리 구조

스레드 역시 프로세스와 단짝인 개념인데, 짧게 말하면 프로세스가 할당받은 자원을 이용하는 실행의 단위 이다. 위의 그림처럼, 여러개의 스레드는 각자의 레지스터와 스택을 가지지만, 나머지 영역은 가지지 않는다. 대신에 코드,힙,데이터 영역을 공유해서 병렬적인 수행이 가능하다.

• TMI : 왜 스레드는 각자의 스택을 가지고 있을까?

  스레드가 하나의 실행의 context라는 것을 생각하면 자명하다. 그 context내에서 아주 간단하게 여러개의 지역변수,파라미터,반환값,복귀주소등을 가지는데, 그 스레드들이 만약 서로의 스택을 공유하게 된다면, 그 context가 서로 섞이게 된다. 사실 각자의 스택을 가지기 때문에 스레드가 종종 Lightweight Process라고 불리는 이유다. 그리고 각자의 스택을 가지고 있다고 얘기하지만 사실은 하나의 메모리공간을 stack pointer를 이용해서 분리하는 것이다.

• TMI2 : 그럼 스레드는 왜 각자의 PC와 register도 있을까?

  위의 답과 비슷한 이유인데, PC(Program Counter)나 레지스터의 역할은 현재 명령어가 어디까지 수행되었는지,수행될때 쓰던 데이터는 무엇이었는지 알려주는 것이다. 스레드는 CPU를 할당받을때 프로세스처럼 스케쥴러에 의해 결정되는데, 그렇기에 명령어가 연속적으로 실행됨을 보장하지 못하기에 어디까지 실행되었는지 기록할 필요가 있는데 그래서 스레드가 각자의 PC를 가지는 것이다.

스레드의 장점과 단점

• 장점
  • 반응성
    • 특정 스레드가 I/O 작업을 처리중이거나(blocked) 긴 작업을 수행중이여도 다른 스레드는 본인의 일을 계속 할 수 있다.
  • 자원 공유
    • 프로세스는 shared memory나 message passing과 같은 기법을 이용해서 자원을 공유할 수 있지만, 스레드끼리는 프로세스의 자원을 서로 공유한다.
  • 경제적
    • 프로세스의 자원을 공유하기 때문에 새로운 메모리 주소공간을 할당받을 필요가 없어 생성에 자원이 적게 들어간다.
    • 스레드 간에 컨텍스트 스위칭을 할 때 캐시 메모리 안비워도 된다. 어차피 같은 메모리 주소공간을 사용하니까 오버헤드가 적다.
    • 근데 이것도 극복하려고 thread pool이라는 기술도 있다.
  • 확장가능성
• 단점
  • 공유자원을 사용하기 때문에 동기화 문제를 고려해야 한다.
    • lock을 함으로써 공유자원에 대한 동기화를 해결할 수 있는데 이게 병목현상이 될 수 있다.
    • 그러므로 적절한 부분만 lock을 하는 것이 필요하다. → Critical Section Only

멀티 프로세싱 vs 멀티 스레드

• 멀티 프로세싱
  • 두 개 이상의 다수의 프로세스가 협력적으로 하나의 작업을 동시에 병렬적으로 처리하는 것
  • 프로세스간 메모리 공유는안되기 때문에, IPC를 이용해 소통
  • 하나의 프로세스에서 문제가 생겨도 다른 프로세스는 계속 진행할 수 있음.
  • 컨텍스트 스위칭 비용이 높음
• 멀티 스레딩
  • 단일 프로세스 내에서 여러 쓰레드로 나누어 동시에 실행
  • 컨텍스트 스위칭 비용이 거의 없음
  • 스택을 제외한 데이터,코드,힙 영역을 공유하기 때문에 공유하는데 편리함
  • 임계영역의 문제가 있음