Module 7: Process Synchronization

Similar documents
10주차.key

Module 7: Process Synchronization

Microsoft PowerPoint - o6.pptx

Microsoft PowerPoint - o6.pptx

Microsoft PowerPoint - o6.pptx

untitled

6주차.key

Microsoft PowerPoint - StallingsOS6e-Chap05.pptx

Synchronization

Chap06(Interprocess Communication).PDF

chap 5: Trees

untitled

Abstract View of System Components

Page 2 of 6 Here are the rules for conjugating Whether (or not) and If when using a Descriptive Verb. The only difference here from Action Verbs is wh

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

Page 2 of 5 아니다 means to not be, and is therefore the opposite of 이다. While English simply turns words like to be or to exist negative by adding not,

Microsoft PowerPoint - StallingsOS6e-Chap06.ppt [호환 모드]

PowerPoint 프레젠테이션

제11장 프로세스와 쓰레드

입학사정관제도

- 2 -

PowerPoint 프레젠테이션

<32382DC3BBB0A2C0E5BED6C0DA2E687770>

본문01

지능정보연구제 16 권제 1 호 2010 년 3 월 (pp.71~92),.,.,., Support Vector Machines,,., KOSPI200.,. * 지능정보연구제 16 권제 1 호 2010 년 3 월

Chap04(Signals and Sessions).PDF

Chapter #01 Subject

강의10

Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100

Mobile Service > IAP > Android SDK [ ] IAP SDK TOAST SDK. IAP SDK. Android Studio IDE Android SDK Version (API Level 10). Name Reference V

<30322D28C6AF29C0CCB1E2B4EB35362D312E687770>

PowerPoint 프레젠테이션

Microsoft Word - FunctionCall

Interstage5 SOAP서비스 설정 가이드

ESP1ºÎ-04

example code are examined in this stage The low pressure pressurizer reactor trip module of the Plant Protection System was programmed as subject for

No Slide Title

Microsoft PowerPoint - 04-UDP Programming.ppt

11¹Ú´ö±Ô

untitled

step 1-1

K7VT2_QIG_v3

APOGEE Insight_KR_Base_3P11

PowerPoint 프레젠테이션

Microsoft Word - ExecutionStack

<31325FB1E8B0E6BCBA2E687770>

#중등독해1-1단원(8~35)학

<32B1B3BDC32E687770>

1

Something that can be seen, touched or otherwise sensed


4. #include <stdio.h> #include <stdlib.h> int main() { functiona(); } void functiona() { printf("hihi\n"); } warning: conflicting types for functiona

CD-RW_Advanced.PDF

4번.hwp

Figure 5.01

대한한의학원전학회지26권4호-교정본(1125).hwp

김기남_ATDC2016_160620_[키노트].key

Chapter 4. LISTS

슬라이드 1

DE1-SoC Board

¹Ìµå¹Ì3Â÷Àμâ

#Ȳ¿ë¼®

2002년 2학기 자료구조

λx.x (λz.λx.x z) (λx.x)(λz.(λx.x)z) (λz.(λx.x) z) Call-by Name. Normal Order. (λz.z)

thesis

歯3이화진

비긴쿡-자바 00앞부속

歯1.PDF

슬라이드 1

I&IRC5 TG_08권

DIY 챗봇 - LangCon

UI TASK & KEY EVENT

thesis

Chapter 4. LISTS

The Self-Managing Database : Automatic Health Monitoring and Alerting

±èÇö¿í Ãâ·Â

03.Agile.key

03장.스택.key

untitled

하나님의 선한 손의 도우심 이세상에서 가장 큰 축복은 하나님이 나와 함께 하시는 것입니다. 그 이 유는 하나님이 모든 축복의 근원이시기 때문입니다. 에스라서에 보면 하나님의 선한 손의 도우심이 함께 했던 사람의 이야기 가 나와 있는데 에스라 7장은 거듭해서 그 비결을

0125_ 워크샵 발표자료_완성.key

<C7D1B9CEC1B7BEEEB9AEC7D03631C1FD28C3D6C1BE292E687770>

Oracle9i Real Application Clusters

휠세미나3 ver0.4

2 min 응용 말하기 01 I set my alarm for It goes off. 03 It doesn t go off. 04 I sleep in. 05 I make my bed. 06 I brush my teeth. 07 I take a shower.

