슬라이드 1

Thread Programming Chapter #14

스레드개요 POSIX Thread APIs Basic Thread APIs 스레드프로그램설계 스레드동기화 Deadlock Problem 강의목차 2

스레드 (Thread) 스레드 (Thread) (1) 하나의프로그램을병행실행하기위해나눌수있는작은크기의실행단위 CPU 스케줄링객체 하나의프로세스는하나또는여러개의스레드로구성된다 프로세스 실행중인프로그램전체 스레드 실행중인프로그램의하나의함수 e.g) 프로젝트팀 vs. 프로젝트팀원 효율적인병행실행을지원하기위한구조적모델을제공 다중프로세스 (multi-process) 구조는프로세스생성및프로세스스위칭, 프로세스간의통신등에의한오버헤드가크다 3

Process vs. Thread 스레드 (Thread) (2) 자원할당단위 Process 프로세스간상호독립 IPC 를이용한통신 통신오버헤드가크다 프로세스생성및문맥교환오버헤드가크다 프로세스스케줄링제어가제약적 Thread 프로그램실행단위 스레드간에프로세스의자원을공유 자원공유를통한통신 통신오버헤드가적다 스레드생성및문맥교환오버헤드가적다 스레드스케줄링제어가용이 4

스레드 (Thread) (3) 5

스레드 (Thread) (4) Single Threaded and Multithreaded Process Models Thread Control Block contains a register image, thread priority and thread state information 6

스레드 (Thread) (5) Thread Control Block(TCB) 스레드생성및제어정보를가진자료구조 e.g) PCB(Process Control Block) 구성내용 : Thread ID Register Image Signal Mask Scheduling Priority Thread State 일부내용는스레드가생성될때에프로세스로부터상속 7

스레드유형 스레드 (Thread) (6) 사용자수준스레드 (ULT: User-Level Thread) 커널수준스레드 (KLT: Kernel-Level Thread) 경량프로세스 (LWP: Light-Weight Process) 8

스레드 (Thread) (7) 사용자수준스레드 (ULT) OS( 커널 ) 은스레드를지원하지않음 프로세스가실행단위 응용프로그램이 thread library 을이용하여쓰레드를생성하여관리한다 Thread switching 은 kernel mode privileges 을요구하지않는다 (no mode switch) 쓰레드간의실행스케줄링은응용프로그램에의해제어가능 예 : Linux O.S 9

스레드 (Thread) (8) 커널수준스레드 (KLT) O.S( 커널 ) 이스레드를생성, 관리한다 커널은프로세스와쓰레드에대한문맥정보 (context information) 을유지한다 커널이쓰레드간의전환을수행한다 커널이쓰레드스케줄링을수행한다 thread library 가없으며커널스레드기능에대한 API 가지원된다 예 : Windows NT and OS/2 10

스레드 (Thread) (9) 결합형스레드 스레드생성은응용프로그램에의해수행 응용프로그램에의해사용자수준스레드와커널레벨스레드간의맵핑 스레드스케줄링과동기화가사용자공간에서수행 경량프로세스 (Light-Weight Process) 사용자수준스레드와커널수준스레드간의맵핑객체 예 : Solaris 11

스레드 (Thread) (10) 경량프로세스 (Light Weight Process) Process 2 is equivalent to a pure ULT approach Process 4 is equivalent to a pure KLT approach We can specify a different degree of parallelism (process 3 and 5) 12

Pthread APIs (1) IEEE POSIX Section 1003.1c IEEE( Institute of Electric and Electronic Engineering ) POSIX ( Portable Operating System Interface ) Pthread is a standardized model for dividing a program into subtasks whose execution can be interleaved or run in parallel Specifics are different for each implementation Mach Threads and NT Threads Pthread of Linux is kernel level thread implemented by clone() system call 13

Pthread APIs (2) The subroutines which comprise the PthreadsAPI can be informally grouped into three major classes: 1. Thread management 2. Mutexes The first class of functions work directly on threads -creating, detaching, joining, etc. Includes functions to set/query thread attributes The second class of functions deal with synchronization, calleda "mutex", which is an abbreviation for "mutual exclusion". Mutex functions provide for creating, destroying, locking and unlocking mutexes. Mutex attribute functions set or modify attributes associated with mutexes. 3. Condition variables The third class of functions address communications between threads that share a mutex. They are based upon programmer specified conditions. And this class includes functions to create, destroy, wait and signal based upon specified variable values. Functions to set/query condition variable attributes are also included. 14

Pthread APIs (3) The Pthreads API contains over 60 subroutines. focus on a subset of these -specifically, those which are most likely to be immediately useful to the beginning Pthreads programmer. The pthread.h header file must be included in each source file using the Pthreads library. The current POSIX standard is defined only for the C language. 15

Basic Pthreads APIs Pthread APIs (4) pthread_create(): thread를생성 pthread_exit(): process를종료하지않고, Thread만종료 pthread_join(): thread 수행이종료되기를기다림 pthread_kill(): thread에게 signal을보냄 pthread_detach(): thread가종료시에자원을해제하도록설정 pthread_equal(): 두 thread ID가동일한지검사 pthread_self(): 자신의 thread ID를얻는다 pthread_cancel(): 다른 thread의수행을취소 16

Pthread APIs (5) Pthreads API program skeleton 다음의두개의헤드파일을포함 <pthread.h> <sched.h> Compilation Options gcc D_REENTRANT lpthread o x x.c gcc mt o x x.c Option -mt = D_REENTRANT lpthread 17

