쓰레드 (Thread) 양희재교수 / 경성대학교컴퓨터공학과

Transcription

1 쓰레드 (Thread) 양희재교수 / 경성대학교컴퓨터공학과

2 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");

3 Multithreads 다중쓰레드 (Multithreads) 한프로그램에 2 개이상의맥 맥이빠른시간간격으로스위칭된다 여러맥이동시에실행되는것처럼보인다 (concurrent vs simultaneous) 예 : Web browser 화면출력하는쓰레드 + 데이터읽어오는쓰레드 예 : Word processor 화면출력하는쓰레드 + 키보드입력받는쓰레드 + 철자 / 문법오류확인쓰레드 예 : 음악연주기, 동영상플레이어, Eclipse IDE,

4 Thread vs Process 한프로세스에는기본 1 개의쓰레드 단일쓰레드 (single thread) 프로그램 한프로세스에여러개의쓰레드 다중쓰레드 (multi-thread) 프로그램 쓰레드구조 프로세스의메모리공간공유 (code, data) 프로세스의자원공유 (file, i/o, ) 비공유 : 개별적인 PC, SP, registers, stack 프로세스의스위칭 vs 쓰레드의스위칭

5 예제 : 자바쓰레드 맥만들기 java.lang.thread 주요메소드 public void run() // 새로운맥이흐르는곳 ( 치환 ) void start() // 쓰레드시작요청 void join() // 쓰레드가마치기를기다림 static void sleep() // 쓰레드잠자기

6 java.lang.thread Thread.run() 쓰레드가시작되면 run() 메소드가실행된다 run() 메소드를치환한다. class MyThread extends Thread { public void run() { // 치환 (override) // 코드 예제 : 글자 A 와 B 를동시에화면에출력하기 모든프로그램은처음부터 1 개의쓰레드는갖고있다 (main) 2 개의쓰레드 : main + MyThread

7 프로세스동기화 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 프로세스간통신 : 전자우편, 파일전송 프로세스간자원공유 : 메모리상의자료들, 데이터베이스등 명절기차표예약, 대학온라인수강신청, 실시간주식거래

8 프로세스동기화 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) 은독립적으로일어난다.

9 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);

10 BankAccount Problem 입출금동작알기위해 "+", "-" 출력하기 입출금동작에시간지연추가 잘못된결과값 이유 : 공통변수 (common variable) 에대한동시업데이트 (concurrent update) 해결 : 한번에한쓰레드만업데이트하도록 임계구역문제

11 임계구역문제 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 ( 유한대기 ): 어느쓰레드라도유한시간내

12 프로세스 / 쓰레드동기화 임계구역문제해결 ( 틀린답이나오지않도록 ) 프로세스실행순서제어 ( 원하는대로 )

13 동기화도구 Synchronization Tools Semaphores Monitors Misc. Semaphores ( 세마포 ) n. ( 철도의 ) 까치발신호기, 시그널 ; U ( 군대의 ) 수기 ( 手旗 ) 신호 동기화문제해결을위한소프트웨어도구 네덜란드의 Edsger Dijkstra 가제안 구조 : 정수형변수 + 두개의동작 (P, V)

