수면 이발사와 식당 철학자 알고리즘의 정확성에 대한 힌트 (답변이 아님)?

Question

저는 운영 체제 과정입니다. 우리는 2 주 만에 시험을 치고 식사 철학자와 이발사 문제 (세마포어 버전)가 거기에 있다고 의심합니다. 내가 원한다면, 나는 교과서를 열어서 답을 나에게 스푼 핑할 수 있었지만, 나는 실제로 그것들을 스스로 배우려고했다. 나는 문제를 해결하기 위해 시간을 보냈고, 나는 가까이 가고 있다고 생각하지만 ... 나는 잘 모르겠다. 내 솔루션에 무엇이 잘못되었는지 정확히 말하고 싶지는 않지만 힌트를 원합니다. 가능한 한 많은 것을 알아 내고 싶습니다.

잠자기 이발 ... 내가 해결해 낸 솔루션에는 3 개의 이진 세마포가 있습니다. 대기실에는 'w', 이발사의 의자에는 'c', 퇴장에는 'x'가 있습니다. 이발사는 한 번에 한 고객을 돌볼 수 있습니다. 완료되면 다른 고객의 대기실을 확인하고 아무도 없다면 잠을 자죠? 이것은 내가 (C와 의사의 좀 하이브리드에) 이발 프로세스의 코드를 밖으로 일한 것입니다 :

while(true) 
{ 
    P(w); //Guarantees an entering customer can't check the waiting room before the barber. 
    P(c); 
    P(x); //A customer being serviced can't leave until barber is done servicing him. 
    while(customersWaiting > 0) 
    { 
     V(c); //Allow a waiting room customer to sit in barber's chair. 
     V(w); //Allow another customer to enter the waiting room 
     service customer 
     V(x); //Allow customer to leave 
     P(w); //Lock waiting room so barber can check it. 
    } 
    //No customers 
    V(w); //Allow next entering customer to check waiting room. 
    sleep 
    V(c); //Allows new customer service. 
    service customer 
    V(x); //Allow customer to leave. 
} 

나는이 잘하지만 난 잘 모르겠어요 생각합니다. 막 들어온 고객이 while (customersWaiting> 0) 루프의 코드에 의해 처리되어야한다고 생각하지만, 세마포어를 정렬하는 방법을 알 수는 없습니다.

고객이 이해한다면 의자가 있는지 확인해야합니다. 그렇다면 그는 이발사인지 확인해야합니다. 그것이 있다면, 나는 그를 깨우고, 그렇지 않으면 그는 대기실에 앉는다. 대기실이 가득차면 그는 떠난다. 그렇지? 어쨌든, 여기에 내가 고객의 프로세스 밖으로 작업 한 코드입니다 :

P(w); //Guarantees neither barber nor other customers can check waiting room. 
if (chair is occupied) //Could you write this as if(c), or would you create a separate flag? 
{  
    if (barber is sleeping) 
    { 
     wakeup barber 
     V(w); //Now the waiting room can be checked by someone else. 
     P(c); //Sit in barber's chair 
     P(x); //Attempt to exit shop 
    } 
} 
else 
{ 
    if (customersWaiting < amountOfChairs) 
    { 
     customersWaiting++; 
     V(w); //Now the waiting room can be checked by someone else. 
     P(c); //Sit in barber's chair, when it's available that is. 
     P(x); //Attempt to exit shop 
     customersWaiting--; 
    } 
} 
exit shop 

내가 여기 여부를 올바른 궤도에있어 잘 모르겠어요 ... 내가 볼 문제는 경우가 그 고객이 없으면 이발사는 잠을 자지 만 새 고객이 도착하면 잠 들어 있지 않을 수도 있습니다. 따라서 고객은 대기실에 가서 영원히 기다릴 것입니다. 이 문제를 해결할 수있는 몇 가지 방법을 생각해 보았습니다. 저는 이발사가 잠자기 전에 (세마포어를 사용하여 액세스) 플래그를 설정할 수 있습니다. 그러면 새로운 고객이이를 확인하고 이발사가 항상 잠들 때까지 꽉 조이고 잠에서 깨어나 ...하지만 그게 최선의 해결책은 아니지, 그렇지? 나는 이것에 관해 확실하지 않다. .. 어떤 암시? 다시 나는 대답을 곧바로하고 싶지 않다. 나는 힌트를 원한다.