Pthread APIs (6) POSIX 스레드지원모드확인 // ex14-1.c #include <stdio.h> #include <unistd.h> #include <pthread.h> int main(void) { printf( POSIX version is set to %ld\n, _POSIX_VERSION); if (_POSIZ_VERSION < 199506L) { if (_POSIX_X_SOURCE >= 199506L) { printf( Sorry, your system doesn t support POSIX.1c threads\n ); else { printf( Try again with D_POSIX_C_SOURCE=199506L\n ); else { printf( Your system support POSIX.1c thread,\n ); #ifdef _POSIX_THREAD_PRIORITY_SCHEDULING printf( including support for thread priority scheduling\n ); #else printf( but does not support thread priority scheduling\n ); #endif exit(exit_success); 18

Basic Pthread APIs (1) POSIX 스레드생성 Initially, your main() program comprises a single, default thread. All other threads must be explicitly created by the programmer POSIX thread 생성 API #include <pthread.h> int pthread_create(pthread_t* tid_p, const pthread_attr_t* attr, void* (*fp)(void*), void *argp) /* pthread_t* tid_p: 생성된스레드 ID 반환변수 */ /* const pthread_attr_t* attr: 생성된스레드에설정되는속성값 */ /* void* (*fp)(void*): 생성된스레드가실행하는함수포인터 */ /* void *argp: 스레드가실행하는함수에전달되는매개변수 */ /* 정상종료하면 0 를반환하고, 에러가발생한경우에는 -1 를반환한다. 외부변수 errno 에에러를나타내는값을설정한다 */ Creates a new thread and makes it executable Once created, threads are peers, and may create other threads 19

Basic Pthread APIs (2) POSIX 스레드생성 ( 계속 ) POSIX 스레드모드 연결된스레드 (joinable thread) Main 스레드와연결된스레드로서부모와자식관계를가짐 Main 스레드는비분리스레드가종료할때까지대기하여야함 분리된스레드 (detached thread) Main 스레드와의연결이끊어진스레드로서독립적인동작모드를가짐 Main 스레드는분리된스레드에대해종료를대기할필요가없다 분리된스레드생성 pthread_attr_detachstate() 를이용하여속성값을 detach mode 로설정한후에스레드를생성 pthread_detach() 호출하여생성후에분리 20

Basic Pthread APIs (3) POSIX 스레드속성다루기 POSIX 스레드속성객체초기화및제거 #include <pthread.h> int pthread_attr_init(pthread_attr_t *attr) int pthread_attr_destroy(pthread_attr_t *attr) pthread_attr_init() 파라미터를통해전달된스레드속성객체를초기화한다 pthread_attr_destroy() 초기화된스레드속성객체를제거한다 21

Basic Pthread APIs (4) POSIX 스레드속성다루기 ( 계속 ) POSIX 스레드속성검사및설정 속성 검사 APIs 설정 APIs 경쟁영역 pthread_attr_getscope pthread_attr_setscope 스택크기 pthread_attr_getstacksize pthread_attr_setstacksize 스택주소 pthread_attr_getstackaddr pthread_attr_setstackaddr 분리상태 pthread_attr_getdetachstate pthread_attr_setdetachstate 스케줄정책 pthread_attr_getschedpolicy pthread_attr_setschedpolicy 스케줄파라미터 pthread_attr_getschedparam pthread_attr_setschedparam 22

Basic Pthread APIs (5) POSIX 스레드속성다루기 ( 계속 ) pthread_attr_getxxx(pthread_attr_t *attr, void* attrval_p) 1 st parameter 속성값을검사할속성객체 2nd parameter 검사한속성값을저장한변수포인터 검사 API 에따라지정되는변수유형이달라진다 pthread_arrt_setxxx(pthread_attr_t *attr, int attr_type) 1 st parameter 설정할속성값을가지고있는속성객체 2nd parameter 설정할속성값의종류를지정하는상수 예 : pthread_attr_t *lpattr; pthread_attr_setscope(lpattr, PTHREAD_SCOPE_SYSTEM); 23

Basic Pthread APIs (6) POSIX 스레드속성다루기 ( 계속 ) POSIX 스레드 scope 속성 스레드에대한관리영역범위를지정 PTHREAD_SCOPE_SYSTEM 사용자수준스레드 스레드라이브러리를통해관리하며스케줄링수행 Linux O.S PTHREAD_SCOPE_PROCESS 커널수준스레드 커널에의해관리되며스케줄링이루어짐 Solaris O.S 24

Basic Pthread APIs (7) POSIX 스레드속성다루기 ( 계속 ) POSIX 스레드 scope 속성검사및설정 #include <pthread.h> #include <stdlib.h> #include <stdio.h> int main() { pthread_attr_t pattr; int scope; pthread_attr_init(&pattr); pthread_attr_setscope(&pattr, PTHREAD_SCOPE_PROCESS); pthread_attr_getscope(&pattr, &scope); if (scope == PTHREAD_SCOPE_SYSTEM) { printf("user mode thread\n"); else if (scope == PTHREAD_SCOPE_PROCESS) { printf("kernel mode thread\n"); return 1; 25

