Prova 1 2010/1 * Diferencie threads de nível de kernel e nível de usuários, suas vantagens e desvantagens. Threads de nível de usuários não são conhecidas pelo kernel, logo devem ser tratadas diretamente pelo usuário dentro do seu espaço de memória fornecido pelo sistema operacional. Threads de kernel são manuseadas diretamente pelo sistema operacional, e são suportadas por quase todos os sistemas operacionais. A relação entre threads de usuário e threads de kernel deve sempre existir de alguma forma, são essas: Many-to-One Cada thread de kernel é mapeada para diversas threads de usuário se revezando segundo gerenciamento por uma biblioteca de threads que as organiza no espaço do usuário. Embora ofereça melhor vazão do processamento, se uma thread fazer uma chamada ao sistema, ela será respondida a nível de processo, fazendo com que todas as outras threads sejam interrompidas. Como todas as threads concorrem para uma instância de processamento no kernel, não é possível efetuar processamento paralelo neste modelo. É um modelo útil para aplicações e dispositivos específicos. One-to-One É o modo como geralmente os sistemas operacionais atuais trabalham. Cada thread de usuário é mapeada para uma thread de kernel. Assim os processos requisitam threads através de uma API do sistema operacional. Como o kernel é informado de todas as threads criadas deste modo, é possível efetuar processamento paralelo, e também uma thread que faça uma chamada de sistema não interfere no processamento das demais. O ponto negativo é o overhead das aplicações no processo de criação de threads, o que pode causar problemas de desempenho. Por este motivo a maioria das implementações deste modelo acaba limitando o número de threads que podem ser criadas. Many-to-Many A ideia base deste modelo é a multiplexação das threads de usuário em relação às threads de kernel. Deste modo o usuário pode criar quantas threads desejar, mas somente um número limitado delas será instanciada por vez. Assim não é necessário se preocupar com o número de threads que podem ser criadas pelos usuários, e também não há problemas com chamadas de sistema de uma thread bloquearem as demais. Trata-se de um modelo mais recente implementado somente por alguns sistemas operacionais. * Quais os resultados possíveis para a execução de um fork()? Quais suas vantagens e desvantagens? Quando um processo é criado, o seu processo pai pode continuar executando ou pode entrar em espera até que alguns ou todos os seus filhos terminem a execução. Se um processo pai quiser esperar o retorno do seu filho, ele usará a chamada de sistema wait() até que seu filho chame um exit(). Quanto à memória ocupada pelos processos, um processo filho pode ser uma cópia exata do processo pai - possuindo a mesma seção de dados e programa, ou pode ter um novo programa carregado nele após sua criação. Neste último caso a chamada de sistema exec() é feita logo após o fork() por um dos processos para substituir sua imagem de memória pelo conteúdo de um arquivo binário. Quanto às suas threads, um novo processo pode replicar todas as threads ou somente a thread que a chamou replicada. Alguns sistemas possuem as duas implementações. No Linux, o padrão é copiar somente a thread que chamou a operação fork(). * Quais as situações em que é melhor usar um processo ou uma thread? Processos são modularizações de sistema para administrar a execução das tarefas em relação aos usuários. Diversos processos representam diversos programas, ou mesmo diversas instanciações ou funcionalidades de um mesmo programa sendo executados sobre um sistema operacional. Estas estruturas possuem todas as informações necessárias para que os programas possam ser colocados e retirados de execução. Um programa é útil para a divisão segura dos recursos de um computador, possibilitando que usuários diferentes executem os mesmos programas e acessem as mesmas funcionalidades da máquina sem interferir na integridade dos dados que estão sendo usados por cada um deles. São também os que possuem as divisões básicas de estado de execução organizados de diferentes formas pelo sistema operacional. Um processo pode estar em criação, execução, espera de um evento, espera para execução ou finalizado. As rotinas do sistema operacional precisam basicamente colocar os processos nestes estados nos momentos adequados. Uma thread é a denominação para a instanciação de um processo em CPU. Nos sistemas operacionais modernos um processo pode ter diversas threads, e assim ter sua vazão melhorada, principalmente em multiprocessadores. Colocar e retirar uma thread em execução custa muito menos do que fazer o mesmo com um processo que demanda troca de contexto. Duas threads do mesmo processo possuem os mesmos dados principais necessários para execução, o que requere uma operação mais rápido por parte do sistema operacional para trocá-las na CPU. Threads também são úteis no oferecimento de serviços. Um determinado programa pode criar diversas threads que ficam prontas para receber requisições, e assim ganhar o tempo de criação do processo em CPU quando uma tarefa precisar ser executada. * Quais as seções de compartilhamento de um processo em relação às suas threads? Um processo possui: Threads de um mesmo processo compartilham: - Seção de Código - Seção de Código - Seção de Dados - Seção de Dados - Arquivos - Arquivos - Registradores - Pilha * Codifique um semáforo contador de 1 a 6 em forma de semáforo binário, com as operações dormir e acordar para regular o acesso à uma região crítica. /* Considerar as funções list_[add, remove] (item, lista) como sendo uma verificação, adição e remoção do item em uma lista. */ /* Semáforo contador inicializado com 6 slots */ #define SLOTS 6 typedef struct { int count; struct process *list; } semaphore; semaphore *s; s->count = SLOTS; s->list = malloc (sizeof(long int) * SLOTS); /* Função a ser usada em entrada de região crítica. O mesmo processo não pode adentrar a mesma região crítica com diferentes threads. */ void* wait(semaphore *s) { s->count--; if (s->count <= 0) { list_add(pid, s->list); block(p); } } /* Função a ser usada em saída de região crítica. Simplesmente libera a contagem do semáforo para mais processos poderem adentrar a região. */ void* signal(semaphore *s) { s->count++; if (s->count <= 0) { list_remove(pid, s->list); wakeup(p); } } * O que é a chamada nice de um processo do UNIX? A chamada nice(), no formato nice(int inc) adiciona inc para o valor de prioridade de um processo, que é também chamado de nice na struct implementada no kernel. Um valor de nice mais alto significa uma menor prioridade. Somente superusuários podem especificar um incremento negativo para aumentar a prioridade de um processo. A variação destes valores depende de cada kernel. A partir da versão 1.3.43 do Linux esta faixa de valores passou a ser de -20 a 19, e -20 a 20 em alguns sistemas. Em algumas instâncias do kernel temos que os erros são números negativos, e faz-se necessária a conversão do valor nice para a faixa de 1 a 40. * O que é spinlock? Spinlock é também chamada de espera ocupada, e acontece quando um processo aguarda pela liberação de um semáforo enquanto gasta ciclos de CPU. Este método é especialmente oneroso porque outros processos poderiam usar este tempo de modo mais produtivo na CPU. Uma solução para este problema é causar um bloqueio em semáforo. O processo que precisa entrar em espera vai então para uma fila, e é acordado quando um outro processo executa um signal neste semáforo. * O que é liveness? Liveness é também chamado de progresso, e é o conceito de que somente os processos que não estão executando podem decidir qual será o próximo processo autorizado a adentrar em determinada região crítica. * O que é espera limitada? É o limite do número de vezes que os processos podem adentrar suas regiões críticas durante o período de tempo logo após a requisição de outro processo para um região crítica, e logo antes que esta permissão é concedida. * Qual a diferença entre mutex e semáforo? Mutex é um recurso usado para permitir que somente uma thread por vez acesse determinada região crítica. Outras threads que queiram adentrar esta região devem entrar em espera até que ela seja liberada. Um semáforo é uma contagem do número máximo de threads que podem adentrar uma região crítica. Quando uma thread entra, o contador decrementa. Quando o semáforo for zero, as threads devem esperar até que uma de suas posições seja liberada. Desse modo, podemos dizer que uma mutex é um semáforo com somente uma posição. * Considere o problema da montanha-russa: Existem n passageiros e um carro em uma montanha-russa, e eles repetidamente esperam para dar uma volta no carro. O carro tem capacidade para C passageiros, com C < n. O carro só pode partir quando estiver cheio. Após dar uma volta na montanha russa, cada passageiro passeia pelo parque de diversões e depois retorna à montanha russa para a próxima volta. Cada passageiro pode dar 3 voltas na montanha-russa. #define TOTAL_SEATS 3 #define MAX_RIDES 3 typedef struct { int id; int count; } person; typedef struct { int total; person *passengers; person *queue; } semaphore; void wait (semaphore *s) { if (p->count >= 3) return; p->count++; s->total--; if (s->total < 0) { list_add (p, s->queue); block(); } list_add (p, s->passengers); while (s->total < TOTAL); } void signal (semaphore *s) { s->total++; if (s->total < 0) { p = list_remove (s->passengers); wakeup(p); } }