04 Semaforos

Question 1

semaforos

Answer 1

Intro
Hasta ahora estudiamos herramientas para solucionar el problema de la sección crítica que están implementadas a muy bajo nivel: en el capítulo de sección crítica estudiamos varios intentos que terminaron culminando en el algoritmo de Dekker, y vimos el algoritmo de la panadería; en el capítulo siguiente estudiamos los locks, que sirven para ejecutar una serie de instrucciones de forma atómica, pero cuya implementación necesita muchísimo soporte de hardware. Lo que buscamos ahora es alguna herramienta que pueda ser manejada en un alto nivel, como el SO.

Estados de procesos
Antes de continuar, vamos a presentar los distintos estados en que se puede encontrar un proceso. El primer estado en que se encuentra un proceso es el inactivo, de ahí pasa a estado ready, de ready pasa a estado running. De running puede pasar a 3 estados: puede pasar nuevamente a ready, puede pasar a blocked, o puede pasar a finished. Finished es el último estado en que se encuentra un proceso, cuando termina su ejecución. De blocked puede pasar únicamente a ready.

Abstraccion de semaforo.
Ahora bien, los semáforos se pueden modelar como una entidad que tiene 2 atributos y 2 métodos. Los atributos son un entero no negativo y una cola o set de procesos. Los métodos que implementa un semáforo son signal y wait.

Tipos de semaforos (6)
grales vs binarios vs split, set vs cola vs busy-wait (weakly vs strongly fair).

Invariantes (2)

• v >= 0
• v = k + signal - wait

Demostracoin de exclusion mutua

• v = 1 + signal - wait
• # cs = wait - signal
• v = 1 - #cs
• # cs = 1 - v

Problemas clasicos

• produc - cons
  
  • buff inf: soluc. clasica. Sol. con semaforos.
  • buff finito:
• lectores escritores
  
  • solucion con var readers + 2 sem binarios
  • solucion con molinete
  • solucion sanguche
• filo
  
  • clasica -> deadlock
  • toman del lado izq salvo uno que agarra de la der.
  • entran todos menos 1 poniendo un semaforo sobre el room
• fumadores
  
  • 3 agentes - 3 fum
  • se exitnede lo anterior con pushers. 3 bools + 3 sem por ing. mas
  • sol gral: se pone var. entera en lugar de bool al caso anterior.

Question 2

prod/cons. con sem.

Answer 2

buff inf.
Productores producen y meten en el buff. sin problema
Consumidores tienen que chequear que ptr out < ptr in.

Con semaforos:
sem inicializado en 0. Prod. hacen signal. Consumidores hacen wait.

buff. finito
se agrega un sem. inicializado en N (capacidad del buffer). Prod. hacen wait. Cons. hacen signal.

Question 3

lectores/escritores. Sol.1 com sem.

Answer 3

numReaders: int
mutex: sem(1)
roomEmpty: sem(1)

Question 4

lectores/escritores. Sol.2 con sem

Answer 4

turnstile: sem(1)
roomEmpty: sem(1)
numReaders: int

Question 5

lectores/escritores. Sol.3 sem

Answer 5

numReaders: int(0)
numWriters: int(0)
noReaders: Sem(1)
noWriters: Sem(1)