Operating System 6 - Thread scheduling

 OS는 interrupt 없이 해결이 안됨. 우리가 입력하는 행동에 대한 피드백을 모두 이것으로 처리하기 때문.
따라서 interrupt는 막을 수 없다.

ULT/KLT : 어플리케이션에서 만든 것은 user, 그러나 실제로 OS에서 스케쥴링 되는 애들은 kernel. KLT는 ULT의 존재를 연결시켜주기 전 까지 모른다. 따라서 실행시키려면 ULT와  KLT를 연결해주어야 한다.

-Many to one
ULT는 많지만, KLT는 하나이므로 ULT가 돌아가면서 KLT와 연결되어 사용된다. 단, KLT는 여전히 어느 ULT와 연결되는지 알지 못하고 주어지는 instruction을 그냥 계속 처리하기만 한다.
하드웨어 단의 pc switch 등이 필요없다. (어플리케이션 내부에서 발생) 그래서 좀 더 빠르지만 여전히 누가 실행되는지 모르므로 서로 block/running이 엇갈릴 수 있다. (밑에 따로 위에 따로 돈다.) 어느 순간에 ULT 하나에 KLT 하나만 연결가능하므로 ULT가 block되어 버리면 KLT가 할당받은 시간을 다 사용하지 못한다. (다른 ULT로 switch 불가)
코어가 여러 개 있어도 여러 개를 동시에 수행 불가능하므로 multiprocessing의 이득을 누릴 수 없다.

* jacketing routine : ULT에 block이 발생되었을 때  i/o 장치를 사용할 수 있는지 체크하고 자기자신만 block화 시켜 KLT가 할당 받은 시간 동안 다른 ULT를 실행 할 수 있게 해주는 것. (시스템 콜을 바로 할 수 없을 때는 바로 요청하지 않고 자기자신만 블럭되고 다른 ULT가 실행되도록 양보)

- One to one
ULT - KLT가 1:1매칭하므로 상기한 문제점이 없음. 그러나 kernel level로 들어갔다가 나올 때 context switch의 오버헤드가 발생한다.

waiting time은 RR에서는 같은 우선순위의 다른 것들을 수행하며 기다리는 시간도 포함함. RR은 response time이 빨라지므로 시분할 시스템에서 주로 사용.
기아상태 - aging 기법 : 일정 시간이 지나면 한 번은 실행시켜줌



Multi-processor scheduling
이제까지 배운 것들은 모두 interleaving의 운용. 그러나 실제로는 여러 코어가 있으므로 병렬화 - overlapping에 대해서도 알아보자.

크게 세 가지 결합으로 구분 가능. 완전히 독립된 경우(네트워크로 묶임) - 약결합 / master-slave / main memory, 노드를 공유하여 같이 존재하는 경우 - 강결합
강결합으로 갈 수록 서로 간의 통신이 많아짐.

Granularity : 병렬화의 단위. fine/medium/coarse/very coarse.
-fine : instruction 단위에서 병렬화 시킬 수 있는 구간을 병렬화 시키는 것. 컴파일러가 하는 영역
- medium : 한 어플리케이션 단위에서 병렬화 시키는 것. 스레드 등
- coarse : 노드 단위, 프로세스 등 - interleaving 되는 환경에 overlapping을 시키는 것
- very coarse : 네트워크로 연결되어 있는 것.

coarse/very coarse는 interleaving이 되는 단위로 끊어서 여러 프로세스에서 실행되게만 바꿔주면 쉽게 적용가능하므로 자주 사용한다. 또한 이 경우 서로 다른 프로세스의 응답을 기다리면서 block되는 경우도 줄어든다. 만약 서로 자주 통신하지 않는 프로세스들은 네트워크 단으로 분리하여 처리할 수도 있다.

이와 별개로 independent는 연관성이 없는 완전히 서로 다른 작업을 병렬화 시키는 것을 가리킨다.

- Independent Parallelism
각 job을 독립적으로 수행하도록 제공해줌. interleaving 보다 그냥 코어를 따로 할당하여 overlapping을 하면 더 빠른 처리가 가능하다.


- Medium-grained parallelism
single application에서 어떻게 스레드 스케쥴링을 하느냐가 관건. 프로그래머의 역할.

Multiprocessing Design Issue
어느 프로세서에 무슨 프로세스를 할당할 지, 각각의 프로세서의 interleaving/overlapping 여부, 어떤 프로세스를 dispatch 할 지 등의 선택 사항이 존재.
이는 가능한 processor 개수와 granularity의 정도에 따라 달리 선택하게 된다.

