Lista cap5

Prévia do material em texto

LISTA DE EXERCÍCIO DE SISTEMAS OPERACIONAIS - CAP 5
Thayza Sacconi Guarnier
2014204174
5.1. Na Seção 5.4, mencionamos que a desabilitação de interrupções pode
afetar com frequência o relógio do sistema. Explique por que isso pode
ocorrer e como esses efeitos podem ser minimizados.
A atualização do relógio é feita toda a fez que acontece uma interrupção. Se as
interrupções forem desabilitadas por um longo período de tempo, é possível que o
relógio do sistema possa perder a hora certa. O sistema utiliza o relógio para fazer o
escalonamento, ou seja, o escalonamento é feita de forma errada causando
problemas ao sistema operacional. Esse efeito pode ser minimizado se as
interrupções forem desabilitadas somente por períodos curtos.
5.2. Explique por que o Windows, o Linux e o Solaris implementam vários
mecanismos de trancamento. Descreva as circunstâncias em que eles usam
spinlocks, locks mutex, semáforos, locks mutex adaptativos e variáveis de
condição. Em cada caso, explique por que o mecanismo é necessário.
Os spinlocks — junto com a habilitação e desabilitação da preempção do kernel —
são usados no kernel somente quando um lock (ou a desabilitação da preempção do
kernel) é mantido por um tempo curto. O Solaris usa o método do mutex adaptativo
para proteger apenas os dados que são acessados por curtos segmentos de código.
Isto é, um mutex é usado se um lock for mantido por menos de algumas centenas de
instruções. Se o segmento de código é maior do que isso, o método de aguardar em
um spinlock é excessivamente ineficiente. Para esses segmentos de código mais
longos, variáveis de condição e semáforos são usados.
5.3. Qual é o significado do termo espera em ação? Que outros tipos de
espera existem em um sistema operacional? A espera em ação pode ser
totalmente evitada? Explique sua resposta.
Enquanto um processo está em sua seção crítica, qualquer outro processo que tente
entrar em sua seção crítica deve entrar em um loop contínuo na chamada a acquire.
A espera em ação pode ser evitada porem isto irá causar um aumento de overhead
significativo.
5.4. Explique por que os spinlocks não são apropriados para sistemas com um
único processador, mas são usados com frequência em sistemas
multiprocessadores.
Os spinlocks — junto com a habilitação e desabilitação da preempção do kernel —
são usados no kernel somente quando um lock (ou a desabilitação da preempção do
kernel) é mantido por um tempo curto. O Solaris usa o método do mutex adaptativo
para proteger apenas os dados que são acessados por curtos segmentos de código.
Isto é, um mutex é usado se um lock for mantido por menos de algumas centenas de
instruções. Se o segmento de código é maior do que isso, o método de aguardar em
um spinlock é excessivamente ineficiente. Para esses segmentos de código mais
longos, variáveis de condição e semáforos são usados.
5.5. Mostre que, se as operações de semáforo wait ( ) e signal ( ) não
forem executadas atomicamente, a exclusão mútua pode ser violada.
Uma operação wait decrementa atomicamente o valor associado a um semáforo. Se
duas operações wait forem executadas em um semáforo quando seu valor for 1, se
as duas operações não forem executadas atomicamente, é possível que ambas
decrementem o valor do semáforo, violando assim a exclusão mútua.
5.6. Mostre como um semáforo binário pode ser usado para implementar a
exclusão mútua entre n processos.
do{
wait(mutex);
/*seção critica*/
signal(mutex);
/*seção restante*/
}while(true);
5.7. As condições de corrida podem ocorrer em muitos sistemas de
computação. Considere um sistema bancário que controle o saldo das contas
com duas funções: deposit(amount) e withdraw (amount). Essas duas
funções recebem a quantia(amount) a ser depositada em uma conta bancária
ou dela retirada. Suponha que um marido e a esposa compartilhem uma conta
bancária. Concorrentemente, o marido chama a função de withdraw( ), e a
esposa chama de deposit( ). Descreva como uma condição de corrida é
possível e o que pode ser feito para impedir que ela ocorra.
Uma situação em que vários processos acessam e manipulam os mesmos dados
concorrentemente e o resultado da execução depende da ordem específica em que o
acesso ocorre, é chamada uma condição de corrida. Chegaríamos a esse estado
incorreto porque permitimos que os dois processos manipulassem uma variável
concorrentemente. Para proteger da condição de corrida acima, temos de assegurar
que apenas um processo de cada vez possa manipular a variável.
5.8. A primeira solução de software correta conhecida para o problema da
seção crítica envolvendo dois processos foi desenvolvida por Dekker. Os dois
processos, P0 e P1, compartilham as variáveis a seguir:
boolean flag[2]; /* inicialmente falso */
int turn;
A estrutura do processo Pi (i == 0 ou 1) é mostrada na Figura 5.21. O outro
processo é Pj (j == 1 ou 0). Prove que o algoritmo satisfaz todos os três
requisitos do problema da seção crítica.
Exclusão mútua: feita através do uso da bandeira e do turno das variáveis. Se ambos
os processos definirem o seu sinalizador como verdadeiro, apenas um terá sucesso.
O processo de espera só pode entrar na seção crítica quando o outro processo
atualiza o valor do turno. Progresso: fornecido através da bandeira e altera as
variáveis. Não fornece uma alternância rigorosa. Em vez disso, se o processo deseja
acessar sua seção crítica, ele pode definir sua variável de bandeira como verdadeira
e inserir sua seção crítica. Ele define o valor do outro processo somente ao sair de
sua seção crítica. Se esse processo desejar entrar novamente em sua seção crítica -
antes do outro processo - repete o processo de entrar em sua seção crítica e
deixando de lado o outro processo após a saída. Espera limitada: preservada através
do uso da variável turno. Assuma dois procedimentos para inserir suas respectivas
secções críticas. Ambos estabelecem o seu valor como verdade; no entanto, apenas
o segmento cuja virada é pode prosseguir; o outro fio aguarda. Se você é delimitado,
você não está preservado. Para esperar indefinidamente enquanto o primeiro
processo entrou repetidamente - e saiu - sua seção crítica. Porém, o algoritmo tem
um processo que define o valor de se voltar para o outro processo, garantindo assim
que o outro processo entrará em sua seção crítica a seguir.
5.9. A primeira solução de software correta conhecida para o problema da
seção crítica, envolvendo n processos com um limite inferior de espera igual a
n – 1 vezes, foi apresentada por Eisenberg e McGuire. Os processos
compartilham as variáveis a seguir:
enum pstate {idle, want_in, in_cs};
pstate flag[n];
int turn;
Inicialmente, todos os elementos de flag estão ociosos. O valor inicial de turn
é imaterial (entre 0 e n – 1). A estrutura do processo Pi é mostrada na Figura
5.22. Prove que o algoritmo satisfaz a todos os três requisitos para o problema
da seção crítica.
Provando a propriedade Exclusão Mútua, nota-se que cada Pi entra em sua seção
crítica somente se a flag[j]=false. Uma vez que apenas Pi pode definir a sinalização
flag[j] , e como Pi inspeciona a flag [j] somente enquanto a flag [i] = true, o resultado
segue. Provando a propriedade Progresso, observa-se que o valor da curva pode ser
modificado somente quando um processo entra em sua seção crítica e quando ele
sai de sua seção crítica. Assim, se nenhum processo está executando ou deixando
sua seção crítica, o valor da volta permanece constante. O primeiro processo que
tem na ordem cíclica (turn, turn + 1, ..., n-1, 0, ..., turn-1) entrará na seção crítica.
Provando a propriedade Espera Limitada, observamos que, quando um processo
deixa a seção crítica, ele deve designar como sucessor exclusivo o primeiro processo
quecontém o turn cíclico + 1, ...,n - 1, 0, ... , gire-1, gire, garantindo que qualquer
processo que deseje entrar em sua seção crítica fará isso dentro de n - 1 turn.
5.10. Explique por que a implementação de primitivos de sincronização
através da desabilitação de interrupções não é apropriada em um sistema
com um único processador se os primitivos de sincronização devem ser
usados em programas de nível de usuário.
Ele pode desativar a interrupção do temporizador e evitar a mudança de contexto,
permitindo que ele use o processador sem deixar outros processos a serem
executados.
5.11. Explique por que as interrupções não são apropriadas para a
implementação de primitivos de sincronização em sistemas
multiprocessadores.
Interrupções não são suficientes em sistemas multiprocessadores desde
incapacitantes interrupções só impede outros processos de execução no
processador no qual as interrupções eram deficientes. Não há limitações sobre quais
processos poderiam ser executando em outros processadores e, portanto, o
processo de desativação interrupções não pode garantir o acesso mutuamente
exclusivo ao estado do programa.
5.12. O kernel do Linux tem uma política de que um processo não pode
manter um spinlock enquanto tenta adquirir um semáforo. Explique por que
essa política foi definida.
Não é possível segurar um bloqueio de rotação, enquanto você adquirir semáforo,
porque você pode ter que dormir enquanto aguardava o semáforo, e você não pode
dormir, mantendo um bloqueio de rotação.
5.13. Descreva duas estruturas de dados do kernel em que as condições de
corrida são possíveis.
Certifique-se de incluir uma descrição de como uma condição de corrida pode
ocorrer.
Sistema de gerenciamento de id do processo (pid) é possível que dois processos
possam ser criados ao mesmo tempo e há uma condição de corrida que atribui cada
processo a PID original. Uma tabela de processo do kernel, a condição de corrida
pode ocorrer quando dois processos são criados ao mesmo tempo e há uma raça
atribuindo-os a uma localização na tabela de processo do kernel.
5.14. Descreva como a instrução compare_and_swap( ) pode ser usada
para fornecer uma exclusão mútua que satisfaça ao requisito da espera
limitada.
A exclusão mútua pode ser fornecida como descrito a seguir: uma variável global
(lock) é declarada e inicializada com 0. O primeiro processo que invocar
compare_and_swap() atribuirá 1 ao lock. O processo entrará então em sua seção
crítica porque o valor original de lock era igual ao valor esperado (0). Chamadas
subsequentes a compare_and_swap() não serão bem-sucedidas porque, agora, lock
não é igual ao valor esperado (0). Quando um processo sair de sua seção crítica, ele
atribuirá de novo a lock o valor 0, o que permitirá que outro processo entre em sua
seção crítica.
5.15. Considere como implementar um lock mutex com o uso de uma
instrução de hardware atômica.
Suponha que a estrutura a seguir, que define o lock mutex esteja disponível:
typedef struct {
int available;
} lock;
(available == 0) indica que o lock está disponível, e um valor igual a 1
indica que o lock está indisponível.
do {
flag[i] = true;
while (flag[j]) {
if (turn == j) {
flag[i] = false;
while (turn == j)
; /* não faz coisa alguma */
flag[i] = true;
}
}
/* seção crítica */
turn = j;
flag[i] = false;
/* seção remanescente */
} while (true);
Figura 5.21 A estrutura do processo Pi no algoritmo de Dekker.
do {
while (true) {
flag[i] = want_in;
j = turn;
while (j != i) {
if (flag[j] != idle) {
j = turn;
else
j = (j + 1) % n;
}
flag[i] = in_cs;
j = 0;
while ((j < n) && (j == i || flag[j] != in_cs))
j++;
if ((j >= n) && (turn == i || flag[turn] == idle))
break;
}
/* seção crítica */
j = (turn + 1) % n;
while (flag[j] == idle)
j = (j + 1) % n;
turn = j;
flag[i] = idle;
/* seção remanescente */
} while (true);
Figura 5.22 A estrutura do processo Pi no algoritmo de Eisenberg e McGuire.
Usando essa struct, mostre como as funções a seguir podem ser
implementadas com o uso das instruções test_and_set( ) e
compare_and_swap( ):
 void acquire(lock *mutex)
 void release(lock *mutex)
Certifique-se de incluir qualquer inicialização que possa ser necessária.
5.16. A implementação de locks mutex fornecida na Seção 5.5 sofre de
espera em ação. Descreva que alterações seriam necessárias para que um
processo em espera para adquirir um lock mutex seja bloqueado e inserido
em uma fila de espera até que o lock se torne disponível.
5.17. Suponha que um sistema tenha vários núcleos de processamento. Para
cada um dos cenários a seguir, descreva qual é o melhor mecanismo de
trancamento — um spinlock ou um lock mutex em que processos em espera
adormecem enquanto aguardam que o lock se torne disponível.
 O lock deve ser mantido por um período curto.
 O lock deve ser mantido por um período longo.
 Um thread pode ser adormecido enquanto mantém o lock.
#define MAX_PROCESSES 255
int number_of_processes = 0;
/* a implementação de fork ( ) chama essa função */
int allocate_process() {
int new_pid;
if (number_of_processes == MAX_PROCESSES)
return -1;
else {
/* aloca recursos necessários aos processos */
++number_of_processes;
return new_pid;
}
}
/* a implementação de exit ( ) chama essa função */
void release process() {
/* libera recursos dos processos */
--number_of_processes;
}
Figura 5.23 Alocando e liberando processos.
O lock deve ser mantido por um período curto. Se o bloqueio for mantido por uma
curta duração, faz mais sentido usar o spinlock, pois, de fato, será mais rápido do que
usar o bloqueio mutex que requer suspender - e despertar - o processo de espera. O
lock deve ser mantido por um período longo. Se for para ser mantida durante um
longo período, a fechadura de exclusão mútua é preferível, pois isso permite que o
outro núcleo de processamento de marcar outro processo, enquanto o processo de
espera bloqueado. Um thread pode ser adormecido enquanto mantém o lock. Se a
linha poderá ser posto para dormir, mantendo o bloqueio, o bloqueio mutex é
definitivamente preferível que você não gostaria que o processo de espera estivesse
girando enquanto espera para o outro processo para acordar.
5.18. Suponha que uma mudança de contexto leve um tempo T. Sugira um
limite superior (em termos de T) para a manutenção de um spinlock. Se o
spinlock for mantido por mais tempo, um lock mutex (em que threads em
espera são postos para dormir) é uma alternativa melhor.
O spinlock deve ser mantido para maior que 2 vezes T. Mais longo do que essa
duração, seria mais rápido colocar o fio em suspensão (exigindo uma mudança de
contexto) e, posteriormente, despertá-lo (exigindo um segundo parâmetro de
contexto).
5.19. Um servidor web multithreaded quer controlar o número de solicitações
a que ele atende (conhecidas como hits). Considere as duas estratégias a
seguir, que impedem a ocorrência de uma condição de corrida na variável
hits. A primeira estratégia é usar um lock mutex básico quando hits é
atualizada:
int hits;
mutex_lock hit_lock;
hit_lock.acquire();
hits++;
hit_lock.release();
Uma segunda estratégia é usar um inteiro atômico:
atomic_t hits;
atomic_inc(&hits);
Explique qual dessas duas estratégias é mais eficiente.
5.20. Considere o exemplo de código para alocação e liberação de processos
mostrado na Figura 5.23.
a. Identifique a(s) condição(ões) de corrida.
Quantidade de variável de processos
b. Suponha que você tenha um lock mutex chamado mutex com as
operações acquire( ) e release( ). Indique onde o lock precisa ser
inserido para evitar a(s) condição(ões) de corrida.
O chamado paraacquire () deve ser colocado ao entrar cada função e call()
imediatamente antes de sair de cada função.
c. Poderíamos substituir a variável inteira
int number_of_processes = 0
pelo atômico inteiro
atomic_t number_of_processes = 0
para evitar a(s) condição(ões) de corrida?
Não, a razão é porque a corrida ocorre na função de process () atribuída onde o
número de processos foi testado pela primeira vez na instrução if, ainda é atualizado
posteriormente, com base no valor do teste.