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 변수 : 단일 함수 호출 중에만 표시
profile
숭실대학교 컴퓨터학부 21

0개의 댓글