Assignment to processors(단, 프로세서의 성능은 동일하다고 가정)
static/dynamic 할당을 결정해야 함.
-static : 한 번 프로세스가 한 프로세서에 할당되면 끝날 때 까지 해당 프로세서에서 실행. 각 프로세서가 자신의 큐만 보고 스케쥴링 된 것들을 처리. 이 경우 옮길 필요가 없으므로 스케줄링의 오버헤드가 적다.
그러나 한 번 할당되면 바꿀 수 없으므로 어떤 프로세서는 작업이 몰리고, 어떤 프로세서는 놀고 있는 경우가 있을 수 있다. (전체 시스템에서 효율성의 감소)

- dynamic : 위와 반대로 할당 받아도 다른 프로세서에서 실행 가능.
Common ready queue에 처리 필요한 프로세스들을 넣어놓고, 프로세서가 하나씩 가져와서 실행하는 방법.
혹은 static 처럼 각자의 queue를 가지고 있지만, 자신이 idle 할 때 남들 것을 가져와서 대신 수행해주는 load balancing을 사용할 수도 있다.

Master & Slave
병렬 처리와 프로세스 할당 등을 짜주는 것이 마스터, 그렇게 스케줄 해준 것을 실행하는 것이 슬레이브 프로세서가 된다.
이 경우 원래 interleaving에서 하나의 프로세서가 두 역할을 다 했으므로 조금만 수정해도 쉽게 적용 가능하다는 장점이 있다.
또한 마스터가 모든 스케줄을 짜고, 요청을 관리하므로 장치 충돌이 발생하지 않는다.

그러나 만약 마스터 커널이 죽어버리면 모든 것이 죽어버린다. 또한 모든 슬레이브가 마스터만 바라보고 있으므로 마스터의 과부하가 걸릴 수 있다. (bottle neck 발생 - 성능 저하)

Peer architecture
각각의 프로세서들이 큐에서 작업을 가져와 self scheduling이 가능하다. 그러나 큐에 할당된 작업들을 여러 프로세서가 동시에 가져가서 작업하지 않도록 상호배제 해주어야 한다.

interleaving/overlapping
프로세스 단위라면 interleaving을 사용해 block을 기다리는 것이 효율적이다(interleaving). 그러나 스레드들은 서로의 연관관계가 있는 경우가 많기 때문에 다른 것들이 block되지 않고 서로 통신할 수 있도록 한 번에 cpu에 올려 실행하는 것이 더 좋다(overlapping).
동시에 수행하면 어플리케이션이 더 빨리 실행, 번갈아가면서 수행하면 시스템을 busy하게 만듬. 그래서 큰 범위에서는 interleaving, 작은 범위에서는 overlapping이 되는 것이 효율적이다.

Process dispatching
단일 프로세서에서는 복잡한 스케줄로 효율화 하는게 좋지만, CPU 개수 자체가 많을 때는 전체 시스템에서 간단한 알고리즘을 사용하는 것이 더 효과적일 수 있다. (dispatch의 overhead를 줄이는 것이 더 좋음)

표준편차 - 시행시간이 차이가 큰 경우가 많다면 커짐.
싱글 프로세서에 비해 듀얼 프로세서만 되어도 복잡한 알고리즘의 효과가 확 떨어지므로 간단한 알고리즘(FCFS) 정도만 사용하여 오버헤드를 줄이는 것이 훨씬 좋다.

Thread Scheduling
싱글 프로세서에서 스레드의 기능은 어떤 것이 block되어도 다른 스레드가 실행되어 cpu를 쉬지 않게 하는 것이다. 이를 다르게 생각해보면 block된 것들과 실제 실행되는 것 이렇게 두 경우가 overlap되어 동시에 실행되는 것으로 볼 수 있다.

멀티 프로세서에서는 실제 사용할 수 있는 프로세서가 여러 개이므로 여러 스레드가 실제로 동시에 실행되어 진정한 병렬처리가 가능하므로 성능이 매우 향상된다.

Load sharing
전통적이고 가장 간단한 기법, 앞서 큐 하나에 스레드들을 두고 여러 프로세서가 가져가서 실행하는 것. global que를 두므로 모든 프로세서에서 idle 한 상태가 발생할 수 없다는 장점이 있다. 또한 각 프로세서가 알아서 가져가므로(self scheduling) centralized scheduler가 없다.
global queue의 정책도 다양하게 설정할 수 있다.

