운영체제이론
[OS Concepts] 4. Threads& Concurrency
tbonelee
2024. 3. 9. 17:03
'Operating System Concepts - 10th edition' 을 읽고 정리한 내용입니다.
4.1 Overview
- CPU utlization의 기본 단위
- 스레드 ID, 프로그램 카운터(PC), 레지스터 셋, 스택으로 구성
- 동일 프로세스에 속한 다른 스레드와 코드 영역, 데이터 영역, 다른 OS 리소스(open file, signal 등)를 공유
4.1.1 Motivation
- 멀티스레드 앱의 예시 :
- 여러 의미지의 섬네일 생성을 위해 각 이미지마다 개별 스레드를 사용
- 웹 브라우저에서 한 스레드는 네트워크 데이터를 수신하고, 다른 스레드는 이미지나 텍스트를 화면에 띄우는 역할을 할 수 있음
- 워드 프로세서에서 화면을 띄우는 역할, 유저 입력을 받는 역할, 백그라운드에서 스펠링과 문법 체크 역할을 각각의 스레드로 할당할 수 있다.
- 멀티코어를 활용하는 앱을 만들 수도 있음
- CPU 집약적 작업을 멀티코어에서 병렬적으로 진행
- 하나의 앱이 비슷한 작업을 반복하는 경우 멀티 스레딩이 유용
- ex) 웹 서버의 요청 처리
- 서버가 요청을 받았을 때 프로세스 생성을 할 수도 있지만, 동일 작업을 하는 프로세스 생성은 costly
- 요청을 위한 스레드를 새로 생성해서 후속 요청은 해당 스레드에서 listen하여 처리하도록 하는 것이 더 효율적
- ex) 웹 서버의 요청 처리
- 대부분의 OS 커널도 멀티 스레드를 사용
- 시스템 부팅 시점에 리눅스는 여러 커널 스레드를 생성
- ex) 장치 관리, 메모리 관리, 인터럽트 핸들링
- 시스템 부팅 시점에 리눅스는 여러 커널 스레드를 생성
+-----------------------------------------------------------+
| code data files |
|-----------------------------------------------------------|
| registers | registers | registers |
| | | |
| stack | stack | stack |
| | | |
| PC | PC | PC |
+-------------------+-------------------+-------------------+
| || | || | || |
| || <-thread| || | || |
| \/ | \/ | \/ |
+-----------------------------------------------------------+
4.1.2 Benefits
멀티스레드 프로그램의 네 가지 주요 장점
- Responsiveness
- 블럭킹 작업이나 오래 걸리는 작업이 있어도 프로그램이 계속 실행될 수 있도록 하여 유저에 대한 반응성을 높일 수 있음
- Resource sharing
- 기본적으로 프로세스의 메모리와 자원을 공유하므로 프로세스 간 리소스 공유에 비해 간편
- Economy
- 프로세스의 리소스를 공유하므로 불필요하게 추가적인 메모리와 리소스 할당을 할 필요가 없음
- 일반적으로 스레드 생성이 프로세스 생성보다 시간, 메모리 소모가 적음
- 스레드 간 컨텍스트 스위칭이 프로세스 간 컨텍스트 스위칭보다 일반적으로 더 빠르다
- Scalability
- 멀티 프로세서 아키텍쳐에서 별개의 스레드는 여러 프로세서에서 병렬적으로 돌 수 있기 때문에 싱글 스레드 프로그램에 비해 유리
4.2 Multicore Programming
- 싱글 코어 환경에서 여러 스레드의 실행은 동시성(concurrency)은 여러 스레드의 실행을 시간에 따라 번갈아 가면서 실행하는 것을 의미(the execution of the threads will be interleaved over time)
- 멀티 코어 환경에서는 병렬적(parallel)으로 실행 가능
- concurrency와 parallelism의 구분
- concurrent system은 하나 이상의 태스크가 계속 진행될 수 있도록 함
- parallel system은 하나 이상의 태스크가 동시에 실행될 수 있도록 함
- => parallelism 없는 concurrency 가능
- 멀티프로세서와 멀티코어 아키텍쳐 등장 이전에는 싱글 프로세서만 존재
- CPU 스케쥴러가 프로세스 간 빠른 스위칭을 통해 병렬성의 일루전을 만듦
- 프로세스는 concurrently하게 실행되지만 parallel 하게 실행되지는 않음
4.2.1 Programming Challenges
멀티코어 시스템에 맞는 프로그래밍에는 다섯 가지 도전 과제가 존재
- Identifying tasks
- 별개의 concurrent한 태스크로 나뉘어질 수 있는 영역을 파악하는 것이 필요
- Balance
- 태스크 간 작업 밸류를 균등하게 나누는 것이 중요
- 전체 프로세스에 별로 중요하지 않은 작업을 위해 별개의 코어를 사용하는 것은 낭비일 수 있다
- Data splitting
- 나뉘어진 작업들에서 사용되는 데이터도 분리된 코어에서 실행될 수 있게 나뉘어야 한다
- Data dependency
- 어떤 태스크가 다른 태스크의 데이터에 접근한다면 태스크의 실행은 동기화되어야 한다
- Testing and debugging
- 멀티코어에서 병렬적으로 실행되는 프로그램은 아주 다양한 실행 경로를 가질 수 있다.
- 이로 인해 테스팅과 디버깅은 더욱 어려워질 수 있다.
4.2.2 Types of Parallelism
- Data parallelism
- 동일한 데이터의 subset을 여러 연산 코어에 분산하여 동일한 작업을 각 코어에서 실행하는 유형
- ex) 사이즈 $N$의 배열 원소의 합을 구하는 작업
- Task parallelism
- 각 스레드는 각자 유니크한 오퍼레이션을 수행 (같은 데이터를 사용할 수도, 아닐 수도)
- 두 가지 타입은 상호 배타적인 것이 아님. 두 가지가 혼합된 경우도 충분히 가능
4.3 Multithreading Models
- user threads
- 유저 레벨에서 제공됨
- 커널의 도움 없이 관리됨
- kernel threads
- OS가 직접적으로 관리
- 모든 현대적인 OS는 커널 스레드를 지원
- 유저 스레드와 커널 스레드 간에는 relationship 수립이 필요
- 'many-to-one model', 'one-to-one model', 'many-to-many model'
4.3.1 Many-to-One Model
- 여러 유저 레벨 스레드가 하나의 커널 스레드로 맵핑됨
- 유저 영역의 스레드 라이브러리를 통해 스레드 관리가 이루어짐
- 보다 효율적(어떤 측면에서?)
- 단점
- 스레드가 블락킹 시스템 콜을 호출하면 모든 프로세스가 블락될 수 있음
- 한 번에 하나의 스레드만 커널에 접근할 수 있기 때문에 멀티코어 시스템에서 스레드가 병렬적으로 실행될 수 없음
- ex) 자바 초기 버전에서 사용된 Green threads
- 멀티코어가 보편화 된 시점에서 사용이 많이 줄어듦
4.3.2 One-to-One Model
- 블락킹 이슈가 없고, 병렬적으로 실행될 수 있음
- 유저 스레드 생성이 직접적인 커널 스레드 생성을 요구하므로 많은 커널 스레드로 인해 시스템 퍼포먼스에 부담이 될 수 있음
- 리눅스와 윈도우즈 계열 OS에서 one-to-one 모델을 구현
4.3.3 Many-to-Many Model
- 여러 유저 레벨 스레드를 그거보다 같거나 더 적은 수의 커널 스레드로 맵핑
- 커널 스레드의 갯수는 특정 앱이나 머신에 따라 결정될 수 있음
- ex) 어떤 앱은 4코어보다 8코어에서 더 많은 커널 스레드를 할당할 수 있음
- 개발자는 원하는 만큼 유저 스레드를 생성 가능 (One-to-One 에서의 단점 해소)
- 커널이 다른 스레드를 할당할 수 있으므로 유저 스레드의 블락킹 시스템 콜 호출로 전체 프로세스가 블락되지 않음 (Many-to-One의 단점 해소)
- 멀티프로세서에서 병렬적으로 실행 가능 (Many-to-One의 단점 해소)
- two-level model은 many-to-many의 구조를 가져가면서 one-to-one도 허용하는 모델
- 구현하기 어렵다는 단점
- 프로세싱 코어가 늘어가면서 커널 스레드 갯수의 한계는 덜 중요해져서 대부분의 OS는 one-to-one 모델을 채용
- 그럼에도 불구하고 몇몇 동시성 라이브러리는 개발자가 태스크를 분별하여 many-to-many 모델을 사용한 스레드에 맵핑하도록 하고 있음
4.4. Thread Libraries
- Thread library는 개발자가 스레드를 생성/관리할 수 있는 API를 제공
- 스레드 라이브러리 구현의 두 가지 갈래
- 유저 영역에 라이브러리를 제공하여 커널 지원을 받지 않는 방법
- 라이브러리를 위한 모든 코드와 데이터 구조는 유저 공간에 존재
- 라이브러리 함수 호출은 시스템 콜이 아닌 유저 영역의 로컬 함수 호출을 의미
- OS가 지원하는 커널 레벨 라이브러리 구현
- 라이브러리의 코드와 데이터 구조는 커널 영역에 존재
- 라이브러리 API 호출은 보통 커널의 시스템 콜 호출로 이어짐
- 유저 영역에 라이브러리를 제공하여 커널 지원을 받지 않는 방법
- 주요 세 가지 스레드 라이브러리
- POSIX Pthreads
- 유저 레벨로 제공될 수도 있고, 커널 레벨로 제공될 수도 있음
- Windows
- 커널 레벨로 제공됨
- Java
- 보통 JVM이 호스트 OS 위에서 동작하므로 보통 호스트 OS에서 사용 가능한 스레드 라이브러리를 통해 구현됨
- POSIX Pthreads
- POSIX, 윈도우즈에서 전역적으로 선언된 데이터는 동일 프로세스 내의 스레드 간에 모두 공유됨
- 자바는 전역 데이터 개념이 없으므로 공유가 필요한 데이터는 명시적으로 위치시켜야 한다
- 스레드 생성의 두 가지 전략
- asynchronous threading
- 부모가 자식 스레드를 생성한 후 다시 작업을 재개
- 각 스레드가 독립적이므로 보통 스레드 간 데이터 공유가 적음
- 멀티스레드 서버, responsive한 유저 인터페이스에 많이 사용됨
- synchronous threading
- 부모 스레드가 하나 이상의 자식을 생성하고 모든 자녀가 종료한 후에 작업을 재개하는 전략
- 부모가 생성한 스레드는 동시에 실행되지만 부모는 잠시 작업을 멈춤
- 모든 스레드가 작업을 마치면 종료하고 부모에 join하게 됨
- 모든 자식이 join한 후에 부모는 작업을 재개
- 보통 많은 스레드 간 데이터 공유가 이루어짐
- divide and conquer 전략?
- asynchronous threading
- 예제에서는 동기적 스레딩 전략을 사용
Pthreads
- Pthreads : 스레드 생성과 동기화에 대해 정의한 POSIX standard를 일컬음
- specification이지 implementation이 아님
- 윈도우즈를 제외한 많은 시스템이 Pthreads를 구현
아래는 스레드 하나를 생성하여 양의 정수의 합을 구하는 예제 코드이다
#incldue <pthread.h>
#include <stdio.h>
#include <stdlib.h>
int sum; /* 공유 데이터 */
void *runner(void *param); /* 스레드가 실행할 함수 */
int main(int argc, char *argv[]) {
pthread_t tid; /* 스레드 식별자 */
pthread_attr_t attr; /* 스레드 속성 */
/* 스레드의 기본 속성을 설정 */
pthread_attr_init(&attr);
/* 스레드 생성 */
pthread_create(&tid, &attr, runner, argv[1]);
/* 스레드 종료를 기다림 */
pthread_join(tid, NULL);
printf("sum = %d\n", sum);
}
/* 스레드가 실행할 함수 */
void *runner(void *param) {
int i, upper = atoi(param);
sum = 0;
for (i = 1; i <= upper; i++) {
sum += i;
}
pthread_exit(0);
}
Java Threads
- 모든 자바 프로그램은 최소한 하나의 스레드로 이루어짐
- 명시적으로 스레드를 생성하는 두 가지 방식
Thread
클래스를 상속받아run()
메소드를 오버라이드Runnable
인터페이스의public void run()
메소드를 구현
다음은 Runnable
을 구현한 Task
클래스를 사용하는 예시
Thread workder = new Thread(new Task());
worker.start();
start()
메소드를 호출하면,- 메모리를 할당하고 JVM에 새 스레드를 초기화
run()
메소드를 호출하여 JVM에 의해 스레드가 실행되도록 함
try {
worker.join();
}
catch (InterruptedException ie) { }
- Pthreads와 Windows 라이브러리의 join 메소드와 동일하게 스레드 종료를 대기하기 위해
join()
메소드를 사용
4.5 Implicit Threading
- 동시성/병렬 프로그래밍을 돕기 위해 스레드의 생성/관리를 애플리케이션 개발자에서 컴파일러, 런타임 라이브러리로 넘기는 전략이 등장 - implicit threading
- 개발자가 병렬적으로 실행될 수 있는 것들을 (스레드가 아닌) 태스크로 구분해줘야 함
- 그러면 런타임 라이브러리가 개별 스레드로 맵핑시켜준다. (보통은 many-to-many 모델 사용)
- 개발자는 병렬 태스크를 구분. 라이브러리는 스레드 생성/관리를 담당
4.5.1 Thread Pools
- 멀티 스레드로 웹 서버를 구성한다고 해보자
- 서버가 요청을 받으면 처리하기 위해 별개의 스레드를 생성한다.
- 이러한 스레드 생성은 두 가지 이슈를 만든다.
- 한 번 사용하고 버릴 스레드를 생성하기 위해 시간을 소모
- 시스템에 활성화된 스레드의 갯수 상한이 없기에 시스템 리소스를 소진시킬 수 있음.
- 이를 개선하기 위해 thread pool 사용
- 프로그램이 시작할 때 여러 스레드를 생성하여 풀에 놓고 필요할 때 가져다 쓰는 방식
- 장점 :
- 스레드를 생성해서 쓰는 것보다 빠름
- 동시에 존재할 수 있는 스레드 갯수를 제한할 수 있음
- 태스크의 실행을 생성 메커니즘과 구분함으로써 태스크의 실행 전략을 달리할 수 있음 (ex. 일정 시간 지연 후에 실행되도록 스케쥴링, 주기적으로 실행하도록)
- 풀의 스레드 갯수는 시스템의 CPU 갯수, 물리 메모리 갯수, 예상되는 동시적 클라이언트 요청 갯수 등을 바탕으로 휴리스틱하게 결정.
- 동적으로 조정되도록 할 수도 있음
4.5.2 Fork Join
- main 부모 스레드는 하나 이상의 스레드를 생성(forks)하고 자식이 종료하고 join하기를 기다린다. 그러면 그 결과들을 받아서 합치게 된다.
- 이러한 동기적 모델은 명시적 스레드 생성으로 구현할 수도 있지만 implicit 스레딩으로도 가능하다.
- 스레드 생성/관리는 라이브러리가 관리
- 자바 1.7에서 도입된 fork-join 라이브러리는 recursive divde-and-conquer 알고리즘에 활용될 수 있다.
4.6 Threading Issues
4.6.1 The fork() and exec() System Calls
- 모든 스레드를 복사하는 fork (
fork()
)와 호출한 스레드만 복사하는 fork (pthread_atfork()
)가 존재 exec()
를 호출하면 모든 프로세스를 덮어씌우니 스레드도 덮어씌우게 됨- 따라서 fork 후
exec()
를 호출할 것이면 모든 스레드를 복제하는 것은 불필요. - 만약 fork 후
exec()
를 호출하지 않는다면 모든 스레드를 복제해야 함
4.6.2 Signal Handling
- signal : UNIX 시스템에서 특정 이벤트 발생을 프로세스에게 알리는 용도로 사용됨
- 이벤트의 근원과 이유에 따라 동기적으로도 비동기적으로도 받을 수 있음
- 모든 시그널은 다음 패턴을 가짐
- 시그널은 특정 이벤트의 발생을 통해 생성됨
- 시그널은 프로세스에 전달됨
- 전달된 시그널은 처리되어야 함
- illegal memory access, division by 0 등이 동기적 시그널의 예시
- 동기적 시그널은 시그널을 발생시킨 오퍼레이션을 실행한 프로세스에 전달된다
- 시그널이 실행중인 프로세스 외부의 이벤트에 의해 생성되면 프로세스는 비동기적으로 시그널을 받는다.
- 컨트롤 + c 신호, 시간 만료 등의 이벤트가 예시
- 보통 비동기 시그널은 다른 프로세스로 전달된다.
- 시그널은 두 가지 핸들러에서 처리 가능
- 기본 시그널 핸들러
- user-defined 시그널 핸들러
- 모든 시그널은 커널이 실행하는 default signal handler를 가진다.
- default action은 user-defined signal handler를 통해 오버라이드될 수 있다.
- 프로세스가 여러 스레드를 가지는 경우 시그널을 전달할 수 있는 여러 옵션이 존재하게 된다.
- 시그널이 적용되는 스레드에 전달
- 프로세스의 모든 스레드에 전달
- 프로세스의 몇몇 스레드에 전달
- 특정 스레드가 프로세스의 모든 시그널을 받도록 할당
- 동기적 시그널은 원인을 제공한 스레드에 전달하면 되므로 명확
- 비동기적 시그널은 처리 방식이 명확하지 않다.
- 프로세스 종료 등의 몇몇 비동기 시그널은 모든 스레드에 전달되어야 한다.
- 대부분의 UNIX 멀티스레딩은 스레드마다 허용할 시그널과 블럭할 시그널을 정할 수 있도록 해놓았다.
- 따라서 몇몇 케이스에서 비동기 시그널은 블럭하지 않는 스레드로 보내져야 한다.
- 하지만, 시그널은 한 번만 핸들링되어야 하므로 보통 블럭하지 않는 첫 스레드로 보내지게 된다.
4.6.3 Thread Cancellation
Thread cancellation : 스레드가 완료되기 전에 종료시키는 것
Target thread : 취소 대상 스레드
스레드 취소 방식 두 가지 :
- Asynchronous cancellation
- 하나의 스레드가 다른 스레드를 즉시 종료시킴
- Deferred cancellation
- 타겟 스레드가 주기적으로 종료해야 하는지 체크
- 종료해야 할 때 정리해야 할 것들을 잘 정리하고 종료할 수 있음
- Asynchronous cancellation
Asynchronous cancellation 단점
- 할당된 시스템 리소스 반환이 제대로 이루어지지 않을 수 있음
- 다른 스레드와 공유하던 데이터를 업데이트하던 중에 종료되면 문제가 생길 수 있음
Pthreads 예시
pthread_cancel(tid)
를 통해 스레드 취소를 init할 수 있음- 그저 취소 요청을 큐에 넣는 역할
pthread_join()
을 통해 종료를 기다릴 수 있음- 스레드가 종료되면 해당 함수는 return
취소 요청을 받은 스레드는 cancel state와 cancel type에 따라 취소 진행 여부, 취소 방식을 결정
- Cancel state가 비활성화되어 있으면 취소 요청은 계속 큐에 남아 있게 된다.
- 활성화되어 있으면 cancel type에 따라 취소 방식을 결정
- Deferred cancellation type인 경우 스레드가 cancellation point에 다다른 경우에 취소가 진행됨
- Pthreads는 cancellation point인 함수를 명시하고 있고, 해당 함수 중 하나가 호출되면 취소가 진행됨
- 많은 POSIX, 표준 C 라이브러리의 블라킹 함수가 여기에 속함 (ex.
read()
) - 스레드가 cancellation point 중 하나인
pthread_testcancel()
을 호출하여 취소를 진행시키기도 함(취소 요청이 없는 경우 함수 호출은 아무 효과 없이 지나간다)
- 많은 POSIX, 표준 C 라이브러리의 블라킹 함수가 여기에 속함 (ex.
cleanup handler를 등록하여 스레드가 종료될 때 정리 작업이 이루어도록 할 수도 있다.
Mode | State | Type |
---|---|---|
Off | Disabled | - |
Deferred | Enabled | Deferred |
Asynchronous | Enabled | Asynchronous |
4.6.4 Thread-Local Storage
- TLS를 통해 스레드에 고유한 데이터를 만들 수 있다
- 로컬 변수 같아 보이지만 로컬 변수는 하나의 함수 안에서만 접근 가능하지만 TLS는 전역적으로 접근 가능
- 스레드 풀과 같이 개발자가 implicit한 테크닉을 사용할 때는 추가적인 작업이 필요하다. (ex. TLS가 초기 상태인지 체크?)
4.6.5 Scheduler Activations
- 유저-커널 스레드 간에 m : n 관계가 있을 때 유저 레벨 스레드 라이브러리와 커널 간의 커뮤니케이션을 도와주는 방법
- LightWeight Process(LWP)
- 커널과 유저 스레드 라이브러리 사이의 중간 역할
- 유저 스레드는 LWP를 하나의 가상 프로세서로 간주하여 유저 스레드를 맵핑
- 하나의 커널 스레드에 부탁되어 있고, OS가 물리 프로세서에 스케쥴링하면 실행됨
- 커널 스레드가 I/O wait 등으로 블럭되면 LWP와 거기에 부착된 유저 스레드도 블럭된다
- 애플리케이션에 적절한 LWP의 수는 다양할 수 있다.
- 싱글 프로세서에서 실행되는 CPU 집약적인 앱은 하나의 LWP로 충분 (어차피 한 번에 하나의 스레드만 실행 가능하므로)
- I/O 집약적인 앱은 많은 LWP 필요
- LWP는 동시에 존재하는 각각의 블로킹 시스템 콜 호출마다 필요하다.
- 프로세서에 네 개 LWP가 있는 상황에서 모두 I/O 입출력 완료를 대기 중이라면, 다섯번째 요청은 그 중 하나의 LWP가 리턴하기를 기다려야 한다.
- 유저 스레드 라이브러리와 커널은 scheduler activation을 통해 커뮤니케이션
- 커널이 애플리케이션에 가상 프로세서 집합(LWPs)을 제공
- 애플리케이션은 유저 스레드를 사용 가능한 가상 프로세서에 스케쥴
- 이벤트가 발생하는 경우 커널은 upcall로 정보를 전달해줌
- upcall은 스레드 라이브러리가 upcall handler를 통해 처리해야 하고, upcall handler 또한 가상 프로세서에서 실행되어야 한다.
- upcall 예시1 (블로킹)
- 애플리케이션 스레드가 블럭되는 경우, 커널은 스레드가 블럭되는 것과 어떤 스레드가 블럭되는지 알려준다.
- 커널은 새 가상 프로세서를 앱에 할당
- 앱은 upcall handler를 새 가상 프로세서에서 실행
- upcall handler는 블로킹 스레드의 상태를 저장하고 블로킹 스레드가 실행 중이던 가상 프로세서를 놓아준다
- 그리고 upcall handler는 실행할 수 있는 다른 스레드를 새 가상 프로세서에 할당
- upcall 예시2 (블로킹 스레드가 대기하고 있던 이벤트 발생)
- 커널은 upcall을 통해 스레드 라이브러리에 아까 블럭된 스레드가 이제 실행될 수 있다고 알려준다
- 커널은 새 가상 프로세서를 할당하거나 유저 스레드 중 하나를 preempt하여 그 위에서 upcall handler를 실행할 수 있도록 한다.
- 블로킹된 스레드가 이제 실행 가능하므로 애플리케이션은 이제 가능한 가상 프로세서에서 이를 실행한다.