[운영체제] 공룡책🦖 ch04. Threads & Concurrency

Reference
1. Abraham Silberschatz, Greg Gagne, Peter B. Galvin - Operating System Concepts (2018)
2. Operating System class by Professor Sukyong-Choi at Korea University

중요한 내용 위주로 요약 && 정리했습니다.

 

목차

1. Overview
2. Multicore Programming
3. Multithreading Models
4. Thread Libraries
5. Implicit Threading
6. Threading Issues
7. Operating System Examples

현대 운영체제는 한 process가 다중 스레드를 포함합니다.

따라서 다중 CPU를 제공하는 multicore system에서 thread를 통한 병렬 처리(parallelism)가 중요합니다.

 

4.1 Overview

thread : CPU utilization의 기본 단위

• thread ID, program counter(PC), register set, stack으로 구성
• 동일한 process에 속하는 다른 thread들과 code, data, resource, file signal 공유
• 동시에 하나 이상의 task 실행 가능

• 한 application이 비슷한 여러 task를 수행할 일이 많기 때문에 multi thread process 사용

→ 예를 들어 web server는 여러 client들의 비슷한 request를 처리한다.

 

single-thread process VS multi-thread process

1. single-thread process를 여러 개 생성하여 일을 처리 → 시간, 자원 소모가 큼
2. mulit-thread process → 한 process가 더 효율적으로 여러 일을 처리할 수 있게 됨

⇒ 요청마다 process 생성 x → thread 단위로 처리해서 자원과 시간 사용을 효율적으로 함

 

OS kernel

• multithread 방식 사용
• ps -ef : kernel thread 보여줌
• kthreadd (pid = 2) : 모든 kernel thread의 부모

 

benefits

(1) Responsiveness

• 스레드 단위로 분리→ 한 작업에 대해 응답을 기다리지 않고 다른 작업 수행 가능
• 프로그램이 계속 실행되어 응답성 증가

(2) Resource Sharing

• thread는 자신이 속한 process 내 모든 thread와 메모리, 자원을 공유
• 동일 주소 공간 내에 다른 여러 스레드를 가질 수 있음

(3) Economy

• 프로세스 생성에는 메모리, 자원을 할당 → cost
• thread는 process 내 자원을 공유하기 때문에 경제성이 좋음
• thread 생성이 process 생성보다 비용이 쌈
• thread 간 Context switching은 process보다 빠름

(4) Scalability

• core가 많더라도 single-threaded process는 한 프로세서에서만 실행됨
• 하지만, thread는 다른 core에서 병렬 수행 가능

 

---

4.2 Multicore Programming

• 멀티 코어를 효율적으로 사용하고 병행성을 향상시키는 방법

Ex) application with four threads

(1) 1 core 4 threads

⇒ processing core가 한 번에 하나의 스레드만 실행; 스레드의 실행이 interleave됨

(2) 2 core 4 threads

⇒ 개별 thread가 각 core에 할당; thread들이 병렬로 실행됨

 

concurrency VS parallelism

• concurrency (병행) : 모든 task가 진행되도록 하여 둘 이상의 task를 지원함; 병렬성 x
• parallel (병렬) : 둘 이상의 task가 동시에 실행; 병렬성 o

⇒ parallelism 없이 concurrency를 가질 수 있다.

⇒ single processor에서는 process들이 concurrently하게 동작하였으나 parallel 하게는 못했고, 마치 그렇게 보이는 것처럼 매우 빠르게 process간 switching 하였음

 

Challenges in programming for multicore system

(1) Identifying tasks
독립된 병행 taks로 나눠지는 영역 찾기

(2) Balance
task들이 균등하게 처리되도록 해야 함; 작업 기여도가 균등하도록

(3) Data splitting
applicationdl task로 나눠지는 것처럼, task가 사용하는 data도 core들에 나눠져야 함

(4) Data dependancy
task에서 접근하는 data는 task들 사이에 의존성이 있는지 확인 필요

