थ्रेड लॉक एक चौराहे सिमुलेटिंग

Question

मैं धागे और म्यूटेक्स ताले का उपयोग करके एक चौराहे अनुकरण करने की कोशिश कर रहा हूं।

मेरे पास स्ट्रेट जाने के लिए फ़ंक्शन हैं, बाएं मुड़ें, दाएं मुड़ें। अब, मेरे पास चौराहे के पास आने के लिए एक फ़ंक्शन है। यह एक यादृच्छिक अभिविन्यास उत्पन्न करता है और बारी करता है। प्रत्येक धागा निकट चौराहे साझा करता है।

मेरे पास सभी दिशाओं में सभी कारों के लिए परिभाषित सभी ताले हैं।

चल रहे स्ट्रेट फ़ंक्शन को लें। इसमें एक स्विच स्टेटमेंट है जो उस समय प्रिंट करता है कि कार क्या कर रही है। अब, मुझे यकीन नहीं है कि इस फ़ंक्शन में क्या लॉक करना है। अगर कार उत्तर दिशा में दिशा में है, तो क्या मैं पूर्व और पश्चिम को बंद कर दूंगा और दक्षिण में उत्तर की ओर इशारा करते हुए कार के साथ?

यहाँ मेरी ताले जो सिर्फ एक फ़ंक्शन को कॉल लॉक या अनलॉक

#define NUMCARS 30 

#define lock_NW(CAR) lock(CAR, NW_mutex) 
#define lock_NE(CAR) lock(CAR, NE_mutex) 
#define lock_SW(CAR) lock(CAR, SW_mutex) 
#define lock_SE(CAR) lock(CAR, SE_mutex) 

#define unlock_NW(CAR) unlock(CAR, NW_mutex) 
#define unlock_NE(CAR) unlock(CAR, NE_mutex) 
#define unlock_SW(CAR) unlock(CAR, SW_mutex) 
#define unlock_SE(CAR) unlock(CAR, SE_mutex) 

यहाँ

मुख्य है करने के लिए है

int main(int argc, char **argv){ 
/* Initial variables*/ 
int index, tid; 
unsigned int carids[NUMCARS]; 
pthread_t carthreads[NUMCARS]; 

/* Start up a thread for each car*/ 
for(index = 0; index <NUMCARS; index++){ 
carids[index] = index; 
tid = pthread_create(&carthreads[index], NULL, approachintersection, (void*)&carids[index]); 
} 

/* Wait for every car thread to finish */ 
for(index = 0; index <NUMCARS; index++){ 
pthread_join(carthreads[index], NULL); 
} 
printf("Done\n"); 
return 1; 
} 

यहाँ

आ चौराहे जो फ़ंक्शन को कॉल स्ट्रेट जा रहा है

static void * approachintersection(void* arg){ 
unsigned int * carnumberptr; 
unsigned int carnumber; 
orientation_t cardir = (orientation_t)random()%4; 
unsigned long turn = random()%3; 

carnumberptr = (unsigned int*) arg; 
carnumber = (unsigned int) *carnumberptr; 

if(turn==LEFT){ 
turnleft(cardir, carnumber); 
} else if(turn==RIGHT){ 
turnright(cardir, carnumber); 
} else {//straight 
gostraight(cardir, carnumber); 
} 

return (void*)carnumberptr; 
} 

अब, यहां चलने वाला स्ट्रेट फ़ंक्शन है जहां मैं उचित डायर लॉक करना चाहता हूं ections।

/* 
    cardirection - The direction the car is pointing. If it is pointing NORTH, 
    it is starting from the South-Eastern corner of the intersection 
    and "going straight" means it wants to move SOUTH to NORTH. 

    valid options: NORTH, SOUTH, EAST, WEST 

carnumber - The car identifier 
*/ 


