1. Kernel Thread
우선 저번시간에 했던 내용을 간략히 집고 넘어가고자 한다. 이제는 쓰레드와 프로세스를 구분할수 있다. 일반적인 프로세스는 부모의 모든 리소스를 그대로 가져오는 놈이라면, 쓰레드는 요령있게 최소한으로 복사해오는 놈이다.
그리고 커널은 memory resident program이라고 표현할수 있다. 부팅이 되고나서 꺼지기 전 까지 항상 메모리에 올라와있으며, 커널 역시 프로그램으로 main문부터 시작하는 우리가 익히 알고있는 프로그램이다.
그렇다면 커널 쓰레드란 무엇일까?. 아래 그림을 봐보자.
커널 쓰레드는 커널 프로그램 Light Weight로 생성한 프로그램 즉, 쓰레드를 뜻한다. 커널 프로그램이 부팅시 메모리에 올라온뒤, main문 부터 쭉 실행이 된다. 그러다가 커널 내부에서도 역시 시스템 콜을 호출하는 경우가 발생하는데, fork나 clone을 불러서 child를 만들게 된다. 이렇게 생성되는게 바로 커널 쓰레드이다.
대부분의 저렇게 생성된 커널 쓰레드는 서버 혹은 데몬 프로그램이다.
정리를 하면 커널 쓰레드란, 커널 프로세스가 Light weight한 오버헤드로 child를 만든것이라고 볼수 있다. 이런 커널 쓰레드는 커널 프로세스가 clone() 과 같은 시스템 콜 호출시 생성이 되며, 생성된 커널 쓰레드는 현 커널 프로세스의 메모리 공간에 접근할수 있다.
또한 커널 코드도 실행시킬수 있으며 커널 영역에서만 존재하게 된다. 그리고 데몬 프로그램들이 이러한 커널 쓰레드에 속한다.
위 그림을 봐보자. 현재 4개의 CPU중 0번 CPU의 PC가 커널 프로세스를 가리키고 있다. 이 상태에서 clone 시스템 콜 호출을 통해 2개의 child를 만들었다고 가정해보자. 이렇게 되면 2개의 쓰레드가 생성된다.
현재 CPU2에 쓰레드1이 할당되어 커널 내부의 print 서버데몬을 돌리게되고, CPU3에 쓰레드2가 할당되어 PageFault()라는 서버데몬을 돌리게된다. 이때의 쓰레드 1,2는 커널 프로세스의 모든 PCB정보를 가져오는게 아닌, Task basic info만 복사해오고, 나머지 것들은 커널 프로세스것들을 공유하게 된다.
Task basic info안에 CPU state vector 즉, PC, SP 등의 정보들이 있고 이런것들만 가져오기 때문에 각각의 쓰레드에는 자기들만의 PC, SP 등의 정보들이 생기게 된다. 이 말은 커널 프로세스든 쓰레드든, 각자의 커널 스택을 갖고있다는 소리이고 그렇기 때문에 쓰레드들은 각자 서로 다른 함수의 호출이 가능하다.
2. Process State
이번에는 프로세스의 상태에 대해서 알아보자. 기본적으로 프로세스는 run, ready, wait 3가지의 상태로 존재한다.
•
Running
프로세스가 실행중이란 소리이다. 만약 실행되다가 disk에서 read or write를 해야하면 I/O를 요청하게 된다. I/O 처리를 해주는 도중 CPU는 놀게 되므로 해당 프로세스의 CPU를 뺏어린다. 그러면 I/O가 다 될때까지 Wait 상태가 된다. (=sleep =block)
•
Waiting
waiting 도중 시그널이 오는 경우가 있다. 일반적으로 우리가 많이 사용하는 ctrl+c 같은거로 생각을 해보자. 이러한 시그널이 발생하면 반응을 할것이냐 안할것이냐로 wait 상태는 나뉘게 된다.
•
Ready
wait 상태에 있다가 I/O가 끝났다고 해서 그 즉시 CPU를 받는건 아니다. 왜냐? CPU는 항상 임자가 있다. 나만 바라보고 있는게 아니다. I/O처리가 끝났어도 다른 우선순위가 높은 놈에게 갈수도 있다. 따라서 wait가 끝나면 Ready 상태로 가게된다. Ready 상태에 있다가 자기 차례가 됬을때 Distpatch가 되면서 다시 running 상태로 돌아간다.
ready 상태에서 cpu info를 load하고 program counter로 가라 ! 하면서 실행이 되는데 이를 dispatch되었다 라고 한다.
추가적으로 running 상태가 되었다고 해도, 무한정으로 CPU를 점유하는 건 아니다. 프로세스는 특정 시간동안만 해당 CPU를 할당받게 되고, 할당받은 시간이 끝나면 다시 ready 큐의 맨 뒤로 돌아간다. 이는 선점, 비선점 스케줄링 기법에 따른 차이로 생각된다. (wait로 가냐, ready로 가냐 그 차이인듯).
그리고 running중 exit() 시스템 콜이 호출되면 좀비 상태로 된다. 프로세스가 좀비로 되면, 모든게 다 날라가고 PCB만 남게 된다. child로 생성된 프로세스가 exit가 되면, 해당 child를 생성한 부모가 zombie 상태로 된 child 프로세스의 PCB 정보를 보고, 자기 자식 말소를 실제 시작한다. 부모가 말소를 다 끝내기 직전까지는 좀비 상태로 유지된다.
여기까지가 process management에 대한 설명이였고 이제 이러한 프로세스들이 어떻게 스케줄링 되면서 CPU를 양도받는지에 대한 자세한 과정을 살펴보자.
Kernel of Linux Scheduling
어떤 프로세스가 다음에 실행될까?. 일반적으로 우선순위가 가장 높은 놈이 실행되는건 맞지만 하나더 생각해야하는게 있다. 바로 remaining timeslice를 가지고 있느냐이다.
remaining timeslice 이 뭘까?
예를 들어 특정 Task에게 CPU를 줄때는 무제한으로 써라! 가 아니라 100ms 정도 시간만 사용해라! 라고 하면서 CPU를 준다. 한 20ms 정도의 시간동안 쓰다가 아직 시간이 남았는데 아주 흉악한 놈이 자기가 엄청 급하다며 CPU를 뺏어갔다. 그러면 현재 Task에는 80ms의 가용시간이 남았있다.
이 남은 시간을 바로 remaining timeslice라고 한다. 즉 CPU를 차지하려면 우선순위도 높아야하고, remaining timeslice도 0이 아니여야 한다. 이점을 기억하면서 스케줄링을 살펴보자.
2.1 Scheduling Algorithm
맨위를 보면 Ready 큐가 있고, 해당 레디큐에 PCB가 이어져있다. 이는 실행할수 있는 Task list이다. 만약 멀티프로세싱 시스템이 되서 CPU가 매우 많아지게 되면, 레디큐에 수많은 PCB가 연결되어 너무 길어질 것이다.
따라서 이러한 비효율성을 없애기 위해 단순히 레디큐가 아닌, Hi-priority 큐, Low-priority 큐 이렇게 구분짓게 되었다. 전보다는 훨씬 퍼포먼스가 줄어들게 되고, 만약 우선순위를 더 구분지어 여러개의 큐를 만들게 되면 더 효율적이게 된다.
여기서 더 높은 효율을 내려면, 우선순위 큐들 앞에 실제 우선순위 큐의 헤더들이 비여있는지 없는지를 판단하는 지표의 역할을 수행시키는 기능을 추가할수 있다.
방금 말한게 바로 위 사진이다. 제일 앞쪽에 binary 배열을 하나 두고 해당 배열에는 우선순위 큐의 head pointer를 가리키게 한다. binary 배열의 값이 0이면 현재 heap 포인터에 아무것도 안들어 있다는 의미이고, 1이면 현재 리스트에 Task들이 존재한다는 소리이다.
만약 우선순위를 132개로 구분지었다면, binary[2]을 보고 이게 1이면 아 우선순위 2를 가진 task가 존재하구나. 라고 바로 알수 있다. 이러한 binary 배열을 바로 bitmap이라고 부르고, heap pointer들을 바로 queue라고 한다.
따라서 만약 멀티프로세스로 cpu가 10개다 라고 하면 10개의 cpu 전부다 위 그림 하단에 있는 구조체(prio_array)를 다 가지고 있다. 구조체안에는 bitmap과 queue가 존재한다.
CPU 스케줄러가 스케줄링을 수행하는 순서는 크게 다음과 같다.
1.
우선 bitmap을 차례대로 스캔한다. bitmap에 현재 1로 세팅된 인덱스가 있으면
2.
해당 인덱스에 해당하는 queue의 task list를 순회하며 cpu를 할당해준다.
3. cpu가 할당되서 빨간색 task가 현재 실행중이다. 이는 Active array라고 부르는 공간에 존재한다. 헌데 만약 실행도중 할당받은 timeslice가 만료되면, expried array로 빠지게 되고, 거기에 가서 자기 우선순위에 맞는 리스트에 다시 삽입되고, 다시 자기 차례를 기다리게 된다.
그후 다시 active array에서는 다음 우선순위의 task에게 cpu를 주고 쭉 실행된다. 그럼 다시 time slice가 만료된 놈들은 다 expired array로 빠지고, 결국 수행을 끝내지 못한 놈들은 전부 expired array로 가게 된다.
그때는 이제 expired array에 들어있는 모든 task에게 동일하게 time slice를 배정시키고, exipred array가 아닌 active array로 변경된다. 그럼 자동적으로 active arrary 였던 놈은 expired array가 된다.
따라서 각 CPU마다 두개의 Prior_array를 가지게 된다. (active array, expired arry). 이게 바로 리눅스의 O(1) 스케줄링이다.
방금 설명한 부분이 위 그림으로 표현이 된다. 현재 task가 timeslice가 만료되면 expired array로 넘어가고, 이렇게 모든 task들이 time out이 되버리면 다 넘어가버린다. 그러면 그때 2개의 priority array 를 바꿔버린다. (inter-chance 2 priority arrays). 그리고 active array로 변경된 array에 모든 task들은 일률적으로 새로운 timeslice를 할당받게된다.
실제 active array와 expried array가 변경되는 로직은 위 사진을 통해 알수가 있다.
3. Kernel Preemption
컴퓨터에서 Mutal Exclusion이 가장 중요하다고 해도 무방하다. 즉 상호배제라는 단어를 가지고 있는 Mutal Exclusion이 어떻게 진행되는지 자세히 알고있는게 바로 기술자로 가는 첫단계이다. 우선 그전에 보고가야 할게 있다.
만약 우리가 코드내에 x++ 라는 걸 사용했다고 하자. 이는 x변수에 들어있는 값을 1 증가시키는 역할이다. 우리 눈에는 하나의 연산이라고 보이지만 실제로는 3단계로 진행된다.
1.
x 변수가 저장된 곳에서 해당 값을 가져온다.
2.
cpu는 alu를 통해 +1 연산을 진행한다.
3.
연산의 결과를 다시 저장시킨다.
이러한 개념을 가지고 아래 그림을 한번 봐보자.
현재 X는 공유메모리에 저장되어있다고 가정해보자. A라는 프로세스가 X++ 연산을 진행하려고 하면 위에서 설명한 3단계를 거쳐야 한다. B 역시도 3단계를 거쳐야 한다.
현재 x가 11이라고 해보자. 그러면 A에서 x를 load했을때 11이 로드된다. B역시도 load하면 11이된다. 그리고 A에서 alu를 통해 연산이 되면 12가되고, B에서도 12가 된다. 마지막으로 A에서 연산결과를 돌려주면 12를 돌려주고, B역시도 12를 돌려준다.
뭔가 이상하지 않는가? X는 현재 공유메모리에 들어있어 A와 B 둘다 접근이 가능하다. A 에서 +1을 증가시키고 B에서도 1을 증가시켰으면 13이 되야하는데 12가 되었다.
이게 바로 올바르지 못한 상호배제의 결과이다. (Lost update problem). A,B 둘다 업데이트했는데, 그중 하나만 적용되고 나머지 하나는 날라가 버린 상황이다.
이렇게 공유되는 메모리에 접근하는 영역을 critical section이라고 부르고 이러한 critical section은 같이 진행되면 안된다.
임계 구역(critical section) 또는 공유변수 영역은 병렬컴퓨팅에서 둘 이상의 스레드가 동시에 접근해서는 안되는 공유 자원(자료 구조 또는 장치)을 접근하는 코드의 일부를 말한다
즉 한 순간에는 하나의 프로세스만이 critical section에 진입해야한다. 이를 바로 mutual exclusion 원칙이라고 한다. 그럼 이게 실제 어떠한 문제를 야기실킬수 있는지를 자세히 봐보자.
만약 A라는 프로세스가 진행되면서 user mode, kernel mode 를 번갈아 가면서 수행하고 있다. 그러다가 kernel mode로 수행중 x++을 진행한다. 이는 3단계로써, 변수를 load하고 연산을 진행하게 되었다. 따라서 x=12가 되었는데 그때 Cpu를 뺏기면서 B 프로세스가 진행된다.
lock
{
x++
}
C
복사
B도 역시 user mode, kernel mode를 번갈아 가면서 수행되는데, 커널 모드로 진행되면서 x++를 진행하다. load를 통해 x를 가져오고 이는 11이 들어있다. 왜냐하면 A에서 3번의 저장 과정을 거치지 않았기 때문이다. load후 연산을 하고 12가 된다. 그리고 저장한다.
B의 실행이 끝나고 다시 A에게 CPU가 넘어간다. A는 3번의 과정을 마져 수행하고 12를 그대로 변수에 저장한다. 위에서 말한 상호배제의 원칙이 깨져버렸다. 위 사진은 설명은 위한 가정이지만, 만약 이 변수가 중요한 역할을 하는 것이였다면 커널은 망가질 것이다.
따라서 OS kernel에서는 이러한 문제가 발생할수 있다. user mode로 진행되다 CPU를 뺏겨도 그건 아무 문제가 안된다. 왜냐하면 각자의 local한 영역을 사용하기 때문이다. 하지만 커널 모드로 진행되는 도중에 CPU를 뺏겨버리면 위에서 설명한 문제가 발생하게 된다.
유닉스에서는 지난 40년간 이러한 문제를 어떻게 해결했을까?
방법은 간단하다. 만약 현재 실행되고 있는 프로세스의 CPU가 뺏길때 user-mode라면 그대로 뺏기지만 만약 현재 모드가 커널모드라면 뺏지 않는다. 그렇게 기다리다가 커널모드가 끝나고 유저모드로 변경되는 그순간 바로 뺏어버린다. (NO Cpu preemption in kernel)
하지만...
이 방법도 한가지 문제가 발생한다. 만약 엄청 급한 작업이 요청되었다. 따라서 현재 실행되는 프로세스의 CPU를 뻇을라고 봤더니 커널모드네?? 그럼 위에서 설명한 방법대로라면 끝날때까지 기다려야한다.
이건 real-time computing 시스템에서는 매우 부적합하다. 실시간으로 매우 빠른 처리를 해야하는데, 저런 방법은...
예를 들어 스마트폰으로 노래를 듣고있다. 한소절이 끝나면 바로 다음 소절이 와야하는데, 그 도중 커널이 야 ! 나지금 뭐 안끝났어 기달려! 이러면 음악은 망가지게 된다. 따라서 이렇게 생겨난 문제를 해결하는 연구가 진행되었고,
결국 아래의 그림처럼 해결하게 되었다.
실제 커널과 관련된 로직을 보자.
중간 네모박스가 커널 프로그램이다. 그위 shell이 다른 프로그램들을 서포팅 하기 위해 PCB를 가지고 올라가 있다. 또한 shell에서 호출되는 시스템 콜을 커널 프로그램 내부에서 관리하기 위해 커널 스택이 올라가 있다. 이는 노란색 박스인 PCB 바로 아래영역이라고 보면 된다.
참고로 전에 말했다시피 PCB, 커널 스택은 모든 프로세스들 마다 다 존재한다.
ff()
{
int i,j;
i++;
j--;
}
C
복사
만약 send든 read든 둘다 저런 변수를 가지고 있다고 해보자. 소스코드로 보기는 shell 프로그램이든 mail 프로그램이든 동일한 변수처럼 보이지만 실제론 local 변수이기 때문에 할당된 주소는 서로 다르다. 따라서 이러한 변수들이 사용될때는 아무 문제가 없다.
하지만 global한 변수에 접근할때는 문제가 생길수 있으므로, 이러한 global 영역을 하나의 프로세스가 접근할땐 lock을 걸어 다른 놈이 접근을 못하게 만들어버리는게 바로 해법이다. 수행을 다하면 unlock을 하게 된다.
정리를 하면, global 변수에 접근할땐 lock을 걸고 다하면 unlock으로 풀는 식이다. 이렇게 lock이 걸려있으면 커널모드이든 유저모드이든, CPU를 뺏지못하고, unlock 상태면 critical section이 아니므로 커널모드임에도 CPU점유를 뺏앗길수 있게된다.
이러한 lock, unlock 에 대한 로직은 2가지의 변수를 이용하게 된다.
•
Preempt_count - per thread마다 존재
global 변수에 접근할때마다 count를 증가시킨다. 따라서 이 count는 해당 쓰레드가 접근중인 global 변수의 개수라고 볼수 있다. 접근이 끝나면 count를 감소시킨다.
이 상태에서 커널이 해당 쓰레드의 CPU를 뺏으러 왔을때 preempt_count 를 확인하고 0이면 현재 global 변수에 접근안하는것을 알고 바로 CPU를 뺏게된다. 0이 아니면 못뺏는다.
•
need_resched - flag
만약 CPU를 뺏으려고 왔는데 preempt_count가 0이 아니여서 못뺏으면, 기다리면서 해당 flag를 setting한다. 해당 flag가 set되었단 의미는, 현재 다른 waiting하고 있는 우선순위가 높은 놈이 있으니 걔한테 할당해줘! 라는 의미이다.
4. 결론
컴구시간이였나 운영체제 수업이였나 하튼 스케줄링을 구현한적이 있었는데, 그 원리를 쫌더 자세하게 알수 있었다. 넘나 재밌네 하핫
