PV 고전 문제 의 읽 기와 쓰기 문제

20141 단어 운영 체제
문제 설명
많은 프로 세 스 가 공유 하 는 데이터 구역 이 있 습 니 다. 이 데이터 구역 은 파일 이나 메 인 저장 공간 일 수 있 습 니 다.이 데이터 영역 만 읽 는 프로 세 스 (Reader) 와 데이터 영역 에 만 데 이 터 를 쓰 는 프로 세 스 (Writer) 가 있 습 니 다. 또한 다음 조건 을 만족 시 켜 야 합 니 다. (1) 여러 개의 읽 기 프로 세 스 가 이 파일 을 동시에 읽 을 수 있 습 니 다.(2) 한 번 에 하나의 쓰기 프로 세 스 만 파일 에 쓸 수 있 습 니 다.(3) 쓰기 프로 세 스 가 작 동 하고 있다 면 어느 정도 의 파일 도 읽 을 수 없습니다.
독자 우선 알고리즘
관계 분석: 주제 분석 을 통 해 알 수 있 듯 이 독자 와 글 쓰 는 사람 은 서로 배척 하고 쓴 사람과 쓴 사람 도 서로 배척 하 며 독자 와 독 자 는 서로 배척 하 는 문제 가 존재 하지 않 는 다.
정리 사고: 작성 자 는 비교적 간단 하 다. 이 는 모든 스 레 드 와 서로 배척 하고 스토리 보드 신 호 량 의 PV 조작 으로 해결 할 수 있다.독자 의 문 제 는 비교적 복잡 하 므 로 반드시 작성 자 와 의 상호 배척 을 실현 하고 여러 독자 가 동시에 읽 을 수 있다.그래서 여기 서 스토리 보드 는 12032 개의 카운터 에 도착 하여 스토리 보드 로 현재 독자 가 읽 고 있 는 지 여 부 를 판단 한다.독자 가 있 을 때 쓰 는 사람 은 '12102' 법 으로 '12098' 을 쓴다. 이때 독 자 는 '12032' 를 직접 차지 하고 독자 가 없 을 때 쓰 는 사람 이 '12098' 을 쓸 수 있다.이 동시에 서로 다른 독자 들 이 카운터 에 대한 방문 도 서로 배척 해 야 한다.
그러므로 문제 의 전체 해답 은 다음 과 같다.상호 배척 신 호 량 mutex 를 설정 하고 count 변 수 를 업데이트 할 때의 상호 배척 을 보호 하 며 초기 값 은 1 입 니 다.상호 배척 신 호 량 rw 를 설정 하여 독자 와 작성 자의 상호 배척 방문 을 확보 하고 초기 값 은 1 입 니 다.
int count = 0;                  //              

semaphore mutex = 1;            //        count        semaphore rw = 1;               //                   

writer () {                     //    
        while (1) {        
        P(rw);                  //                 
        Writing;                //           
        V(rw);                 //           
	}
}

reader () {                     //     
    while (1) {
	P(mutex);               //    count           
	if (count == 0) {       //                           				 
		 P(rw);              //        
	}
	 count++;                //       1        
	 V(mutex);               //       count        
	 reading;                //          
	 P(mutex);               //    count          
	 count--;                //       1        
	 if (count == 0) {       //                 	
	 	V(rw);              //        
	 }
	  V(mutex);               //       count 
	}
}

문제 풀이 분석: 위 에 있 는 12207 알고리즘 에서 읽 기 프로 세 스 가 우선 입 니 다. 즉, 읽 기 프로 세 스 가 존재 할 때 쓰기 작업 이 지연 되 고 읽 기 프로 세 스 가 활성화 되면 다음 에 읽 기 프로 세 스 가 모두 12098 건 (독자 새치기) 에 접근 할 수 있 습 니 다.이러한 ⽅ 식 에 서 는 쓰기 프로 세 스 가 오래 기다 릴 수 있 고 쓰기 프로 세 스 가 굶 어 죽 을 수도 있 습 니 다.왜 상호 배척 신 호 량 mutex 를 설정 하고 count 변 수 를 업데이트 할 때의 상호 배척 을 보호 해 야 합 니까?분석 은 다음 과 같다. 상호 배척 신 호 량 mutex 를 설정 하지 않 으 면 여러 독자 프로 세 스 가 동시에 count 변 수 를 방문 할 수 있다. 그러면 여러 번 P (rw) 를 초래 할 수 있다.작업 ⽽ 은 쓰기 프로 세 스 를 장시간 ⽆ 법 으로 ⽂ 건 에 접근 하 게 하고 이때 count 계수 변수의 값 도 정확 하지 않 을 수 있 습 니 다.
작성 자 우선 순위 알고리즘
알고리즘 설명 은 다음 과 같다. 1. 작성 자가 데 이 터 를 신청 하면 새로운 독자 가 데 이 터 를 읽 는 것 을 허락 하지 않 는 다. 2. 작성 자 는 새치기 할 것 이다.
그러므로 문제 의 완전한 해답 은 다음 과 같다. 계산 변수 인 readercount 을 설정 하고 스토리 보드 로 현재 의 독자 수량 을 기록 하 며 초기 값 은 0 이다.계산 변수 writercount 을 설정 하고, rsem 신 호 량 을 제어 하 며, 초기 값 은 0 입 니 다.상호 배척 신 호 량 rmutex 를 설정 하고 readercount 변 수 를 업데이트 할 때의 상호 배척 을 보호 하 며 초기 값 은 1 입 니 다.상호 배척 신 호 량 wmutex 를 설정 하고 writercount 에 대한 상호 배척 과 감소 작업 을 제어 하 며 초기 값 은 1 입 니 다.상호 배척 신 호 량 rw 를 설정 하여 독자 와 작성 자의 상호 배척 방문 을 확보 하고 초기 값 은 1 입 니 다.상호 배척 신 호 량 rsem 을 설정 합 니 다.
이 문 제 를 해결 하 는 코드 는 다음 과 같다.
int readercount = 0;            //              
int writercount = 0;            //     rsem     