static void gostraight(orientation_t cardirection, unsigned int carnumber){ 

switch(cardirection){ 
case NORTH: 
printf("Car %d, Moving South-North\n", carnumber); 
break; 
case SOUTH: 
printf("Car %d, Moving North-South\n", carnumber); 
break; 
case EAST: 
printf("Car %d, Moving West-East\n", carnumber); 
break; 
case WEST: 
printf("Car %d, Moving East-West\n", carnumber); 
break; 
} 
} 

तो, अगर आ कार दक्षिण से उत्तर की ओर रहे कार एसई कार होगी और मैं lock_SE (सीएआर) के साथ पूर्व के मामले में, पश्चिम प्रिंट समारोह ताला चाहते हैं? अन्य धागे को आने और प्रिंट करने से रोकते हैं? तो मैं प्रिंट स्टेटमेंट अनलॉक लॉक होगा?

या क्या मैं पूरे स्विच स्टेटमेंट को लॉक कर दूंगा?

** संपादित करें: क्या यह ऐसा करने का तरीका होगा? **

static void turnleft(orientation_t cardirection, unsigned int carnumber){ 

int CAR; 
CAR = carnumber; 


    switch(cardirection){ 
    case NORTH: 
    lock_SE(CAR) 
    printf("Car %d, Moving South-West\n", carnumber); 
    unlock_SE(CAR) 
    break; 
    case SOUTH: 
    lock_NW(CAR) 
    printf("Car %d, Moving North-East\n", carnumber); 
    unlock_NW(CAR) 
    break; 
    case EAST: 
    lock_SW(CAR) 
    printf("Car %d, Moving West-North\n", carnumber); 
    unlock_SW(CAR) 
    break; 
    case WEST: 
    lock_NE(CAR) 
    printf("Car %d, Moving East-South\n", carnumber); 
    unlock_NE(CAR) 
    break; 
    } 

}

Answer 1

यह एक आसान समस्या नहीं है। मैं दो समाधान दिखाने की कोशिश करूंगा।

पहले स्पष्ट एक: पूरे छेड़छाड़ के लिए एक म्यूटेक्स, turnleft, turnright, gostraight की शुरुआत में lock(car, intersection_mutex); जोड़ें, प्रत्येक समारोह रिलीज के अंत से पहले म्यूटेक्स ने कहा। यह केवल एक कार को एक समय में छेड़छाड़ के माध्यम से जाने देगा। इसका उल्टा यह है कि यह समझना आसान है और न ही मृत ताले के परिणामस्वरूप। नकारात्मकता यह है कि एकमात्र एक कार एक समय में प्रवेश कर सकती है, लेकिन जैसा कि हम सभी जानते हैं कि गैर-छेड़छाड़ करने वाले पथों की यात्रा करने वाली दो कारें बिना किसी समस्या के प्रवेश कर सकती हैं। यहाँ go_straight() का एक उदाहरण है (दूसरों के एक ही दृष्टिकोण का पालन करें):

static void gostraight(orientation_t cardirection, unsigned int carnumber){ 
    pthread_mutex_lock(&intersection_mutex); 
    switch(cardirection){ 
     case NORTH: 
      printf("Car %d, Moving South-North\n", carnumber); 
      break; 
     case SOUTH: 
      printf("Car %d, Moving North-South\n", carnumber); 
      break; 
     case EAST: 
      printf("Car %d, Moving West-East\n", carnumber); 
      break; 
     case WEST: 
      printf("Car %d, Moving East-West\n", carnumber); 
      break; 
     } 
    } 
    pthread_mutex_unlock(&intersection_mutex); 
} 

में एक समय में हम एक ठीक छोटाबीजवाला दृष्टिकोण की जरूरत है एक से अधिक कार जाने के लिए। एक बढ़िया दाग दृष्टिकोण के साथ समस्या यह है कि इसे लागू करना और सही होना मुश्किल है। go_straight और turn_left दोनों को दो म्यूटेक्स लॉक करने की आवश्यकता है (आप तर्क दे सकते हैं कि बाएं बाएं तीन की जरूरत है ..)। तो यदि आप दोनों म्यूटेक्स प्राप्त नहीं कर सकते हैं तो आपको वापस जाने की आवश्यकता है। ड्राइविंग के नियमों में इस का अनुवाद:

