KON-KUK UNIVERSITY Dept. of Computer Science Since 1996The readers and writers problem987266 정보 박준표997328 정보 이승열KON-KUK UNIVERSITY Dept. of Computer Science Since 1996Reader/Writer 문제 : ① 여러 r/w 문제 중 Database 접근 모델에 대해서 ② 여러 개의 Reader 프로세스는 동시에 Database 접근 가능 ③ Reader 프로세스(Writer)가 Database에 접근 중이면 Writer (Reader) 프로세스는 Database 접근 불가능 1. Writer 공유 데이터 베이스를 사용하지 않을 때 어떤 reader 도 기다리면 안 된다. 다른 말도 writer 가 대기 하기 때문에 다른 reader 가 끝날 때 까지 대기하는 reader 는 없어야 한다. 2. Writer 가 데이터에 접근 대기 하면 새로운 reader 는 읽기를 시작하면 안 된다. 3. 세마포어 db는 writer 위한 상호배제 역할을 한다. 이것은 데이 터 베이스가 읽혀지는 동안 writer 가 들어오는 것은 막기위한 reader 에 의해서 사용됨KON-KUK UNIVERSITY Dept. of Computer Science Since 1996typedef int semaphore; semaphore mutex = 1; /* 상호 배제 controls access to 'rc'*/ semaphore db = 1; /* 데이터베이스 접근 제어 */ int rc = 0; /* 데이터베이스에 접근한 reader process의 개수 */ void reader(void) { while(TRUE) down( mutex); rc = rc + 1; if( rc == 1) down( db); /* 첫 번째 reader이면 */ up( mutex); read_database(); /*access the data*/ down( mutex); /* reE) think_up_data(); /* Non CS */ down( db); /* 독점적인 엑세스를 얻는다. */ write_database(); /* data 수정 update the data */ up( db); }KON-KUK UNIVERSITY Dept. of Computer Science Since 1996인터넷 성적시스템에서의 문제의 예 :database학생학생학생관리자1.성적 50 점 2.성적 70 점1 성적 50 점 2 성적 70 점1 성적 50 점 2 성적 70 점1 성적 50 점 2 성적 70 점1.성적 70 점 2.성적 80 점1. 성적 70 점 2. 성적 80 점갱신인터넷 게시판KON-KUK UNIVERSITY Dept. of Computer Science Since 1996인터넷 성적시스템에서의 문제의 예 : `database학생학생관리자1. 성적 70 점 2. 성적 80 점1. 성적 70 점 2. 성적 80 점1. 성적 50 점 2. 성적70 점학생1. 성적 70 점 2. 성적 80 점도중 접근이 가능하다면 잘못된 데이터를 읽어옴인터넷 게시판KON-KUK UNIVERSITY Dept. of Computer Science유 닛 설 명ROOMReaderwriterDown( db)up( db)database회전문Reader 프로세스writer 프로세스블럭됨블럭됨KON-KUK UNIVERSITY Dept. of Computer ScienceCASE –1 reader writer 의 경우ROOMROOMReaderReader작업자인 Reader 가 ROOM 에 들어오면서 문을 닫는다.RC 카운터는 한 사람씩 들어올 수 있다 RC = RC+1Down( mutex)up( mutex)KON-KUK UNIVERSITY Dept. of Computer ScienceCASE –1 reader writer 의 경우ROOMReaderwriterWriter 블 럭ROOMReader문이 닫혀 있음으로 문이 열릴 때까지 Writer 작업자는 들어갈 수 없다. Wr문에 다른 reader 가 끝날 때 까지 대기하는 rea der 는 없어야 한다.KON-KUK UNIVERSITY Dept. of Computer ScienceCASE –2 writer reader 의 경우ROOMwriterROOMwriterwriter가 들어올 때 down( db) 따라서, 작업자인 writer 가 ROOM 에 들어오면서 문을 닫는다.KON-KUK UNIVERSITY Dept. of Computer ScienceCASE –2 writer reader 의 경우ROOMwriterReaderReader 블럭ROOMwriter결국 ROOM 에는 Reader 와 Writer 는 함께 작업을 할 수 없다.Writer 가 데이터에 접근 대기 하면 새로운 reader 는 읽기를 시작하면 안 된다.KON-KUK UNIVERSITY Dept. of Computer ScienceCASE –2.1 writer writer 의 경우ROOMwriterROOMwriterwriterWriter 블 럭KON-KUK UNIVERSITY Dept. of Computer ScienceROOMROOMReader 0Reader 0CASE –3 reader0 reader1 writer reader2의 경우KON-KUK UNIVERSITY Dept. of Computer Science Since 1996Case - 3 함수 구현Reader 0writerReader 1mutex = 0; rc = 1; db = 0; mutex = 1; read_database();CPU 제어down( mutex) mutex=0semaphore mutex = 1; /* 상호 배제 controls access to 'rc'*/ semaphore db = 1; /* 데이터베이스 접근 제어 */ int rc = 0; /* 데이터베이스에 접근한 reader process의 개수 */rc = rc + 1 rc = 1If(rc==1)down( db) db = 0up( mutex) mutex=1read_database있는 것은 문제가 되지 않는다. 함수 구현.. 뒷부분RC 카운터는 한 사람씩 들어올 수 있다 rc = 2, 2명의 작업자Critical regionnon-Critical regionCASE –3 reader0 reader1 writer reader2의 경우KON-KUK UNIVERSITY Dept. of Computer Science Since 1996Reader 0mutex = 0; rc = 2; mutex = 1; read_database(); mutex = 0; rc = 1; mutex = 1;writerReader 1CPU 제어semaphore mutex = 1; semaphore db = 1; int rc = 0;down( mutex) mutex=0rc = rc + 1 rc = 2up( mutex) mutex=1read_database(); db를 읽는다down( mutex) mutex=0rc = rc - 1 rc = 1up( mutex) mutex=1Case - 3 함수 구현KON-KUK UNIVERSITY Dept. of Computer ScienceROOMReader1writerWriter 블 럭ROOMReader1Reader 0Reader 0CASE –3 reader0 reader1 writer reader2의 경우KON-KUK UNIVERSITY Dept. of Computer Science Since 1996Reader 0think_up_data(); down( db) ; ⇒ sleepwriterReader 1CPU 제어semaphore mutex = 1; semaphore db = 1; int rc = 0;down( db) db(0) sleepthink_up_data();앞에서 살펴본 down operation 로 인해 sleep db 가 0 보다 크면 줄이고 0이거나 작으면 sleepIf(rc==1)down( db) db = 0Case - 3 함수 구현KON-KUK UNIVERSITY Dept. of Computer ScienceROOMder2의 경우세마포어 db는 writer 위한 상호배제 역할을 한다. 이것은 데이 터 베이스가 읽혀지는 동안 writer 가 들어오는 것은 막기위한 reader 에 의해서 사용됨KON-KUK UNIVERSITY Since 1996mutex = 0; rc = 0; db = 1; mutex = 1;Reader 0writerWake up signalReader 1semaphore mutex = 1; semaphore db = 1; int rc = 0;down( mutex) mutex=0rc = rc - 1 rc = oIf(rc==0)up( db) db = 1up( mutex) mutex=1앞에서 살펴본 up operation 로 인해 sleep 되었던 프로세스를 깨운다.CPU 제어Case - 3 함수 구현KON-KUK UNIVERSITY Dept. of Computer ScienceROOMwriterROOMwriterCASE –3 reader0 reader1 writer reader2의 경우Reader 0Reader 1Reader 0Reader 1KON-KUK UNIVERSITY Dept. of Computer Science Since 1996Reader 0db = 0; write_database(); db = 1;writerCPU 제어Reader 1write_data_base(); 데이터 수정(data updata)down( db) db reader 막아줌up( db) db = 1 reader 투입semaphore mutex = 1; semaphore db = 1; int rc = 0;If(rc==0)up( db) db = 1Case - 3 함수 구현KON-KUK UNIVERSITY Dept. of Computer ScienceROOMwriterReader 2Reader 2 블럭ROOMwriterCASE –3 reader0 reader1 writer reader2의 경우KON-KUK UNIVERSITY Dept. of Computer Science Since 1how}
KON-KUK UNIVERSITY Dept. of Computer Science Since 1996피터슨의 해법Critical region 이란? 정의 : 프로세스(프로그램 코드)상에서 공유 메모리에 접근하는 부분 경쟁조건의 회피 : ① 상호배제(Mutual Exclusion) : 2개 이상의 프로세스가 동시에 CR에 존재할 수 없다. ② 진행(Progress) : CR 밖에서 실행중(즉, Non CR)인 프로세스는 다른 프로세스가 CR에 들어오는 것을 blocking시킬 수 없다. ③ 한계 대기(Bounded Waiting) : 어떤 프로세스도 CR에 들어가기 위해 무한정 기다리지 않는다. * CR = critical region 앞으로 CR 로 표시함KON-KUK UNIVERSITY Dept. of Computer Science Since 1996KON-KUK UNIVERSITY Since 1996#define FALSE 0 #define TRUE 1 #define N 2 Int turn: /* 공유변수*/ Int interested[N]; /*array [0.1] of boolean */ Void enter_region(int process); /* process is 0 or 1 */ { int other; other = 1 – process; interested[process] = TRUE; turn = process; while(turn == process interested[other] == TRUE) } /* 공유변수의 사용이 끝난 뒤 가능하다는 표시인 leave_region 호출 */ Void leave_region(int process) { interested[process] = FALSE: }KON-KUK UNIVERSITY Dept. of Computer Science Since 1996#define FALSE 0 #define TRUE 1 #define N 2 Int turn: Int interested[N]; Void enter_region(int process); { int other; other = 1 – process; interested[process] = TRUE; turn = process; while(turn == process interested[other] == TRUE) } Void leave_region(int process) { interested[process] = FALSE: }프로세스 0 other = 1; interested[0] = TRUE; turn = 1; while( 1 == 1 interested[1] == TRUE) FALSE프로세스 1프로세스 0이 enter_region 들어온 경우 Interested [N] 로 초기화 /* all values initially 0 (FALSE) */ interested[1] =/ TRUEKON-KUK UNIVERSITY Dept. of Computer Science Since 1996FF#define FALSE 0 #define TRUE 1 #define N 2 Int turn: Int interested[N]; Void enter_region(int process); { int other; other = 1 – process; interested[process] = TRUE; turn = process; while(turn == process interested[other] == TRUE) } Void leave_region(int process) { interested[process] = FALSE: }TF각 프로세서는 자신을 나타내는 값인 0 또는 1 을 이용하여 enter_region을 호출KON-KUK UNIVERSITY Dept. of Computer Science Since 1996#define FALSE 0 #define TRUE 1 #define N 2 Int turn: Int interested[N]; Void enter_region(int process); { int other; other = 1 – process; interested[process] = TRUE; turn = process; while(turn == process interested[other] == TRUE) } Void leave_region(int process) { interested[process] = FALSE: }enter_region(); other = 0; interested[1] = TRUE; turn = 0; while(0 ==0 interested[0]==TRUE) true (loop)CASE 1 process 0이 CR 에 있음CPU 제어KON-KUK UNIVERSITY Dept. of Computer Science Since 1996#define FALSE 0 #define TRUE 1 #define N 2 Int turn: Int interested[N]; Void enter_region(int process); { int other; other = 1 – process; interested[process] = TRUE; turn = process; while(turn == process interested[other] == TRUE) } Void leave_region(int process) { interested[process] = FALSE: }interested[0] = FALSE; 공유변수 사용이 끝난 뒤! while(0 ==0 interested[0]==TRUE) FALSE CR에 진입함.CASE 2 process 0이 CR 을 빠져나갔음CPU 제어KON-KUK UNIVERSITY Since 1996other = 1; interested[0] = TRUE; turn = 1; while(0==1 inte~[1]==TRUE) CR에 진입CASE 3 두개의 process가 동시에 enter_region을 호출process 0other = 0; interested[1] = TRUE; turn = 0; while(0==0 inte~~[0]==TRUE) true (loop)process 1CPU 제어CPU 제어CPU 제어따라서, 상호 배제, 진행, 한계 대기가 실현됨KON-KUK UNIVERSITY Since 1996#define FALSE 0 #define TRUE 1 #define N 2 Int turn: /* 공유변수*/ Int interested[N]; /*array [0.1] of boolean */ Void enter_region(int process); /* process is 0 or 1 */ { int other; other = 1 – process; interested[process] = TRUE; turn = process; while(turn == process interested[other] == TRUE) } 이 빠진 경우에 대한 오류 설명!! Void leave_region(int process) { interested[process] = FALSE: }KON-KUK UNIVERSITY Since 1996other = 1; interested[0] = TRUE; while(interested[1]==TRUE) (loop)CASE 4-1 turn == process 가 빠진경우의 예 !process 0other = 0; interested[1] = TRUE; turn = 0; while(interested[0]==TRUE) true (loop)process 1CPU 제어CPU 제어CPU 제어두 프로세스 모두 blocking 된다. 진행의 오류KON-KUK UNIVERSITY Since 1996other = 1; while(inte[1] = TRUE); !! inte[1]은 FALSE interested[0]= TRUE !CR에 진입CASE 4-2 turn == process 가 빠진경우의 예 !process 0other = 0; while(inte[0] = TRUE;) interested[1]=1 !CR에 진입process 1CPU 제어CPU 제어두 프로세스 모두 CR에 집입 상호배제에 오류.{nameOfApplication=Show}
![[운영체제] The readers and writers problem](https://image4.happycampus.com/Production/thumbnail/2003/11/16/data2504517-0001.jpg)
[운영체제] The readers and writers problem
평가B괜찮아요
![[운영체제] 피터슨의 해법(Critical region)](https://image4.happycampus.com/Production/thumbnail/2003/11/16/data2504510-0001.jpg)
