Tehnica Jetoanelor pe un Inel
49 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Care este rolul inițiatorului (procesul P) în tehnica jetoanelor pe un inel?

  • Să pornească algoritmul prin trimiterea unui jeton cu valoarea inițială 0 și culoarea albastră. (correct)
  • Să monitorizeze culoarea tuturor proceselor și să anunțe terminarea.
  • Să crească valoarea jetonului la fiecare pas.
  • Să primească primul jeton și să nu îl mai transmită.
  • Ce acțiune întreprinde un proces P[i] (unde i este de la 2 la N) când primește un jeton?

  • Își setează culoarea la albastru, resetează valoarea jetonului la 0 și trimite jetonul mai departe.
  • Verifică valoarea jetonului și își schimbă culoarea doar dacă jetonul are o valoare specifică.
  • Își setează culoarea la roșu, crește valoarea jetonului și trimite jetonul mai departe.
  • Își setează culoarea la albastru, crește valoarea jetonului și trimite jetonul următorului proces. (correct)
  • Ce condiție trebuie să îndeplinească inițiatorul P(1) pentru a anunța terminarea algoritmului în tehnica jetoanelor pe un inel?

  • Să primească un jeton și să aibă culoarea roșie.
  • Să primească jetonul cu valoarea 0 și culoarea să fie roșie.
  • Să trimită un jeton cu valoarea finală egala cu numărul total de procese.
  • Să primească jetonul și să aibă culoarea albastră. (correct)
  • Cum se diferențiază acțiunile proceselor când primesc un mesaj obișnuit față de primirea unui jeton în tehnica jetoanelor pe inel?

    <p>La primirea unui mesaj obișnuit culoarea devine roșie, iar la primirea jetonului culoarea devine albastră. (D)</p> Signup and view all the answers

    În cazul general al tehnicii jetoanelor pe grafuri, ce reprezintă nc?

    <p>Lungimea ciclului care include toate arcele grafului. (A)</p> Signup and view all the answers

    Care este condiția pentru ca un proces în cazul general să anunțe terminarea, folosind tehnica jetoanelor?

    <p>Când jetonul ajunge la valoarea <code>nc</code> și culoarea sa este albastră. (C)</p> Signup and view all the answers

    Ce se întâmplă cu un proces P[i] în cazul general, când primește jetonul și jetonul este diferit de nc iar procesul are culoarea albastră ?

    <p>Valoarea jetonului se incrementează cu 1, iar procesul trimite jetonul următorului proces din ciclu. (C)</p> Signup and view all the answers

    Într-o topologie de tip arbore, cum semnalează un proces frunză terminarea calculului?

    <p>Trimite un mesaj de confirmare către părintele său. (C)</p> Signup and view all the answers

    Într-un arbore, cum notifică un nod terminarea sa?

    <p>Așteaptă notificări de la toți fiii săi și apoi își anunță părintele. (B)</p> Signup and view all the answers

    Într-un canal, cum se realizează confirmarea mesajelor?

    <p>Se trimit mesaje de date și se primesc semnale de confirmare, sau se primesc mesaje de date și se trimit semnale de confirmare. (D)</p> Signup and view all the answers

    Ce caracteristică are un proces sursă în contextul confirmării mesajelor?

    <p>Nu are legături de intrare și poate accesa orice alt proces pe o cale oarecare din graf. (C)</p> Signup and view all the answers

    În algoritmul Dijkstra-Scholten, ce reprezintă variabila prim într-un nod i?

    <p>Identificatorul nodului care a trimis primul mesaj către nodul <code>i</code>. (D)</p> Signup and view all the answers

    Ce condiție trebuie îndeplinită pentru ca un canal să fie considerat gol?

    <p>Să fie primit un semnal de confirmare pentru fiecare mesaj de date transmis pe acel canal. (A)</p> Signup and view all the answers

    În algoritmul Dijkstra-Scholten, când un proces frunză se termină, ce acțiune întreprinde?

    <p>Îl anunță pe părintele său despre terminare. (A)</p> Signup and view all the answers

    Ce se întâmplă când un nod primește un mesaj cu eticheta terminare în algoritmul Dijkstra-Scholten?

    <p>Nodul începe un proces de trimitere a mesajelor de tip <code>semnal</code> către nodurile de care depinde, până când deficitele acestora sunt zero. (C)</p> Signup and view all the answers

    Ce reprezintă 'deficitul unei legături' într-un graf dirijat aciclic de procese?

    <p>Diferența dintre numărul de mesaje de date transmise și numărul de semnale de confirmare primite pe acea legătură. (B)</p> Signup and view all the answers

    Care este scopul principal al algoritmului de detecție a terminării folosind marcaje, conform textului?

    <p>Să identifice momentul în care toate procesele distribuite și-au finalizat calculele și s-au oprit. (D)</p> Signup and view all the answers

    În algoritmul de detecție a terminării cu marcaje, ce indică primirea unui semnal de confirmare?

    <p>Confirmă primirea unui mesaj marcaj. (C)</p> Signup and view all the answers

    Ce acțiune directă întreprinde un nod care dorește să termine, conform algoritmului Dijkstra-Scholten?

    <p>Așteaptă primirea unor semnale pe legăturile de ieșire a datelor, care reduc deficitele la zero, apoi trimite pe fiecare legătură de intrare a datelor un număr de semnale egal cu deficitul. (C)</p> Signup and view all the answers

    Cum se propagă notificările de terminare într-un arbore, în cadrul algoritmului Dijkstra-Scholten?

    <p>De la frunze către rădăcină. (D)</p> Signup and view all the answers

    Ce rol are variabila nsemnale în algoritmul Dijkstra-Scholten?

    <p>Contorizează diferența dintre mesajele de tip <code>transmitere</code> și <code>semnal</code> primite de un nod. (C)</p> Signup and view all the answers

    În algoritmul Dijkstra-Scholten, cum sunt gestionate legăturile de intrare pentru a genera arborele de acoperire?

    <p>Fiecare legătură este generată la prima recepție, numită <code>prim</code>. (A)</p> Signup and view all the answers

    Ce acțiune inițiază un nod (servitor) în algoritmul Dijkstra-Scholten după ce primește o scrisoare de la lordul său?

    <p>Trimite un semnal de confirmare către lordul său. (B)</p> Signup and view all the answers

    Ce rol au chm, chs și stop în contextul algoritmului Dijkstra-Scholten?

    <p><code>chm</code> pentru comunicarea între prelucrări, <code>chs</code> pentru comunicarea între noduri, iar <code>stop</code> între nod și prelucrare. (D)</p> Signup and view all the answers

    Ce reprezintă 'deficit' în structura 'arc' din algoritmul Dijkstra-Scholten?

    <p>Numărul semnalelor de care un nod mai are nevoie pentru a termina. (A)</p> Signup and view all the answers

    Care este rolul procesului Prelucrare în algoritmul Dijkstra-Scholten din text?

    <p>Efectuează prelucrarea principală a datelor. (C)</p> Signup and view all the answers

    Ce conditionează trimiterea unui semnal către prim în algoritmul Dijkstra-Scholten?

    <p>Recepția de semnale pentru toate legăturile de ieșire. (D)</p> Signup and view all the answers

    Cum comunică un lord cu servitorul său în contextul algoritmului Dijkstra-Scholten?

    <p>Prin semnale de comunicare pe canalul <code>stop</code>. (D)</p> Signup and view all the answers

    Conform textului, ce face un servitor când este întrebat de lord dacă a terminat treaba?

    <p>Răspunde afirmativ doar dacă a primit și trimis toate confirmările. (D)</p> Signup and view all the answers

    În codul dat, ce se întâmplă după ce Prelucrare[i] primește un mesaj pe chm[i]?

    <p>Trimite un semnal de confirmare pe canalul <code>chs[i]</code>. (A)</p> Signup and view all the answers

    Care este scopul semnalelor de tip terminare din cadrul algoritmului Dijkstra-Scholten?

    <p>Semnalează că un proces a finalizat prelucrarea. (A)</p> Signup and view all the answers

    În contextul terminării proceselor, ce acțiune efectuează un nod după ce a primit un marcaj pe o legătură de intrare?

    <p>Actualizează starea legăturii de intrare, scade numărul de marcaje așteptate și verifică dacă este marcat ca prim. (A)</p> Signup and view all the answers

    Ce scop are variabila nsemnale în cadrul algoritmului de detecție a terminării?

    <p>Ține evidența numărului de mesaje trimise, dar neconfirmate, către alte noduri. (D)</p> Signup and view all the answers

    În ce condiții un nod trimite un semnal de confirmare unui alt nod, conform algoritmului prezentat?

    <p>Când a primit un semnal de terminare și numărul de marcaje este zero. (D)</p> Signup and view all the answers

    Ce rol are variabila prim în procesul de detecție a terminării folosind marcaje?

    <p>Stochează identificatorul nodului care a inițiat procesul de detecție a terminării. (D)</p> Signup and view all the answers

    Ce se întâmplă cu variabilele out[id].activ și out[id].marcaj atunci când un nod primește un semnal de confirmare pe o anumită legătură de ieșire?

    <p>Ambele variabile, <code>out[id].activ</code> și <code>out[id].marcaj</code>, devin <code>false</code>. (C)</p> Signup and view all the answers

    În codul prezentat, ce reprezintă chs[i](k, id)?

    <p>Un canal de comunicare unidirecțional prin care nodurile trimit semnale de control. (D)</p> Signup and view all the answers

    Care este rolul instrucțiunii if (NOT in[id].activ) în blocul de cod ce tratează semnalul de recepție (k == recepție)?

    <p>Verifică dacă s-a primit deja un semnal de recepție pe legătura respectivă si daca nu, seteaza <code>in[id].activ</code> la <code>true</code> și incrementeaza <code>nmarcaje</code>. (B)</p> Signup and view all the answers

    Ce condiție trebuie să fie îndeplinită pentru ca un nod să intre în starea de terminare (k == terminare)?

    <p>Să fi primit semnalul 'terminare' și să fie marcat ca prim. (B)</p> Signup and view all the answers

    Ce reprezintă chm[i](id, data) în contextul codului prezentat?

    <p>Un canal prin care un process transmite altei procesului un set de date si id-ul procesului care trimite. (D)</p> Signup and view all the answers

    Care este scopul principal al structurii arc?

    <p>Utilizata pentru a urmari daca s-a primit/trimis un mesaj si un marcaj pe fiecare legatura din nod. (B)</p> Signup and view all the answers

    În algoritmul lui Huang, ce reprezintă variabila 'W' în contextul unui agent de control?

    <p>Suma ponderilor DW ale mesajelor neprocesate. (B)</p> Signup and view all the answers

    Care este condiția de terminare a algoritmului lui Huang, în ceea ce privește valoarea variabilei 'W'?

    <p>Când W este egal cu 1. (A)</p> Signup and view all the answers

    Ce se întâmplă cu valoarea 'W' când agentul de control primește un mesaj cu o pondere 'DW'?

    <p>'W' este incrementat cu 'DW'. (B)</p> Signup and view all the answers

    În cazul algoritmului lui Huang, ce se întâmplă la 'Timpul 1', ținând cont de mesajele trimise?

    <p>Procesul A trimite un mesaj cu DW = 0.25 către procesul 2, iar procesul 3 trimite un mesaj cu DW=0.25 către procesul 4. (D)</p> Signup and view all the answers

    La timpul 3, care sunt mesajele trimise și de la ce surse?

    <p>Procesul 4 trimite un mesaj către 1, procesul 2 către A, procesul 1 către 3 și procesul 5 către 1. (A)</p> Signup and view all the answers

    Care este scopul principal al algoritmului lui Huang?

    <p>Să detecteze terminarea unui program distribuit. (C)</p> Signup and view all the answers

    Ce rol are mesajul de tip C în algoritmul lui Huang?

    <p>Anunță că un proces a efectuat o acțiune și contribuie cu o pondere la suma totală W. (D)</p> Signup and view all the answers

    Ce reprezintă 'DW' în contextul algoritmului lui Huang?

    <p>Ponderea asociată unui mesaj și contribuția acestuia la suma 'W'. (B)</p> Signup and view all the answers

    Study Notes

    Algoritmi Paraleli și Distribuiți - Terminarea Programelor Distribuite

    • Problemă: Detectarea terminării execuției programelor distribuite
    • Algoritmi paraleli:
      • Toate procesele trebuie să se termine
      • Verifică existența ciclurilor infinite
      • Depistarea proceselor terminate sau blocate
      • Coada de procese gata de executat (ready) este goală pentru un singur procesor
    • Algoritmi distribuiți:
      • Fiecare proces trebuie să fie liber = Procesul a terminat execuția sau Așteaptă un mesaj (receive)
      • Nu există mesaje în tranzit pe canale

    Procese organizate în inel

    • Procesele sunt organizate într-un inel circular
    • Fiecare proces are un succesor și un predecesor
    • Primul proces începe execuția
    • Există metode de semnalizare între procese

    Tehnica jetoanelor

    • Inițiatorul de terminare este procesul P[1]
    • Acțiuni P[1] la activarea sa:
      • Se setează culoarea procesului la albastru
      • Se setează jetonul la 0
      • Se trimite jetonul prin canal
    • Acțiuni ale proceselor P[i] (i=1 la N) la primirea mesajului obişnuit:
      • Se setează culoarea procesului la roşu
    • Tehnica jetoanelor (2)
      • Procesele P[i], (i=2 la N) la primirea unui jeton (după ce devine liber):
        • Se setează culoarea procesului la albastru
        • Se incrementează jetonul
        • Se trimite jetonul către procesul succesor
      • Acțiuni ale procesului P[1] la recepția jetonului:
        • Dacă culoarea procesului este albastră, se anunță terminarea şi se oprește procesul

    Terminarea în cazul general (tehnica jetoanelor)

    • Topologia este un graf
    • Există un ciclu care conține toate arcele grafului
    • Lungimea ciclului este nc
    • Un jeton este transmis după mesajele de date
    • Valoarea inițială a jetonului este 0
    • Acţiunile proceselor Pi la primirea unui mesaj obişnuit:
      • culoarea[i] = roşu;
    • Acţiunile proceselor P[i] (i = 1...N) la primirea jetonului:
      • Dacă jetonul este egal cu nc, şi culoarea procesului este albastru, anunță terminarea și stop.
      • În caz contrar, dacă culoarea este albastră, incrementă jetonul cu 1, selectează următorul canal din ciclu (c) și trimite jetonul

    Terminare (topologii arbore)

    • Când un proces frunză se termină, acesta anunță părintele său.
    • Când un nod oarecare din arbore se termină, aşteaptă notificări de la fiii săi şi apoi anunță părintele său.
    • Notificările se propagă până la rădăcina arborelui (procesul sursă)

    Confirmarea mesajelor

    • Funcția de determinare a stării canalelor se poate împărți între procese.
    • Fiecare proces verifică canalele sale de ieșire.
    • Pe un canal:
      • Trimite mesaje de date și primește semnale de confirmare (sau invers)
    • Confirmarea mesajelor:
      • Procesul primește semnale de confirmare de la receptor pentru fiecare mesaj de date transmis pe un canal. Atunci canalul este gol.

    Algoritmul Dijkstra-Scholten

    • Bazat pe transmiterea unor semnale de confirmare
    • În cazul unei rețele cu topologie arborescentă:
      • Procesele frunză anunță părintele când se termină
      • Un nod oarecare din arbore așteaptă notificare de la toți fii săi și apoi anunță părintele lui
      • Notificarea se propagă până la procesul sursă (rădăcină)
    • Deficitul unei legături este diferența dintre numărul de mesaje de date transmise și numărul de confirmări primite pe legătură
    • Când un nod dorește să se termine, aşteaptă primirea semnalelor de la legăturile de ieșire, până la un deficit zero
    • Se trimite un semnal egal cu deficitul pe fiecare legătură de intrare

    Algoritmul lui Huang

    • Modelul se bazează pe:
      • Procesele pot fi active sau inerte
      • Doar procesele active transmit mesaje
      • Procesele inerte pot deveni active la primirea unui mesaj de calcul
      • Un proces activ poate deveni inerent la orice moment
      • Terminare: toate procesele sunt inerte și nu există mesaje de date în tranzit
      • Topologia este un graf conex
    • Utilizează agent de control cu pondere inițială 1
    • Alte procese au pondere inițială 0
    • Calculul începe atunci când agentul trimite un mesaj de date unui proces
    • Un proces liber devine activ la recepția unui mesaj de date

    Detecția terminării folosind marcaje

    • Procesele transmit mesaje de marcaj la sfârșitul comunicației
    • Procesele primesc semnale de confirmare doar pentru marcaj
    • Pentru terminare:
      • Așteaptă marcaje pe legăturile de intrare
      • Transmite marcaj pe legăturile de ieșire
      • Transmite semnale pe legăturile de intrare (mai puțin prim)
      • Așteaptă semnale pe legăturile de ieșire
      • Trimite semnal pentru prim

    Studying That Suits You

    Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

    Quiz Team

    Description

    Explorați conceptele esențiale ale tehnicii jetoanelor pe un înel, inclusiv rolul inițiatorului și comportamentul proceselor la primirea unui jeton. Aflați despre condițiile necesare pentru anunțarea terminării algoritmului și cum se compară acțiunile proceselor în diferite scenarii de comunicare. Testați-vă cunoștințele despre tehnicile avansate de sincronizare în computație.

    More Like This

    Networking Technologies Quiz
    15 questions

    Networking Technologies Quiz

    ProficientPerception avatar
    ProficientPerception
    Token Ring Protocol Overview
    32 questions

    Token Ring Protocol Overview

    AmazingNeptunium3354 avatar
    AmazingNeptunium3354
    Use Quizgecko on...
    Browser
    Browser