you must not enter the intersection before you can exit it. 

तो, सीधे हम पहले आप के सबसे नजदीक म्युटेक्स प्राप्त करना होगा जाने के लिए है, तो अपने रास्ते में अगले एक बाहर निकलने के लिए सक्षम होने के लिए। अगर हम दोनों नहीं मिल पा रहे हैं तो हमें उस लॉक को रिलीज़ करना होगा जिसे हमने लॉक किया है। अगर हम इसे जारी नहीं करते हैं तो हम मृत-लॉक करेंगे।

ऐसा करने के लिए मैं दो सहायक कार्यों जोड़ेंगे:

static void lock_two(pthread_mutex_t *a, pthread_mutex_t *b) { 
    while(1) { 
     pthread_mutex_lock(a); 
     if(pthread_mutex_trylock(b) == 0) 
      break; 
     else 
     /* We must release the previously taken mutex so we don't dead lock the intersection */ 
      pthread_mutex_unlock(a);        
     pthread_yield(); /* so we don't spin over lock/try-lock failed */ 
    } 
} 
static void unlock_two(pthread_mutex_t *a, pthread_mutex_t *b) { 
    pthread_mutex_unlock(a); 
    pthread_mutex_unlock(b); 
} 

यहाँ सीधे जाने के अपने संस्करण है:

static void gostraight(orientation_t cardirection, unsigned int carnumber){ 
    switch(cardirection){ 
     case NORTH: 
      lock_two(&SE_mutex, &NE_mutex); 
      printf("Car %d, Moving South-North\n", carnumber); 
      unlock_two(&SE_mutex, &NE_mutex); 
      break; 
     case SOUTH: 
      lock_two(&NW_mutex, &SW_mutex); 
      printf("Car %d, Moving North-South\n", carnumber); 
      unlock_two(&NW_mutex, &SW_mutex); 
      break; 
     case EAST: 
      lock_two(&SW_mutex, &SE_mutex); 
      printf("Car %d, Moving West-East\n", carnumber); 
      unlock_two(&SW_mutex, &SE_mutex); 
     break; 
     case WEST: 
      lock_two(&NE_mutex, &NW_mutex); 
      printf("Car %d, Moving East-West\n", carnumber); 
      unlock_two(&NE_mutex, &NW_mutex); 
      break; 
    } 
} 

turn_left तो एक ही दृष्टिकोण का पालन करने की आवश्यकता होगी।

Answer 2

मैं काफी यकीन है कि मैं समझता हूँ कि आप क्या करने की जरूरत नहीं कर रहा हूँ, लेकिन मैं अपने तर्क समझाने पर एक कोशिश करनी होगी। मैं डिजाइन में शुरू करूंगा, क्योंकि मुझे लगता है कि आपकी समस्या कहां है।

आप एक सादा चौराहे, दो सड़कों, कोई रोशनी, कोई संकेत नहीं मानते हैं। कोई भी कार चार अलग-अलग दिशाओं, उत्तर, दक्षिण, पूर्व और पश्चिम से छेड़छाड़ पर पहुंच सकती है, और चौराहे को पार करते समय प्रत्येक कार तीन अलग-अलग दिशाओं में से एक ले सकती है। इस तरह, आपके पास 4 * 3 = 12 विभिन्न सड़क अनुभाग हैं जिन्हें आप विचार करना चाहते हैं, सभी अलग-अलग हैं।

यदि कोई कार किसी निश्चित पल पर किसी निश्चित पथ पर छेड़छाड़ को पार करती है, तो यह सैद्धांतिक रूप से 11 या उससे अधिक यातायात को अवरुद्ध करती है, सैद्धांतिक रूप से 11 तक, विभिन्न वर्ग (अभ्यास में, कम से कम दो अनुभाग मुक्त रहते हैं, इसलिए सीमा 9 है)। ये आपको ब्लॉक करना है। बीटीडब्लू, अगर आप 12 अलग-अलग वर्गों की तस्वीर बनाते हैं तो इससे मदद मिलती है।

