[OS /운영 체제] Thread Scheduling, Contention Scope, Pthread Scheduling, Linux Scheduler, Linux CFS Scheduler, Windows Scheduling, Process Synchronization, Critical Section, Progress

 

Thread Scheduling

Kernel Thread가 Scheduling의 단위가 된다. PCB에 메달려 있는 LWP가 있다. LWP와 Thread는 One to one correspondence가 있다. 하나의 프로세스가 있고 여러 개의 Kernel에 해당하는 LWP가 존재한다. 실제 스케줄링은 LWP 단위로 이루어지는 경우가 많다.

 

 

Contention Scope

PCS와 SCS가 있다. Scheduling은 kernel에서 이루어지고 (CPU를 Kernel Thread로 나눠주는 것) 이때 경쟁이 발생하는데 이때를 SCS라고 한다. 두 번째로 Process 안에서의 경쟁이다. User Process 안에서의 경쟁이 PCS라고 한다. 

 

 

Pthread Scheduling

pthread_attr_init으로 default setting을 한다. getscope를 하면 attr의 정보를 꺼내서 scope로 가져다 주게 된다. scope의 값은 두 가지 Constant의 값을 가진다. PTHREAD SCOPE SYSTEM은 user level의 scheduling을 하는 경우에 사용된다. attr 값에다가 SCOPE값을 집어넣게 된다. create를 하면 attr대로 tid를 만드려고 노력을 한다. one to one model은 user level thread library가 없다. 자신의 Thread 모델이 지원을 하면 만들 수 있게 되고 지원할 수 없다면 무시하게 된다. setscope는 지원하는 것을 넣었을 때 적용이 된다.

 

JUMP

 

Operating System Example

 

Linux Scheduler

kernel version이 2.5아래였다. SMP를 잘 지원하지 못했다. 이후에 나온 Big Oh (1)의 알고리즘을 가지는 것이 등장했다. Scheduler가 Constant Time으로 돌아가는 스케줄링을 지원해줬다. 2.6 버전부터 CFS라는 이름을 갖게 되었다.

 

 

Linux Scheduler

Real-time scheduling은 제일 우선순위가 높은 것들이다. Real time은 0에서 99까지의 번호가 주어진다. 우선순위가 자기보다 낮은 친구는 먼저 들어간다. SCHED_FIFO 자기보다 우선순위 낮은 녀석이 돌고있으면 자기꺼를 돌릴 수 있다. Nonpreemtive이고 나는 Preemtive인데 상대방은 나한테 Nonpreemtive하다는 것이다. SCHED_RR(Round Robin은 최대 시간의 제한이 있게 된다) 일정 시간 이후에는 양보하게 되어있다. Preemtive할 수 있다는 관점에서 FIFO와 RR의 공통점을 들 수 있다.

 

 

Linux CFS Scheduler

task마다 nice value라는 것을 가지고 있다. nice value는 일종의 상대적인 값이다. User가 직접 지정할 수도 있다. External Priority와 Internal Priority가 있다고 했었다. 이는 Expernal Priority이다. Nice를 높이면 상대적인 우선순위를 낮출 수 있고 Nice 값을 줄이면 상대적인 우선순위를 높일 수 있다. 

 

Target latency 제약 조건으로 만들었기 때문에 Completely라고 표현을 한다. min 값도 가지고 있다. 현재 task가 많아지면 target latency가 증가할 수 밖에 없다. 이 값은 처음에 주어지지만 task의 개수에 따라 변할 수 있다.

 

 

 

Linux CFS Scheduler

vruntime value는 두 가지 값의 곱으로 결정된다. Physical runtime에 decay factor 값을 곱해서 사용한다. Normal priority는 곱하나 마다 한 1의 값을 갖게 된다. 우선순위가 높은 값들은 Decay factor를 줄이게 된다. scheduling하는 방법은 간단하다. 

 

 

Linux CFS Scheduler

IO Bound process는 IO쪽으로 가므로 자연스럽게 우선순위가 올라간다.

CPU Bound Process는 vruntime 값이 큰 것이 된다. vruntime이 작은 것부터 택하므로 우선순위가 낮게 된다.

 

 

Windows Scheduling

Dispatcher가 한다고 얘기를 한다. 윈도우는 숫자가 높은 것의 우선순위가 높은 체제를 가지고 있다.