Basic Pthread APIs (8) POSIX 스레드속성다루기 ( 계속 ) POSIX 스레드 detach 속성검사및설정 PTHREAD_CREAT_JOINABLE / PTHREAD_CREAT_DETACHED #include <pthread.h> #include <stdlib.h> #include <stdio.h> pthread_attr_t attr; void *test(void *a) { int policy; printf("thread Create\n"); pthread_attr_getdetachstate(&attr, &policy); if (policy == PTHREAD_CREATE_JOINABLE) { printf ("Join able\n"); else if (policy == PTHREAD_CREATE_DETACHED) { printf ("Detache\n"); int main() { int status; pthread_t p_thread; pthread_attr_init(&attr); // JOINABLE 상태로변경하고자할때 pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE); if (pthread_create(&p_thread, NULL, test, (void *)NULL) < 0) { exit(0); pthread_join(p_thread, (void **)&status); return 0; 26

POSIX 스레드종료 Basic Pthread APIs (9) There are several ways in which a pthread may be terminated: The thread returns from its starting function The thread makes a call to the pthread_exit function The thread is canceled by another thread via the pthread_cancel function The entire process is terminated due to a call to either the exec or exit Pthread 스레드종료 API #include <pthread.h> int pthread_exit(void *status) Cleanup handler 함수가등록되어있으면이함수를호출하여 cleanup 작업을수행한다 27

Basic Pthread APIs (10) POSIX 스레드종료 ( 계속 ) Routines: pthread_exit(void* status) If main() finishes before the threads it has created, and exits with pthread_exit(), the other threads will continue to execute. Otherwise, they will be automatically terminated when main() finishes. status: The programmer may optionally specify a termination status, which is stored as a void pointer for any thread that may join the calling thread. Cleanup: the pthread_exit() routine does not close files; any files opened inside the thread will remain open after the thread is terminated Recommendation: Use pthread_exit() to exit from all threads...especially main(). 28

Basic Pthread APIs (11) 예제 - POSIX 스레드생성및종료 // ex14-2.c #include <pthread.h> #define NUM_THREADS 5 void *PrintHello(void* threadid) { printf(" n%d: Hello World! n", threadid); pthread_exit(null); int main (int argc, char *argv[]) { pthread_t threads[num_threads]; int rc, t; for(t=0; t < NUM_THREADS; t++) { printf("creating thread %d n", t); rc= pthread_create(&threads[t], NULL, PrintHello, (void *)t); if (rc) { printf("error; return code from pthread_create() is %d n", rc); exit(-1); pthread_exit(null); 29

Basic Pthread APIs (12) POSIX 스레드종료대기 Main 스레드는연결된스레드에대해서는실행을종료할때까지대기하여야한다 Process에대한 fork() & wait() 와유사하게동작 스레드종료에따른정리작업을수행 POSIX 스레드종료대기 API #include <pthread.h> int pthread_join(pthread_t th, void **thread_return) /* pthread_t th: 기다릴 (join) 할스레드식별자 */ /* void **thread_return: 스레드의반환값. thread_return 이 NULL 이아닐경우해당포인터로스레드반환값을받아올수있다 */ /* 일반적으로자식스레드를생성한스레드에서자식스레드가종료대기함으로써자식스레드의자원을회수하도록한다 */ 30

Basic Pthread APIs (13) POSIX 스레드종료대기 ( 계속 ) // ex14-3.c #include <pthread.h> #include <stdio.h> #include <unistd.h> #include <stdlib.h> // 쓰레드함수 // 1 초를기다린후파라미터 ^2 을반환한다. void *t_function(void *data) { int num = *((int *)data); printf("num %d\n", num); sleep(1); return (void *)(num*num); // pthread_exit((void *)(num*num)); int main() { pthread_t p_thread; int thr_id; int status; int a = 100; thr_id = pthread_create(&p_thread, NULL, t_function, (void *)&a); if (thr_id < 0) { perror("thread create error : "); exit(0); // 스레드 p_thread 가종료되길기다렸다가 // 종료반환값을가져온다. pthread_join(p_thread, (void *)&status); printf("thread join : %d\n", status); return 0; 31

Basic Pthread APIs (14) POSIX 스레드분리 POSIX 스레드분리 API #include <pthread.h> int pthread_detach(pthread_t th, void **thread_return) /* pthread_t th: main 스레드에서분리할스레드식별자 */ /* 스레드가 main 스레드로부터 detach 되었을경우해당 (detach 된 ) 스레드가종료하면 pthread_join() 을호출하지않더라도즉시모든자원이해제된다 */ /* pthread_attr_setdetachstate() 호출를통해 pthread_create 호출시에스레드가 detach 되도록할수도있다 */ 분리된스레드에대해서는 main 스레드가종료대기를수행할필요가없다 32

Basic Pthread APIs (15) POSIX 스레드분리 ( 계속 ) // ex14-4.c #include <pthread.h> #include <stdio.h> #include <unistd.h> #include <stdlib.h> // 쓰레드함수 // 1 초를기다린후파라미터 ^2 을반환한다. void *t_function(void *data) { char a[100000]; int num = *((int *)data); printf("thread Start\n"); sleep(5); printf("thread end\n"); int main() { pthread_t p_thread; int thr_id; int status; int a = 100; printf( Before thread \n ); thr_id = pthread_create(&p_thread, NULL, t_function, (void *)&a); if (thr_id < 0) { perror("thread create error : "); exit(0); // 스레드 p_thread 를 detach 시킨다 pthread_detach(p_thread); pause(); return 0; 33