यदि आप म्यूटेक्स का उपयोग करना चाहते हैं, तो आपको प्रत्येक अनुभाग (एक कार के लिए जरूरी नहीं) के लिए एक की आवश्यकता होगी।दाएं हाथ से पहले, बाएं ड्राइविंग परिदृश्य, दक्षिण में आने वाली एक कार सीधे जाने के इच्छुक है:

• पूर्व में आने वाली एक कार सीधे चल रही है;
• पूर्व में आने वाली एक कार बाईं ओर जा रही है;
• पूर्व में आने वाली एक कार सही हो रही है;
• पश्चिम से आने वाली एक कार सीधे जा रही है;
• पश्चिम से आने वाली एक कार बाईं ओर जा रही है;
• उत्तर से आने वाली एक कार बाईं ओर जा रही है;

अन्य सभी अनुभाग अन्य कारों के लिए नि: शुल्क हैं। आप प्रत्येक आगमन/दिशा जोड़ी के लिए ब्लॉक की यह सूची बना सकते हैं। [आपको यह निर्दिष्ट करना होगा कि विपरीत दिशाओं से दो बाएं मोड़ वाली कारें एक-दूसरे को कैसे पारित करेंगी, यानी उत्तर की तरफ से आने वाली एक कार दक्षिण मोड़ से आने वाली कार को अवरुद्ध करेगी, या फिर वे एक दूसरे से पहले गुजर सकती हैं]

प्रत्येक कार की ओर से कई म्यूटेक्स (प्रत्येक अनुभाग के लिए एक) को अवरुद्ध करना (पढ़ना: धागा) एक समस्या प्रस्तुत करता है: डेडलॉक। यहां उस समस्या को हल करने के लिए, मैं सुझाव दूंगा कि आप पूरे चौराहे के लिए एक अतिरिक्त, 'मास्टर' म्यूटेक्स बनाएं। जब कोई कार आती है,

1. यह मास्टर म्यूटेक्स को अवरुद्ध करने का प्रयास करता है; अगर असफल, यह ब्लॉक करता है।
2. फिर यह आवश्यक प्रत्येक अनुभाग-म्यूटेक्स को अवरुद्ध करने का प्रयास करता है; यदि असफल हो, तो सभी सफलतापूर्वक लॉक किए गए म्यूटेक्स को छोड़ दें, मास्टर म्यूटेक्स को अनलॉक करें, और प्रतीक्षा करें, फिर से शुरू करें।
3. यदि यह सभी आवश्यक अनुभाग म्यूटेक्स को अवरुद्ध करने में सफल होता है, तो मास्टर म्यूटेक्स को अनलॉक करें, और चौराहे (समय लेना) ।

चौराहे, कार

1. मास्टर म्युटेक्स ब्लॉक करने के लिए कोशिश करता उत्तीर्ण करने के बाद; अगर असफल, यह ब्लॉक करता है।
2. यह सभी अधिग्रहित अनुभाग म्यूटेक्स को अनलॉक करता है।
3. यह मास्टर म्यूटेक्स को फिर से खोलता है।
4. नई दिशा में अपना रास्ता जारी रखता है।

[स्पष्ट करने के लिए संपादित, और pthread mutexes लॉक करने के लिए कोशिश कर रहा है और बंद का समर्थन कर की अनुमति] केवल एक कार के लिए सभी आवश्यक अनुभाग mutexes प्राप्त करने या नहीं कर सकते हैं देखने के लिए प्रयोग किया जाता है, हमेशा बहुत जल्दी जारी की है मास्टर म्युटेक्स। किसी भी तरह से, मास्टर म्यूटेक्स तुरंत इसके बाद जारी किया जाता है।