(5) Testing and debugging
병렬 수행되는 경우, 다양한 실행 경로가 존재하여 각 모든 경우에 대해서 test, debug 필요

 

Amdahl’s Law

만약 n개의 core를 사용하면 성능이 n배로 증가하는가 ? ⇒ X

즉, core의 개수가 perforamance에 주는 영향은 linear하지 않고 아래와 같이 log 형태로 증가합니다.

해당 사실을 정리한 것이 Amdahl’s law 입니다.

application 내에서 병렬적으로 수행될 수 없는 component들은 어쩔 수 없이 serial하게 수행되어야 하므로 병렬 처리가 불가능합니다.

따라서 이에 대한 비율을 S, core 개수를 N이라 한다면 위와 같은 식으로 speed up의 limit이 정립됩니다.

Two types of Parallelism

(1) Data parallelism : multiple core로 data를 분배

• 동일한 task에 대해서 수행 (동일 연산)
• 동일 Data의 부분 집합을 분배시킴

⇒ 여러 core에 동일 data의 부분 집합을 분배 → 각 core에서 동일 연산 수행

ex) 1부터 10000까지 더하기 → 종속성 없으므로 가능

(2) Task parallelism : multiple core로 task를 분배

• 다른 task를 분배해서 수행
• 동일 data OR 다른 data

⇒ 각 thread별 고유의 연산을 수행함

ex) 더하기, 빼기, 곱하기, 나누기를 같이 해야 하는 경우

(1), (2)는 상호 배타적x, 혼합 사용 가능

 

---

4.3 Multithreading Models

• user thread : user level , 커널 위에서 실행됨, 커널 지원 없이 관리됨, system call 사용 안 하는 thread
• kernel thread : OS에 의해서 직접 관리됨, CPU core를 할당 받는 단위가 됨

user thread와 kernel therad의 개수가 안 맞을 수 있다! → multithreading model 분류

(1) many to one model

(2) one to one model

(3) mant to one model

 

(1) Many to one model

• 한 번에 한 thread만 커널에 접근, 병렬 수행 X

입출력 같은 system call이 필요하면 kernel thread에 접근

• 다중 core의 이점을 활용 못함

(2) One to one model - 가장 많이 씀

• thread가 blocking system call을 하더라도 다른 thread가 실행 가능
• Linux, Window에서 사용
• user thread 생성 시 kernel thread도 생성 → kernel thread의 증가로 시스템 부담

(3) Many to many model

• user thread를 개수가 작거나 같은 kernel thread로 multiplex
• user thread ≥ kernel thread
• 4개보다 8개의 core를 가진 시스템에서 더 많은 kernel thread를 할당 받음

(4) Two-level model (Many to many model 변형)

• user level thread가 kernel thread에 묶일 수 있음
• 가장 flexible하지만, 구현이 어렵다

Effect on Concurrency(동시성)

(1) many to one model

• 개발자가 원하는 만큼 thread를 생성 가능하지만, 병렬 수행 X, 한 번에 하나씩 스케줄됨

(2) one to one model

• 병렬 수행은 가능하지만 너무 많은 thread가 생성되지 않도록 관리 필요

(3) many to many model

• 개발자가 필요한 만큼 user thread 생성; 대응되는 kernel thread가 병렬로 수행함
• 한 thread가 blocking system call 수행 시, kernel이 다른 thread를 실행

 

⇒ 요즘 core 수의 증가 → kernel thread 수 제한의 중요성이 줄어듦 , switching 부담 증가

⇒ 대부분의 OS들은 one to one model을 사용한다.

 

---

4.4 Thread Libraries

• Thread Library : 개발자에게 thread를 생성/관리하기 위한 API 제공

thread library 구현 방법

(1) user-level threads library

kernel의 도움없이, 전적으로 user space에서 thread library 제공

→ 함수 호출은 system call이 아닌, user space에서의 local 함수 호출

(2) kernel-level threads library

OS에 의해 직접 지원되는 kernel-level library 제공

