Vés al contingut

Monitor (concurrència)

De la Viquipèdia, l'enciclopèdia lliure

En la programació paral·lela, els monitors són objectes destinats a ser usats sense perill per més d'un fil d'execució. La característica que principalment els defineix és que els seus mètodes són executats amb exclusió mútua. Això significa, que en cada moment en el temps, un fil com a màxim pot estar executant qualsevol dels seus mètodes. Aquesta exclusió mútua simplifica el raonament d'implementar monitors en lloc de codi de ser executat en paral·lel.

En l'estudi i ús dels semàfors es pot veure que les crides a les funcions necessàries per utilitzar-los queden repartides en el codi del programa, fent difícil corregir errors i assegurar el bon funcionament dels algorismes. Per evitar aquests inconvenients es van desenvolupar els monitors. El concepte de monitor va ser definit per primera vegada per Charles Antony Richard Hoare en un article de l'any 1974. L'estructura dels monitors s'ha implementat en diversos llenguatges de programació, inclòs Pascal concurrent, Modula-2, Modula-3 i Java, i com a biblioteca de programes.

Components

[modifica]

Un monitor té quatre components: inicialització, dades privades, procediments del monitor i cua d'entrada.

  • Inicialització: conté el codi a ser executat quan el monitor és creat.
  • Dades privades: conté els procediments privats, que només poden ser usats des de dins del monitor i no són visibles des de fora.
  • Procediments del monitor: són els procediments que poden ser anomenats des de fora del monitor.
  • Cua d'entrada: conté els threads que han cridat a algun procediment del monitor però no han pogut adquirir permís per executar-se encara.

Exclusió mútua en un monitor

[modifica]

Els monitors estan pensats per a ser usats en entorns multiprocés o multienllaçats, i per tant molts processos o threads poden trucar al mateix temps a un procediment del monitor. Els monitors garanteixen que en qualsevol moment, com a màxim un thread pot estar executantdinsd'un monitor. Executar dins d'un monitor vol dir que només un thread estarà en estat d'execució mentre dura la crida a un procediment del monitor. El problema que dos threads executin un mateix procediment dins del monitor és que es poden donar condicions de carrera, perjudicant el resultat dels càlculs. Per evitar-ho i garantir la integritat de les dades privades, el monitor fa complir l'exclusió mútua implícitament, de manera que només un procediment estigui sent executant-se al mateix temps. D'aquesta manera, si un thread crida a un procediment mentre un altre thread està dins del monitor, es bloquejarà i esperarà a la cua d'entrada fins que el monitor quedi novament lliure. Encara que se l'anomena cua d'entrada, no té per què suposar cap política de la teoria de cues.

Perquè resultin útils en un entorn de concurrència, els monitors han d'incloure algun tipus de forma de sincronització. Per exemple, suposem un thread que forma part del monitor i necessita que es compleixi una condició per poder continuar l'execució. En aquest cas, s'ha de comptar amb un mecanisme de bloqueig del thread, alhora que ha d'alliberar el monitor per a ser utilitzat per un altre fil. Més tard, quan la condició permeti a l'thread bloquejat continuar executant, ha de poder ingressar en el monitor en el mateix lloc on va ser suspès. Per això els monitors tenenvariables de condició que són accessibles només des de dins. Hi ha dues funcions per operar amb les variables de condició:

  • Cond_wait (c): suspèn l'execució del procés que la flama amb la condicióc. El monitor es converteix en el propietari del lock i queda disponible perquè un altre procés pugui entrar
  • Cond_signal (c): reprèn l'execució d'algun procés suspès ambcond_waiten la mateixa condició. Si hi ha diversos processos amb aquestes característiques tria un. Si no hi ha cap, no fa res.

Noteu que, al contrari que els semàfors, la crida a cond_signal (c) es perd si no hi ha tasques esperant a la variable de condicióc.

