쓰레드 (Thread) 양희재교수 (hjyang@ks.ac.kr) / 경성대학교컴퓨터공학과
Thread? 쓰레드 (Thread) 프로그램내부의흐름, 맥 class Test { public static void main(string[] args) { int n = 0; int m = 6; System.out.println(n+m); while (n < m) n++; System.out.println("Bye");
Multithreads 다중쓰레드 (Multithreads) 한프로그램에 2 개이상의맥 맥이빠른시간간격으로스위칭된다 여러맥이동시에실행되는것처럼보인다 (concurrent vs simultaneous) 예 : Web browser 화면출력하는쓰레드 + 데이터읽어오는쓰레드 예 : Word processor 화면출력하는쓰레드 + 키보드입력받는쓰레드 + 철자 / 문법오류확인쓰레드 예 : 음악연주기, 동영상플레이어, Eclipse IDE,
Thread vs Process 한프로세스에는기본 1 개의쓰레드 단일쓰레드 (single thread) 프로그램 한프로세스에여러개의쓰레드 다중쓰레드 (multi-thread) 프로그램 쓰레드구조 프로세스의메모리공간공유 (code, data) 프로세스의자원공유 (file, i/o, ) 비공유 : 개별적인 PC, SP, registers, stack 프로세스의스위칭 vs 쓰레드의스위칭
예제 : 자바쓰레드 맥만들기 java.lang.thread 주요메소드 public void run() // 새로운맥이흐르는곳 ( 치환 ) void start() // 쓰레드시작요청 void join() // 쓰레드가마치기를기다림 static void sleep() // 쓰레드잠자기
java.lang.thread Thread.run() 쓰레드가시작되면 run() 메소드가실행된다 run() 메소드를치환한다. class MyThread extends Thread { public void run() { // 치환 (override) // 코드 예제 : 글자 A 와 B 를동시에화면에출력하기 모든프로그램은처음부터 1 개의쓰레드는갖고있다 (main) 2 개의쓰레드 : main + MyThread
프로세스동기화 Process Synchronization cf. Thread synchronization Processes Independent vs. Cooperating Cooperating process: one that can affect or be affected by other processes executed in the system 프로세스간통신 : 전자우편, 파일전송 프로세스간자원공유 : 메모리상의자료들, 데이터베이스등 명절기차표예약, 대학온라인수강신청, 실시간주식거래
프로세스동기화 Process Synchronization Concurrent access to shared data may result in data inconsistency Orderly execution of cooperating processes so that data consistency is maintained Example: BankAccount Problem ( 은행계좌문제 ) 부모님은은행계좌에입금 ; 자녀는출금 입금 (deposit) 과출금 (withdraw) 은독립적으로일어난다.
class Test { public static void main(string[] args) throws InterruptedException { BankAccount b = new BankAccount(); Parent p = new Parent(b); Child c = new Child(b); p.start(); c.start(); p.join(); c.join(); System.out.println( "\nbalance = " + b.getbalance()); class Parent extends Thread { BankAccount b; Parent(BankAccount b) { this.b = b; public void run() { for (int i=0; i<100; i++) b.deposit(1000); class BankAccount { int balance; void deposit(int amount) { balance = balance + amount; void withdraw(int amount) { balance = balance - amount; int getbalance() { return balance; class Child extends Thread { BankAccount b; Child(BankAccount b) { this.b = b; public void run() { for (int i=0; i<100; i++) b.withdraw(1000);
BankAccount Problem 입출금동작알기위해 "+", "-" 출력하기 입출금동작에시간지연추가 잘못된결과값 이유 : 공통변수 (common variable) 에대한동시업데이트 (concurrent update) 해결 : 한번에한쓰레드만업데이트하도록 임계구역문제
임계구역문제 The Critical-Section Problem Critical section A system consisting of multiple threads Each thread has a segment of code, called critical section, in which the thread may be changing common variables, updating a table, writing a file, and so on. Solution Mutual exclusion ( 상호배타 ): 오직한쓰레드만진입 Progress ( 진행 ): 진입결정은유한시간내 Bounded waiting ( 유한대기 ): 어느쓰레드라도유한시간내
프로세스 / 쓰레드동기화 임계구역문제해결 ( 틀린답이나오지않도록 ) 프로세스실행순서제어 ( 원하는대로 )
동기화도구 Synchronization Tools Semaphores Monitors Misc. Semaphores ( 세마포 ) n. ( 철도의 ) 까치발신호기, 시그널 ; U ( 군대의 ) 수기 ( 手旗 ) 신호 동기화문제해결을위한소프트웨어도구 네덜란드의 Edsger Dijkstra 가제안 구조 : 정수형변수 + 두개의동작 (P, V)
세마포 (Semaphore) 동작 구조 P: Proberen (test) acquire() V: Verhogen (increment) release() class Semaphore { int value; // number of permits Semaphore(int value) {... void acquire() {... void release() {...
세마포 (Semaphore) void acquire() { value--; if (value < 0) { add this process/thread to list; block; void release() { value++; if (value <= 0) { remove a process P from list; wakeup P;
세마포 (Semaphore) 일반적사용 (1): Mutual exclusion sem.value = 1; sem.acquire(); Critical-Section sem.release(); 예제 : BankAccount Problem java.util.concurrent.semaphore
세마포 (Semaphore) 일반적사용 (2): Ordering sem.value = 0; P 1 P 2 sem.acquire(); S 1 ; S 2 ; sem.release(); 예제 : BankAccount Problem 항상입금먼저 (= Parent 먼저 ) 항상출금먼저 (= Child 먼저 ) 입출금교대로 (P-C-P-C-P-C- )
전통적동기화예제 Classical Synchronization Problems
전통적동기화예제 Producer and Consumer Problem 생산자-소비자문제 유한버퍼문제 (Bounded Buffer Problem) Readers-Writers Problem 공유데이터베이스접근 Dining Philosopher Problem 식사하는철학자문제
Producer-Consumer Problem 생산자 - 소비자문제 생산자가데이터를생산하면소비자는그것을소비 예 : 컴파일러 > 어셈블러, 파일서버 > 클라이언트, 웹서버 > 웹클라이언트 Bounded Buffer 생산된데이터는버퍼에일단저장 ( 속도차이등 ) 현실시스템에서버퍼크기는유한 생산자는버퍼가가득차면더넣을수없다. 소비자는버퍼가비면뺄수없다.
class Buffer { int[] buf; int size; int count; int in; int out; Buffer(int size) { buf = new int[size]; this.size = size; count = in = out = 0; void insert(int item) { /* check if buf is full */ while (count == size) ; int remove() { /* check if buf is empty */ while (count == 0) ; /* buf is not full */ buf[in] = item; in = (in+1)%size; count++; /* buf is not empty */ int item = buf[out]; out = (out+1)%size; count--; return item;
class Buffer { int[] buf; int size; int count; int in; int out; Buffer(int size) { buf = new int[size]; this.size = size; count = in = out = 0; void insert(int item) { /* check if buf is full */ while (count == size) ; int remove() { /* check if buf is empty */ while (count == 0) ; /* buf is not full */ buf[in] = item; in = (in+1)%size; count++; /* buf is not empty */ int item = buf[out]; out = (out+1)%size; count--; return item;
/****** 생산자 ******/ class Producer extends Thread { Buffer b; int N; Producer(Buffer b, int N) { this.b = b; this.n = N; public void run() { for (int i=0; i<n; i++) b.insert(i); /****** 소비자 ******/ class Consumer extends Thread { Buffer b; int N; Consumer(Buffer b, int N) { this.b = b; this.n = N; public void run() { int item; for (int i=0; i<n; i++) item = b.remove(); class Test { public static void main(string[] arg) { Buffer b = new Buffer(100); Producer p = new Producer(b, 10000); Consumer c = new Consumer(b, 10000); p.start(); c.start(); try { p.join(); c.join(); catch (InterruptedException e) { System.out.println("Number of items in the buf is " + b.count);
Producer-Consumer Problem 잘못된결과 실행불가, 또는 count 0 ( 생산된항목숫자 소비된항목숫자 ) 최종적으로버퍼내에는 0 개의항목이있어야 이유 공통변수 count, buf[] 에대한동시업데이트 공통변수업데이트구간 (= 임계구역 ) 에대한동시진입 해결법 임계구역에대한동시접근방지 ( 상호배타 ) 세마포를사용한상호배타 (mutual exclusion) 세마포 : mutex.value = 1 (# of permit) 코드보기
Producer-Consumer Problem Busy-wait 생산자 : 버퍼가가득차면기다려야 = 빈 (empty) 공간이있어야 소비자 : 버퍼가비면기다려야 = 찬 (full) 공간이있어야 세마포를사용한 busy-wait 회피 코드보기 생산자 : empty.acquire() // # of permit = BUF_SIZE 소비자 : full.acquire() // # of permit = 0 [ 생산자 ] empty.acquire(); PRODUCE; full.release(); [ 소비자 ] full.acquire(); CONSUME; empty.release();
Readers-Writers Problem 공통데이터베이스 Readers: read data, never modify it Writers: read data and modifiy it 상호배타 : 한번에한개의프로세스만접근 비효율적 효율성제고 변종 Each read or write of the shared data must happen within a critical section Guarantee mutual exclusion for writers Allow multiple readers to execute in the critical section at once The first R/W problem (readers-preference) The second R/W problem (writers-preference) The Third R/W problem
Dining Philosopher Problem 식사하는철학자문제 5명의철학자, 5개의젓가락, 생각 식사 생각 식사 식사하려면 2개의젓가락필요 프로그래밍 젓가락 : 세마포 (# of permit = 1) 젓가락과세마포에일련번호 : 0 ~ 4 왼쪽젓가락 오른쪽젓가락
import java.util.concurrent.semaphore; class Philosopher extends Thread { int id; Semaphore lstick, rstick; // philosopher id // left, right chopsticks Philosopher(int id, Semaphore lstick, Semaphore rstick) { this.id = id; this.lstick = lstick; this.rstick = rstick; public void run() { try { while (true) { lstick.acquire(); rstick.acquire(); eating(); lstick.release(); rstick.release(); thinking(); catch (InterruptedException e) { void eating() { System.out.println("[" + id + "] eating"); void thinking() { System.out.println("[" + id + "] thinking");
class Test { static final int num = 5; // number of philosphers & chopsticks public static void main(string[] args) { int i; /* chopsticks */ Semaphore[] stick = new Semaphore[num]; for (i=0; i<num; i++) stick[i] = new Semaphore(1); /* philosophers */ Philosopher[] phil = new Philosopher[num]; for (i=0; i<num; i++) phil[i] = new Philosopher(i, stick[i], stick[(i+1)%num]); /* let philosophers eat and think */ for (i=0; i<num; i++) phil[i].start();
Dining Philosopher Problem 잘못된결과 : starvation 모든철학자가식사를하지못해굶어죽는상황 이유 = 교착상태 (deadlock)
교착상태 Deadlocks
Deadlock 프로세스는실행을위해여러자원을필요로한다. CPU, 메모리, 파일, 프린터, 어떤자원은갖고있으나다른자원은갖지못할때 (e.g., 다른프로세스가사용중 ) 대기해야 다른프로세스역시다른자원을가지려고대기할때교착상태가능성! 교착상태필요조건 (Necessary Conditions) Mutual exclusion ( 상호배타 ) Hold and wait ( 보유및대기 ) No Preemption ( 비선점 ) Circular wait ( 환형대기 )
자원 (Resources) 동일자원 동일형식 (type) 자원이여러개있을수있다 (instance) 예 : 동일 CPU 2개, 동일프린터 3개등 자원의사용 요청 (request) 사용 (use) 반납 (release) 자원할당도 (Resource Allocation Graph) 어떤자원이어떤프로세스에게할당되었는가? 어떤프로세스가어떤자원을할당받으려고기다리고있는가? 자원 : 사각형, 프로세스 : 원, 할당 : 화살표
자원할당도 교착상태필요조건 자원할당도상에원이만들어져야 ( 환형대기 ) 충분조건은아님! 예제 : 식사하는철학자문제 원이만들어지지않게하려면?
교착상태처리 교착상태방지 Deadlock Prevention 교착상태회피 Deadlock Avoidance 교착상태검출및복구 Deadlock Detection & Recovery 교착상태무시 Don't Care
(1) 교착상태방지 Deadlock Prevention 교착상태 4가지필요조건중한가지이상불만족 상호배타 (Mutual exclusion) 보유및대기 (Hold and wait) 비선점 (No preemption) 환형대기 (Circular wait)
(1) 교착상태방지 상호배타 (Mutual exclusion) 자원을공유가능하게 ; 원천적불가할수도 보유및대기 (Hold & Wait) 자원을가지고있으면서다른자원을기다리지않게 예 : 자원이없는상태에서모든자원대기 ; 일부자원만가용하면보유자원을모두놓아주기 단점 : 자원활용률저하, 기아 (starvation) 비선점 (No preemption) 자원을선점가능하게 ; 원천적불가할수도 ( 예 : 프린터 ) 환형대기 (Circular wait) 예 : 자원에번호부여 ; 번호오름차순으로자원요청 단점 : 자원활용률저하
(2) 교착상태회피 Deadlock Avoidance 교착상태 = 자원요청에대한잘못된승인 ( 은행파산 ) 예제 12개의 magnetic tape 및 3개의 process 안전한할당 (Safe allocation) Process Max needs Current needs P 0 10 5 P 1 4 2 P 2 9 2
(2) 교착상태회피 예제 ( 계속 ) 12개의 magnetic tape 및 3개의 process 불안전한할당 (Unsafe allocation) Process Max needs Current needs P 0 10 5 P 1 4 2 P 2 9 3 운영체제는자원을할당할때불안전할당되지않도록 불안전할당 교착상태 대출전문은행과유사 : Banker's Algorithm
(3) 교착상태검출및복구 Deadlock Detection & Recovery 교착상태가일어나는것을허용 주기적검사 교착상태발생시복구 검출 검사에따른추가부담 (overhead): 계산, 메모리 복구 프로세스일부강제종료 자원선점하여일부프로세스에게할당
(4) 교착상태무시 교착상태는실제로잘일어나지않는다! 4 가지필요조건모두만족해도 교착상태발생시재시동 (PC 등가능 )
모니터 Monitors
모니터 모니터 (Monitor) 세마포이후프로세스동기화도구 세마포보다고수준개념 구조 공유자원 + 공유자원접근함수 2개의 queues: 배타동기 + 조건동기 공유자원접근함수에는최대 1개의쓰레드만진입 진입쓰레드가조건동기로블록되면새쓰레드진입가능 새쓰레드는조건동기로블록된쓰레드를깨울수있다. 깨워진쓰레드는현재쓰레드가나가면재진입할수있다.
자바모니터 자바의모든객체는모니터가될수있다. 배타동기 : synchronized 키워드사용하여지정 조건동기 : wait(), notify(), notifyall() 메소드사용 class C { private int value, ; synchronized void f() {... synchronized void g() {... void h() {...
모니터 (Monitor) 일반적사용 (1): Mutual exclusion synchronized { Critical-Section 예제 : BankAccount Problem 뒷면
class Test { public static void main(string[] args) throws InterruptedException { BankAccount b = new BankAccount(); Parent p = new Parent(b); Child c = new Child(b); p.start(); c.start(); p.join(); c.join(); System.out.println( "\nbalance = " + b.getbalance()); class Parent extends Thread { BankAccount b; Parent(BankAccount b) { this.b = b; public void run() { for (int i=0; i<100; i++) b.deposit(1000); class BankAccount { int balance; synchronized void deposit(int amt) { int temp = balance + amt; System.out.print("+"); balance = temp; synchronized void withdraw(int amt) { int temp = balance - amt; System.out.print("-"); balance = temp; int getbalance() { return balance; class Child extends Thread { BankAccount b; Child(BankAccount b) { this.b = b; public void run() { for (int i=0; i<100; i++) b.withdraw(1000);
모니터 (Monitor) 일반적사용 (2): Ordering P 1 P 2 wait(); S 1 ; S 2 ; notify(); 예제 : BankAccount Problem 항상입금먼저 (= Parent 먼저 ) 항상출금먼저 (= Child 먼저 ) 입출금교대로 (P-C-P-C-P-C- )
전통적동기화예제 Producer and Consumer Problem 생산자-소비자문제 유한버퍼문제 (Bounded Buffer Problem) Readers-Writers Problem 공유데이터베이스접근 Dining Philosopher Problem 식사하는철학자문제
class Buffer { int[] buf; int size, count, in, out; Buffer(int size) { buf = new int[size]; this.size = size; count = in = out = 0; synchronized void insert(int item) { while (count == size) try { wait(); catch (InterruptedException e) { synchronized int remove() { while (count == 0) try { wait(); catch (InterruptedException e) { buf[in] = item; in = (in+1)%size; notify(); count++; int item = buf[out]; out = (out+1)%size; count--; notify(); return item;
The Dining Philosopher Problem class Chopstick { private boolean inuse = false; synchronized void acquire() throws InterruptedException { while (inuse) wait(); inuse = true; synchronized void release() { inuse = false; notify();