→ API 에서의 함수 호출은 kernel에 대한 system call을 야기함

 

3가지 main Thread Library

(1) Pthread

유닉스 계열의 user level, kernel level 라이브러리 제공

(2) Windows thread library

윈도우 system의 kernel-level 라이브러리 제공

(3) Java thread API

JVM이 host OS에서 실행되므로, host system에서 가용한 thread library로 구현

⇒ host OS에 따라서 Pthread, Window thread library 사용

 

multiple threads 생성 전략

(1) Asynchronous threading (비동기 스레딩)

• 부모는 자식을 생성 후 자신의 실행을 재개함 → 동시/독립적 실행
• data sharing이 거의 없음
• multithreaded server , user interface 구현에 사용 (각 요청에 대해 비동기적으로 처리)

(2) Synchronous threading (동기 스레딩)

• 부모 thread는 모든 자식 thread가 종료되기를 기다림
• 자식 thrad들은 concurrently 실행, 종료되면 부모가 실행
• 자식이 끝나서 종료되면 부모와 join
• 모든 자식들이 join되어야 부모가 실행을 재개함
• data sharing이 많이 일어남 (자식들의 계산 결과를 취합)

부모가 자식의 수행 결과를 모아서 실행 → data sharing 활발

 

Multithreaded C Program using the Pthreads API

공유 메모리 사용

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
int sum; /* this data is shared by the thread(s) */
void *runner(void *param); /* threads call this function */

// 부모 thread
int main(int argc, char *argv[])
{
	pthread t tid; /* the thread identifier */
	pthread attr t attr; /* set of thread attributes */

	/* set the default attributes of the thread */
	pthread attr init(&attr);

	/* create the thread */
	pthread create(&tid, &attr, runner, argv[1]);

	/* wait for the thread to exit */
	pthread join(tid,NULL);

	printf("sum = %d∖n",sum);
}

// 자식 thread
/* The thread will execute in this function */
void *runner(void *param)
{
	int i, upper = atoi(param);
	sum = 0;

	for (i = 1; i <= upper; i++){
		sum += i;
	}
	pthread exit(0);
}

여러 thread 사용 시

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#define NUM_THREADS 10

int sum; /* global data shared by the thread(s) */
void *runner(void *param); /* threads call this function */

int main(int argc, char *argv[]) { /* a single thread(parent) of control begins */
	pthread_ t workers[NUM_THREADS]; /* the thread identifier */
	pthread_attr_t attr; /* set of thread attributes */

	pthread_attr_init(&attr); /* set the default attributes of the thread */
	pthread_create(&workers[0], &attr, runner, argv[1]); /* create a second thread */

	for (int i=0; i<NUM_THREADS; i++){
		pthread_join(workers[i], NULL); /* wait for the thread to exit */
	}	

	printf("sum = %d∖n", sum);
}

void *runner(void *param) { /* The thread(child) will execute */
	int i, upper=atoi(param);
	sum=0;

	for (i=1; i< upper; i++){
		sum += i;
	}
	pthread_exit(0);
}

Multithreaded C Program using the Window API

#include <windows.h> // win API
#include <stdio.h>
DWORD Sum; // 공유 데이터

//자식 스레드
DWORD WINAPI Summation(LPVOID Param) { /* The thread(child) will execute */
	DWORD Upper = *(DWORD*)Param;
	for (DWORD i=1; i<=Upper; i++){
		Sum += i;
	}
	return 0;
}

// 부모 스레드
int main(int argc, char *argv[]) { // parent thread
	DWORD ThreadId; /* global data */
	HANDLE ThreadHandle;
	int Param;
	Param = atoi(argv[1]);

	ThreadHandle = CreateThread( /* create the thread */
	NULL, /* default security attributes */
	0, /* default stack size */
	Summation, /* thread function */
	&Param, /* parameter to thread function */
	0, /* default creation flags */
	&ThreadId); /* returns the thread identifier */

	WaitForSingleObject(ThreadHandle, INFINITE); /* wait for the thread to finish */
	CloseHandle(ThreadHandle); /* close the thread handle */
	printf("sum = %d∖n", Sum); // child 종료 후child 가 계산한sum 출력
}

 

 