Basic Pthread APIs (16) POSIX 스레드 cleanup handler 등록및제거 Cleanup handler pthread_exit() 호출에의해스레드실행이종료될때에호출 스레드실행시에할당된자원을반환하거나 mutex 잠금등을해제하는등스레드정리작업을수행 Cleanup handler 등록및제거 API #include <pthread.h> void pthread_cleanup_push(void (*routine)(void*), void *arg) void pthread_cleanup_pop(int execute) /* void (*routine)(void*): 등록하고자하는 cleanup handler */ /* void *arg: cleanup handler 파라미터 */ /* int execute: 이값이 0 이면등록된 cleanup handler 를제거하고, 0 이아닌값이면 cleanup handler 를실행한후에제거한다 */ 34

Basic Pthread APIs (17) POSIX 스레드 cleanup handler 등록및제거 ( 계속 ) // ex14-3.c #include <pthread.h> #include <stdio.h> #include <unistd.h> #include <stdlib.h> #include <sys/types.h> // 쓰레드함수 char *mydata; void cleanup(void *); void *t_function(void *data) { int num = *((int *)data); int i = 0, a = 1; pthread_cleanup_push(cleanup, (void *) &a); mydata = (char *)malloc(1000); while(1) { if (i == 3) { pthread_exit(0); return 1; printf("loop %d\n", i); i++; sleep(1); pthread_cleanup_pop(0); int main() { pthread_t p_thread; int thr_id; int status; int a = 100; thr_id = pthread_create(&p_thread, NULL, t_function, (void *)&a); if (thr_id < 0) { perror("thread create error : "); exit(0); pthread_join(p_thread, (void **)&status); printf("join finish\n"); // cleanup handler void cleanup(void *myarg) { printf("thread is clean up\n"); printf("resource free\n"); free(mydata); 35

Basic Pthread APIs (18) POSIX 스레드시그널처리 POSIX 스레드는시그널을공유한다 프로세스에시그널이전달되면프로세스가생성한모든스레드에시그널이전달된다 POSIX 스레드의시그널처리 스레드는시그널마스킹을통해특정시그널만처리가능 스레드는다른스레드에게시그널전송이가능 스레드는시그널전달을동기적으로대기가능 시그널처리관련 APIs #include <pthread.h> #include <signal.h> int pthread_sigmask(int mode, sigset_t* newmask, sigset_t* oldmask) int pthread_kill(pthread_t thread, int signo) int sigwait(const sigset_t *sigmask, int *sig); 36

Basic Pthread APIs (19) POSIX 스레드시그널처리 ( 계속 ) pthread_sigmask() 1 st parameter masking mode Mode SIG_BLOCK SIG_UNBLOCK SIG_SETMASK 의미 newmask 인자에포함된시그널을스레드의신호마스크에추가 newmask 인자에포함된시그널을스레드의신호마스크로부터제거 newmask 인자에포함된시그널을스레드의신호마스크로데체 37

Basic Pthread APIs (20) POSIX 스레드식별자검사 스레드식별자검사 API #include <pthread.h> pthread_t pthread_self(void) /* 현재스레드의식별자를반환한다 */ 38

스레드프로그램설계 (1) In order for a program to take advantage of pthreads, it must be able to be organized into discrete, independent tasks which can execute concurrently Splitting CPU-based (e.g., computation) I/O-based (e.g., read data block from a file on disk) Potential parallelism The property that statements can be executed in any order without changing the result 39

스레드프로그램설계 (2) Reasons for exploiting potential parallelism Obvious : make a program run faster on a multiprocessor Overlapping I/O Parallel executing of I/O-bound and CPU-bound jobs e.g.) word processor -> printing & editing Asynchronous events If one more tasks is subject to the indeterminate occurrence of events of unknown duration and unknown frequency, it may be more efficient to allow other tasks to proceed while the task subject to asynchronous events is in some unknown state of completion. e.g.) network-based server 40

스레드프로그램설계 (3) 41

스레드프로그램설계 (4) Common models for threaded programs Manager/worker a single thread, the manager assigns work to other threads, the workers. Typically, the manager handles all input and parcels out work to the other tasks. Two forms of the manager/worker model are common: static worker pool and dynamic worker pool. Pipeline a task is broken into a series of sub operations, each of which is handled in series, but concurrently, by a different thread. An automobile assembly line best describes this model. Peer similar to the manager/worker model, but after the main thread creates other threads, it participates in the work. 42

스레드프로그램설계 (5) Manager/worker Manage r Workers Thread Pool Program 43

스레드프로그램설계 (6) Manager/worker ( 계속 ) 예제 #1 manager/work model mprogram main ( void ) /* the manager */ { forever { get a request; switch request case X : pthread_create( taskx); case Y : pthread_create( tasky);.. taskx() /* Workers processing requests of type X */ { perform the task, synchronize as needed if accessing shared resources; done; 44

스레드프로그램설계 (7) Manager/worker ( 계속 ) Thread Pool A variant of the Manager/worker model The manager could save some run-time overhead by creating all worker threads up front 예제 #2 - manager/worker model with a thread pool main ( void ) /* the manager */ { for the number of workers pthread_create(.pool_base ); forever { get a request; place request in work queue; signal sleeping threads that work is available; 45

스레드프로그램설계 (8) Manager/worker ( 계속 ) 예제 #2 ( 계속 ) pool_base() /* All workers */ { forever { sleep until awoken by boss; dequeuea work request; switch { case request X : taskx(); case request Y : tasky();. 46