Chapter 4. LISTS

13주-14주proc.PDF

Microsoft PowerPoint - 27.pptx


Let G = (V, E) be a connected, undirected graph with a real-valued weight function w defined on E. Let A be a set of E, possibly empty, that is includ

CompareAndSet(CAS) 함수는 address 주소의값이 oldvalue 인지비교해서같으면 newvalue 로 바꾼다. 소프트웨어 lock 을사용하는것이아니고, 하드웨어에서제공하는기능이므로더빠르고 간편하다. X86 에서는 _InterlockedCompareEx

PRO1_04E [읽기 전용]

<B3EDB9AEC1FD5F3235C1FD2E687770>

(2005) ,,.,..,,..,.,,,,,

프로그램을 학교 등지에서 조금이라도 배운 사람들을 위한 프로그래밍 노트 입니다. 저 역시 그 사람들 중 하나 입니다. 중고등학교 시절 학교 도서관, 새로 생긴 시립 도서관 등을 다니며 책을 보 고 정리하며 어느정도 독학으르 공부하긴 했지만, 자주 안하다 보면 금방 잊어

HW5 Exercise 1 (60pts) M interpreter with a simple type system M. M. M.., M (simple type system). M, M. M., M.

untitled

C# Programming Guide - Types

04-다시_고속철도61~80p

DBPIA-NURIMEDIA

Transcription:

Chapter 6: Process Synchronization ( 프로세스동기화 ), Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Module 6: Synchronization( 동기화 ) Background( 배경 ) The Critical-Section Problem( 임계구역문제 ) Peterson s Solution( 피터슨솔루션 ) Synchronization Hardware( 동기화하드웨어 ) Semaphores( 세마포 ) Classic Problems of Synchronization( 고전적동기화문제들 ) Monitors( 모니터 ) Synchronization Examples ( 동기화사례 ) Atomic Transactions( 원자적트랜잭션 ) 6.2 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Objectives To introduce the critical-section problem, whose solutions can be used to ensure the consistency of shared data( 공유데이터의일관성을보장하기위한임계구역문제소개 ) To present both software and hardware solutions of the critical-section problem( 임계구역문제의소프트웨어및하드웨어솔루션 ) To introduce the concept of an atomic transaction and describe mechanisms to ensure atomicity( 원자적트랜잭션의개념을소개하고원자성을보장하기위한매카니즘을기술한다.) 6.3 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Background Concurrent access to shared data may result in data inconsistency ( 공유데이터의동시접근은데이터의불일치를초래할수있다.) Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes ( 데이터의일관성을유지하기위해서는프로세스들의실행순서를보증하는메커니즘이요구된다.) Suppose that we wanted to provide a solution to the consumerproducer problem that fills all the buffers. We can do so by having an integer count that keeps track of the number of full buffers. Initially, count is set to 0. It is incremented by the producer after it produces a new buffer and is decremented by the consumer after it consumes a buffer. ( 모든버퍼를사용하는소비자 - 생산자문제에서 count 변수를이용하여소비실행순서를보증하였다.) 6.4 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Previous Producer-Consumer (3.4.1) Bounded Shared Buffer Producer process item nextproduced; while (true) { /* Produce an item in nextproduced */ while ((((in + 1) % BUFFER_SIZE) == out) ; /* do nothing -- no free buffers */ buffer[in] = nextproduced; in = (in + 1) % BUFFER SIZE; Shared Data Consumer process item nextconsumed; while (true) { while (in == out) ; // do nothing -- nothing to consume nextconsumed = buffer[out]; // remove an item from the buffer out = (out + 1) % BUFFER SIZE; /* consume the item in nextconsume */ At most BUFFER_SIZE-1 items in the buffer of BUFFER_SIZE #define BUFFER_SIZE 10 typedef struct {... item; item buffer[buffer_size]; int in = 0; //used by producer int out = 0; //used by consumer 6.5 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Previous Producer-Consumer (3.4.1) New Shared Buffer with counter Producer process while (true) { /* produce an item and put in nextproduced */ while (count == BUFFER_SIZE) ; // do nothing buffer [in] = nextproduced; in = (in + 1) % BUFFER_SIZE; count++; Consumer process while (true) { while (count == 0) ; // do nothing nextconsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; count--; /* consume the item in nextconsumed Allow full buffer, BUFFER_SIZE items in the buffer of BUFFER_SIZE Modified Producer Consumer define BUFFER_SIZE 10 typedef struct {... item; item buffer[buffer_size]; int in = 0; int out = 0; int counter = 0; 6.6 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Bounded Buffer The statements counter++; counter--; must be performed atomically ( 원자적으로연산되어야한다.) Atomic operation means an operation that completes in its entirety without interruption ( 원자연산은외부의인터럽트없이완전히실행되는연산이다.) 6.7 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Race Condition( 경합상태 ) 경합상태 (race condition) : 두개의프로세스가경쟁적으로한변수를조작 ( 예 ) 공유변수 count 의변경명령이동시에수행될경우불일치발생 생산자의 count ++ register1 = count; register1 = register1 + 1; count = register1; 소비자의 counter -- register2 = count; register2 = register2-1; count = register2; 병행실행 (concurrent execution) T0: 생산자 register1 := count {register1 = 5 T1: 생산자 register1 : = register1 + 1 {register1 = 6 T2: 소비자 register2 := count {register2 = 5 T3: 소비자 register2 := register2-1 {register2 = 4 T4: 생산자 count := register1 {counter = 6 T5: 소비자 count := register2 {counter = 4 한 process 만접근하게해야함 6.8 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

An Example Withdraw money from a bank account( 은행계좌인출문제 ) Suppose you and your girl(boy) friend share a bank account with a balance of 1,000,000won What happens if both go to separate ATM machines, and simultaneously withdraw 100,000won from the account? ( 은행의 100 만원을두사람이다른 ATM 에서인출을동시에시도한다 ) int withdraw (account, amount) { balance = get_balance (account); balance = balance - amount; put_balance (account, balance); return balance; 6.9 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

An Example (Cont d) Interleaved schedules Represent the situation by creating a separate thread for each person to do the withdrawals The execution of the two threads can be interleaved, assuming preemptive scheduling: 6.10 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Solution to Critical-Section Problem( 임계구역문제 ) 임계구역 프로세스가공유자료를변경하는코드영역 상호배타적 (mutually exclusive) 이어야함 프로세스구조 진입구역 (entry section) : 진입허가요청 ( 한프로세스만실행 ) 출구구역 (exit section) 잔류구역 (remainder section) 임계구역해결을위한 3 요구조건 (requirements) R1. 상호배제 (mutual exclusion): 한프로세스만임계구역진입 R2. 진행 (progress): 자연스럽게막힘이없이진행, 임계구역에진입할프로세스선택이영원히지연되지않음 R3. 한계대기 (bounded waiting): 한프로세스가임계구역진입요청후기다리는데한계가있음 (no starvation) 기본기계명령어들 (load, store, test) 들은원자적으로실행됨 (executed atomically) 을가정 6.11 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Solution to Critical-Section Problem General structure for a typical process Pi do { entry section exit section critical section remainder section while (TRUE); 6.12 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Mechanisms for Critical Sections Locks Very primitive, minimal semantics, used to build others Semaphores Basic, easy to get the hang of, hard to program with Monitors High-level, requires language support, implicit operations Easy to program with: Java synchronized Messages Simple model of communication and synchronization based on (atomic) transfer of data across a channel Direct application to distributed systems 6.13 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Locks Very primitive, minimal semantics, used to build others Software Solutions Peterson s Solution for two process Bakery Algorithm for n processes Hardware Solutions Mutual Exclusion solution using TestAndSet Mutual Exclusion Solution using Swap Instruction Bounded Mutual Exclusion solution using TestAndSet 6.14 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Locks A lock is an object (in memory) that provides the following two operations: acquire(): wait until lock is free, then grab it (lock 가해제될때까지가다린후해제되면잡는다 ) release(): unlock, and wake up any thread waiting in acquire() ( 해제, 대기중인쓰레드를활성화한다 ) Using locks Lock is initially free Call acquire() before entering a critical section, and release() after leaving it Between acquire() and release(), the thread holds the lock acquire() does not return until the caller holds the lock At most one thread can hold a lock at a time Locks can spin (a spinlock) or block (a mutex) A mutex is an object in a program that serves as a lock and used to negotiate mutual exclusion among threads. 6.15 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Using Locks 6.16 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Implementing Locks (Cont d) Problem Implementation of locks has a critical section, too! The acquire/release must be atomic A recursion, huh? Atomic operation Executes as though it could not be interrupted Code that executes all or nothing Solutions Software-only algorithms Algorithm for two processes Bakery algorithm for more than two processes Hardware atomic instructions Test-and-set, compare-and-swap, etc. Disable/re-enable interrupts To prevent context switches 6.17 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Initial Attempts to Solve Problem Only 2 processes, P0 and P1 General structure of process Pi (other process Pj) do { entry section critical section exit section remainder section while (1); Processes may share some common variables to synchronize their actions Entry section Acquire a lock Exit section Release a lock 6.18 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Peterson s Solution(software) 2개프로세스의 S/W 임계구역문제해법 LOAD 와 STORE 명령은원자적 (atomic) 즉, 수행도중절대인터럽트되지않음 2개프로세스가아래 2개변수공유 : int turn; Boolean flag[2] 변수 turn 은어느임계구역진입순번표시 The flag 배열은임계구역진입준비됨표시 flag[i] = true 는 process P i 가준비되었음! 6.19 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Algorithm for Process P i in Peterson s solution The structure of process Pi do { flag[i] = TRUE; turn = j; //trigger Pj while (flag[j] && turn == j); critical section flag[i] = FALSE; remainder section while (TRUE); The structure of process Pj do { flag[j] = TRUE; turn = i; //trigger Pi while (flag[i] && turn == i); flag[j] = FALSE; while (TRUE); critical section remainder section Pi enter CS only when frag[j]==false or turn==i 동시시도시 frag[i]==frag[j]==true => turn 값배타적, 상대방 trigger 6.20 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Bakery Algorithm Critical section for n processes(n 개프로세스에대한임계구역문제 ) Before entering its critical section, process receives a number. Holder of the smallest number enters the critical section If processes Pi and Pj receive the same number, if i < j, then Pi is served first; else Pj is served first The numbering scheme always generates numbers in increasing order of enumeration; i.e., 1,2,3,3,3,3,4,5... 최소번호수령 작은번호를받은프로세스가먼저실행한다. 6.21 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Bakery Algorithm Notation < lexicographical order (ticket #, process id #) (a,b) < (c,d) if a < c or if a = c and b < d max (a 0,, a n-1 ) is a number, k, such that k >= a i for i = 0,, n 1 Shared data boolean choosing[process]; // 우선순위받는기간의미 int priority[process]; // process : process id # Data structures are initialized to false and 0 respectively 6.22 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Bakery Algorithm Shared Varialbes boolean choosing[p]; // 우선순위받기위한대기상태 int priority[p]; // p : process id initially choosing[..]=false; prioty[..]=0; do { choosing[p] = true; // 프로세스 p 가우선순위받는모드진입 priority [p] = max(priority[0], priority[1],, priority[n 1])+1; choosing[p] = false; // // 프로세스 p 가우선순위받는모드종료 for (j = 0; j < n; j++) { while (choosing[j]) ; // 우선순위받는중이면대기 while ((priority[j]!= 0) && ((priority[j],j)< (priority[p], p))) ; critical section priority[p] = 0; remainder section while (1); // 다른프로세스가우선하면그프로세스의처리까지대기 6.23 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Synchronization Hardware Many systems provide hardware (instruction) support for critical section code Uniprocessors could disable interrupts( 입터럽트무력화 ) Currently running code would execute without preemption Generally too inefficient on multiprocessor systems Operating systems using this not broadly scalable Modern machines provide special atomic hardware instructions Atomic = non-interruptable Either test memory word and set value Or swap contents of two memory words 6.24 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Synchronization Hardware General s/w solution to Critical-section Problem Using Locks do { acquire lock critical section release lock remainder section while (TRUE); 6.25 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Mutual Exclusion solution using TestAndSet Mutual Exclusion using TestAndSet (hardware) instruction Shared boolean variable lock., initialized to false. Process Pi for mutual exclusion using TestAndSet atomic instruction initially lock =false; // global variable do { while ( TestAndSet (&lock )) ; // critical section lock = FALSE; // remainder section while (TRUE); //hardware, Atomic instruction boolean TestAndSet (boolean *target { boolean rv = *target; *target = TRUE; return rv: do { while ( TestAndSet (&lock )) ; // critical section lock = FALSE; // remainder section while (TRUE); 6.26 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Mutual Exclusion Solution using Swap Instruction Mutual Exclusion Solution using Swap Shared Boolean variable lock initialized to FALSE; Each process has a local Boolean variable key Process Pi for mutual exclusion using Swap atomic instruction: initially lock=false //shared do { key = TRUE; //local variable while ( key == TRUE) Swap (&lock, &key ); // critical section lock = FALSE; // remainder section while (TRUE); void Swap (boolean *a, boolean *b) //hardware { boolean temp = *a; *a = *b; *b = temp: do { key = TRUE; //local variable while ( key == TRUE) Swap (&lock, &key ); // critical section lock = FALSE; // remainder section while (TRUE); 6.27 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Bounded-waiting Mutual Exclusion with TestandSet() ( 유한대기상호배제소루션 ) do { waiting[i] = TRUE; // key = TRUE; while (waiting[i] && key) //proceed when waiting[i]==false or key(lock)=false key = TestAndSet(&lock); waiting[i] = FALSE; // critical section j = (i + 1) % n; while ((j!= i) &&!waiting[j]) // i다음의대기중인프로세스를활성화한다. Bounded waiting 보장 j = (j + 1) % n; if (j == i) lock = FALSE; // lock= false로하여다른프로세스에게허용 else waiting[j] = FALSE; // lock==true 인상태에서 Pj에서 wile문장을지나 critical section 진입하게한다. // remainder section while (TRUE); 6.28 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

세마포어 (Semaphore concept) Semaphore is A kind of general synchronization tool Aslo is able to be sued as a synchronization tool that does not require busy waiting Semaphore( 신호기 ) S : 원자적함수 wait() 과 signal() 로접근되는정수변수 S originally called P() and V(), (P from Duch proberen, to test. V from verhogen, to increment ) wait (S) { //atomic operation S:semaphor variable while (S <= 0) ; // S>0 때까지대기 S--; signal (S) { //atomic operation S++; 6.29 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Usage of Semaphor Two types of semaphore Counting semaphore 무제한정수처리, N 개의자원관리공유시 Binary semaphore 정수 0,1,mutex locks An example of Binary semaphore Process p with mutual exclusion using semaphore mutex. Semaphore mutex=1; // initialized to 1 Shared data do { wait (mutex); // 1->0 or 다른프로세스가 1 로설정할때까지 busy waiting // Critical Section signal (mutex); // 0->1 // remainder section while (TRUE); An example of Counting semaphore N 개의공유자원을이용하기위한상호배제 Semaphore res=n ; // 공유자원수 : N do { Wait(res) //res 자원이용하기전 N==0이면모든자원이사용중 // Critical Section Signal(res) //res++ 자원이용후 // remainder section while(true); 6.30 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Semaphore Implementation with no Busy waiting 기본개념 Wait 연산의대기를무한반복대신에대기큐에서수행되도록하여시스템의효율을증가시킨다. Semaphore 구조 typedef struct { int value; // struct process *L; //pointer to next record in the list semaphore; Two operations: block 프로세스를대기큐에추가하고일시중지 suspends the process, place the process invoking the operation on the appropriate waiting queue. wakeup 대기중인큐의포세스한개를분리하여 ready 큐에삽입하여실행을재개한다. resumes the execution of a blocked process, remove one of processes in the waiting queue and place it in the ready queue. 6.31 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Semaphore Implementation with no Busy waiting (Cont.) Implementation of wait: wait(semaphore *S) { S->value--; //-value 의 value 는대기중인 process 의수이다. if (S->value < 0) { add this process to S->list; //add itself onto waiting list block(); // 자신의프로세스는대기큐로이동 / 실행중지 // 0 : 다른프로세스실행방지시키고자신은계속실행 Implementation of signal: signal(semaphore *S) { S->value++; if (S->value <= 0) { remove a process P from S->list; wakeup(p); // OS scheduler 의 ready queue 로이동시킨다. // >=1 : 다른프로세스실행을허용 6.32 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Deadlock and Starvation Deadlock 예 two or more processes are waiting indefinitely for an event(signal()) that can be caused by only one of the waiting processes ( 둘또는그이상의프로세스들이대기중인프로세스중하나가발생시킬이벤트를무한정기다리고있는상태 ) Let S and Q be two semaphores initialized to 1 where two processes P1,P2 ( 프로세스 P1,P2 가 3 개의세마포 S,M 를다음과같이사용하면발생가능 ) P 0 P 1 wait (S); wait (Q); wait (Q); wait (S);.... signal (S); signal (S); signal (Q); Starvation signal (Q); indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended. (P0,P1 모두세마포대기큐에추가된상태면영원히재실행이불가하다.) 6.33 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

6.6 Classical Problems of Synchronization Bounded-Buffer Problem Readers and Writers Problem Dining-Philosophers Problem Semaphore 변수사용 6.34 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Bounded Buffer Problem Synchronization with critical problem initially in=out=counter=0 35 6.35 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Bounded Buffer Problem (Cont d) Implementation with semaphores 36 6.36 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

C# Implementation with semaphores using C# language Mutex mutex = new Mutex() Semaphore empty = new Semaphore(N,N): Semaphore full =new Semaphore(0,N): void Produceer { while (true) { T t = Produce(); empty.waitone(); //empty mutex.waitone(); //mutex Append(t); mutex.releasemutex(); //mutex++ full.release(); //full++ void Consume er { while (true) { full.waitone(); //full mutex.waitone(); //mutex T t = Take(); mutex.releasemutex(); //mutex++ empty.release(); //empty-- Consume(t); 37 6.37 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Semaphore 와 mutex 를이용한생산자 - 소비자문제 (C#) using System.Text; using System.Threading; abstract class ProCon<T> { public ProCon(int maxbuffersize) { this.maxbuffersize = maxbuffersize; mutex = new Mutex(); full = new Semaphore(0, maxbuffersize); empty = new Semaphore(maxBufferSize, maxbuffersize); public void Producer(){ public void Consumer(){ abstract public T Take(); abstract public void Append(T t); abstract public T Produce(); abstract public void Consume(T t); class MyProCon : ProCon<string> { protected List<string> list; public MyProCon(int maxsize) : base(maxsize) { list = new List<string>(maxSize); override public T Take() { override public void Append(T t) { override public T Produce() { override public void Consume(T t) { class Program { public static void Main(string[] args) { MyProCon m = new MyProCon(4); Thread pro = new Thread(m.Producer); pro.start(); // Thread pro2 = new Thread(m.Producer); //pro2.start(); Thread con = new Thread(m.Consumer); con.start(); Thread.Sleep(10000); //10 초정지 pro.suspend(); con.suspend(); //pro.join(); //con.join(); 6.38 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

abstract class ProCon<T> { protected readonly int maxbuffersize; protected Mutex mutex; protected Semaphore full; protected Semaphore empty; public ProCon(int maxbuffersize) { this.maxbuffersize = maxbuffersize; mutex = new Mutex(); full = new Semaphore(0, maxbuffersize); empty = new Semaphore(maxBufferSize, maxbuffersize); public void Producer() { while (true) { T t = Produce(); empty.waitone(); //empty-- mutex.waitone(); //mutex-- Append(t); mutex.releasemutex(); //mutex++ full.release(); //full++ public void Consumer() { while (true) { full.waitone(); //full-- mutex.waitone(); //mutex-- T t = Take(); mutex.releasemutex(); //mutex++ empty.release(); //empty++ Consume(t); //codes of critical section abstract public T Take(); abstract public void Append(T t); //non critical section abstract public T Produce(); abstract public void Consume(T t); class MyProCon : ProCon<string> { protected List<string> list; public MyProCon(int maxsize) : base(maxsize) { list = new List<string>(maxSize); // 데이터추가 ( 저장 ) //critical codes override public void Append(string t) { list.add(t); string s = ""; foreach (string a in list) s += a + " "; Console.WriteLine(Thread.CurrentThread.ManagedThreadId + "\tadd : " + list.count + "\t:" + s); //Thread.Sleep(1000); // 데이터소비 //critical codes : override public string Take() { string t = list[0]; list.removeat(0); string s=""; foreach (string a in list) s += a + " "; Console.WriteLine(Thread.CurrentThread.ManagedThreadId+"\tTake: " + list.count + "\t:" +s); Thread.Sleep(2000); return t; // 데이터생성 override public string Produce() { Random r = new Random(); int i = r.next(10); Console.WriteLine(Thread.CurrentThread.ManagedThreadId + "\tpro: " +i); return i.tostring(); // 데이터처리 override public void Consume(string t) { Console.WriteLine(Thread.CurrentThread.ManagedThreadId + "\tcon: " + t); 6.39 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

실행결과분석 void Main() { MyProCon m = new MyProCon(4); Thread pro = new Thread(m.Producer); Thread con = new Thread(m.Consumer); pro.start(); con.start(); Thread.Sleep(10000); //10 초정지 pro.suspend(); con.suspend(); Producer while (true) { 1 T t = Produce(); 2 empty.waitone(); //empty-- 3 mutex.waitone(); //mutex-- 4 Append(t); 5 mutex.releasemutex(); //mutex++ 6 full.release(); //full++ Consumer while (true) { 1 full.waitone(); //full 2 mutex.waitone(); //mutex 3 T t = Take(); 4 mutex.releasemutex(); //mutex++ 5 empty.release(); //empty++ 6 Consume(t); 3 1 Pro: 4 3 4 add : 1 :4 3 1 Pro: 4 4 3 Take: 0 : 3 4 add : 1 :4 3 1 Pro: 2 3 4 add : 2 :4 2 3 1 Pro: 2 3 4 add : 3 :4 2 2 3 Pro: 2 3 add : 4 :4 2 2 2 3 Pro: 2 4 Con: 4 4 Take: 3 :2 2 2 4 Con: 4 3 add : 4 :2 2 2 2 4 Take: 3 :2 2 2 3 Pro: 1 4 Con: 2 3 add : 4 :2 2 2 1 4 Take: 3 :2 2 1 3 Pro: 9 4 Con: 2 3 add : 4 :2 2 1 9 3 Pro: 8 4 Take: 3 :2 1 9 4 Con: 2 6.40 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Readers-Writers Problem 복수의 reader 및 writer 프로세스들이데이터집합을공유하는문제 Readers 읽기전용, 복수의프로세스읽기가능, 수정불가능 Writers 읽고쓰기가능, writer 프로세스들끼리배타적공유 6.41 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Shared Data, initially Readers-Writers Problem (Cont.) Semaphore mutex =1 //readcount 갱신시상호배제용 Semaphore wrt = 1 //writer 상호배제 Integer readcount =0 // reading process The structure of a writer process do { wait (wrt) ; //writing is performed //wrt=0 signal (wrt) ; //wrt=1 while (TRUE); The structure of a reader process do { wait (mutex) ; //mutex=0 readcount ++ ; if (readcount == 1) wait (wrt); // 첫번째 reading 시부터읽는동안 write 금지 signal (mutex) // reading is performed, // 복수프로세스가동시읽기가능 wait (mutex) ; readcount - - ; if (readcount == 0) signal (wrt) ; // 모두 (process) 읽으면쓰기허용 signal (mutex) ; //mutex=1 while (TRUE); 6.42 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Dining-Philosophers Problem Dining philosopher problem Dijkstra, 1965 Life of a philosopher: Repeat forever Thinking Getting hungry Getting two chopsticks Eating The structure of Philosopher i: Shared Data Semaphor chopstick [5] initialized to 1 philosohphor pi do { wait ( chopstick[i] ); wait ( chopstick[ (i + 1) % 5] ); // eat signal ( chopstick[i] ); signal (chopstick[ (i + 1) % 5] ); // think while (TRUE); 6.43 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Problems with Semaphores Correct use of semaphore operations: signal (mutex). wait (mutex) wait (mutex) wait (mutex) Omitting of wait (mutex) or signal (mutex) (or both) 6.44 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Monitors concept 프로세스에서세마포변수를잘못사용하면다양한문제가발생된다. 이런문제를해결하기위하여세마포변수및프로시듀어를구조체 (struct) 안에정의하고추상화하고프로그래머는이프로시듀어를사용하여세마포변수를제어하므로서프로그램머의오류를줄일수있다. Signal(mutex) //critical section wait(mutex) 상호배제위반, 여러프로세스가동시실행,.. Wait(mutex) //critical section wait(mutex) 교착상태 6.45 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Monitors Monitor 는멤버를을캡슐화는 software module 이다. 소프트웨어모듈 ( 구조체, 클래스 ) 이다. 공유데이터구조들과공유데이터구조에서실행되는프로시주어들을캡슐화한다. 이들프로시쥬어를호출하는동시실행주인프로세스간의동기화 한번에하나의프로세스만인활성화된다. 추상화된데이터타입의안전한공유 Monitor syntax(struct) monitor monitor-name { shared variable declarations procedure P1 ( ) {. procedure Pn ( ) { Initialization code (.) { 6.46 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Monitors Condition variable( 개체 ) 모니터의멤버개체 ( 일종의 struct) condition x, y; 프로세스들이모니터내에서대기할수있는수단 condition 개체의멤버 operations wait and signal x.wait(); 프로세스가호출, suspended 상태진입 x.signal(); one suspended process 를재개시킨다. 만일 suspended 프로세스가없으로무시된다. 6.47 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Schematic view of a Monitor waiting queue of processes trying to enter the monitor at most one process in monitor at a time 6.48 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Monitor with Condition Variables 6.49 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Solution to Dining Philosophers 좌우의이웃철학자가젓가락을얻을수있을때만잡도록강제한다. 양쪽의철학자가식사를하지않을때만식사한다. 전체구조 monitor DP { pick(); putdown();.. while(1) { for all i in process Pi { think(); DP.pickup (i); eat(); DP.putdown (i); 6.50 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

monitor DP { Monitor Solution to Dining Philosophers enum { THINKING; HUNGRY, EATING) state [5] ; condition self [5]; void pickup (int i) { // state[i] = HUNGRY; // 상태를 hungry 로 test(i); // 죄우상태점검에따라서식사모드설정 if (state[i]!= EATING) self [i].wait(); // 식사모드로못들어갔으면대기상태로 void putdown (int i) { state[i] = THINKING; // 사색모드로 // test left and right neighbors test((i + 4) % 5); test((i + 1) % 5); void test (int i) { if ( (state[(i + 4) % 5]!= EATING) && (state[i] == HUNGRY) && // 우를점검하여식사대기중이었으면활성화 // 좌를점검하여식사대기중이었으면활성화 (state[(i + 1) % 5]!= EATING) ) // 좌우철학자가식사중이아니고내가 { // 배고프면 state[i] = EATING ; self[i].signal () ; void initialization code() { for (int i = 0; i < 5; i++) state[i] = THINKING; // 내상태를식사모드로설정 // 대기중이었으면자신을활성화 // 모든프로세스의상태를생각모드로 6.51 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

An example of a Monitor to Allocate Single Resource 하나의자원을할당해주는모니터 monitor ResourceAllocator { boolean busy; condition x; void acquire(int time) { if (busy) x.wait(time); //time 과함께저장큐에 busy = TRUE; void release() { busy = FALSE; x.signal(); initialization code() { busy = FALSE; 프로세스에서자원접근하는방법 R.acquire(t) 자원접근 R.release() t: 자원접근요청시간 6.52 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Synchronization Examples Solaris Windows XP Linux Pthreads 6.53 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Solaris Synchronization Implements a variety of locks to support multitasking, multithreading (including real-time threads), and multiprocessing Uses adaptive mutexes for efficiency when protecting data from short code segments Uses condition variables and readers-writers locks when longer sections of code need access to data Uses turnstiles to order the list of threads waiting to acquire either an adaptive mutex or reader-writer lock 6.54 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Windows XP Synchronization Uses interrupt masks to protect access to global resources on uniprocessor systems Uses spinlocks on multiprocessor systems Also provides dispatcher objects which may act as either mutexes and semaphores Dispatcher objects may also provide events An event acts much like a condition variable 6.55 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Linux Synchronization Linux: Prior to kernel Version 2.6, disables interrupts to implement short critical sections Version 2.6 and later, fully preemptive Linux provides: semaphores spin locks 6.56 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

Pthreads Synchronization Pthreads API is OS-independent It provides: mutex locks condition variables Non-portable extensions include: read-write locks spin locks 6.57 / 57 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010

End of Chapter 6, Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010