---

4.5 Implicit Threading

배경

다중 코어 성장 → 다중 스레드 application 등장 → 처리가 어려움

explicit threading (개발자가 직접 thread 생성/관리)은 너무 복잡하고 어렵다

• thread 생성/관리를 application 개발자 대신 complier/run-time library가 수행

⇒ implicit threading (밑 단에서 thread 생성, 관리를 알아서 해주는 것) 등장

• application 개발자가 병렬 수행되는 task를 구분해야 함
• task는 함수로 작성 → run-time library가 개별 thread로 map함; many to many

 

장점

1. 개발자는 parallel task를 식별만 함
2. library들이 세부적인 thread 생성/관리를 결정함

 

---

4.6 Threading Issues

(1) Semantices of fork() and exec() system calls (복제)

• 스레드가 fork() 호출 시, “모든 스레드를 복제 OR 호출한 스레드만 복제??”

(2) Signal handling (신호 전달)

• signal을 어느 스레드로 전달하는가?
• Synchronous and Asynchronous signal

(3) Thread cancellation of target thread (취소)

• 강제 종료 vs 스스로 종료
• 공유 자원을 update 중이면 기록이 끝내고 종료할 것인가?

(4) Thread-local storage (TLS) (저장소)

• 스레드가 자신만의 data가 필요한 경우

(5) Scheduler Activations (스케줄러)

 

(1) Semantices of fork() and exec() system calls (복제)

• unix의 경우 두 버전의 fork()를 제공 (모든 thread 복제 vs 호출한 thread만 복제)
• fork() 후 자식 스레드가 본인만의 코드를 실행하기 위해 exec()를 호출하는 경우 굳이 모든 thread를 복제할 필요가 없고 해당되는 thread만 복제
• 부모와 똑같은 코드를 실행하는 경우 모든 thread 복제

(2) Signal handling (신호)

• signal : process에게 특정 event가 일어났음을 알림
• synchronous signals : process 내부 이벤트 (같은 process)
• asynchronous signals : process 외부 이벤트

synchronous signal

ex) 불법적인 메모리 접근

• 프로그램이 특정 행동 시 signal이 발생 (불법적인 행동)
• signal을 야기한 연산을 수행한 process에게 전달됨

 

asynchronous signal

ex) 컨트롤 + C

• signal이 실행중인 process의 외부 이벤트에 의해 생성 → 비동기적 전달
• 보통 비동기적 signal은 다른 process로 전달됨

 

Signal Handling

signal 생성 → process에 전달(signal handler) → signal 처리

signal 무시 vs 처리

→ multihread인 경우 signal은 어디로 전달?? → 복잡

1. 문제를 일으킨 thread에게만 전달
2. 모든 thread에게 전달
3. 특정 thread만 전달
4. 모든 signal을 전담해서 수신하는 특정 thread에게 전달

signal type에 따라 배달 방식이 다르다.

• Synchronous signals :내부, signal을 야기한 thread에게 전달
• Asynchronous signals : 외부, 정확히 정해지진 않음,

ex) 컨트롤 + C : 모든 thread에 전달됨

ex) thread가 signal 별로 받거나 block하는 걸 정해둠

→ 특정 thread에게만 전달됨

 

(3) Thread Cancellation (취소)

• thread가 완료되기 전에 강제로 종료

ex) 병렬로 검색하다가 하나가 결과를 찾으면 나머지 thread를 종료

ex) 페이지 로딩 전에 사용자가 취소하는 경우

• target thread : 취소되어야 하는 thread

 

Asynchronous cancellation

• 다른 process에 의해 즉시 종료됨

 

Deferred cancellation (안전하다)

• 지연 시간을 줌, 값을 변경하는 경우 완료될 때까지 기다려줌
• 종료시켜도 되는 지 확인하는 시간을 줌
• target thread가 스스로 종료되어야 하는지를 확인함; 순차적 종료

 