이제 식사 철학자 문제 ... 나는이 문제에 대해 훨씬 더 확신하고 있지만, 나는 여전히 두 번 확인하고 싶다. 내가 해결 해낸 솔루션에서, 나는 한 쌍의 젓가락을 잡기 위해 바이너리 세마포어 'g'를 먹었고, 먹기 시작할 수있는 철학자의 수를 세는 세마포어 'a'와 하나의 바이너리 세마포어 c [0..n -1] 각 젓가락에 대해. 기본적으로, 철학자의 반 (물론 반올림)은 언제든지 먹을 수 있습니다. 맞습니까? (내림차순) 그래서 내 생각에 철학자는 생각을 한 후에 젓가락 한 켤레를 움켜 쥐려고 노력하지만 철학자의 절반도 채 안되면 다른 사람은 젓가락을 움켜 쥐지 못한다. 나는이 같은 철학자의 코드를 코딩했습니다

내가 볼 수있는 하나의 문제는 철학자가 먹고 그 옆에 사람이 젓가락 한 쌍을 잡아하려고하면, 그는 할 수 없습니다 점이다

while(true) 
{ 
    think 
    P(g); //Above all, no one else can try to grab a chopstick at the same time as someone else. 
    P(a); //Decrement the amount of philosophers that may start eating. 
    P(c[left chopstick's number]); 
    take left chopstick 
    P(c[right chopstick's number]); 
    take right chopstick 
    V(g); //Now someone else may attempt to grab a pair. 
    eat 
    V(c[left chopstick's number]); 
    replace left chopstick 
    V(c[right chopstick's number]); 
    replace right chopstick 
    V(a); 

가득한 쌍을 얻는 것. 그리고 그러므로 현재의 공저자가 끝날 때까지 모두는 얼 것이다. 나는 올바른 길을 가고 있는가?

나는 모든 피드백에 크게 감사 할 것입니다. 감사합니다

, 레드 존

Answer 1

나 자신에 의해 가능한 한 많이 알아 내야합니다.

각 위키피디아 기사를 읽었습니까? 거기에서 구체적인 질문이 있으십니까? 네가 스스로 해결하고 싶다 니 기쁘다.하지만 그건 나쁜 계획이야. 어떤 통찰력이 존재하는지 확인하십시오. Wikipedia는 종종 당신에게 스푼 피드를하지는 않지만 당신에게 기초를 제공합니다. 내가 볼 수

한 문제는 철학자가 먹고 그 옆에 사람이 젓가락 한 쌍을 잡아하려고하면, 그는 전체 쌍을 얻을 수 없습니다, 따라서 모든 사람들이 동결 될 것이다 현재의 먹는 사람이 끝날 때까지. 나는 올바른 길을 가고 있는가?

올바른 길을 가고 있습니다. 그렇습니다. 두 사람이 동시에 먹을 수도 있지만 더 이상 먹지 못할 수도 있습니다. 트릭은 당신이 그것을 집어 들었을 때입니다, 당신이 두 번째 것을 얻을 수 없다면, 당신이 몇 틱 동안 붙잡고있는 것을 내려 놓으십시오. (얼마쯤 C의 하이브리드 의사 코드)

:

모든 의사 코드 C의 혼성되는 경향

)

Answer 2

식사 철학자 로크 순서에 의해 해결 고전 교착 문제 (나는 이것이 당신의 책에 있다고 확신하지만, 코드를 시험해 보는 것이 좋다. 기초가있는 것이 좋다.)

1. 모든 젓가락은 (다른) 숫자로되어있다.
2. 철학자는 높은 번호의 젓가락을 집기 전에 낮은 번호의 젓가락을 집을 수 있어야합니다.
3. 번호가 매겨진 젓가락을 내리면 더 높은 번호의 젓가락을 즉시 가져올 수없는 경우에도 계속 유지할 수 있습니다.
4. 철학자 한 명이 (아마도 두 사람이) 항상 먹을 수있게 될 것이고, 마침내 끝내고 다른 한 사람 (또는 두 사람)은 먹을 수있게 될 것입니다.

 

     1 o 2 

     o  o 

     4 o 3 

당신은 대부분의 교착 상태 문제에 동일한 논리를 적용 할 수 있습니다. 이러한 유형의 문제에 대한 요점은 솔루션을 코딩하는 방법이 아니라 문제 (예 : 교착 상태, 자원 부족), 솔루션을 인식 한 다음 솔루션을이 유형의보다 일반화 된 다른 문제에 적용하는 것입니다 (A, B 및 C를 잠그십시오. 여러 개의 잠금을 획득하려고 시도하는 스레드간에 교착 상태가 없는지 확인하는 방법 (젓가락은 잠금에 대한 은유이고 철학자는 스레드 또는 프로세스에 대한 은유입니다).