배열 기반 바운드 버퍼의 빈 요소

Question

나는 고전적인 생산자/소비자 문제가 있습니다. 생산자에 대한 코드는 이것이다 :

#define BUFFER_SIZE 10 
while (true) { 
    /* Produce an item */ 
    while (((in + 1) % BUFFER_SIZE) == out) 
    ; /* do nothing -- no free buffers */ 
    buffer[in] = item; 
    in = (in + 1) % BUFFER_SIZE; 
} 

그리고 소비자는 다음과 같습니다

while (true) { 
    while (in == out) 
    ; // do nothing -- nothing to consume 

    // remove an item from the buffer 
    item = buffer[out]; 
    out = (out + 1) % BUFFER_SIZE; 
    return item; 
} 

이 잘 작동하지만 문제는 처음 8 개 요소가 가득 in=9 및 out=0 때, 생산자가 앉아 있다는 것입니다 거기 마지막 (9) 요소를 채우지 않습니다. 이는 in=4 및 out=5과 같은 경우에도 발생합니다. 하나의 슬롯이 여전히 비어 있더라도 하나의 요소는 항상 비어 있고 큐는 "가득"합니다.

몇 가지 복잡한 검사를 할 수 있지만 큐 전체를 채울 수있는 깨끗한 솔루션이 있는지 알아야합니다. 나는 처음에 증가를 시도한 다음 item을 넣었지만 비슷한 문제가 발생합니다. (in과 out 모두에 대해 -1으로 초기화하는 것도 작동하지 않습니다.

Answer 1

바로 가기 주제에 Wikipedia을 참조하십시오. 항상 비어있는 하나 개의 슬롯을 유지

• : 가장 간단한 솔루션 중 하나를 것으로 보인다 in == out 다음 버퍼가 비어있는 경우; in == out - 1 인 경우 버퍼가 가득합니다.
• out을 num_unread_items으로 바꿉니다. num_unread_items에서 out 및

in를 검색하는 간단한 산술 연산하지만 & 기록 동작 (별도의 변수 또는 직접 in 및 out에서 하나)를 읽을 수를 카운트 관련된 다른 옵션이있다; 또는 현재의 in 및 out 이외에 마지막 작업이 읽기인지 또는 쓰기인지 추적하여 버퍼 전체/버퍼 비어있는 경우를 명확히 할 수 있습니다.

Answer 2

대학의 OS 개발 클래스에서 버퍼의 N 개 요소를 모두 사용할 수있는 소프트웨어 전용 솔루션을 사용할 수 없다고 주장하는 부가 교사가있었습니다. 나는 그가 내가 트랙을 달리기를 좋아한다는 사실에 영감을받은 경주 트랙 솔루션이라고 부르기로 결정한 무언가를 잘못했다고 판명했다.

경마장에서는 400m 경주에 국한되지 않습니다. 경주는 두 개 이상의 랩으로 구성 될 수 있습니다. 2 명의 주자가 경주에 목과 목 인 경우 어떻게됩니까? 그들이 묶여 있는지, 한 주자가 다른 주자를 겹쳐 봤는지 어떻게 알 수 있습니까? 대답은 간단합니다 : 경주에서 트랙의 주자 위치 을 모니터링하지 않습니다. 우리는 주자가 횡단 한 거리를 모니터링합니다. 따라서 두 명의 주자가 목과 목인 경우, 한 주자가 다른 하나를 랩핑했을 때 넥타이 사이를 명확하게 판단 할 수 있습니다.

우리 알고리즘은 N 요소 배열을 가지고 있으며 2N 레이스를 관리합니다. 생산자/소비자 카운터가 각각의 2N 경주를 마칠 때까지 0으로 다시 시작하지 않습니다. 우리는 생산자가 소비자보다 한 바퀴 더 앞서도록 허용하지 않으며 우리는 소비자가 생산자보다 앞서 있도록 허용하지 않습니다. 실제로 제작자와 소비자 간의 거리 만 모니터링하면됩니다.다음과 같이

코드는 다음과 같습니다 제가 원래 문제를 해결하기 때문에

Item track[LAP]; 
int consIdx = 0; 
int prodIdx = 0; 

void consumer() 
{ while(true) 
    { int diff = abs(prodIdx - consIdx); 
    if(0 < diff) //If the consumer isn't tied 
    { track[consIdx%LAP] = null; 
     prodIdx = (prodIdx + 1) % (2*LAP); 
    } 
    } 
} 

void producer() 
{ while(true) 
    { int diff = (prodIdx - consIdx); 
    if(diff < LAP) //If prod hasn't lapped cons 
    { track[prodIdx%LAP] = Item();  //Advance on the 1-lap track. 
     prodIdx = (prodIdx + 1) % (2*LAP);//Advance in the 2-lap race. 
    } 
    } 
} 

그것은 오랜만이야, 그래서 이것은 내 가장 기억에 따라입니다. 바라건대 나는 어떤 버그도 간과하지 않았다. 희망이 도움이됩니다!