semaphore rmutex = 1;           //        readercount        semaphore wmutex = 1;           //        writercount       
semaphore rw = 1;               //                   
semaphore rsem = 1;             //                            

writer() {
   while (1) {
   	 P(wmutex);
   	 if (writercount == 0) {            
   	 	P(rsem);        
   	 }       
   	 writercount++;        
   	 V(wmutex);        
   	 P(rw);        
   	 writing;        
   	 V(rw);        
   	 P(wmutex);        
   	 writercount--;        
   	 if (writercount == 0) {            
   	 	V(rsem);       
   	  }        
   	  V(wmutex);    
    } 
}
   
reader() {   
    while (1) { 
   	 P(rsem);        
   	 P(rmutex);        
   	 if (readercount == 0) {            
   	 	P(rw);       
   	  }        
   	  readercount++;       
   	  V(rmutex);        
   	  V(rsem);        
   	  reading;        
   	  P(rmutex);        
   	  readercount--;       
   	  if (readercount == 0) {           
   	   	 V(rw);        
   	   	}         
   	   	V(rmutex);   
    }
}


읽 기와 쓰기 공평 알고리즘
읽 기와 쓰기 공정 알고리즘 은 읽 기 프로 세 스 가 공유 파일 을 읽 고 있 을 때 쓰기 프로 세 스 가 접근 을 요청 합 니 다. 이 때 는 읽 기 프로 세 스 의 요청 을 금지 하고 공유 파일 의 읽 기 프로 세 스 가 끝 날 때 까지 기 다 려 야 합 니 다. 즉, 쓰기 프로 세 스 가 실 행 될 때 까지 기 다 려 야 합 니 다.이 동시에 읽 기와 쓰기 공정 알고리즘 도 '선착순' 의 준칙 에 따라 야 한다. 전체 12032 개의 쓰기 프로 세 스 가 전체 12098 개의 파일 을 방문 할 때 먼저 일부 읽 기 프로 세 스 가 전체 12098 개의 파일 을 방문 해 야 한다. 전체 12157 개의 쓰기 프로 세 스 가 전체 12098 개의 파일 을 방문 해 야 한다. 그러면 현재 전체 12098 개의 프로 세 스 가 전체 12098 개의 파일 에 대한 쓰기 작업 을 끝 낼 때 읽 기 프로 세 스 가 전체 12098 개의 파일 을 차지 하 는 것 이 아니 라 전체 12098 개의 읽 기 프로 세 스 를 사용 하 는 것 이다.(신 호 량 w 의 차단 대기 열 에 있 습 니 다. 읽 기 프로 세 스 가 먼저 시작 되 었 기 때문에 차단 팀 에 줄 을 서 있 습 니 다.
그러므로 문제 의 완전한 해답 은 다음 과 같다. 계산 변수 count 를 설정 하고 스토리 보드 로 현재 의 독자 수량 을 기록 하 며 초기 값 은 0 이다. 서로 배척 하 는 신 호 량 mutex 를 설정 하고 count 변 수 를 업데이트 할 때의 상호 배척 을 보호 하 며 초기 값 은 1 이다. 상호 배척 하 는 신 호 량 rw 를 설정 하여 독자 와 쓰기 자의 상호 배척 방문 을 확보 하고 초기 값 은 1 이다. 신 호 량 w 를 설정 하여 독자 쓰기 자 간 의 읽 기와 쓰기 공평, 초기 값 을 실현 한다.위 1.
코드 는 다음 과 같 습 니 다:
int count = 0;                  //              

semaphore mutex = 1;            //        count       
semaphore rw = 1;               //                   
semaphore w = 1;                //                 

writer () {                     //     
   while (1) {        
   	P(w);                           
   	P(rw);                  //                 
   	Writing;                //           
   	V(rw);                 //               
   	V(w);   
    }
}

reader () {         //     
   	while (1) {        
   		P(w);        
   		P(mutex);               //    count          
   	 	if (count == 0) {       //                           
    			P(rw);              //              
   		 }                             
     	count++;                //       1        
     	V(mutex);               //       count        
     	V(w);        
     	reading;                //          
      	P(mutex);               //    count          
        count--;                //       1        
        if (count == 0) {       //                            
      		 V(rw);              //              
        }            
        V(mutex);               //       count  
    }
}

좋은 웹페이지 즐겨찾기