Priority class를 여러 개 가지고 있다. IDLE Process는 놀고 있는 CPU에게 빈 Process를 만들어서 준 것이다. 동일한 클래스에서도 Prioriry가 존재하는데 이를 relative priority라고 부른다. real time이 들어갔다고 하면 일단 높다... 

 

 

Windows Scheduling

setPriorityClass(), setThreadPriority()

IO bound process의 우선순위를 높이고 CPU Bound Process의 우선순위를 낮춘다. quantum을 전체 다 썼다 하면 CPU Bound Process이므로 우선순위를 낮춘다. wait process를 사용했다고 하면 IO Bound Process이므로 우선순위를 높인다. time quantum의 길이를 3배 정도 늘리게 된다. 

 

---

 

 

Background

공유하는 메모리가 있으면 ~~ 이 그림에서 Buffer가 shared memory가 된다. Producer와 Consumer가 Process이면 Buffer가 shared memory여야 한다. 하지만 Thread인 경우 Global 변수를 사용하면 된다.

 

 

Concurrent Access of Shared Data

전역 변수 count를 이용해서 데이터를 넣고 빼고를 계산할 수 있다. count는 전역 변수에 있고 이는 메모리에 존재한다. 메모리의 값을 바로 증가할 수 없으므로 래지스터로 가져다 넣고 증감을 해야 한다. 

 

 

Synchronization Problem

시작 count 의 값이 5라고 하자. 분명히 잘못 저장될 수 있음을 알 수 있다.

 

 

Process Synchronization

race condition

일종의 버그. 그것을 막는 것을 Synchronize라고 한다. 공유되고 있는 자원이 있을 때 약속에 의해서 사용하자는 것이다. 

 

 

Critical Section

shared data에 access하는 Process의 Interaction이 있다. 나머지 영역을 Remainder Sectioin이라고 부른다. 남의 Process와 충돌이 일어날 수 있는 부분을 critical section이라고 부른다. Remainder section에서 버그가 있을 수 있다. 하지만 Sync 관련된 버그는 발생하지 않는다. 

Critical section, 주차 공간. 차가 있는지 없는 지를 먼저 확인해야 한다. 만약 누가 있다고 하면 기다리고 없다고 하면 내가 들어가면 된다. 들어가면 남이 들어오지 못하도록 한다. Entry Section이 누가 있는지를 확인하는 부분이고 Exit Section은 내가 있다가 나오는 상황이고 해당 공간에 남이 들어갈 수 있도록 열어 놓는 역할을 한다. 

 

 

Critical Section

누가 Critical Section에 있다면 Shared Data를 사용하고 있다는 것이다. Shared Section을 만진다는 것은 Critical section에 있다는 것이다. Remainder section은 Shared Section에 관여하지 않는다.

 

 

The Critical Section Problem

상호 작용이라 함은 Shared Resource를 같이 공유하는 경우에 해당한다. Process의 코드는 4가지 종류의 Section으로 나뉘어져 있다. 

 

The Critical Section Problem

do while이 4가 section에 대한 표현이다. 

 

 

The Critical Section Problem

Mutual exclusion

어느 하나가 Critical section에 있으면 다른 것들이 들어오면 안된다.

 

Progress

어떤 순간에는 어디에 걸려서 정지되는 상황을 얘기한다. 누가 주차 공간에 들어갔는데, 누가 있어서 기다리는 것은 정상적인 상황이다. 하지만 나왔는데도 다른 애들이 들어가지 못하는 경우가 존재한다. 

주차 공간에서 나온 친구들은 다시 들어가려고 경쟁하면 안된다는 뜻이다. 그리고 그러한 판단이 즉각적으로 이루어져야 한다. 

 

Bounded waiting

경쟁 상황에서 남에게 양보하는 것. 경쟁자가 5명인데 양보를 하지 않으면 적어도 몇 번 이상 기다리지는 않겠다라는 Buffer bound가 존재한다.

Mutual exclusion과 Progress는 무조건 Critical 하다.

 

 

Critical section problem

kernel의 사례

Non-preemtive scheduling은 Usermode에서 사용하다가 scheduling을 당할 수 있다 아니다를 따지는 것

Non-preemtive kernel은 System call 상황에서 scheduling을 당할 수 있는지의 여부를 보인다.

Non-preemtive kernel을 사용하면 kernel 구조를 만들기 쉬워진다. 이의 최대 장점은 performance보다 Responsibility이다.