मास्टर म्यूटेक्स के बिना आप म्यूटक्स प्राप्त करने के लिए केवल सख्त आदेश का उपयोग करके डेडलॉक से बच सकते हैं। इससे छेड़छाड़ आंशिक हो जाएगी: यदि दो कारें एक ही समय में आती हैं, तो एक दिशा/मोड़ संयोजन हमेशा दूसरे पर जीत जाएगा। मास्टर म्यूटेक्स इससे बचाता है।

Answer 3

इस तरह

खैर कुछ जा रहा सीधे समारोह के लिए काम करेगा: -

static void gostraight(orientation_t cardirection, unsigned int carnumber){ 
    int CAR; 
    cAR = carnumber; 

    switch(cardirection){ 
    case NORTH: 
     lock_SE(CAR); 
     lock_NE(CAR); 
     printf("Car %d, Moving South-North\n", carnumber); 
     unlock_NE(CAR); 
     unlock_SE(CAR); 
     break; 
    case SOUTH: 
     lock_NW(CAR); 
     lock_SW(CAR); 
     printf("Car %d, Moving North-South\n", carnumber); 
     unlock_SW(CAR); 
     unlock_NW(CAR); 
     break; 
    case EAST: 
     lock_SE(CAR); 
     lock_SW(CAR); 
     printf("Car %d, Moving West-East\n", carnumber); 
     unlock_SE(CAR); 
     unlock_SW(CAR); 
     break; 
    case WEST: 
     lock_NE(CAR); 
     lock_NW(CAR); 
     printf("Car %d, Moving East-West\n", carnumber); 
     unlock_NW(CAR); 
     unlock_NE(CAR); 
     break; 
    } 
} 

बाईं बारी, (सिर्फ एक उदाहरण दे रही है) के लिए: -

switch(cardirection) { 
    case NORTH: 
    lock_SE(CAR); 
    lock_NE(CAR); 
    lock_NW(CAR); 
    printf("Car %d, Moving South-West\n", carnumber); 
    unlock_NW(CAR); 
    unlock_NE(CAR); 
    unlock_SE(CAR); 
    break; 
} 

सही बारी के लिए (फिर से बस एक उदाहरण): -

switch(cardirection) { 
    case EAST: 
    lock_SW(CAR); 
    printf("Car %d, Moving East-South\n", carnumber); 
    unlock_SW(CAR); 
    break; 
} 

ध्यान दें कि डेडलॉक्स से बचने के लिए, मैं हमेशा उन्हें आर्बिट्रा में लॉक कर रहा हूं एसई, एनई, एनडब्ल्यू, एसडब्ल्यू के आरई आदेश।

यह क्यों काम करता है? उदाहरण के लिए, एक ऐसी कार लें जो सीधे दक्षिण में जाना चाहती है और दूसरा जो उत्तर की ओर जाता है और बाएं से पश्चिम में बदल जाता है। फिर यदि बाएं मोड़ने वाली कार पहले आती है, तो वह उस क्रम में एसई, एनई और एनडब्ल्यू को लॉक कर देगी और सीधी चलती कार एनडब्लू पर लॉक नहीं पा पाएगी। हालांकि, पूर्व में जाने वाली एक कार और दक्षिण में दाएं मुड़ने से एसडब्ल्यू पर लॉक मिल जाएगा।

इसलिए, यह योजना काम करेगी। इसमें डेडलॉक नहीं होगा क्योंकि प्रत्येक फ़ंक्शन किसी दिए गए क्रम में ताले प्राप्त करता है। इसलिए कोनों के लिए प्रतिस्पर्धा करने वाले धागे की चक्रीय श्रृंखला कभी नहीं हो सकती है। असल में, यदि कोई थ्रेड 1 लॉक को रिलीज़ करने के लिए थ्रेड 2 की प्रतीक्षा कर रहा है, तो इसका मतलब है कि थ्रेड 2 को थ्रेड 1 से पहले से प्राप्त किसी भी ताले की आवश्यकता नहीं है। इसलिए कोई डेडलॉक नहीं हो सकता है।