[OS 공룡책] Ch04. Threads and Concurrency

Chapter 4: Threads and Concurrency

Overview

Multithreaded Architecture

• thread
  • process 내의 하나의 function을 맡음
  • process : 독립된 공간 thread : 독립된 공간 X, 독립된 control flow(PC값)
    
• text + data + heap + stack + stack
  • stack, register만 하나 더 생김
  • resource 절약
• shared memory, message passing없이 자료 공유 가능
  • 장점이자 단점
  • synchronization 문제 (→ 5장)

Benefits of Multithreading ⭐️

• Responsiveness
  • 빠른 응답성
• Resource Sharing
• Economy
  • 시공간 절약
• Scalability
  • multiprocessor architecture의 장점 얻음

Multicore Programming

Concurrency vs. Parallelism

1. Parallelism : 진짜 동시에 실행
   • Bit-level ← H/W
     • 16bit, 32bit, 64bit 컴퓨터
     • 동시에 처리하는 자료의 크기 증가
   • Instruction-level ← H/W
     • pipe
     • fetch, decode할 때 다음 거 fetch
   • Thread-level ← S/W
     • thread별로 독립적인 control flow 지원
2. Concurrency : 동시에 실행되는 것처럼 보임
   • scheduling

Multicore Programming

• Programming Challenge

  • Task dividing activities → 어떤 영역이 separate task인지 찾기
    
  • Load balancing
  • Data splitting → separate core에 실행될 수 있는 data divide
    
  • Minimizing data dependency → 작업 실행이 종속성에 맞게 동기화됨
    
  • Testing and debugging → 어려워짐
    

• Parallelism

  • 동시에 두 개 이상의 작업 수행

  1. Data parallelism

     

     • 동일한 데이터의 하위집합을 여러 코어에 분산
     • 각 코어에서 동일한 작업 수행

  2. Task parallelism

     

     • 코어 간에 스레드 분산
     • 각 스레드가 고유한 작업 수행

• single processor(core)의 concurrency = scheduler

Amdahl’s Law

• 암달의 법칙 : 코어는 무조건 많을 수록 좋은가?

  

  • S : serial portion

  • N : processing cores

    → 100% parallel portion이 아니라면 core의 개수는 큰 의미 X

• portion

  1. Parallel portion 병렬

     • 컴파일러 최적화
     • thread 코딩하면 100%

     → 코어가 N개면 Parallel은 N배 성능 향상 기대

  2. Serial portion 직렬

     • 컴파일러가 최적화할 수 없는 부분의 코드
     • S = 0.25, N = 2, sppedup = 1.6 S = 0.25, N = 4, sppedup = 2.28 → N배 향상되지는 않음
       

User Threads & Kernel Threads

1. User threads
   • user-level threads library 활용
   • POSIX Pthreads, Windows threads, Java threads
2. Kernel threads
   • Kernel이 지원
   • Windows, Solaris, Linux, Mac OS X

• user threads, kernel threads 간의 Multithreading model
  • Many-to-One
  • One-to-One
  • Many-to-Many

Multithreading Models

Many-to-One Model

• 하나의 thread blocking → 모두 차단
• 한 번에 kernel에 하나만 존재 가능 → muticore system에서 병렬로 실행 X
  
• 현재 잘 사용 X
  • Solaris green thread library
  • Java 초기 버전 thread

One-to-One Model

• user thread 생성시, kernel thread 생성
• Many-to-One보다 Concurrency 향상
• overhead → process당 thread 수 제한
• Linux, Solaris 9 and later

Many-to-Many Model

• 다대일, 일대일의 장점을 취한 접근법 → 여러 user thread들이 더 적은 수의 kernel thread에 매핑
  
• 충분한 수의 kernel thread를 생성
• 원하는 수 만큼의 user thread 생성 → 이에 대응하는 kernel thread들이 다중 처리기에서 병렬 수행
  

Two-level Model

• M:M + 1:1 모델 혼합 → 하나의 kernel thread에 하나의 user thread 바인딩 가능 !
  
• LWP (Lightweight Process)
  • 일반적으로 user thread와 kernel thread 간의 중간 데이터 구조 사용
  • virtual procesor : user thread를 실행하도록 예약할 수 있는 processor
  • kernel thread에 연결된 각 LWP

Thread Libraries

POSIX Pthreads

#include <pthread.h>
#include <stdio.h>

int sum;   // thread에 의해 공유되는 변수
void *runner(void *param) {
		int upper = atoi(param);
		sum = 0;
		for (int i = 1; i <= upper; i++) sum += i;
		pthread_exit(0);
}

