스레드

참고 자료

• [운영체제(OS)] 4. 멀티쓰레드(Multithreaded Programming)
• [운영체제(OS)] 5. 프로세스 스케줄링(Process Scheduling)

스레드란?

스레드(Thread)는 CPU 수행의 기본 단위 또는 프로세스 안의 제어권의 흐름이다. 스레드가 수행되는 환경을 Task라고 부르는데, 전통적인 프로세스는 하나의 스레드가 있는 Task와 일치한다.

한 프로세스가 하나의 스레드를 이용하여 한 번에 한 작업만 수행하는 것은 싱글 스레드(Single thread), 한 프로세스가 여러 스레드로 동시에 여러 작업을 수행하는 것은 멀티 스레드(Multi thread)라고 한다. 프로세스 내의 스레드는 모두 각각 독립적인 실행 파일이며, 모든 스레드는 프로세스의 일부이다. 프로세스를 여러 개 수행해도 되지만 굳이 스레드를 사용하는 이유는 다음과 같다.

1. 프로세스를 생성하거나 Context switching 하는 작업은 너무 무겁고 잦으면 성능 저하가 발생하는데, 스레드를 생성하거나 switching 하는 것은 그에 비해 가볍다.

2. 두 프로세스가 하나의 데이터를 공유하려면 메시지 패싱이나 공유 메모리 또는 파이프를 사용해야 하는데, 이는 효율도 떨어지고 개발자가 구현, 관리하기도 번거롭다.

멀티 스레싱

프로세서가 여러 개인 경우 멀티 스레드를 통해 병렬성(Parallelism)을 높일 수 있다. 즉, 여러 작업이 동시에 수행될 수 있다.

이는 프로세스의 스레드들이 각각 다른 프로세서에서 병렬적으로 수행될 수 있기 때문이다. 병렬성은 CPU의 개수에 비례한다.

만약 프로세서가 하나인 경우엔 멀티 스레드를 통해 동시성(Concurrency)을 높일 수 있다. 실제로는 각각의 시간에 한 작업만 수행되지만, 병렬적으로 수행되는 것처럼 보이는 것이다. 만약 한 스레드가 blocked(waiting) 되더라도 커널이 다른 스레드로 switch 시켜 실행할 수 있어서, 하나의 프로세서임에도 불구하고 빠른 처리가 가능하고 계산 속도가 증가한다.

멀티스레딩의 장점

1. 응답성(Responsiveness)

   싱글 스레드인 경우, 작업이 끝나기 전까지 사용자에게 응답하지 않는다. 반면 멀티스레드인 경우 작업을 분리해서 수행하므로 실시간으로 사용자에게 응답할 수 있다.

2. 자원 공유(Resource sharing)

   프로세스는 오직 공유 메모리나 메시지 패싱을 이용해서 자원을 공유할 수 있지만, 스레드는 자신이 속한 프로세스 내의 스레드들과 메모리나 자원을 공유하여 효율적으로 사용할 수 있다.

3. 경제성(Economy)

   프로세스를 새로 생성하는 비용보다 스레드를 새로 생성하는 게 훨씬 싸다. 그리고 Context switching의 오버헤드 또한 스레드가 더 경제적이다. 실제로 Solaris에서 프로세스 생성은 스레드 생성보다 30배 느리고, switching은 5배 느리다.

4. 확장성(Scalability)

   싱글 스레드인 경우 한 프로세스는 오직 한 프로세서에서만 수행 가능하다. 반면 멀티 스레드인 경우 한 프로세스를 여러 프로세서에서 수행할 수 있으므로 훨씬 효율적이다.

멀티 스레드 스케쥴링

스케줄러(Scheduler)는 언제, 어떤 프로세스를 선택해서 CPU에서 실행시키는지 선택하는 모듈(Module)이다. 멀티프로그래밍의 목적이 CPU 효율 극대화이므로 적절한 스케줄링이 필요하다.

기본적으로 프로세스는 CPU만 사용하는 단계(CPU burst)와 I/O 작업만 하는 단계(I/O burst)의 반복으로 구성된 사이클의 형태로 수행된다.

이러한 여러 Job이 섞여있기 때문에 CPU 스케줄링이 필요하다.

CPU Scheduler는 메모리에서 Ready 상태의 프로세스 중 어떤 프로세스를 CPU에 할당해줄지 선택한다. CPU 스케줄링으로 인해 변경되는 프로세스의 상태는 다음과 같다.

1) Running → Waiting(Blocked) : I/O 요청이나 자식의 종료를 위해 wait( ) 함수 호출한 경우

2) Running → Ready : 인터럽트가 발생한 경우

3) Waiting → Ready : I/O 작업이 끝난 경우

4) Terminate

여기서 1)과 4)는 Non-preemptive (비선점) 방식이고, 그 외의 모든 과정은 preemptive(선점) 방식이다.

Preemptive 방식은 운영체제가 강제로 프로세스의 사용권을 통제하는 방식이고, Non-preemptive 방식은 프로세스가 스스로 다음 프로세스에게 자리를 넘겨주는 방식이다.

Preemptive 스케줄링은 여러 프로세스가 데이터를 공유하고 있는 경우, 경쟁 상태(Race condition)의 문제점을 낳을 수 있다. 만약 한 프로세스가 데이터를 수정하고 있는 동안에 다른 프로세스의 수행을 위해 preempted 된다면, 다른 프로세스는 일관성이 없는 상태의 데이터를 읽게 된다.