Les variables de condició indiquen esdeveniments, i no tenen cap valor. Si un thread ha d'esperar que passi un esdeveniment, es diu s'espera per (o en) la variable de condició corresponent. Si un altre thread provoca un esdeveniment, simplement utilitza la funció cond_signal amb aquesta condició com a paràmetre. D'aquesta manera, cada variable de condició té una cua associada per als threads que estan esperant que passi l'esdeveniment corresponent. Les cues s'ubiquen en el sector de dades privades vist anteriorment.

La política d'inserció de processos en les cues de les variables condició és la FIFO, ja que assegura que cap procés caigui en l'espera indefinida, cosa que sí que passa amb la política LIFO (pot ser que els processos de la base de la pila mai siguin despertats) o amb una política en què es desbloqueja a un procés aleatori.

Tipus de monitors

[modifica]

Abans es va dir que una crida a la funció cond_signal amb una variable de condició feia que un procés que estava esperant per aquesta condició reprengués la seva execució. Noteu que el thread que reprèn la seva execució caldrà obtenir novament el lock del monitor. Sorgeix la següent pregunta: què passa amb el thread que va fer el cond_signal? Perd el lock per donar-lo al thread que esperava? Quin thread continua amb la seva execució? Qualsevol solució ha de garantir l'exclusió mútua. Segons qui continua amb l'execució, es diferencien dos tipus de monitors: Hoare i Taula.

Tipus Hoare

[modifica]

En la definició original de Hoare, el thread que executa cond_signal li cedeix el monitor al thread que esperava. El monitor pren llavors el lock i l'hi lliura al thread dorment, que reprèn l'execució. Més tard quan el monitor quedi lliure novament el thread que va cedir el lock tornarà a executar.

Avantatges:

  • El thread que reprèn l'execució pot fer-ho immediatament sense fixar-se si la condició es compleix, perquè des que es va executar cond_signal fins que va arribar el seu torn d'executar cap procés pot canviar-la.
  • El thread despertat ja estava esperant des d'abans, de manera que podria suposar que és més urgent executar a seguir amb el procés despertant.

Desavantatges:

  • Si el procés que executa cond_signal no va acabar amb la seva execució es necessitaran dos canvis de context perquè torni a prendre el lock del monitor.
  • Al despertar a un thread que espera en una variable de condició, s'ha d'assegurar que reprengui la seva execució immediatament. Altrament, algun altre thread podria canviar la condició. Això implica que la planificació ha de ser molt fiable, i dificulta la implementació.

Tipus Taula

[modifica]

Butler W. Lampson i David D. Redell a 1980 van desenvolupar una definició diferent de monitors per al llenguatge Taula que brega amb els desavantatges dels monitors de tipus Hoare i afegeix algunes característiques.

En els monitors de Lampson i Redell el thread que executa cond_signal sobre una variable de condició continua amb la seva execució dins del monitor. Si hi ha un altre thread esperant en aquesta variable de condició, l'hi desperta i deixa com a punt. Podrà intentar entrar el monitor quan aquest quedi lliure, encara que pot succeir que un altre thread aconsegueixi entrar abans. Aquest nou thread pot canviar la condició per la qual el primer thread estava dormint. Quan reprengui l'execució el dorment, hauria de verificar que la condició efectivament és la que necessita per seguir executant. En el procés que va dormir, per tant, cal canviar la instrucció if per while, perquè en despertar comprovi novament la condició, i de no ser certa torni a trucar a cond_wait.

A més de les dues primitives cond_wait (c) i cond_signal (c), els monitors de Lampson i Redell tenen la funció cond_broadcast (c), que notifica als threads que estan esperant a la variable de condició c i els posa en estat llest. A l'entrar al monitor, cada thread verificarà la condició per la qual estaven detinguts, igual que abans.

Els monitors del tipus Taula són menys propensos a errors, ja que un thread podria fer una crida incorrecta a cond_signal o cond_broadcast sense afectar el thread en espera, que verificarà la condició i seguirà dormint si no fos l'esperada.

Vegeu també

[modifica]