그러나 memory access에 대한 bottleneck이 발생한다. 왜냐하면 global queue를 쓰므로 여러 프로세서가 같은 프로세스에 접근 하지 못하도록 막아야 한다. (상호배제)따라서 어떤 프로세서가 가져가고 있으면 접근할 수 없으므로 접근에 대한 bottleneck이 발생한다.
그리고 caching의 효과가 작다. 내가 실행하는 매 프로세스는 전혀 연관성이 없으므로 캐시 메모리에 있던 정보가 무용하다.
이런 문제점은 각 프로세서마다 전용 큐를 가지면 해결할 수 있다.
하나의 프로세스를 구성하는 스레드는 앞서 말한 것 처럼 동시에 실행하는 것이 좋은데, 글로벌 큐에서 처리되므로 context switch가 다수 발생한다.

Gang scheduling
연관되어 있는 것들을 조직적으로 동시에 수행시켜주는 것(앞서 스레드를 할 때 overlapping이 더 좋다고 했던 것을 실행)
상기한 마지막 문제점을 해결하기 위해 simultaneous scheduling of threads which consist single process를 적용한 것.
context switching이 줄어들고 각 cpu의 스케줄링 오버헤드가 줄어든다.
이 방식은 medium ~ fine grained에서 효율적이다.

gang을 만들고 사이클을 돌릴 때 가중치를 주는 것이 좋다. 왜냐하면 여러 개의 스레드를 가지는 프로세스와 적은 스레드를 가지는 프로세스를 1:1로 매칭하여 사이클을 만들면 낭비되는 cpu가 많아지기 때문이다. 그러나 적은 스레드를 가지는 프로세스의 response time이 늦어지는 문제점이 있을 수 있다.

Dedicated Processor assignment
각 스레드에 대해 전용  프로세서 할당. 따라서 block되어도 그냥 cpu를 대기 시킨다. (interleaving 안함) 이 방식은 grid/distributed, core가 수천개 단위의 거대한 시스템을 돌릴 때 사용.

이 때 전체 프로세서 수보다 스레드 수가 적을 때(혹은 같을 때) 가장 좋은 효율을 보인다. (idle한 것을 제외하고) 만약 스레드 수가 더 많아지면 context switch 때문에 효율적이지 못하다. 즉, 시스템에서 스레드 수를 지나치게 늘리는 것은 좋지 않다. (코어 수 > 스레드 수 지켜야 함) 따라서 시스템의 프로세서 상태에 따라 스레드를 적당히 만들어야 한다.

Dynamic scheduling
OS는 core/cpu를 할당, application은 해당 core를 받아 어느 스레드를 실행에 올리는지 결정.
따라서 여러 프로그램 실행 상태, 현재 cpu의 상태에 따라 상황에 따라 cpu을 os가 application에 할당하고, application은 받은 cpu의 상태에 따라 scheduling 한다.
만약 가용한 cpu가 없으면 대기해야 함. 따라서 어떤 활동이 끝난 cpu가 있을 때 이를 다시 OS가 할당한다. 만약 cpu가 남을 경우는 또 더 요청하는 application들에게 할당한다.

CPU의 core, cache 공유 상태를 고려하여 스레드들을 할당하는 것이 좋다. (L2 cache는 공유하는 코어들이 L3 cache 까지 가야 하는 코어보다 한 프로세스의 스레드를 실행하는 것이 더 빠르다. 왜냐하면 정보 교환에 시간이 덜 걸리므로 - 하드웨어 고려, 주로 컴파일러가 해줌.)



Hardware Thread
이들은 CPU가 알아서 해주는 것. OS가 부팅되기 전 화면에서 설정할 수 있는 것들.

memory stall : cpu가 연산하기 위해 필요한 정보를 메모리에서 가져오기 기다리는 것.
따라서 해당 memory stall에 다른 스레드를 동시에 수행하여 interleaving을 할 수 있게 해주는 것. 이를 chip-multithreading, (hyper threading)이라 한다.
이 설정을 키면 core에 할당되는 스레드가 두 개씩 된다. 따라서 만약 4개의 코어가 있을 경우, 이 설정을 키면 OS는 코어가 8개로 보이게 된다.  (코어 가상화)


스레드 - 병행성 좋아짐.
dispatch를 덜 하는 것이 좋음 -> 멀티 프로세서를 사용하여 병행성이 높아져 성능 향상. 코어가 많아질 수록 알고리즘이 간단하면 더 효과적.