Scheduling Flashcards
Considere el modelo de memoria compartida. (2/8/2016)
Dé dos primitivas de sincronización.
Explique ventajas y desventajas de cada una.
TAS y CAS (Compare-And-Swap)
No hay mejor o peor, simplemente tienen usos distintos. Ejemplos:
TAS sirve para hacer TASLock y TTASLock
CAS tiene número de consenso infinito, a diferencia de TAS que sólo es 2
¿Cómo cambiaría la implementación de los locks distribuidos para sistemas non-preemptive (sistemas sin desalojo)? (2013)
El hint era algo así como pensar en la implementación de los WAIT() y los SIGNAL()
No necesitas que todas las cosas sean atómicas, porque ya no te pueden interrumpir.
Defina condición de carrera (race condition).
Se llama condición de carrera a lo que ocurre cuando una ejecución da un resultado erróneo (un resultado que no es equivalente a ninguna ejecución secuencial de los procesos involucrados). Porque el output varía sustancialmente dependiendo de en qué momento se ejecuten las cosas (o del orden en que se ejecuten).
¿Cuáles son las 4 condiciones de Coffman y para qué nos sirven?
Exclusión mutua: Un recurso no puede estar asignado a más de un proceso.
Hold and wait: Los procesos que ya tienen algún recurso pueden solicitar otro.
No preemption: No hay mecanismo compulsivo para quitarle los recursos a un proceso.
Espera circular: Tiene que haber un ciclo de N≥2 procesos, tal que Pi espera un recurso que tiene Pi+1.
Se deben cumplir todas ellas en un sistema para que exista la posibilidad de deadlock.
Por ello, nos sirven para determinar si un sistema está expuesto a deadlock o no.
Es decir, alcanza con que en un sistema no se cumpla alguna de estas condiciones para que esté libre de deadlock. Algunos mecanismos para prevenir deadlock se basan en tratar de eliminar la posibilidad de que se cumpla alguna de las condiciones.
¿Por qué es necesaria la primitiva Test & Set para la implementación de semáforos?
It is critical that semaphore operations be executed atomically. We must guarantee that no two processes can execute wait() and signal() operations on the same semaphore at the same time. This is a critical-section problem; and in a single-processor environment, we can solve it by simply inhibiting interrupts during the time the wait() and signal() operations are executing. This scheme works in a single-processor environment because, once interrupts are inhibited, instructions from different processes cannot be interleaved. Only the currently running process executes until interrupts are re-enabled and the scheduler can regain control.
In a multiprocessor environment, interrupts must be disabled on every processor. Otherwise, instructions from different processes (running on different processors) may be in some arbitrary way. Disabling interrupts on every processor can be a difficult task and furthermore can seriously diminish performance. Therefore, SMP systems must provide alternative locking techniques— such as compare and swap() or spinlocks*—to ensure that wait() and signal() are performed atomically.
(Silberschatz pag. 275 10ma. edición)
*Spinlocks son los objetos lock que utilizan TAS para su implementación.¿Alcanza con la primitiva T&S en arquitecturas multiprocesador? En caso afirmativo justificar. En caso negativo, proponer una solución.
Si, ya que alcanza con poder tomar un mutex para modificar la variable del semáforo. Un mutex puede ser implementado usando solo TAS.
En caso de poseer compare-and-swap se puede hacer más “fácilmente” ya que se tiene acceso exclusivo a la variable y se modifica a la vez.
Desarrollar ReentrantLock que soporte locks recursivos. (16/11/2017)
Qsy esta en el drive
Explicar por qué la implementación de una cola FIFO no es correcta. (16/11/2017)
atomic<int> tail, head = 0;
int capacidad = N;
T[] items = new T[N];
void queue(x){
assert(!full());
items[tail.getAndInc() % capacidad] = x;
}
T dequeue(){
assert(!empty());
T x = items[head.getAndInc() % capacidad];
return x;
}
bool full(){return tail.get() - head.get() == capacity};
bool empty(){return tail.get() - head.get() == 0};</int>
Porque tanto queue como dequeue no son atómicas, lo que podría generar race conditions.