14 세마포 (Semaphore) 동작 구조 P: Proberen (test) acquire() V: Verhogen (increment) release() class Semaphore { int value; // number of permits Semaphore(int value) {... void acquire() {... void release() {...

15 세마포 (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;

16 세마포 (Semaphore) 일반적사용 (1): Mutual exclusion sem.value = 1; sem.acquire(); Critical-Section sem.release(); 예제 : BankAccount Problem java.util.concurrent.semaphore

17 세마포 (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- )

18 전통적동기화예제 Classical Synchronization Problems

19 전통적동기화예제 Producer and Consumer Problem 생산자-소비자문제 유한버퍼문제 (Bounded Buffer Problem) Readers-Writers Problem 공유데이터베이스접근 Dining Philosopher Problem 식사하는철학자문제

20 Producer-Consumer Problem 생산자 - 소비자문제 생산자가데이터를생산하면소비자는그것을소비 예 : 컴파일러 > 어셈블러, 파일서버 > 클라이언트, 웹서버 > 웹클라이언트 Bounded Buffer 생산된데이터는버퍼에일단저장 ( 속도차이등 ) 현실시스템에서버퍼크기는유한 생산자는버퍼가가득차면더넣을수없다. 소비자는버퍼가비면뺄수없다.

21 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;

22 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;

23 /****** 생산자 ******/ 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);

24 Producer-Consumer Problem 잘못된결과 실행불가, 또는 count 0 ( 생산된항목숫자 소비된항목숫자 ) 최종적으로버퍼내에는 0 개의항목이있어야 이유 공통변수 count, buf[] 에대한동시업데이트 공통변수업데이트구간 (= 임계구역 ) 에대한동시진입 해결법 임계구역에대한동시접근방지 ( 상호배타 ) 세마포를사용한상호배타 (mutual exclusion) 세마포 : mutex.value = 1 (# of permit) 코드보기

25 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();

26 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

27 Dining Philosopher Problem 식사하는철학자문제 5명의철학자, 5개의젓가락, 생각 식사 생각 식사 식사하려면 2개의젓가락필요 프로그래밍 젓가락 : 세마포 (# of permit = 1) 젓가락과세마포에일련번호 : 0 ~ 4 왼쪽젓가락 오른쪽젓가락

28 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");

29 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();

30 Dining Philosopher Problem 잘못된결과 : starvation 모든철학자가식사를하지못해굶어죽는상황 이유 = 교착상태 (deadlock)

31 교착상태 Deadlocks

32 Deadlock 프로세스는실행을위해여러자원을필요로한다. CPU, 메모리, 파일, 프린터, 어떤자원은갖고있으나다른자원은갖지못할때 (e.g., 다른프로세스가사용중 ) 대기해야 다른프로세스역시다른자원을가지려고대기할때교착상태가능성! 교착상태필요조건 (Necessary Conditions) Mutual exclusion ( 상호배타 ) Hold and wait ( 보유및대기 ) No Preemption ( 비선점 ) Circular wait ( 환형대기 )

33 자원 (Resources) 동일자원 동일형식 (type) 자원이여러개있을수있다 (instance) 예 : 동일 CPU 2개, 동일프린터 3개등 자원의사용 요청 (request) 사용 (use) 반납 (release) 자원할당도 (Resource Allocation Graph) 어떤자원이어떤프로세스에게할당되었는가? 어떤프로세스가어떤자원을할당받으려고기다리고있는가? 자원 : 사각형, 프로세스 : 원, 할당 : 화살표

34 자원할당도 교착상태필요조건 자원할당도상에원이만들어져야 ( 환형대기 ) 충분조건은아님! 예제 : 식사하는철학자문제 원이만들어지지않게하려면?

35 교착상태처리 교착상태방지 Deadlock Prevention 교착상태회피 Deadlock Avoidance 교착상태검출및복구 Deadlock Detection & Recovery 교착상태무시 Don't Care

36 (1) 교착상태방지 Deadlock Prevention 교착상태 4가지필요조건중한가지이상불만족 상호배타 (Mutual exclusion) 보유및대기 (Hold and wait) 비선점 (No preemption) 환형대기 (Circular wait)

37 (1) 교착상태방지 상호배타 (Mutual exclusion) 자원을공유가능하게 ; 원천적불가할수도 보유및대기 (Hold & Wait) 자원을가지고있으면서다른자원을기다리지않게 예 : 자원이없는상태에서모든자원대기 ; 일부자원만가용하면보유자원을모두놓아주기 단점 : 자원활용률저하, 기아 (starvation) 비선점 (No preemption) 자원을선점가능하게 ; 원천적불가할수도 ( 예 : 프린터 ) 환형대기 (Circular wait) 예 : 자원에번호부여 ; 번호오름차순으로자원요청 단점 : 자원활용률저하

38 (2) 교착상태회피 Deadlock Avoidance 교착상태 = 자원요청에대한잘못된승인 ( 은행파산 ) 예제 12개의 magnetic tape 및 3개의 process 안전한할당 (Safe allocation) Process Max needs Current needs P P P 2 9 2

39 (2) 교착상태회피 예제 ( 계속 ) 12개의 magnetic tape 및 3개의 process 불안전한할당 (Unsafe allocation) Process Max needs Current needs P P P 운영체제는자원을할당할때불안전할당되지않도록 불안전할당 교착상태 대출전문은행과유사 : Banker's Algorithm

40 (3) 교착상태검출및복구 Deadlock Detection & Recovery 교착상태가일어나는것을허용 주기적검사 교착상태발생시복구 검출 검사에따른추가부담 (overhead): 계산, 메모리 복구 프로세스일부강제종료 자원선점하여일부프로세스에게할당

41 (4) 교착상태무시 교착상태는실제로잘일어나지않는다! 4 가지필요조건모두만족해도 교착상태발생시재시동 (PC 등가능 )

42 모니터 Monitors

43 모니터 모니터 (Monitor) 세마포이후프로세스동기화도구 세마포보다고수준개념 구조 공유자원 + 공유자원접근함수 2개의 queues: 배타동기 + 조건동기 공유자원접근함수에는최대 1개의쓰레드만진입 진입쓰레드가조건동기로블록되면새쓰레드진입가능 새쓰레드는조건동기로블록된쓰레드를깨울수있다. 깨워진쓰레드는현재쓰레드가나가면재진입할수있다.

44 자바모니터 자바의모든객체는모니터가될수있다. 배타동기 : synchronized 키워드사용하여지정 조건동기 : wait(), notify(), notifyall() 메소드사용 class C { private int value, ; synchronized void f() {... synchronized void g() {... void h() {...

45 모니터 (Monitor) 일반적사용 (1): Mutual exclusion synchronized { Critical-Section 예제 : BankAccount Problem 뒷면

46 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);

47 모니터 (Monitor) 일반적사용 (2): Ordering P 1 P 2 wait(); S 1 ; S 2 ; notify(); 예제 : BankAccount Problem 항상입금먼저 (= Parent 먼저 ) 항상출금먼저 (= Child 먼저 ) 입출금교대로 (P-C-P-C-P-C- )

48 전통적동기화예제 Producer and Consumer Problem 생산자-소비자문제 유한버퍼문제 (Bounded Buffer Problem) Readers-Writers Problem 공유데이터베이스접근 Dining Philosopher Problem 식사하는철학자문제

49 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;

50 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();