PDF de programación - Tema 2. Regiones críticas

Contenidos
(cid:132) El problema de la sección crítica
(cid:132) Semáforos
(cid:132) Regiones críticas
(cid:132) Monitores

Bibliografía
(cid:132) Programación Concurrente

(cid:132) J. Palma, C. Garrido, F. Sánchez, A. Quesada,

2003

(cid:132) Capítulo 5

(cid:132) Concurrent Programming

(cid:132) A. Burns, G. Davies. Addison-Wesley, 1993
(cid:132) Capítulo 7

(cid:132) Sistemas Operativos

(cid:132) A. Silberschatz, P. Galvin. Addison-Wesley, 1999
(cid:132) Capítulo 6

© Alexis Quesada Arencibia

ProgramaciónConcurrente

1

© Alexis Quesada Arencibia

ProgramaciónConcurrente

2

Región crítica (RC)
(cid:132) Brinch Hansen, 1972

var

i,j: integer;
resource V: i, j;

...
...
region V do

S;

RC

(cid:132) La semántica de la RG establece

(cid:132) Los procesos concurrentes sólo pueden acceder a las
variables compartidas dentro de su correspondientes
RC

(cid:132) Un proceso que quiera entrar a una RC lo hará en un

tiempo finito

(cid:132) En un instante t, sólo un proceso puede estar dentro

de una RC determinada

(cid:132) Un proceso está dentro de una RC un tiempo finito, al

cabo del cual la abandona

© Alexis Quesada Arencibia

ProgramaciónConcurrente

3

© Alexis Quesada Arencibia

ProgramaciónConcurrente

4

RC
(cid:132) Esto significa que:

(cid:132) Si el número de procesos dentro de una RC es

igual a 0, un proceso que lo desee puede entrar a
dicha RC

(cid:132) Si el número de procesos dentro de una RC es
igual a 1 y N procesos quieren entrar, esos N
procesos deben esperar

(cid:132) Cuando un proceso sale de una RC se permite que

entre uno de los procesos que esperan

RC
(cid:132) Las decisiones de quien entra y cuando se
abandona una RC se toman en un tiempo
finito

(cid:132) Se supone que la puesta en cola de espera es

justa

© Alexis Quesada Arencibia

ProgramaciónConcurrente

5

© Alexis Quesada Arencibia

ProgramaciónConcurrente

6

1

Región crítica condicional (RCC)

Var

i,j: integer;
resource V:i,j;

...
...
region V when B do

S;

RCC
(cid:132) Su funcionamiento es similar a la RC

sólo que además para que un proceso
ejecute S, la condición B debe ser cierta

(cid:132) La evaluación de la condición B se
considera parte de la región crítica

(cid:132) En caso de evaluarse a falso, abandona

la RC para permitir a otros procesos
entrar en ella

© Alexis Quesada Arencibia

ProgramaciónConcurrente

7

© Alexis Quesada Arencibia

ProgramaciónConcurrente

8

RCC
(cid:132) Un proceso que haya evaluado la

condición a falso no vuelve a entrar a su
RC hasta que otro proceso abandone
ésta (espera pasiva)
(cid:132) Se vuelve a ejecutar cuando ¡posiblemente!

alguien haya modificado dicha condición

Implementación
(cid:132) Brinch Hansen sugirió el empleo de dos colas

para la implementación de las RCC

Qv

RC

(B=false)

When B

(B=true)

Cuando algún proceso
completa la RC

Qs

© Alexis Quesada Arencibia

ProgramaciónConcurrente

9

© Alexis Quesada Arencibia

ProgramaciónConcurrente

10

Limitaciones de las RCC’s
(cid:132) Aunque mejoran algunos aspectos
negativos de los semáforos, tienen
algunas limitaciones:
(cid:132) Pueden aparecer a lo largo de todo el

programa

(cid:132) No se garantiza la integridad de las

estructuras de datos compartidas

(cid:132) Realizar una implementación eficiente de

las mismas es una tarea difícil

Ejercicios
(cid:132) En un sistema concurrente existen dos tipos de
procesos, A y B, que compiten por utilizar cierto
recurso. Al recurso se accede mediante la rutina de
solicitarlo, esperar hasta que se pueda usar, usarlo y
luego liberarlo. En cualquier momento puede haber
un máximo de N procesos de cualquier tipo usando el
recurso (N es constante). Por otro lado, para que un
proceso de tipo A pueda entrar a emplear el recurso,
debe haber al menos el doble de procesos de tipo B
que procesos de tipo A dentro del recurso. Diseñe un
algoritmo que cumpla con estas reglas de
funcionamiento empleando regiones críticas

© Alexis Quesada Arencibia

ProgramaciónConcurrente

11

© Alexis Quesada Arencibia

ProgramaciónConcurrente

12

2

Ejercicios

(cid:132) Supongamos dos operaciones: pedir_memoria(cantidad) y

dejar_memoria(cantidad). Cuando un proceso pide memoria, se
bloquea hasta que haya la cantidad pedida de páginas libres, una vez
que ocurre las toma. Un proceso devuelve las páginas llamando a
dejar_memoria. Implementar dichas operaciones usando RCC en los
siguientes supuestos:

(cid:132)

Implementar la sincronización sin establecer ninguna política de quién
recibe primero.

(cid:132) Modificar lo anterior para que el trabajo que pide menos memoria sea el

primero.

salir o ser atendido.

(cid:132) Cambiar la política anterior para que el primero en llegar sea el primero en

(cid:132) Suponer que pedir y dejar devuelven páginas contiguas. Es decir, si un

proceso reclama dos páginas, se retrasa hasta que haya dos páginas
adyacentes disponibles. Desarrollar implementaciones de esa versión de
pedir_memira y dejar_memoria. Elegir una representación del estado de
páginas de memoria.

© Alexis Quesada Arencibia

ProgramaciónConcurrente

13

3