스레드프로그램설계 (9) Pipeline Model Threads Program 47

스레드프로그램설계 (10) Pipeline Model - 예제 main (void) { pthread_create( stage1 ); pthread_create( stage2); wait for all pipeline threads to finish; do any clean up; stage1 () { forever { get next input for the program; do stage1 processing of the input; pass result to next thread in pipeline; 48

스레드프로그램설계 (11) Pipeline Model 예제 ( 계속 ) stage2 () { forever { get input from previous thread in pipeline; do stage2 processing of the input; pass result to next thread in pipeline; stagen () { forever { get input from previous thread in pipeline; do stagen processing of the input; pass result to program output; 49

Peer Model 스레드프로그램설계 (12) Thread Pool Program 50

스레드프로그램설계 (13) Peer Model - 예제 main (void) { pthread_create( thread1 task1 ); pthread_create( thread2 task2 ); signal all workers to start; wait for all workers to finish; do any clean up; task1 () { wait for start; perform task, synchronize as needed if accessing shared resources; done; 51

스레드동기화 (1) Creating thread is the easy part. But, it s harder to get them to share data properly 하나의프로세스내의스레드들은프로세스의주소공간을공유한다 Sharing global variables is dangerous two threads may attempt to modify the same variable at the same time 52

Race Conditions 스레드동기화 (2) 두개이상의스레드가동시에동일한자원을접근할수있다 53

스레드동기화 (3) 스레드동기화도구 (Synchronization Tools) pthread_join function Allows one thread to suspend execution until another has terminated Mutex lock functions Mutually exclusive lock Only one thread at a time can hold the lock and access the data it protects Condition variable functions An event in which threads have a general interest Pthread library provides ways for threads both to express their interest in a condition and to signal that an awaited condition has been met 54

스레드동기화 (4) 스레드동기화도구 (Synchronization Tools) Reader/writer exclusion Allow multiple threads to read data concurrently but any thread writing to the data has exclusive access Semaphores POSIX real-time extensions(posix.1b) 55

Mutex Lock (1) Mutual exclusion (mutex) Exclusive access to data When one thread has exclusive access to data, other threads can not simultaneously be accessing the same data Critical section Exclusive access to the code paths or routines that access data How large does a critical section have to be? Even a single statement Single statement is no longer atomic at the hardware level Should always use mutexesto ensure a thread s shared data operations are atomic with respect to other threads 56

Mutex Lock (2) Using mutex lock in pthread Create and initialize a mutex for each resource you want to protect, like a record in a database When a thread must access the resource, use pthread_mutex_lock to lock the resource s mutex Only one thread at a time can lock the mutex, and others must wait When the thread is finished with the resource, unlock the mutex by calling pthread_mutex_unlock 57

Mutex Lock (3) Creating & destroying mutex variables #include <pthread.h> int pthread_mutext_init(pthread_mutex_t *muxp, pthread_mutextattr_t *attrp) int pthread_mutext_destroy(pthread_mutex_t *muxp) Mutex variable 은 declare 후, 반드시초기화되어야한다 Mutex variable 초기화방법 Statically, declare 시 : pthread_mutex_t mymutex= THREAD_MUTEX_INITIALIZER; Thread 실행중 : pthread_mutex_init(mutex, attr) 호출 The mutex is initially unlocked 58

Using mutex lock Mutex Lock (4) #include <pthread.h> int pthread_mutext_lock(pthread_mutex_t *muxp) int pthread_mutext_trylock(pthread_mutex_t *muxp) int pthread_mutext_unlock(pthread_mutex_t *muxp) pthread_mutex_lock() used by a thread to acquire a lock on the specified mutex var iable. If the mutex is already locked by another thread, this call will block the calling thread until the mutex is unlocked 59

Mutex Lock (5) Using mutex lock pthread_mutex_unlock() Unlock a mutex by the owning thread. An error will be returned If the mutex was already unlocked If the mutex is owned by another thread pthread_mutex_trylock() Does not suspend its caller if another thread already holds the mutex, instead, returns immediately Practically, trying and backtracking may cause polling overhead and starvation Acceptable situation Real-time programmers to poll for state changes Detecting and avoiding deadlock and priority inversion 60

Mutex Lock (6) 예제 #1 - using mutex lock This example program illustrates the use of mutex variables in a threads program that performs a dot product. The main data is made available to all threads through a globally accessible structure. Each thread works on a different part of the data. The main thread waits for all the threads to complete their computations, and then it prints the resulting sum. 61

Mutex Lock (7) 예제 #1 - using mutex lock ( 계속 ) #include <pthread.h> #include <stdio.h> #include <malloc.h> typedef struct{ double *a; // first vector double *b; // second vector double sum; // dot product of two vectors int veclen; // dimension DOTDATA; #define NUMTHRDS 4 #define VECLEN 100 DOTDATA dotstr; pthread_t callthd[numthrds]; pthread_mutex_t mutexsum; 62

Mutex Lock (8) 예제 #1 - using mutex lock ( 계속 ) void *dotprod(void *arg) { int i, start, end, offset, len; double mysum, *x, *y; offset = (int)arg; len= dotstr.veclen; start = offset*len; end = start + len; x = dotstr.a; y = dotstr.b; /* Perform the dot product */ mysum= 0; for (i=start; i < end ; i++) { mysum += (x[i] * y[i]); /* Lock a mutex prior to updating the value in the shared structure, and unlock it upon updating. */ pthread_mutex_lock(&mutexsum); dotstr.sum += mysum; pthread_mutex_unlock(&mutexsum); pthread_exit((void*) 0); 63

Mutex Lock (9) 예제 #1 - using mutex lock ( 계속 ) int main (intargc, char *argv[]) { int i; double *a, *b; int status; pthread_attr_t attr; a = (double*) malloc(numthrds*veclen*sizeof(double)); b = (double*) malloc(numthrds*veclen*sizeof(double)); for (i=0; i < VECLEN*NUMTHRDS; i++) { a[i]=1; b[i]=a[i]; dotstr.veclen= VECLEN; dotstr.a= a; dotstr.b= b; dotstr.sum=0; pthread_mutex_init(&mutexsum, NULL); /* Create threads to perform the dot product*/ pthread_attr_init(&attr); pthread_attr_setdetachstate(&attr,pthread_create_joinable); 64

Mutex Lock (10) 예제 #1 - using mutex lock ( 계속 ) for(i=0;i < NUMTHRDS;i++) { pthread_create( &callthd[i], &attr, dotprod, (void *)i); pthread_attr_destroy(&attr); /* Wait on the other threads */ for(i=0;i < NUMTHRDS;i++) { pthread_join( callthd[i], (void **)&status); /* After joining, print out the results and cleanup */ printf("sum = %f n", dotstr.sum); free (a); free (b); pthread_mutex_destroy(&mutexsum); pthread_exit(null); 65

Condition Variables (1) Thread synchronization 도구 특정조건이참이될때까지스레드를블록시키기위해사용 항상 mutex lock 과연계하여사용 동작방식 : 스레드는동기화작업을위해우선 mutex lock을획득하는데, 지정된조건의발생을기다리는조건변수가만족하지못하면블록킹된다 스레드가블록되어있는동안획득했던 mutex lock은자동으로해제된다 다른스레드가지정된조건의상태를변경시키면, 조건변수가스레드의블록상태를해제한다 스레드가블록상태에서해제되면 mutext lock을자동으로획득하고다시조건검사한다 조건이거짓이면스레드는다시블록되고, 조건이참이면 mutext lock을해제하고실행을계속한다 66

Condition Variables (2) Creating & destroying condition variables Condition variable 은 pthread_cond_t type 으로선언 사용전에항상초기화되어야한다 초기화방법 Static한방법 : pthread_cond_t myconvar= PTHREAD_COND_INITIALIZER; 동적인방법 pthread_cond_init(condition, attr); #include <pthread.h> int pthread_cond_init(pthread_cond_t *condp, pthread_condtattr_t *attrp) int pthread_cond_destroy(pthread_cond_t *condp) 67

Condition Variables (3) Waiting & signaling on condition variables #include <pthread.h> int pthread_cond_wait(pthread_cond_t *condp, pthread_muext_t *muxp) int pthread_cond_timedwait(pthread_cond_t *condp, pthread_muext_t *muxp, struct timespec *timep) int pthread_cond_signal(pthread_cond_t *muxp) int pthread_cond_broadcast(pthread_cond_t *muxp) pthread_cond_wait() specified condition 이 signal 될때까지 block 되는함수 반드시 mutex가 locked된상태에서호출되어야하며, 호출되면자동적으로 mutex를 unlock하고대기한다. Signal에의해깨어날때에는 mutex는다시 locked된상태이다 68

Condition Variables (4) Waiting & signaling on condition variables ( 계속 ) pthread_cond_signal() pthread_cond_wait() 로대기하는 thread를 wakeup하는함수이다 Mutex가 lock된상태에서호출되어야한다 pthread_cond_broadcast() Condition variable 에대기하는여러 thread 모두를깨울때사용된다 pthread_cond_wait() 에의한대기 thread가없는상태에서의 pthread_cond_signal() 호출은 no action이다 cond_signal은stack되지않는다 69

Condition Variables (5) 많은스레드가대기상태인경우 If multiple threads are waiting on a condition variable, who gets awakened first when another thread issues a pthread_cond_signal call? Scheduling priority First-in first-out order 70

Condition Variables (6) 예제 using condition variables This simple example program demonstrates the use of several Pthread condition variable routines. The main routine creates three threads. Two of the threads perform work and update a "count" variable. The third thread waits until the count variable reaches a specified value. 71

Condition Variables (7) 예제 using condition variables ( 계속 ) #include <pthread.h> #include <stdio.h> #define NUM_THREADS 3 #define TCOUNT 10 #define COUNT_LIMIT 12 int count = 0; int thread_ids[3] = {0,1,2; pthread_mutex_t count_mutex; pthread_cond_t count_threshold_cv; void *inc_count(void *idp) { int i, j; double result=0.0; int *my_id = idp; for (i=0; i < TCOUNT; i++) { pthread_mutex_lock(&count_mutex); count++; 72

Condition Variables (8) 예제 using condition variables ( 계속 ) /* Check the value of count and signal waiting thread when condition is reached. Note that this occurs while mutex is locked. */ if (count == COUNT_LIMIT) { pthread_cond_signal(&count_threshold_cv); printf("inc_count(): thread %d, count = %d Threshold reached. n", *my_id, count); printf("inc_count(): thread %d, count = %d, unlocking mutex n", *my_id, count); pthread_mutex_unlock(&count_mutex); /* Do some work so threads can alternate on mutex lock */ for (j=0; j < 1000; j++) result = result + (double)random(); // for pthread_exit(null); 73

Condition Variables (9) 예제 using condition variables ( 계속 ) void *watch_count(void *idp) { int *my_id = idp; printf("starting watch_count(): thread %d n", *my_id); pthread_mutex_lock(&count_mutex); while (count < COUNT_LIMIT) { pthread_cond_wait(&count_threshold_cv, &count_mutex); printf("watch_count(): thread %d Condition signal received. n", *my_id); pthread_mutex_unlock(&count_mutex); pthread_exit(null); 74

Condition Variables (10) 예제 using condition variables ( 계속 ) int main (intargc, char *argv[]) { int i, rc; pthread_t threads[3]; pthread_attr_t attr; // Initialize mutexand condition variable objects pthread_mutex_init(&count_mutex, NULL); pthread_cond_init(&count_threshold_cv, NULL); /* For portability, explicitly create threads in a joinable state so that they can be joined later. */ pthread_attr_init(&attr); pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE); pthread_create(&threads[0], &attr, inc_count, (void *) &thread_ids[0]); pthread_create(&threads[1], &attr, inc_count, (void *) &thread_ids[1]); pthread_create(&threads[2], &attr, watch_count, (void*) &thread_ids[2]); for (i = 0; i < NUM_THREADS; i++) { pthread_join(threads[i], NULL); printf("main(): Waited on %d threads. Done. n",num_threads); /* Clean up and exit */ pthread_attr_destroy(&attr); pthread_mutex_destroy(&count_mutex); pthread_cond_destroy(&count_threshold_cv); pthread_exit(null); 75

Condition Variables (11) 예제 #2 Mutex lock과조건변수를사용하여다음의조건을만족하는프로그램을작성하여라 프로그램조건 : Reader & writer 스레드를생성한다 Reader 스레드는사용자로부터데이터를읽고전역배열 msgbuf를통해 writer 스레드에전달한다 Writer 스레드는 msgbuf에있는데이터를표준출력에출력한다 두스레드는사용자로부터입력이종료됨을발견하면종료한다 두스레드는 mutex lock과조건변수를통하여 msgbuf 접근을동기화한다 76

예제 #2 ( 계속 ) Condition Variables (12) #include <pthread.h> #include <string.h> #include <stdio.h> #include <signal.h> #define FINISH() { fprintf(stderr, %d exits\n, (int)pthread_self()); \ pthread_mutext_unlock(&mutx); pthread_exit(0); return (0); pthread_mutext_t mutx; pthread_cond_t condx; int msglen, done; Char msgbuf[256]; void *writer(void *argp) { do { pthread_mutext_lock(&mutx); while (!msglen) { pthread_cond_wait(&condx, &mutx); if (done) FINISH(); printf( *> %s\n, msgbuf); msglen = 0; pthread_mutex_unlock(&mutx); while (1); FINISH(); 77

예제 #2 ( 계속 ) Condition Variables (13) void *reader(void *argp) { do { pthread_mutext_lock(&mutx); if (!msglen) { if (!gets(msgbuf)) break; msglen = strlen(msgbuf) + 1; pthread_cond_signal(&condx); else pthread_yeild(); pthread_mutex_unlock(&mutx); while (1); FINISH(); int main(void) { pthread_t wtid, rtid, tid; pthread_mutex_init(&mutx, 0); pthread_cond_init(&condx, 0); if (pthread_create(&wtid, NULL, writer, NULL)) perror( pthread_create ); if (pthread_create(&rtid, NULL, reader, NULL)) perror( pthread_create ); 78

예제 #2 ( 계속 ) Condition Variables (14) if (!pthread_join(rtid, NULL)) { done = 1; pthread_cond_signal(&condx); pthread_join(wtid, NULL); pthread_mutex_destroy(&mutx); pthread_cond_destroy(&condx); pthread_exit(0); 79

Reader/Writer Lock (1) Reasons and rules If a thread tries to get a read lock on a resource, it will succeed only if no are thread holds a lock on the resource or if all threads that hold a lock are readers If another thread holds a write lock on the resource, the would-be reader must wait Conversely, if a thread tries to get a write lock on the resource, it must wait if any other thread holds a read or write lock 80

Reader/Writer Lock (2) Define reader/writer variable of type pthread_rdwr_t Initialize & destroy reader/write variables pthread_rdwr_init_np: initialize reader/writer lock pthread_rdwr_destroy_np: destroy reader/writer lock Lock & unlock reader/writer variables pthread_rdwr_rlock_np: obtain read lock pthread_rdwr_wlock_np: obtain write lock pthread_rdwr_runlock_np: release read lock pthread_rdwr_wunlock_np: release write lock 81

Reader/Writer Lock (3) 예제 Using reader/writer lock int llist_init(llist_t *llistp) { int rtn; llistp->first=null; if ((rtn=pthread_rdwr_init_np(&(llistp->rwlock), NULL))!=0) { printf( pthread_rdwr_init_np error %d, rtn); exit(1); return 0; int llist_insert_data(int index, void* datap, llist_t *llistp) { llist_node_t *cur, *prev, *new; int found = FALSE; pthread_rdwr_wlock_np(&(llistp->rwlock)); 82

Reader/Writer Lock (4) 예제 Using reader/writer lock ( 계속 ) for(cur=prev=llistp->first;cur!=null;prev=cur,cur=cur->nextp) { if (cur->index == index) { free(cur->datap); cur->datap=datap; found=true; break; else if(cur->index>index) { break; if (!found) { new = (llist_node_t*)malloc(sizeof(llist_node_t)); new->index=index; new->datap=datap; new->nextp=cur; if (cur==llistp->first) llistp->first=new; else prev->nextp= new; pthread_rdwr_wunlock_np(&(llistp->rwlock)); return 0; 83

Reader/Writer Lock (5) 예제 Using reader/writer lock ( 계속 ) int llist_find_data(int index, void **datapp, llist_t *llistp) { llist_node_t *cur, *prev; /* Initialize to not found */ *datapp= NULL; pthread_rdwr_rlock_np(&(llistp->rwlock)); /* Look through index for our entry */ for (cur=prev=llistp->first;cur!=null;prev=cur, cur=cur->nestp) { if (cur->index == index) {*datapp=cur->datap; break; else if (cur->index>index) { break; pthread_rdwr_runlock_np(&(llistp->rwlock)); return 0; 84

Review of mutex Semaphore (1) most popular primitives easy to use easy to understand what it is prone to errors programmers forget to unlock what if another thread forgets to use lock very difficult to understand programs that contain it 85

Semaphore (2) Why semaphore? Mutex may result in busy-waiting Mutex is only for mutual exclusion -no sharing no guarantee of fairness Semaphore a shared variable with two attributes integer value: number of threads that can share this semaphore allows n threads to share thread list: list of threads waiting for this semaphore guarantees FIFO order Operations cc [ flag... ] file... -lposix4 [ library... ] /* lib for real time extension */ #include <semaphore.h> int sem_init(sem_t *sem, int pshared, unsigned int value ); pshared: if non-zero, it is shared between processes i.e., zero means that it will be used between threads 86

Operations Semaphore (3) int sem_wait(sem_t *sem); int sem_trywait(sem_t *sem); if the integer value > 0, decrement it and proceeds else block (or fail for trywait) int sem_post(sem_t *sem); if there is a thread waiting, wake up a thread according to its schedparam ptread_attr_setschedparm(); else increment the integer value int sem_destroy(sem_t *sem); other combination: sem_open(), sem_close() 87

Semaphore (4) Mutex lock vs. Semaphore void producer_function(void) { while(1){ pthread_mutex_lock(&mutex); if ( buffer_has_item == 0 ) { buffer = make_new_item(); buffer_has_item = 1; pthread_mutex_unlock(&mutex); pthread_delay_np(&delay); void consumer_function(void) { while(1){ pthread_mutex_lock(&mutex); if ( buffer_has_item == 1) { consume_item( buffer ); buffer_has_item = 0; pthread_mutex_unlock(&mutex); pthread_delay_np(&delay); 88

Semaphore (5) Mutex lock vs. Semaphore ( 계속 ) void producer_function(void) { while(1){ semaphore_down(&writers_turn); buffer = make_new_item(); semaphore_up(&readers_turn); void consumer_function(void) { while(1){ semaphore_down(&readers_turn); consume_item(buffer); semaphore_up(&writers_turn); 89

Semaphore (6) 예제 #3 예제 #2 프로그램을세마포어를사용하여수정하여라 Mutex lock & condition variable a semaphore 90

Semaphore (7) 예제 #3 ( 계속 ) #include <pthread.h> #include <string.h> #include <stdio.h> #include <semaphore.h> #define FINISH() { fprintf(stderr, %d exits\n, (int)pthread_self()); \ pthread_mutext_unlock(&mutx); pthread_exit(0); return (0); sem_t semx; int msglen, done = 0; Char msgbuf[256]; void *writer(void *argp) { do { sem_wait(&semx); if (msglen) { printf( *> %s\n, msgbuf); msglen = 0; sem_post(&semx); pthread_yeild(); while (!done); FINISH(); 91

Semaphore (8) 예제 #3 ( 계속 ) void *reader(void *argp) { do { sem_wait(&semx); if (!msglen) { if (fgets(msgbuf, 256, stdin)) msglen = strlen(msgbuf) + 1; else done = 1; sem_post(&semx); pthread_yeild(); while (!done); FINISH(); int main(void) { pthread_t wtid, rtid, tid; sem_init(&semx, 0, 0); if (pthread_create(&wtid, NULL, writer, NULL)) perror( pthread_create ); if (pthread_create(&rtid, NULL, reader, NULL)) perror( pthread_create ); 92

Semaphore (9) 예제 #3 ( 계속 ) while (!pthread_join(rtid, NULL)); pthread_join(wtid, NULL); sem_destroy(&semx); pthread_exit(0); 93

Deadlock Problem (1) A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set Hold & wait Circular waiting Example #1 System has 2 tape drives. P1 and P2 each hold one tape drive and each needs another one. Example #2 semaphores A and B, initialized to 1 P0 wait(a); wait (B); P1 wait(b); wait(a); 94

Bridge Crossing Deadlock Problem (2) Traffic only in one direction. Each section of a bridge can be viewed as a resource. If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback). Several cars may have to be backed up if a deadlock occurs. Starvation is possible. 95

Traffic Crossing Deadlock Problem (3) 96

Deadlock Problem (4) Resource Aquisition 97

Deadlock Problem (5) Memory Management Space is available for allocation of 200Kbytes, and the following sequence of events occur P1 Request 80 Kbytes; Request 60 Kbytes; P2 Request 70 Kbytes; Request 80 Kbytes; Deadlock occurs if both processes progress to their second request 98