Dispatcher는 CPU의 제어권을 CPU 스케줄러에 의해 선택된 프로세스에게 넘겨주는 모듈이다. 즉, Context switching이나 커널 모드에서 유저 모드로 스위칭하는 작업등을 수행한다. 한 프로세스를 멈추고 다른 프로세스를 실행하는 데까지 걸리는 시간을 Dispatch latency라고 부른다.

1. FCFS Scheduling

FCFS 스케줄링은 First Come First Served의 약자로 CPU에 먼저 도착하는 순서대로 프로세스를 할당해주는 방식이다.

각 작업이 종료될 때까지 CPU를 빼앗지 않으므로 Non-Premptive 방식이며, FIFO 방식의 큐(Queue)와 동일하다.

구현하기 쉬워 간단한 시스템에 자주 사용된다.

Gantt Chart는 작업들이 CPU에 어떻게 스케줄링되는지를 보여주는 차트를 말한다.

2. SJF (Shortest Job First) Scheduling

SJF(Shortest Job First) 스케줄링은 Convoy Effect를 해결하기 위한 방식이다. 프로세스의 수행 시간이 짧은 순서대로 CPU에 할당한다. SJF 스케줄링은 항상 주어진 프로세스에 대해 최소의 평균 대기 시간을 보장한다. 즉, 항상 최적(Optimal) 임이 보장된다.

하지만, 수행시간이 긴 프로세스는 계속 뒤로 밀려나는 기아(Starvation) 현상이 발생할 수 있다.

SJF 방식은 Non-preemptive와 Preemptive 두 방식이 존재한다.

1) Non-preemptive SJF

프로세스가 한번 CPU를 잡으면 이번 CPU burst 시간이 만료될 때까지 CPU를 뺏기지 않는다.

2) Preemptive SJF

이 경우는 평균 대기 시간이 3이며, 최적의 경우이다.

따라서, 새로운 프로세스가 도착했을 때, 현재 남아있는 작업 중 가장 빨리 끝나는 작업부터 CPU를 할당해주는 Preemptive 방식을 이용하면 평균 대기 시간을 더 줄일 수 있다. 이 방식을 SRTF(Shortest Remaining Time First) 혹은 STCF(Shortest Time-to-Completion First)라고도 부른다.

하지만 여전히 기아(Starvation) 현상을 막을 수 없다.

3. Round Robin (RR) scheduling

Round Robin 스케줄링은 각 프로세스가 주로 10 ~ 100ms의 동일한 크기의 할당 시간(Time quantum)을 갖는다. 할당 시간이 끝나면 프로세스는 자동으로 선점(Preempted)당하고, Ready queue의 제일 뒤에 가서 다시 줄을 선다.

n개의 프로세스가 Ready queue에 존재하고, 할당 시간이 q라면 어떤 프로세스도 (n-1)q 이상 기다리지 않으므로 기아 현상이 발생하지 않는다. 따라서 응답 시간이 빠르다는 장점이 있다.

다만, 일반적으로 SJF보다 평균 소요 시간(Average Turnaround Time)은 길다.

4. Priority Scheduling

우선순위 스케줄링은 특정 기준으로 프로세스에게 우선순위를 부여해 우선순위가 제일 높은 프로세스에게 CPU를 할당하는 방식이다. 일반적으로 숫자가 작으면 우선순위가 높은 것을 의미하며, SJF도 일종의 우선순위 스케줄링이다.

다만 이 방식 또한 우선순위가 낮은 프로세스가 계속해서 수행되지 않는 기아 현상이 발생할 수 있는데, 이를 에이징(Aging) 기법을 통해 해결한다. 에이징 기법은 시간이 지날수록 오래 대기한 프로세스의 우선순위를 높이는 방식이다.

다른 스케줄링 알고리즘과 결합해서 사용할 수 있어 선점, 비선점 모두 가능하다.

5. MLFQ (Multi-Level Feedback Queue)

Multi-Level Queue는 Ready Queue를 여러 개로 분할한 것이다. 각 큐는 독립적인 스케줄링 알고리즘을 가진다.

Foreground task 같은 Interactive 프로그램은 응답 시간이 중요하기 때문에 Round Robin 스케줄링으로, Background Task 같은 Batch 프로그램은 소요시간이 중요하기 때문에 FCFS 스케줄링을 사용한다.

큐 사이에서도 스케줄링이 필요한데, Foreground 작업을 먼저 다 수행한 후, Background 작업을 수행하는 고정된 우선순위 스케줄링을 이용할 수 있다. 따라서 이 방식은 기아 현상이 발생할 수 있다.

또는, 각 큐에 CPU Time을 적절한 비율로 할당하는 Time slice 방식을 사용할 수도 있다. 예를 들어 80%는 Foreground에, 20%는 Background에 사용한다.

Multi-Level Feedback Queue는 여기에 프로세스가 큐들 사이에서 이동할 수 있는 성질이 추가된 것이다. 우선순위를 부여해서 에이징(aging) 기법을 통해 구현될 수 있다. 우선순위는 프로세스들의 과거 CPU burst time을 이용하여 미래의 행동을 예상하여 부여한다. 이를 이용하여 기아 현상을 해결할 수 있다.