Difficulty with cancellation

만약에 바로 종료 시켜 버릴 때 문제가 되는 경우

• 취소된 thread에 자원이 할당된 경우
• 공유 데이터를 갱신하는 동안 취소되는 경우

⇒ 필요한 시스템 자원이 못 사용하게 될 수도 있음

⇒ deferred cancellation → target therad가 안전하게 취소될 수 있는지 검사

Pthread : 3가지 cancellation mods

off : 취소 x

deferred : 안전할 때 취소, default임

asynchronous : 즉시 취소

 

(4) Thread-local Storage

thread는 원래 process 내 자원을 공유하지만, thread 자신만의 data가 필요하다

⇒ Thread-local Storage (TLS)에 저장

ex) 각 트랜잭션을 독립된 thread로 서비스하는 경우

→ 트랜잭션 별 id 부여

→ thread와 id를 연관시키기 위해 TLS 사용

• TLS는 지역 변수가 아니다. TLS 데이터는 전체 함수 호출에 걸쳐 보임
• thread 별로 고유한 static data임 ⇒ 해당 scope에서만 접근 가능
• program에서 제공해줘야 함

 

(5) Scheduler Activations

• kernel과 thread library 간 통신을 고려해야 함
• many to many model , two-level model이 사용

⇒ user thread는 4개, kernel thread는 3개 → 어떻게 매칭되는가?

⇒ LWP 자료구조

• Light Weight Process (LWP) : user와 kernel hread 사이 중재하는 자료구조
• application(user thread)입장에서는 LWP가 마치 user thread를 스케줄하는 processor처럼 보임 (virtual processor)
• 각 LWP는 하나의 kernel thread에 부착됨

⇒ kernel thread의 수를 동적으로 조절

아래 그림과 같이 kernel thread당 LWP를 둬서 멀티 플랙싱과 매핑을 수행하게 한다.

Example

5개의 다른 파일을 read하는 application → 5개의 LWP 필요

→ LWP가 4개라면, 5번째 요청은 기다려야 함

→ 밑 단에 있는 core에 실제로 연결돼서 처리하는 것은 kernel-thread이고, 윗 단에서 user가 접근할 때는 가상의 processor인 LWP로 접근

→ 4개의 LWP를 동시 실행, 1개는 대기

 

shceduler activation

• user-thread library와 kernel간 통신
• upcall : kernel이 application에게 event를 알림

1. kernel이 applicaiton에 LWP 제공
2. application은 user thread를 가용한 LWP로 스케줄함
3. kernel은 application에게 특정 event에 대해 알림

⇒ 한 kernel이 block되면 (새 LWP를 할당하여) 다른 kernel이 실행 가능하도록 함

 

Upcall 발생

• lwp입장에서 필요한 kernel thread의 각종 정보를 알리기 위함
• 밑에서 부터 event가 발생하여 올라가면서 처리 (I/O 시작 or 끝)

1. application thread가 block되려 할 때 upcall을 일으키는 event를 발생함
2. kernel이 application에게 upcall로 알림
3. kernel은 application에 새로운 LWP를 할당함

 

Upcall Handler

• application은 새로운 LWP에서 upcall handler를 실행함; block된 thread의 상태를 저장, 사용하던 LWP를 반환
• Upcall handler는 새로운 LWP에 다른 thread를 스케줄함

<과정>

1. Upcall handler가 새로운 LWP에서 실행되어 block된 thread의 상태를 저장하고,
2. 이것이 사용하던 LWP를 반환하며,
3. 새로운 LWP에 다른 thread를 스케줄함

• Block된 thread가 기다리던 event가 일어나면 kernel은 새로운 upcall로 block된 thread가 계속 실행될 수 있음을 알림
• kernel이 새 LWP를 할당하거나 다른 것에서 선점하여 실행함
• unblocked thread로 표시한 후, LWP에서 실행하기 위해 스케줄함