[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/algorytm-petersona-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/algorytm-petersona-wikipedia\/","headline":"Algorytm Petersona – Wikipedia","name":"Algorytm Petersona – Wikipedia","description":"before-content-x4 W informatyce, Algorytm Petersona jest algorytmem wzajemnego wykluczenia do konkurencyjnego programowania. Ten algorytm opiera si\u0119 na aktywnym podej\u015bciu oczekuj\u0105cym","datePublished":"2023-05-27","dateModified":"2023-05-27","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":100,"height":100},"url":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/algorytm-petersona-wikipedia\/","wordCount":5933,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4W informatyce, Algorytm Petersona jest algorytmem wzajemnego wykluczenia do konkurencyjnego programowania. Ten algorytm opiera si\u0119 na aktywnym podej\u015bciu oczekuj\u0105cym i gwarantuje, \u017ce b\u0119dzie bez g\u0142odu i bez interbock [[[ Pierwszy ] . Sk\u0142ada si\u0119 z dw\u00f3ch cz\u0119\u015bci: protoko\u0142u wej\u015bcia w sekcji krytycznej i protoko\u0142u wyj\u015bciowego. Przedstawiony algorytm to wersja, kt\u00f3ra mo\u017ce dzia\u0142a\u0107 z dwoma w\u0105tkami. Zosta\u0142 opublikowany przez Gary Peterson w 1981 roku.        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4  Podstawow\u0105 zasad\u0105 algorytmu Petersona jest to, \u017ce ka\u017cdy w\u0105tek b\u0119dzie mia\u0142 dost\u0119p do sekcji krytycznej i \u017ce w\u0105tek mo\u017ce wprowadzi\u0107 sekcj\u0119 krytyczn\u0105 tylko wtedy, gdy jest bezp\u0142atny. Ka\u017cdy w\u0105tek ma unikalny identyfikator. Wed\u0142ug konwencji uwa\u017camy, \u017ce dwa zastosowane w\u0105tki b\u0119d\u0105 nosi\u0107 identyfikatory 0 I Pierwszy . W swojej podstawowej implementacji z 2 procesami algorytm u\u017cywa Tabela dw\u00f3ch warto\u015bci logicznych Aby wskaza\u0107, czy jeden z w\u0105tk\u00f3w jest obecnie zainteresowany wprowadzeniem sekcji krytycznej. On te\u017c u\u017cywa Inna zmienna Aby wskaza\u0107, kt\u00f3ry w\u0105tek ma obecnie dost\u0119p do obszaru krytycznego.        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Wa\u017cn\u0105 szczeg\u00f3lno\u015bci\u0105 tego algorytmu jest to, \u017ce wykorzystuje on dwie r\u00f3\u017cne zmienne do kontrolowania dost\u0119pu do strefy krytycznej. Table of ContentsPocz\u0105tkowy algorytm dla 2 proces\u00f3w [[[ modyfikator |. Modyfikator i kod ] Przyk\u0142ad w Javie [[[ modyfikator |. Modyfikator i kod ] Przyk\u0142ad aplikacji w C (z ksi\u0119garni\u0105 ‘ pthread ‘) [[[ modyfikator |. Modyfikator i kod ] Wzajemne wykluczenie [[[ modyfikator |. Modyfikator i kod ] Brak g\u0142odu [[[ modyfikator |. Modyfikator i kod ] Nieobecno\u015b\u0107 d’Alloklocage (impas) [[[ modyfikator |. Modyfikator i kod ] Pocz\u0105tkowy algorytm dla 2 proces\u00f3w [[[ modyfikator |. Modyfikator i kod ]   Poni\u017cej Wants_ tron jest obraz  dw\u00f3ch logicznych, wskazuj\u0105cych dla ka\u017cdego procesu (0 i 1), je\u015bli chce wej\u015b\u0107 do sekcji krytycznej. Zmienna wycieczka Wskazuje, kto jest zakr\u0119tem, aby wykona\u0107 sekcj\u0119 krytyczn\u0105.        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4\/\/ inicjalizacja  Bool  Wants_ tron [[[ 2 ];  Wants_ tron [[[ 0 ]  =  FA\u0141SZ ;  veut_entrer[1] = false;int tour;\/\/ W\u0105tek wykonania n \u00b0 0  T0 :  Wants_ tron [[[ 0 ]  =  PRAWDA ;   wycieczka  =  Pierwszy ;      while (veut_entrer[1] && tour == 1) {} \/\/ attente     \/\/ D\u00e9but de la section critique     ...    \/\/ fin de la section critique    veut_entrer[0] = false;\/\/ W\u0105tek wykonania N \u00b0 1  P1 :  Wants_ tron [[[ Pierwszy ]  =  PRAWDA ;   wycieczka  =  0 ;      while (veut_entrer[0] && tour == 0) {} \/\/ attente     \/\/ D\u00e9but de la section critique     ...    \/\/ fin de la section critique    veut_entrer[1] = false; Przyk\u0142ad w Javie [[[ modyfikator |. Modyfikator i kod ] Oto pseudo-kod algorytmu napisany w Javie [[[ Pierwszy ] . Dwa w\u0105tki maj\u0105 0 i 1 identyfikator, mog\u0105 uzyska\u0107 sw\u00f3j identyfikator, dzwoni\u0105c ThreadId.get () . klasa  Peterson  przybory  Zamek  {   \/\/ indeks lokalnych w\u0105tk\u00f3w, jest wart 0 lub 1   prywatny  Boolean [] []  flaga  =  nowy  Boolean [[[ 2 ] ;   prywatny  int  ofiara ;   publiczny  pr\u00f3\u017cnia  zamek ()  {   int  I  =  Ni\u0107 . Dostawa\u0107 ();   int j = 1 - i;         drapeau[i] = true;                      \/\/ je suis int\u00e9ress\u00e9        victime = i;                            \/\/ il va en premier        while (drapeau[j] && victime == i) {}   \/\/ j'attends    }    public void unlock() {        int i = ThreadID.get();        drapeau[i] = false;                     \/\/ je ne suis plus int\u00e9ress\u00e9    }}Przyk\u0142ad aplikacji w C (z ksi\u0119garni\u0105 ‘ pthread ‘) [[[ modyfikator |. Modyfikator i kod ] #w\u0142\u0105cza\u0107   #w\u0142\u0105cza\u0107    #Define pthread_function (FCT) (void *( *) (void *)) fct   #define FALSE 0#define  TRUE 1\/\/ Utilisons l'algorithme de Peterson, 1981typedef struct {    \/\/ On a besoin d'un tableau de la m\u00eame taille     \/\/ que le nombre de thread qu'on doit g\u00e9rer    int veut_entrer[2];    int tour;    int shared_value;} Peterson_two_thread_struct;void thread_num_zero(Peterson_two_thread_struct *ptt){    ptt->veut_entrer[0] = TRUE;    ptt->tour = 1;        while (ptt->veut_entrer[1] && ptt->tour == 1) {} \/\/ On attends        \/\/ Section critique    for (int i = 0; i shared_value++;        printf(\"[0] shared_value = %in\", ptt->shared_value);    }        \/\/ Fin de la section critique    ptt->veut_entrer[0] = FALSE;}void thread_num_one(Peterson_two_thread_struct *ptt){    ptt->veut_entrer[1] = TRUE;    ptt->tour = 0;        while (ptt->veut_entrer[0] && ptt->tour == 0) {} \/\/ On attends        \/\/ Section critique    for (int i = 0; i shared_value++;        printf(\"[1] shared_value = %in\", ptt->shared_value);    }        \/\/ Fin de la section critique    ptt->veut_entrer[1] = FALSE;}int main(int argc, const char * argv[]) {        pthread_t pthread_0, pthread_1;    Peterson_two_thread_struct ptt_struct;    ptt_struct.veut_entrer[0] = FALSE;    ptt_struct.veut_entrer[1] = FALSE;    ptt_struct.shared_value = 0;        printf(\"START\u00a0: shared_value = %in\", ptt_struct.shared_value);        int ret0 = pthread_create(&pthread_0, NULL, PTHREAD_FUNCTION(thread_num_zero), &ptt_struct);    int ret1 = pthread_create(&pthread_1, NULL, PTHREAD_FUNCTION(thread_num_one), &ptt_struct);        \/\/ Si le syst\u00e8me ne peut plus cr\u00e9er de threads (lisez le manuel)    if(ret0 != 0 || ret1 != 0)    {        printf(\"Errorn\");        printf(\"Thread \"thread_num_zero\" error\u00a0: %i n\", ret0);        printf(\"Thread \"thread_num_one\" error\u00a0: %i n\", ret1);        return -1;    }        pthread_join(pthread_0, NULL);    pthread_join(pthread_1, NULL);        printf(\"END\u00a0: shared_value = %in\", ptt_struct.shared_value);        return 0;}Algorytm spe\u0142nia kilka w\u0142a\u015bciwo\u015bci, takich jak wzajemne wykluczenie, brak g\u0142odu i interpretacja. Oto osi\u0105gni\u0119cia, kt\u00f3re dowodz\u0105 tych w\u0142a\u015bciwo\u015bci. Uwaga: polegaj\u0105 na kodzie przyk\u0142adu w Javie.  Wzajemne wykluczenie [[[ modyfikator |. Modyfikator i kod ] Algorytm Petersona spe\u0142nia w\u0142asno\u015b\u0107 wzajemne wykluczenie . Dow\u00f3d . Za\u0142\u00f3\u017cmy, \u017ce nie spe\u0142nia to wzajemnego wykluczenia. Rozwa\u017c najnowsze wykonania w\u0105tk\u00f3w A I B Zanim przecinaj\u0105 si\u0119 odpowiednio na poziomie swojej krytycznej sekcji Cs A I Cs B . Sprawdzaj\u0105c kod, zauwa\u017camy, \u017ce: pisa\u0107 A (Flaga [a] = PRAWDA ) \u21d2 Napisz A (Ofiara = A ) \u21d2 Przeczytaj A (flaga[ B ]) \u21d2 Przeczytaj A (ofiara) \u21d2 Cs A , (1) Napisz B (Flaga [B] = PRAWDA ) \u21d2 Napisz B (Ofiara = B ) \u21d2 Przeczytaj B (flaga[ A ]) \u21d2 Przeczytaj B (ofiara) \u21d2 Cs B (2) Przypuszczam, \u017ce A jest ostatnim w\u0105tkiem, kt\u00f3ry napisa\u0142 na polu ofiar, to przypuszczenie ma niewielki wp\u0142yw na og\u00f3lno\u015b\u0107 algorytmu. Wi\u0119c mo\u017cemy napisa\u0107: pisa\u0107 B (Ofiara = B ) \u21d2 Napisz A (Ofiara = A ) (3) R\u00f3wnanie (3) zak\u0142ada to A zaobserwowa\u0142 zmienn\u0105 ofiary w (1). Jak A Dlatego wszed\u0142 do swojej strefy krytycznej A koniecznie to zaobserwowa\u0142em Flaga [b] by\u0142 Faux . Wi\u0119c mamy : pisa\u0107 A (Ofiara = A ) \u21d2 Przeczytaj A (flaga[ B ] == Faux ) (4) \u0141\u0105cz\u0105c r\u00f3wnania (2) i (4) razem, otrzymujemy: pisa\u0107 B (flaga[ B ] = PRAWDA ) \u21d2 Napisz B (Ofiara = B ) \u21d2 Napisz A (Ofiara = A ) \u21d2 Przeczytaj A (flaga[ B ] == Faux ). (5) Dzi\u0119ki regu\u0142om przechodno\u015bci zaanga\u017cowania (\u21d2) mo\u017cemy przepisa\u0107 (5) w: pisa\u0107 B (flaga[ B ] = PRAWDA ) \u21d2 Przeczytaj A (flaga[ B ] == Faux ). Kt\u00f3ry stanowi sprzeczno\u015b\u0107. Rzeczywi\u015bcie, \u017cadne inne pisanie Flaga [b] Nie mo\u017cna by\u0142o przeprowadzi\u0107 przed egzekucj\u0105 sekcji krytycznej. W zwi\u0105zku z tym podstawowa hipoteza jest b\u0142\u0119dna, a algorytm Petersona dobrze spe\u0142nia w\u0142a\u015bciwo\u015b\u0107 wzajemnego wykluczenia. \u25a1 Brak g\u0142odu [[[ modyfikator |. Modyfikator i kod ] Algorytm Petersona spe\u0142nia w\u0142asno\u015b\u0107 brak g\u0142odu . Dow\u00f3d . Za\u0142\u00f3\u017cmy, \u017ce tak nie jest. Istnieje zatem co najmniej jeden z dw\u00f3ch w\u0105tk\u00f3w, kt\u00f3ry dzia\u0142a wiecznie bez wchodzenia w sekcj\u0119 krytyczn\u0105. Za\u0142\u00f3\u017cmy, \u017ce tak jest A (Dow\u00f3d jest podobny, je\u015bli zak\u0142ada si\u0119, \u017ce tak jest B ). A Dlatego wykonuje lini\u0119 While (flaga [j] && victim == i) {} w p\u0119tli, a zatem czeka Flaga [j] sta\u0107 si\u0119 Faux , albo ofiara By\u0107 r\u00f3wne B . Co robi B chwila A Wykonaj ten wiersz kodu? Musi wielokrotnie wchodzi\u0107 i wydostawa\u0107 si\u0119 z krytycznego obszaru. Wi\u0119c to znaczy B Umie\u015b\u0107 zmienn\u0105 ofiara ma B Ilekro\u0107 chce wej\u015b\u0107 do sekcji krytycznej. Dlatego zmienna ofiara jest zawsze r\u00f3wny B I nigdy nie zmienia warto\u015bci. Je\u015bli tak jest, A mo\u017ce nast\u0119pnie wyj\u015b\u0107 z p\u0119tli, poniewa\u017c spe\u0142nione jest jeden z dw\u00f3ch warunk\u00f3w. Jest to zatem sprzeczno\u015b\u0107. Je\u015bli to nie to, to dlatego B utkn\u0105\u0142 r\u00f3wnie\u017c w p\u0119tli, czekaj\u0105c na wej\u015bcie do strefy krytycznej, czekaj\u0105c na bycie flaga [a] sta\u0107 si\u0119 Faux Albo ofiara lub A . Wi\u0119cej ofiara nie mo\u017ce by\u0107 warte obu A I B . Jest to zatem r\u00f3wnie\u017c sprzeczno\u015b\u0107. W zwi\u0105zku z tym podstawow\u0105 hipotez\u0105 jest fa\u0142szywa, a algorytm spe\u0142nia w\u0142a\u015bciwo\u015b\u0107 braku g\u0142odu. \u25a1 Nieobecno\u015b\u0107 d’Alloklocage (impas) [[[ modyfikator |. Modyfikator i kod ] Algorytm Petersona spe\u0142nia w\u0142asno\u015b\u0107 nieobecno\u015b\u0107 d’Olloklocage . Dow\u00f3d . Jak ju\u017c wykaza\u0142, \u017ce algorytm spe\u0142nia w\u0142asno\u015b\u0107 braku g\u0142odu i \u017ce w\u0142asno\u015b\u0107 braku g\u0142odu jest silniejsz\u0105 w\u0142a\u015bciwo\u015bci\u0105 ni\u017c brak interbocka, w\u00f3wczas algorytm jest gwarantowany nie do prze\u0142omu. \u25a1 \u2191 A et b (W) Maurice Herlihy , Nir Shavit , Victor Luchangco i Michael W\u0142\u00f3cznia W Sztuka programowania wieloprocesorowego , Morgan Kaufmann, 2 To jest  wyd.  (ISBN 978-0-12-415950-1 ) W P. 27-28        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/algorytm-petersona-wikipedia\/#breadcrumbitem","name":"Algorytm Petersona – Wikipedia"}}]}]