Esse documento representa parte dos meus estudos acerca do Livro - Operational Systems Three Easy Pieces, de dominio publico.

Locks

Uma trava/lock eh apenas uma variavel que delimita uma regiao critica. Essa variavel armazena o estado da trava, seja unlocked ou locked.

A ideia eh um tanto quanto simples. Quando uma thread acessa uma lock via lock(), ele “retem” (vira o owner) a lock para si e so desfaz a trava quando chamado por unlock(). Se outra thread tentar acessar o codigo dentro da regiao critica ele nao conseguira prosseguir.

Pthread Locks

Nome que a Lib POSIX usa para uma lock eh mutex (mutual exclusion).

exemplo:

Tecnicas de criação de um lock

desativando interrupções

Uma das soluções mais antigas para promover exclusão mutua era apenas desabilitar interrupções em regiões criticas. Neste caso, se o ambiente fosse de apenas um processador, parar as interrupções (com algum controle especial) habilitam a exclusão.

[!failure] problemas

  • necessidade de privilegios para todas as threads.
  • nao permite ambientes multiprocessador (ja que parar interrupcao so para um processador por vez)
  • pode-se perder interrupcoes

Spin-lock (test and set)

Test-and-set ou atomic exchange: uma instrução com suporte em hardware:

int TestAndSet(int *old_ptr, int new) {
	int old = *old_ptr; // fetch old value at old_ptr
	*old_ptr = new;     // store 'new' into old_ptr
	return old;         // return the old value 
}

typedef struct __loct_t {
	int flag;
}

void init(lock_t *lock) {
		// 0: lock is available, 1: lock is held
		lock->flag = 0;
}

void lock(lock_t *lock) {
	while (TestAndSet(&lock->flag, 1) == 1) 
		; // spin-wait (do nothing)
}

void unlock(lock_t *lock) {
	lock->flag = 0;
}

Esse metodo cicla até o lock estar disponível, ou seja, checa toda vez (quase como o polling, visto adiante, para IO).

Compare and Swap 

int CompareAndSwap(int *ptr, int expected, int new) {
	int actual = *ptr;
	if (actual == expected)
		*ptr = new;
	return actual;
}

checa se o valor de ptr é igual ao esperado. Se for, troca, se não, devolveo antigo valor de memoria.

…

Usando Filas: Sleeping ao inves de Spinning

Usaremos a seguinte estrutura:

typedef struct __lock_t {
	int flag;
	int guard;
	queue_t *q;
} lock_t;

void lock_init(lock_t *m) {
	m->flag = 0;
	m->guard = 0;
	queue_init(m->q);
}

void lock(lock_t *m) {
	while (TestAndSet(&m->guard, 1) == 1); //acquire guard lock by spinning
	if (m->flag == 0) {
		m->flag = 1; // lock is acquired
		m->guard = 0;
	} else {
		queue_add(m->q, gettid());
		m->guard = 0;
		park();
	}
}

void unlock(lock_t *m) {
	while (TestAndSet(&m->guard, 1) == 1); //acquire guard lock by spinning
	if (queue_empty(m->q))
		m->flag = 0; // let go of lock; no one wants it
	else
		unpark(queue_remove(m->q)); // hold lock (for next thread!)
	m->guard = 0;
}

Two Phase Locks

Uso real: o lock gira parcialmente e depois dorme.

Avaliando um lock

Correctness: garante exclusão mutua. Fairness: evita starvation performance: custo de CPU e mem.

Bibliografia

locks