고급동기화및프로세스간통신

고급동기화및프로세스간통신

Event Mechanism Supported by OS Events Event 란? 일단의프로세스들에게어떤조건의발생을알리는데이용이조건 ( 사건 ) 은 OS 마다여러변형이있음 Event 는세마포어와유사 Event 기다림 P 동작 Event 발생을알림 V 동작 Event descriptor (OS 관리데이터구조 ) Blocked processes list corresponding event Event 의처리방법하나의프로세스는다른프로세스가시그널을보낼때까지대기할수있음 (1) 시그널이발생할때 (2), 대기중인하나의프로세스는 unblock 됨 (3) queue function 이시그널을기다리는프로세스의개수를 return 함시그널을기다리지않는프로세스는그시그널을무시함세마포어와의차이점 - 세마포어는변수를갖는모든프로세스에영향 - Event 기반은 blocked 프로세스에영향 2

Flow of Events Events 의 skeleton Events (Cont d) 선 언 class Event { shared Event 변수이름 ; public: // 함수이름 } 실 행 변수이름. 함수이름 (); 3

Flow of Events Events (Cont d) Events 예제 class Event { shared Event topofhour; public: void signal(); void wait() int queue(); } 1 wait() topofhour 3 Resume 2 signal() Process i 정각이될때 (Event) 까지대기 // Wait until the top of the hour before proceeding topofhour.wait(); // It s the top of the hour... Process j 정각이되면 Event를대기하는프로세스가 없을때까지 Event를발생한다. while(true) if(istopofhour()) while(topofhour.queue() > 0) 4 topofhour.signal(); } 4

UNIX Signals Signal 은일종의 event 임 interrupt 와유사 특징 UNIX OS 가발생시키는소프트웨어적인 condition Interrupt handler (interrupt service routine) 과유사한 signal handler 가주어지거나 (IDT), 사용자가작성가능 UNIX 시그널의예 (Interrupt Descriptor Table) 사용자의 Control + C 입력 0 으로숫자를나누려는연산 존재하지않는파이프에입력하려는시도 etc. Table 사용이유 Desciptor 를장비에서제공하기때문에위치를알수없어직접 Access 가불가능그러므로 Table 에저장된주소값으로호출 Signal Mechanism Supported by OS 5

Characteristic of Signal UNIX Signals (cont d) UNIX는버전에따라고정된개수의 Signal 집합을가짐 signal.h 에 OS가사용할수있는 Signal이정의됨사용자정의시그널정의 SIGUSR1 & SIGUSR2 사용 kill(pid, signal); 시스템호출을이용하여시그널발생 pid : Signal을전송하려는프로세스 ID signal : 전송하려는정의된 Signal 혹은사용자정의 Signal send 기능과유사 6

UNIX Signals (cont d) 시그널처리의세가지방법 Kernel 의 default handler 가 Signal 처리 signal(sig#, SIG_DFL) 프로그래머가정의한 handler 가 Signal 처리 signal(sig#, myhandler) Signal 무시 signal(sig#, SIG_IGN) 7

Process Flow of Signal and Handler Signal Handling UNIX Signals (cont d) /* code for process p */ signal(sig#, sig_hndlr); /* ARBITRARY CODE */ void sig_hndlr(...) { /* ARBITRARY CODE */ } 시그널 SIG# 발생 실행중인프로세스, p p 는 block 시그널 handler (user defined) sig_hndlr 를 p 의 address space 에서실행 프로세스 p 실행재개 8

Example Code of Signal - 1 #include <signal.h> static void sig_handler(int); int main () { int parent_pid, child_pid, status; UNIX Signals (cont d) if(signal(sigusr1, sig_handler) == SIG_ERR) printf( Parent: Unable to create handler for SIGUSR1\n ); if(signal(sigusr2, sig_handler) == SIG_ERR) printf( Parent: Unable to create handler for SIGUSR2\n ); parent_pid = getpid(); if((child_pid = fork()) == 0) { child_pid = getpid(); printf( Child pid: %d\n, child_pid); kill(parent_pid, SIGUSR1); 1 for (;;) pause(); 2 } else { printf( Parent pid: %d\n, parent_pid); kill(child_pid, SIGUSR2); pause(); 1 printf( Parent: Terminating child \n ); kill(child_pid, SIGTERM); 2 wait(&status); printf( done\n ); } } 3 자식프로세스루틴 1 부모프로세스에게 SIGUSR1 시그널을보냄 2 부모가시그널이발생할때까지무한대기 부모프로세스루틴 1 자식프로세스에게 SIGUSR2 시그널을보냄 2 자식에게종료시그널 (SIGTERM) 을보냄 3 자식이종료될때까지대기함 9

static void sig_handler(int signo) { switch(signo) { int cur_pid = getpid(); Unix Signal (cont d) Example Code of Signal - 2 case SIGUSR1: /* Incoming SIGUSR1 */ printf( Parent: Received SIGUSER1 (pid: %d)\n, cur_pid); break; case SIGUSR2: /* Incoming SIGUSR2 */ printf( Child: Received SIGUSER2\n (pid: %d)\n, cur_pid); break; 시그널 handler default: break; } return; } 수행결과화면 10

Definition of Monitors Monitor 란? Monitors Language 에서동기화를제공하는추상화데이터타입 (ADT) 개념적으로동기적인접근이필요한데이터와데이터에접근하는 Critical Section 을포함한함수로구성. 공용인터페이스 아래와같은공용함수들을제공 monitor anadt { semaphore mutex = 1; // Implicit 일반함수 public: proc_i( ) { P(mutex); // Implicit <processing for proc_i>; V(mutex); // Implicit }; proce_j(..) { } } 공용함수 공용함수 J 지역변수 직접적데이터접근불가함수만이용가능 프로세스 / 스레드가사용할공유변수를 Monitor 내지역변수로선언 P, V 부분때문에함수는하나만실행가능 Implicit 부분컴파일러가제공 11

Monitors (Cont d) 모니터동작특징 : 지역변수는모니터내의함수 ( 프로시저 ) 에의해서만접근가능 Class 생각하면되겠네 프로세스는모니터의프로시저호출을통해모니터에진입가능언제나단지하나의프로세스만이모니터내부에존재 ( 상호배제 ) 상호배제 (Mutual exclusion) 를보장 상호배제를위하여별도의프로그램을작성할필요없음 운영체제에서제공 공유데이터또는자원을모니터안에둠으로써보호 공유자원을 Monitor 내부에지역변수로정의 12

Concept of Monitors Monitors (Cont d) Process Waiting Queue shared data operations High-Level Language Support Monitor 자원사용은상위언어에서만지원가능 Queue 에대기하고있는 Process 만이모니터객체의 data, operation 에차례대로접근가능 공유자원의동시접근을완전히해결 initialization code Instance of Monitor Class 13

Monitor Solution of Shared Value Monitor 예제 Monitors (Cont d) balance 변수를조작하는함수는 monitor 내에있으므로하나의프로세스만이 balance 변수조작가능. monitor sharedbalance { double balance; public: credit(double amount) {balance += amount;}; debit(double amount) {balance -= amount;}; 공용함수 공용함수 }; 14

Monitor Solution of Readers-Writers Case 1 Monitors (Cont d) Monitor 의선언과수행 (Reader/Writer 에 Monitor 적용예제 ) 보통의객체지향언어의사용과동일한형태. 협력하는프로세스의기본조건을만족. Monitor 선언코드 monitor readerwriter_1 { int numberofreaders = 0; int numberofwriters = 0; boolean busy = FALSE; - writer가사용중인지체크 public: startread() { }; finishread() { }; startwrite() { }; finishwrite() { }; }; Monitor 실행코드 reader(){ while(true) { startread(); read the resource; finishread(); } fork(reader, 0); fork(reader, 0): fork(writer, 0); fork(writer, 0); writer(){ while(true) { startwriter(); write the resource; finishwriter(); } 15

Monitor Problem of Readers-Writers Monitors (Cont d) 모니터에서발생가능한문제점 시나리오 1. Reader가대기큐에도착 2. Writer가대기큐에도착문제점 : finishread() 를수행하지못함 writer 가 startwriter 에서 busy waiting 을하고있기때문에 monitor 함수 finishread 수행이불가능 monitor readerwriter_1 { int numberofreaders = 0; int numberofwriters = 0; boolean busy = FALSE; public: startread() { while(numberofwriters!= 0) ; numberofreaders++; }; finishread() { numberofreaders--; }; startwrite() { numberofwriters++; while( busy (numberofreaders > 0) ) ; busy = TRUE; }; finishwrite() { numberofwriters--; busy = FALSE; }; }; 한번에하나의 process/threads 만동작가능하므로 while(); 이반복수행되면, 다른 Process / Thread 의진행이불가능함. 16

Problem of Monitor Monitors (Cont d) 모니터에서빠져나오기위해잠시멈추는 (Suspend) 방법이필요 프로세스 / 스레드는 condition 이바뀔때까지대기 Condition Variable condition 이바뀔때재시작할수있는특별한메커니즘필요 프로세스는 condition 이만족하지않을때, Monitor 를빠져나가 suspend 됨 다른프로세스가 condition 을변경할때 Suspend 된프로세스가깨어나고 Monitor 에진입 17

Solution of Monitor Problem Monitors (Cont d) Condition Variables 을이용하여해결. busy waiting 대체 일종의 OS 제공 event 임 모니터내부에서만발생 (event 는모든프로세스 / 스레드에영향 ) Condition Variable 을다루는 Operations wait: Suspend 다른프로세스가 signal 을수행하기전까지일시적으로중지된프로세스 signal: 하나라도일시중지된프로세스가있으면이를재개하도록한다. 없으면아무것도하지않음. queue: 적어도하나의일시중지된프로세스가존재하면 TRUE 를반환. 18

Monitor Solution of Readers-Writers Case 2 Reader/Writer 예제 Monitors (Cont d) monitor readerwriter_2 { int numberofreaders = 0; boolean busy = FALSE; condition oktoread, oktowrite; signal public: startread() { if(busy (oktowrite.queue()) oktoread.wait(); numberofreaders++; oktoread.signal(); }; finishread() { numberofreaders--; if(numberofreaders == 0) oktowrite.signal(); }; signal startwrite() { if((numberofreaders!= 0) busy) oktowrite.wait(); busy = TRUE; }; StartRead 는대기하고있는모든 Reader 에게시그널전송 (Reader 는동시에여러개수행가능 ) FinishRead 는모든 Reader 가작업종료시, Writer 에게시그널전송 signal finishwrite() { busy = FALSE; if(oktoread.queue()) oktoread.signal(); else oktowrite.signal(); }; }; signal FinishWrite 는대기하고있는 Reader 와 Writer 에게시그널전송 (Reader 에게우선순위부여 ) 19

Hoare semantics suspend(p 1 ) Signal Semantics if(resourcenotavailable()) resourcecondition.wait(); /* now available continue */ signal(p 0 ): Signal 이발생하면 P 0 는멈추고 P 1 이 if 문다음부터실행 resourcecondition.signal(); Hansen semantics(mesa 언어에서구현 ) suspend(p 1 ) while(resourcenotavailable()) resourcecondition.wait(); /* now available continue */ signal(p 0 ): P 0 는 Signal 을발생만시키고, 실행을계속하고끝낸후에 P 1 의조건을다시검사 resourcecondition.signal(); 적극적모니터방식 Signal 발생시 context switching 발생 Two Types of Monitor Semantics 수동적모니터방식 Signal 발생하더라도계속수행 20

Monitors 의예 문제정의한방향 (One way) 터널이존재반대편에차량이없는경우에만터널사용가능현재진행중인방향에도착하면터널을바로사용가능 North N Monitor Example of Traffic Problem 터널을지나갈수없음 N N S S 차량 : Process Condition Queue: 1 개 One-way tunnel S S 터널을지나갈수있음 South X S 터널을지나갈수있음 터널을지나갈수없음 21

Monitors 의예 (Cont d) 편도터널해결방법 차량이도착하면반대방향차량이있는가로진행여부판단 현재이동가능한방향은모든차량이지날때까지계속유지됨. 편도터널선언코드 monitor tunnel { int northbound = 0; int southbound = 0; trafficsignal nbsignal = RED; trafficsignal sbsignal = GREEN; condition busy; public: northboundarrival() { }; southboundarrival() { }; depart(direction exit) { }; 편도터널실행코드 NorthCar(){ while(true) { northboundarrival(); depart(north); } fork(northcar, 0); fork(southcar, 0): fork(northcar, 0); fork(southcar, 0); SouthCar(){ while(true) { southboundarrival(); depart(south); } }; 22

Monitors 의예 (Cont d) 편도터널의해결방법 Monitor Solution of Traffic Problem monitor tunnel { int northbound = 0, southbound = 0; trafficsignal nbsignal = RED, sbsignal = GREEN; condition busy; public: northboundarrival() { 1 if(southbound > 0) busy.wait(); northbound++; nbsignal = GREEN; sbsignal = RED; }; southboundarrival() { 2 if(northbound > 0) busy.wait(); southbound++; nbsignal = RED; sbsignal = GREEN; }; depart(direction exit) { 3 if(exit = NORTH) { northbound--; if(northbound == 0) while(busy.queue()) busy.signal(); }; } 4 Signal Signal else if(exit == SOUTH) { southbound--; if(southbound == 0) while(busy.queue()) busy.signal(); } }; 수행내용 1 북쪽터널입구에도착한경우 - 남쪽에차량이있다면대기. - 차량이없다면차량대수변경 - 신호등변경. 2 남쪽터널입구에도착한경우 - 북쪽에차량이있다면대기. - 차량이없다면 Shared Value 변경 - 신호등변경. 3 북쪽에서출발하여남쪽에도착한경우 - Shared Value 변경 - 북쪽에남아있는차량수를확인. : 남아있다면현재신호등유지 : 없다면남쪽에대기하는차량에 signal 전송 4 남쪽에서출발하여북쪽에도착한경우 - Shared Value 변경 - 남쪽에남아있는차량수를확인. : 남아있다면현재신호등유지 : 없다면북쪽에대기하는차량에 signal 전송 23

생각하는철학자문제 Monitors 의예 (Cont d) 5명의철학자와 5개의포크철학자들은오직먹거나생각만함먹기위해서는좌 / 우양쪽의포크가반드시필요아무도먹지못하여굶어죽지않아야함서로아무것도못하는상태가되지않아야함 24

Monitors 의예 (Cont d) Monitor Solution of Dining Philosophers Thinking i test((i-1) mod n) test((i+1) mod n) p2 먹으려고할때 If i = 0: test p4, p1 (0 1) mod 5 = 4 (0 + 1) mod 5 = 1 If i = 1: test p0, p2 (1 1) mod 5 = 0 (1 + 1) mod 5 = 2 Thinking or Eating p1 p3 Thinking or Eating If i = 2: test p1, p3 (2-1) mod 5 = 1 (2 + 1) mod 5 = 3 p2, p3 을 test 함. If i =3: test p2, p4 (3-1) mod 5 = 2 (3 + 1) mod 5 = 4 p0 p4 n : 철학자의수 i : 식사를하려는철학자 If i = 4: test p3, p0 (4 1) mod 5 = 3 (4 + 1) mod 5 = 0 Test 한철학자가 EATING 이아니면 fork 를사용할수있음. 25

Monitors 의예 (Cont d) 생각하는철학자해결방법 식사하려는철학자좌우철학자가생각중이면식사가능식사가끝나면좌우철학자가식사할수있도록해준다. 생각하는철학자선언코드생각하는철학자실행코드 monitor diningphilosophers { status state[n]; condition self[n]; test(int i) public: diningphilosophers() { }; pickupforks(int i) { }; putdownforks(int i) { }; }; Philosophers(){ while(true) { pickupforks(i); putdownforks(i); } fork(philosophers, 0); fork(philosophers, 0): fork(philosophers, 0); fork(philosophers, 0); 26

#define N enum status(eating, HUNGRY, THINKING}; monitor diningphilosophers { status state[n]; condition self[n]; Monitors 의예 (Cont d) 생각하는철학자해결방법 test(int i) { if((state[(i-1) mod N]!= EATING) && (state[i] == HUNGRY) && (state[(i+1) mod N]!= EATING)) { state[i] = EATING; self[i].signal(); } }; public: Signal diningphilosophers() { // Initilization for(int i = 0; i < N; i++) state[i] = THINKING; }; Monitor Solution of Dining Philosophers 식사하려는철학자좌우의철학자상태를점검하고, 식사가가능하면시그널을전송한다. 철학자초기화. 모두생각하는상태. pickupforks(int i) { state[i] = HUNGRY; test(i); if(state[i]!= EATING) self[i].wait(); }; putdownforks(int i) { state[i] = THINKING; test((i-1) mod N); test((i+1) mod N); }; } PickUpForks: 상태변경. 좌우철학자확인. 현재식사중이아니면대기 putdownforks: 상태변경. 좌우철학자가식사하려고하면식사할수있도록한다. 27

Definition of IPC IPC 란? IPC (Inter-Process Communication) 프로세스간정보전달을위해서 Message 를사용하는메커니즘 IPC 의필요성 각각의스레드나프로세스는동기적인 ( 또는비동기적인 ) 공동작업을하기위해상호간에정보전달을할필요가있음 Signal, semaphore 등은하나의프로세스에서다른프로세스로정보를전달할수없음 Monitor 는정보를공유하나, Monitor 내의 shared memory 를통해서만가능. Shared Memory 로프로세스간의사소통을할수없는경우 OS 가 Shared Memory 를지원하지않을경우 보통지원안함 프로세스가네트워크상의서로다른 Machine 에존재할경우 28

Basic Mechanism of IPC Basic Mechanism IPC (Cont d) p 0 가 p 1 에게정보를복사하려면 Memory protection 을우회할필요가있음 원격지에정보를복사하기위해네트워크를사용해야함 p1 이이해할수있는형태로송신해야함 (message format) 공유될정보 Message 복사된정보 OS IPC Address Space for p 0 Mechanism Address Space for p 1 p1 은 message 가온것을알지못함 송신및수신여부인지필요 (protocol) 29

Message Format ( 구조적정보 ) Control information: 버퍼용량을벗어날경우 (Overflow) 처리. 메시지순서번호우선순위등. Header Message Type Destination ID Source ID Message Length Control Information Type 은동기화정보, 오류보고와같은특별한정보가들어있음을나타내는데필요 Body Message Contents 헤더가없는경우프로세스들이구현 (ex. Unix pipe) 30

필요성 Message Protocols Needs of Message Protocols Message 를주고받는각 Process 가서로에대해알아야전송및수신이가능. Sender 는 receiver 가 ready 상태인지또는 sender 가보낸정보를 receiver 가수신했는지를알아야함 Message system 은 protocol 을명세함 Message 의전송과수신시에공통된형태가필요하고, receiver 는 sender 가보낸정보를해석할수있어야함 Standard header 가필요. Message Queue Semaphore Shared Memory <sys/msg.h> <sys/sem.h> <sys/shm.h> 31

Transmit Operations Asynchronous Send Message 전송후, 코드를계속실행. Receiver로부터정보가전달되었다는 feedback이없음 장점 : 전송후에다른작업처리가능. 단점 : 정상전송이되었는지알수없음. Synchronous send Two Message Transmit Methods Message 전송후, 메시지를받을때까지 sender 는 block 됨 장점 : Message의정상처리와오류제어를할수있음. 단점 : Message를받을때까지불특정시간을대기해야함. Message를 mailbox에전달하고, sender는실행을재개 - 약한동기화실제로 receiver가 mailbox에서꺼낼때실행을재개 - 강력한동기화 32

Blocking receive: Receive Operation Mailbox 에 Message 가없다면, receiver 는 Message 가도착할때가지 block 장점 : 정확한 Message 의수신가능. ( 오류제어 ) 단점 : 전송수단의문제발생시불특정시간동안대기해야함. Nonblocking receive: Mailbox 에 Message 가없다면, 이상황에대한 error 값반환 장점 : Process 는지속적으로작업가능. Two Message Receive Methods 단점 : Message 가도착하지못한경우처리불가능상태가됨. 33

Message Send Using Synchronized Transmit and Block Receive Synchronized IPC Code for p 1 Code for p 2 /* signal p 2 */ syncsend(message1, p2); <waiting >; /* wait for signal from p2 */ blockreceive(msgbuff, &from); /* wait for signal from p 1 */ blockreceive(msgbuff, &from); <process message>; /* signal p 1 */ syncsend(message2, p1); p1 p2 syncsend( ) blockreceive( ) waiting blockreceive( ) syncsend( ) 34

Message Send Using Asynchronized Transmit and Nonblock Receive Asynchronous IPC Code for p 1 Code for p 2 /* signal p 2 */ asyncsend(message 1, p 2 ); <other processing>; /* wait for signal from p 2 */ while(!nbreceive(&msg, &from)); p1 asyncsend( ) nonblockreceive( ) nonblockreceive( ) /* test for signal from p 1 */ if(nbreceive(&msg, &from)) { <process message>; asyncsend(message 2, p 1 ); }else{ <other processing>; } p2 nonblockreceive( ) nonblockreceive( ) asyncsend( ) 35

Mailbox in Process Mailbox Mechanism in Process Mailbox는일종의 Message Queue로 IPC의하나임. p 1 s address space는 compiler나 loader에의해할당됨부주의한 Mailbox영역사용을피해야함 p 1 의접근 Address Space for p 0 Address Space for p 1 Mailbox for p 1 Info to be shared Message Message Message Info copy send( p 1, ); receive( ); send function - System Call OS Interface p 1 프로세스내에 mailbox 가있기떄문에 library 로도가능 receive function 36

Mailbox Mechanism in OS Mailbox in OS OS 가 Mailbox 를관리하여더안전한메시지전송이가능. - p 1 이 mailbox 접근불가 정보의복사를위해 Memory protection 을우회할필요가없음 Address Space for p 0 Address Space for p 1 공유될정보 send( p 1, ); 단점 - 모드전환이많이일어남 - OS 에필요한공간이증가 OS Interface 복사된정보 receive( ); Mailbox for p 1 send function Message Message Message receive function 37

Definition of Pipe Pipe 란 UNIX Pipe OS 가제공하는단방향통로를이용하여 Message 를전송하는 IPC 의하나임. 방향성이있어한번에한방향으로만데이터전송이가능. Address Space for p 1 공유될정보 write(pipe[1], ); pip 생성 ( 선언 ) 으로 핸들러얻음 System Call Interface 복사된정보 read(pipe[0]); write function pipe for p 1 and p 2 read function 38

Interface and Execution of Pipe UNIX Pipe (cont d) 파이프인터페이스는파일인터페이스와유사함 open과유사한 pipe 시스템콜을사용해서파이프를생성. File read/write 시스템콜을사용하여정보를받거나보냄 파이프를사용할때일어나는일 파이프가생성될때커널은하나의버퍼생성 프로세스들은 read/write 시스템콜을사용해서버퍼에서정보를읽어오거나자신의주소영역에서버퍼로정보를쓸수있음 39

Read/Write Method of Pipe fork() 시스템콜에의해서생성된자식프로세스는부모프로세스와파일 handler 를공유함 pipeid[0] 은파이프에서읽기위한 handler pipeid[1] 은파이프에쓰기위한 handler Read/Write Method of Pipe int pipeid[2]; pipe(pipeid); if(fork() == 0) { /* the child */ read(pipeid[0], childbuf, len); <process the message>; } else { /* the parent */ write(pipeid[1], msgtochild, len); } 40

Read/Write Method of Pipe ( con t) write() 는비동기적인 operation 임 write 할수없을경우 error 값을돌려줌 Non-blocking Read Method of Pipe 일반적으로 read는 blocking read read operation은 non-blocking read일수있음 #include <sys/ioctl.h> int pipeid[2]; pipe(pipeid); ioctl(pipeid[0], FIONBIO, &on); read(pipeid[0], buffer, len); if(errno!= EWOULDBLOCK) { /* no data */ } else { /* have data */ 41