// $gcc -pthread test.c
int main(int argc, char *argv[]) {
		pthread_t tid;   //thread 식별자
		pthread_attr_t attr;   //thread attritubute 집합

		pthread_attr_init(&attr);   //default attributes 얻기
		pthread_create(&tid, &attr, runner, argv[1]);   //thread 생성
		pthread_join(tid, NULL);   //thread 끝날 때까지 기다리기

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

pid_t pid;
pid = fork();
if (pid == 0) {
		fork();
		thread_create(...);
}
fork();
//process 6개, thread 2개

Windows Threads

#include <windows.h>
#include <stdio.h>

DWORD sum;   // thread에 의해 공유되는 변수
DWORD WINAPI Summation(LPVOID param) {
		DWORD Upper = *(DWORD*)Param;
		for (DWORD i = 0; i <= Upper; i++) sum += i;
}

int main (int argc, char *argv[]) {
		DWORD ThreadId;
		HANDLE ThreadHandle;
		int Param;
		
		ThreadHandle = CreateThread(
				NULL,   // security attributes
				0,   // stack size
				Summation,   // thread function
				&Param,   // thread function parameter
				0,   // creation flags
				&ThreadId);   // thread 식별자 리턴
		if (ThreadHandle != NULL) {
				WaitForSingleObject(ThreadHandle, INFINITE);
				CloseHandle(ThreadHandle);
				printf("sum = %d\n", sum);
		}
}

Java Threads

• JVM에 의해 관리
• thread 생성하는 방법
  • thread class 상속받기
  • Runnable interface 구현하기

class Summation implements Runnable {
		public Summation(int upper, Sum sumValue) { ... }
		public void run() { ... }
}
public class Driver {
		public static void main(String[] args) {
				Thread thrd = new Thread(new Summation(..));
				thrd.start();
				thrd.join();
		}
}

Implicit Threading

Implicit Threading

• Explicit threading
  • fork()
  • join() : thread 끝날 때까지 대기
• thread 수가 증가함에 따라 explicit thread의 프로그램 정확도 어려워짐
• 프로그래머가 아닌 컴파일러 및 런타임 라이브러리가 수행하는 thread 생성 및 관리
• 3가지 주요 방법
  • Thread Pools
  • OpenMP

Thread Pools

• pool : 여러개의 thread 저장소
• 일반적으로 새로운 thread 생성하는 것보다 기존 thread에서 요청을 처리하는 속도가 더 빠름
• 응용프로그램의 thread 수를 pool 크기로 바인딩
• 수행할 작업, 작업 생성 역할 분리 → 작업이 주기적으로 실행되도록 예약
  
• Windows API : Thread Pools 지원

  DWORD WINAPI PoolFunction(AVOID Param) {
  		...
  }

OpenMP

• C/C++에서 쉽게 병렬처리할 수 있게
• parallel region 지정 → 해당 부분 병렬처리

  #include <stdio.h>
  #include <omp.h>
  
  // $gcc -fopenmp test.c
  int main(int argc, char *argv[]) {
  		omp_set_num_threads(4);   // 4개의 thread 생성
  		#pragma omp parallel
  		{
  				... //parallel region
  				printf("OpenMP thread: %d\n", omp_get_thread_num());
  		}
  }

Threading Issues

fork(), exec() System call

• 멀티 스레드 프로그램에서 fork() 시스템 호출 실행한다면?

  • 모든 thread 복제?

  • 하나의 main thread만 가지는 프로세스로 복제?

    → 일부 Unix 시스템에서는 두 가지 버전 모두 지원

• Exec() 시스템 호출은?
  • 기존 thread 모두 무시, 새로운 프로그램으로 대체
• Fork() 이후 exc() 호출 → 모든 thread 복제 X
• Fork() 이후 exec() 호출 X → 모든 thread 복제가 의미 있음

Signal Handling

• Signal
  • 프로세스에게 어떤 사건이 일어났음을 알림
  1. Synchronous signal
     • 어떤 사건을 처리하기 위해 발생
     • ex. 불법적인 메모리 접근, 0으로 나누기
  2. Asynchronous signal
     • 임의 시점에 발생
     • ex. 인터럽트(ctrl+C), timer 만료
• Signal 전달 특정 사건 → Signal 생성 → 프로세스에게 전달 → 반드시 처리(handling)
  
• handler
  1. 디폴트 시그널 처리기
  2. 사용자 정의 시그널 처리기
• single thread program
  • 프로세스 레벨에서 signal 처리
  • 잠시 중단 → handling → 다시 재개
• multi thread program 모든 thread 전달 / 선택적 전달 / 특정 thread가 모든 signal 전달받도록 지정
  

Thread Cancellation

• target thread : 취소된 thread

  pthread_t tid;
  pthread_create(&tid, 0, worker, NULL);
  ...
  pthread_cancel(tid);

  • Linux : thread cancellation을 signal을 통해 처리

1. Asynchronous cancellation
   • target thread 즉시 제거
2. Deferred cancellation
   • 주기적으로 제거해야 하는지 확인

Thread-Local Storage (TLS)

• 각 thread의 고유한 데이터 복사본 저장소
• thread 작성 프로세스에 대한 제어권이 없는 경우 유용 → Thread Pools을 사용하는 경우
  
• TLS : 함수 호출 전반에 걸쳐 표시 ≠ local 변수 : 단일 함수 호출 중에만 표시