A Deadlock Case in Minix3: Considerations about

Abstract— In 2006, professor Tanenbaum released Minix3 with a new book [15] and papers [14, 9, 8] supporting that drivers running as processes in user...
8 downloads 654 Views 404KB Size
Download PDF
Love PNG Images
A Deadlock Case in Minix3: Considerations about Performance and Reliability J. Kinoshita, H. T. Omoto, P. d’A. F. F. de S. Barbuda and W. L. Neto Abstract— In 2006, professor Tanenbaum released Minix3 with a new book [15] and papers [14, 9, 8] supporting that drivers running as processes in user mode made Minix, a microkernel operating system, more reliable than monolithic operating systems. We tested Minix3 in a operating system course at University of São Paulo University and unfortunately, we were able to deadlock the system after inserting a bug in a driver. Based on this problem, we make some considerations about performance and reliability in Minix3. Keywords— Minix, Operating Systems, Microkernel.

I. INTRODUÇÃO

O

S 1PROCESSADORES atuais possuem basicamente dois modos de operação: kernel (ou supervisor) e usuário. No modo kernel, o processador tem todo o controle da máquina, podendo executar instruções que fazem operações de I/O, manipulam ponteiros de pilhas (do kernel ou do usuário), acessam estruturas de dados que guardam o estado da máquina quando os processos são chaveados e ainda, acessam estruturas que cuidam do gerenciamento da memória virtual, atribuindo regiões de memória a processos. No modo usuário, o processador tem uma visão restrita da máquina. Por exemplo: se uma dada instrução tentar acessar I/O ou memória fora de sua região permitida então ocorrerá uma exceção. O processador passa do modo usuário para o kernel sempre que atende uma exceção que pode ser uma interrupção de hardware, erros (ex: divisão por zero) e interrupções de software (traps). O processador passa do modo kernel para o modo usuário ao termino da execução da exceção. A troca de modos causa um grande overhead (tempo gasto no chaveamento ao invés de se executar o aplicativo) pois em cada troca é necessário salvar ou recuperar os estados dos processos, alterar todo o cache de memórias, etc. A grande diferença entre os sistemas operacionais monolíticos e o microkernel é a quantidade de código que roda em modo kernel ou em modo usuário quando o sistema operacional responde a uma chamada de sistema: o microkernel advoga que quanto menos código rodar no kernel, melhor enquanto que nos sistemas monolíticos todo o tratamento é executado no modo kernel. O Minix é um 1 J. Kinoshita, Universidade de São Paulo (USP), São Paulo, São Paulo, Brasil, [email protected] H. T. Omoto, Universidade de São Paulo (USP), São Paulo, São Paulo, Brasil, [email protected] F. F. de S. Barbuda, Universidade de São Paulo (USP), São Paulo, São Paulo, Brasil, [email protected] W. L. Neto, Universidade de São Paulo (USP), São Paulo, São Paulo, Brasil, [email protected]

sistema operacional microkernel e foi criado pelo prof. Andrew Tanenbaum para fins didáticos; mas ao mesmo de forma inovadora porque geralmente eles são monolíticos, como o Windows, Linux, FreeBSD e Solaris.

Um sistema operacional monolítico é visto pelos programas aplicativos como um conjunto de rotinas, conhecidas como system calls (chamadas de sistema), que são executadas em modo kernel (passam a executar em modo kernel através das interrupções de software / trap). Por exemplo: leitura de bytes de um arquivo, alteração de senha, leitura do relógio. Em um sistema operacional microkernel como o Minix, o sistema operacional também tem como objetivo fornecer as mesmas system calls com a diferença de que boa parte das operações não é executada em modo kernel e sim no modo usuário. O microkernel não tem mais a responsabilidade de oferecer system calls e sim, a de oferecer serviços muito mais simples como send e receive que permitem a troca de mensagens entre os processos. A system call será trata por processos usuários rodando fora do kernel. No caso do Minix, dois processos que tratam das system calls são o gerenciador de arquivos FS (File System Manager) e o gerenciador de processos PM (Process Manager no Minix3, antes chamado de gerenciador de memória – Memory Manager nos Minix1-2). O FS trata de system calls como o read e write e o PM de system calls como o fork e exit. Quando um processo aplicativo envia uma mensagem solicitando a system call read ao FS é gerado uma interrupção de software (trap). O FS troca diversas mensagens com outros processos, notoriamente os drivers, para que o read seja executado. O argumento em favor do sistema microkernel que quanto menos código rodar em modo kernel, menos erros fatais tendem a ser cometidos. Portanto, um sistema operacional microkernel tende a ser mais robusto porque ele está menos sujeito a erros por parte do programador. O argumento é semelhante a dar prefêrencia por usar uma máquina como usuário normal ao invés de usar como "root" (administrador do sistema). Quanto mais poder se tem, mais abuso pode se cometer. A idéia é dar poder somente quando estritamente necessário. Neste artigo, vamos argumentar que isso é parcialmente verdadeiro. É verdade que o código executado no microkernel é mais robusto do que o código executado no kernel de um sistema operacional monolítico; porém essa robustez não deveria ser comparada dessa forma. A comparação deve ser feito quanto à resposta às system calls. Por exemplo, é correto afirmar que o sistema microkernel é mais robusto comparando o fato de que ele não trava ao enviar

mensagens (atividade básica do microkernel) enquanto que o sistema monolítico trava ao escrever milhares de bytes em um arquivo (atividade básica do sistema operacional monolítico, mas muito mais complexa). Existe uma queda de desempenho em um sistema operacional microkernel [14] devido a diversas trocas de mensagens entre processos. Cada mensagem exisge que o sistema troque de modo kernel para modo usuário e viceversa, o que causa um overhead significativo. Uma estrutura de dados importante é a tabela de processos. Essa tabela contém informações sobre cada processo e os recursos a ele alocados como memória e arquivos abertos. Assim, uma parte da tabela de processos é manipulada pelo gerenciador de processos PM, pelo gerenciador do sistema de arquivos FS e pelo microkernel. Se um processo termina, é necessário que diversos processos se comuniquem entre si para que a tabela de processos “distribuída” se mantenha consistente. Assim, é fácil perceber que um sistema microkernel possui um desempenho inferior a um sistema monolítico. A queda de desempenho no Minix3 é maior que em outras versões [9] porque na nova versão 3, os drives são processos em modo usuário. Desse modo, é necessário que eles enviem mensagens ao kernel solicitando a entrada ou saída; pois essas operações (in e out no microprocessador x86) são privilegiadas. Em Maio de 2006, o professor Tanenbaum, autor do Minix [15], e outros autores publicaram o artigo: “Can We Make Operating Systems Reliable and Secure?”. Segundo o artigo a resposta é sim, e o caminho é o Minix3. O artigo defende o microkernel, e em especial, que os drivers devam ser colocados no espaço de usuário, rodando como processos de usuário. Isso porque se ocorrerem problemas nos drivers, então, o sistema poderá detectar o problema e reinicializar o driver. De acordo com [14]: Among the other specific features aimed at improving reliability, the most crucial is the self-healing property. If a driver does a store through an invalid pointer, gets into an infinite loop, or otherwise misbehaves, the reincarnation server will automatically replace it, often without affecting running processes. While restarting a logically incorrect driver will not remove the bug, in practice subtle timing and similar bugs cause many problems, and restarting the driver will often repair the system. In addition, this mechanism allows recovery from failures that are caused by attacks, such as the “ping of death” which can crash a computer by sending it an incorrectly formatted IP packet. (ênfase nossa). Em um curso de sistemas operacionais baseado em [15] resolvemos testar a capacidade do Minix de se recuperar no caso de drivers mal escritos; ou seja, a de testar a propriedade de se auto recuperar (self-healing property). Introduzimos um loop infinito em um driver para observar como o sistema se recuperava. Dependendo onde o loop infinito era inserido, o sistema não se recuperava; pelo contrário, todo o sistema travava, isto é, a shell travava e o usuário ficava impossibilitado de dar qualquer comando, mesmo o shutdown. Na seção II. mostramos como o Minix3 foi utilizado em um curso de sistemas operacionais e a proposta de vários projetos que nos possibilitaram estudar um deadlock decorrente do

loop infinito em um driver. Isso foi inesperado porque estávamos apenas testando a veracidade da afirmação em [14]. Na seção III. , apresentamos o estudo do motivo pelo qual o sistema não se recuperou do erro do loop infinito; ou seja, o motivo pelo qual o sistema entrou em deadlock. Por fim, na seção IV. , questionamos se a queda de desempenho em um sistema microkernel é compensada pela robustez adicional ([14, 9, 8]). II. O MINIX EM NOSSO CURSO DE SISTEMAS OPERACIONAIS Existem diversas formas de se apresentar um sistema operacional em um curso de sistemas operacionais. O sistema operacional pode ser real (ex: Minix) ou simulado (ex: nachos que roda em uma máquina virtual MIPS) [2]. Alguns cursos de sistemas operacionais são apenas teóricos e não apresentam o código de um sistema operacional, mas [5] argumenta a importância do aprendizado experimental citando John Dewie (a educação genuína vem pela experiência), Lewin (o aprendizado decorre da participação ativa) e Piaget (o aprendizado decorre da interação entre o indivíduo e o ambiente). Em nossa própria experiência de ensino de sistemas operacionais, um aluno expressou que “colocar a mão na massa” fez a grande diferença no curso, pois de resto ele podia aprender lendo o livro-texto adotado [15]. Vamos nos restringir a discutir duas possíveis alternativas para um curso de sistemas operacionais: o uso do Minix e o uso do Linux. Entre o Minix e o Linux (ou mesmo o freebsd) optamos pelo Minix porque é muito mais simples, didático, e responde às system calls do padrão POSIX. O Minix tem sido usado em diversos cursos de sistemas operacionais. Isso pode ser visto pelas ementas dos cursos ou mesmo por artigos que relatam as experiências de professores e alunos: [7, 6, 1, 10]. O Minix3 apresenta a interface gráfica com o X Windows, roda o compilador gcc e possui interface com a rede; isto é, o Minix3 é um sistema operacional que está muito próximo de um sistema mais desenvolvido como o Linux. Se usássemos o Linux para fins didáticos teríamos diversos problemas: seu código se altera com muito mais rapidez e não é didático. Por exemplo: o Linux foi portado para diversas máquinas (ex: Intel e ARM) e isso se reflete em seu código (ex: código assembly para Intel e ARM). O gerenciador de memória do Linux faz uso da memória virtual enquanto o do Minix é muito mais simples e não suporta memória virtual. Usar a memória virtual implica em se conhecer profundamente o microprocessador. Existem diversos sistemas de arquivos suportados pelo Linux, enquanto que o Minix suporta apenas um bem simples. O Minix possui um livro didático a ele associado, enquanto o Linux não. Assim, do ponto de vista de ensino de sistemas operacionais, o Minix é uma escolha melhor. Ao final de cada capítulo de [15], o professor Tanenbaum propõe exercícios para serem realizados no Minix, em geral, algumas modificações no código. Dado que o Minix evolui mais rápido que o livro, encontramos exercícios propostos que nem podiam ser resolvidos, pois a solução já estava implementada na nova distribuição do Minix. Além disso, não apreciamos seguir os exercícios do livro porque a maioria deles são muito

específicos e complexos, não permitindo que o aluno tenha uma visão de mais alto nível. Em nosso curso de sistemas operacionais, resolvemos propor os nossos próprios projetos. Um exemplo é monitorar as mensagens trocadas entre processos para se entender como o Minix funciona. Vários projetos já foram criados e passados aos alunos cobrindo diversas partes do Minix, em especial, os drivers. Esses exercícios são alterados de ano para ano com o objetivo de criar uma base de trabalhos que podem ser utilizados por alunos de turmas posteriores. Dentre vários exercícios, uma sequência deles nos levou a questionar a capacidade do Minix3 de se auto-recuperar. Essa sequência de exercícios (projetos realizados por diferentes equipes de alunos) consistiu em criar um driver, testá-lo e depois introduzir um erro no driver. Vários desses exercícios já eram propostos em turmas anteriores. A nossa expectativa ao introduzir o loop infinito no driver era que o Minix3 iria de fato se recuperar como diz o artigo [14]; porém dado que nossa expectativa foi frustrada e o Minix travou, então tivemos que analisar o motivo. Os alunos que participaram da analise do motivo é que estão presentes como coautores; porém referenciamos os trabalhos das outras equipes também. Em nosso curso de sistemas operacionais propomos os seguintes exercícios sobre drivers: 1. Acessar portas de entrada e saída fora da competência do driver. Por exemplo: o driver da impressora não deve ser capaz de acessar portas referente à porta serial. Resposta: Constatamos que o Minix3 não se comportava de forma esperada, pois, drivers podiam acessar portas de entrada e saída fora de sua competência. Acreditamos que esse problema será resolvido facilmente em versões futuras do Minix. 2. No caso do Linux (ou outros Unix's), um driver é um conjunto de rotinas que implementam funções padronizadas como read e write. No caso do Minix, um driver é um processo que fica em um loop infinito onde ele recebe uma mensagem (ex: DEV_READ para ler dados do dispositivo, etc.) e as trata. Ao final do tratamento, o driver envia a mensagem TASK_REPLY(ok) informando ao FS que o driver tratou do pedido. Crie um driver muito simples no Minix que apenas imprime mensagens quando recebe mensagens do FS (ex: imprime ao receber DEV_OPEN, DEV_CLOSE, etc.). O driver pode ser associado a /dev/teste. Declare /dev/teste associando um major e minor number e o código do processo associado ao driver. Use service para rodar o driver. Gere um relatório sobre isso. As mensagens que o driver deve responder são: DEV_OPEN (abrir o driver), DEV_CLOSE (fechar o driver) e DEV_WRITE (escrever no driver). Envie mensagens a /dev/teste como em: echo "lixo" > /dev/teste veja as mensagens que são recebidas e que são impressas pelo seu driver. Faça o driver imprimir a string que recebeu (“"lixo“").

Resposta: Os alunos implementaram adequadamente o driver. Puderam constatar que ao realizar um comando na shell como: echo "lixo" > /dev/teste levavam o driver a imprimir o que acontecia como proposto no exercício. A resposta apresentada pelos alunos se encontra em [11]. 3. Crie um driver como especificado em 2). Teste o driver: Envie mensagens a /dev/teste como em: echo "lixo" > /dev/teste e veja a mensagem que é impressa pelo seu driver. Agora faça com que o driver, logo após imprimir a string que recebeu “lixo" entre em um loop infinito simulando um problema no driver. De acordo com [14], o sistema deveria ser capaz de se auto-recuperar de um erro em um driver, porque o reincarnation server deveria automaticamente detectar a falha e retartar o driver. Verifique se a prioridade do driver está sendo alterada, decaindo a cada “ping”. Faça: echo "lixo" > /dev/teste Se de fato for verdade que o driver é restartado então uma nova mensagem será escrita na tela. Verifique isso. Resposta: No Minix3, o responsável pelo gerenciamento do filesystem é o processo FS (File System). Ele é o intermediário entre o aplicativo e o driver, ou seja, é responsável por atender às system calls dos processos aplicativos e mandar as mensagens corretas para os drivers. Os alunos fizeram a experiência colocando um loop infinito em uma posição do código do driver, verificando se o sistema se recuperava. O relatório está apresentado em [12]. Eles colocaram o loop infinito em diversas posições e constataram que em alguns casos o sistema funcionava de acordo com o previsto [14], ou seja, o driver era restartado e em outros casos não. Isso foi inesperado e criamos o próximo exercício. Os casos em que ele trava ocorrem quando o loop infinito impede que o driver responda TASK_REPLY(ok) ao FS. Nesse caso, o FS está bloqueado esperando pela mensagem de retorno. Em outros casos, quando o FS está desbloqueado então o sistema se auto recupera como previsto pelo artigo [14]. 4. Observamos que o driver com o loop infinito faz o Minix travar e suspeitamos que ele trava porque o FS fica bloqueado esperando uma resposta do driver que não chega. Dada a dificuldade de se analisar o que de fato levou o Minix travar, faça o FS imprimir mensagens criando os comandos fale e quieto. O comando fale faz o FS imprimir as mensagens que troca e o comando quieto volta o FS ao estado normal. Através das mensagens impressas, procure entender o motivo pelo qual ele trava em algumas situações quando o driver fica em loop infinito. Resposta: é apresentada na próxima seção. De fato, foi confirmado que o problema envolvia o FS que ficava bloqueado aguardando uma resposta do driver que não chegava devido ao loop infinito. Esse bloqueio levava

outros processos também a serem bloqueados e enfim tivemos o deadlock. Fizemos algumas alterações no relatório original apresentado que está em [4]. Esse problema foi resolvido através dos alunos co-autores desse artigo. III. O LOOP INFINITO EM UM DRIVER LEVA O MINIX A UM DEADLOCK

A grande diferença entre o Minix3 e versões anteriores é que os drivers rodam em modo usuário e além disso, caso se detecte que um driver “morreu”, ele é reinicializado. O processo RS - Reincarnation Server - roda no mesmo nível que o FS e o PM em modo usuário. O objetivo é enviar um “ping” periodicamente aos drivers e, caso o driver não responda, então ele é reinicializado. Para um driver não nativo, deve-se dar um comando para que o RS realize os “pings”. Caso contrário, não há tratamento pelo RS. Para ativar a monitoração do driver é necessário o seguinte comando (na shell): service up /usr/sbin/driverteste –dev /dev/driverteste –period 3Hz O comando faz com que o RS mande o “ping” a cada 3 segundos. Alteramos o Minix com o objetivo de monitorar a troca de mensagens criando os comandos fale e quieto. Esses comandos foram implementados através de system calls que são tratadas pelo FS. O comando fale tem como parâmetro o pid do aplicativo de teste (que acionará a rotina de escrita do driver) de forma que: • O FS imprima as mensagens recebidas pelo processo aplicativo. Se fôssemos imprimir todas as mensagens recebidas teríamos o computador com uma tela cheia de mensagens sem sentido. Ao implementar a monitoração das mensagens, é preciso observar que a comunicação entre processos (usando o send, receive e sendrec) não utiliza o pid do processo origem ou destino e sim o seu endpoint (um número usado pelo Minix para identificar processos que fazem parte do tratamento das system calls). • O FS imprima todas as mensagens enviadas a um driver com o objetivo de atender ao pedido do processo sendo monitorado. As mensagens são enviadas do FS aos drivers através de sendrec. O sendrec é uma forma de enviar mensagens no Minix onde o processo envia uma mensagem (send) e espera uma resposta (rec) [15]. Enquanto a resposta não vem, o processo (no caso, o FS) fica bloqueado. O fato do FS se comunicar dessa forma com o driver já é um indicativo de que problemas no driver podem acarretar problemas ao FS. A implementação dos comandos pode ser vista em [4]. Observamos que o RS possui um modo “verbose” (ativado através de uma flag) herdado de quando o Minix3 estava em desenvolvimento. A forma como esse modo pode ser ativado no Minix3 está em [4]. O problema do modo verbose é que

não seleciona as mensagens como fizemos com o comando “fale”. Isso gera um fluxo relativamente alto de mensagens espúrias e não relacionadas ao nosso problema. Quando monitoramos o FS, executando o aplicativo de teste, observamos que o RS imprime uma mensagem dizendo que detectou um driver que não respondeu ao “ping”. Assim, monitoramos o sistema operacional através dos comandos fale/quieto e do modo verbose do RS. Na Fig. 1 apresentamos o código de teste usando a system call fala criada por nós que recebe como parâmetro o pid do processo a ser monitorado, no caso, o próprio pid do programa de teste.

Figura 1. Programa “"teste“". Faz o FS e driver apresentarem as mensagens trocadas ao escrever algo no driver.

Na Fig. 2 apresentamos a saída ao rodar o programa de teste (em condições normais, sem loop infinito). O processo do usuário abre o driver. Isso acarreta uma mensagem que é enviada ao FS para tratar a system call open. O FS envia a mensagem DEV_OPEN para o driver (nesse exemplo, rodamos com /dev/teste, criado pelos alunos, e não com /dev/lp) , o driver responde com TASK_REPLY para o FS. De forma semelhante ocorre a escrita (DEV_WRITE) e o fechamento do driver (DEV_CLOSE).

Figura 2. Saída do programa teste.

Em condições normais, a comunicação entre o programa teste, o FS e o driver pode ser representado na Fig. 3.

Embora tivéssemos drivers simples construídos por nós mesmos, resolvemos testar o loop infinito em um driver do próprio Minix por considerarmos que esses drivers são bem escritos e testados. Escolhemos o driver da impressora. Introduzimos um loop infinito na função de escrita do driver e constatamos que o Minix inteiro travava. Após monitorarmos e descobrirmos a causa do deadlock, fizemos uma alteração no driver da impressora, colocando o loop infinito de forma que o sistema pudesse se recuperar como previsto por [14]. Assim analisamos as duas possibilidades quando inserimos um loop infinito em um a driver: • O Minix inteiro trava . • RS detecta e reinicia driver.

Figura 3. Fluxo de mensagens trocadas, Minix morre pois o FS fica esperando o TASK_REPLY(OK) do Driver – acima o Minix morre na linha vermelha.

O Minix inteiro trava caso o loop infinito seja inserido de forma que o driver não responda ao FS. Um exemplo é o que ocorre na Fig. 3. Caso o loop infinito seja inserido no driver na posição referente à linha vermelha, então o driver recebe a mensagem DEV_WRITE, mas deixa de responder a mensagem TASK_REPLY(OK) levando o Minix ao deadlock. Caso o driver responda ao FS então o Minix não trava. Utilizando as ferramentas fale/quieto e o modo verbose do RS pudemos chegar à conclusão de que o deadlock ocorre como na Fig. 4.

Figura 4. deadlock

O Minix3 entra em deadlock da seguinte forma: 1. O processo usuário requisita algum serviço (i.e. faz a system call write) ao FS. 2. Enquanto o processo fica bloqueado até receber uma resposta, o FS repassa a requisição ao driver do dispositivo adequado e o FS também fica bloqueado até receber resposta.

3. Enquanto isso, de tempos em tempos o RS (Reincarnation Server) manda mensagens DEV_PING a todos os dispositivos que ele monitora, de modo a verificar se estão funcionando. 4. Quando o RS percebe que o driver não responde ao DEV_PING (pois entrou em loop infinito), ele manda uma mensagem SIGKILL, tentando matá-lo. Esse sinal, assim como todos os outros, são tratados pelo PM - Process Manager. Como o RS usa uma system call normal para se comunicar com o PM, ele fica bloqueado até receber resposta, como qualquer outro processo também ficaria bloqueado esperando o retorno da system call. 5. O PM elimina o processo, libera sua memória e, por fim, tenta avisar o FS que o processo morreu. A função usada para isso, tell_fs, também bloqueia até receber a resposta do FS. 6. Porém, o FS também está bloqueado, esperando resposta do driver. O sistema inteiro trava. No passo 5, o PM está informando o FS que o driver vai ser finalizado para que o FS tome as medidas administrativas cabíveis (exemplo: limpar todos os arquivos associados ao processo que morre), mas o FS está travado pois está aguardando a resposta do driver para a requisição de write. Observamos que o PM se comunica com uma chamada bloqueante com o FS, o que faz com que o PM fique bloqueado esperando uma reposta do FS que já está bloqueado, e assim, temos o deadlock. O Reincarnation Server não restarta um driver em loop infinito em todas as situações. Descobrimos que, na verdade, ele é o principal causador do ciclo que trava o sistema, pois além de ser travado, causa o travamento do PM e, consequentemente, o fim do tratamento de mensagens pelo mesmo – travando o sistema inteiro. Isto não deveria acontecer, pois o RS deveria garantir a confiabilidade do tratamento de erros como este. Sugerimos a seguinte alternativa para a correção deste problema: • A detecção (pelo RS) que o FS está travado e, caso esteja, ele destrava o FS; • Em seguida, manda o kill normalmente, pois o PM não será travado (ao realizar o tell_fs) por consequência do FS não estar também. Essa situação nos mostra que o RS, apesar de tratar o erro de maneira razoável, ainda possui pontos a ser melhorados. Ele, por possuir a função de tratar os erros e realizar a recuperação do sistema, não deveria esperar que nenhum outro servidor lhe enviasse uma resposta. Idealmente, o RS deveria supor que exista a possibilidade de outro servidor (como o FS) estar travado. Portanto, a presença de um sendrec é inaceitável para o processo de finalização do driver. Uma alternativa (ao lado daquela sugerida anteriormente) é o RS enviar mensagens (pedindo o kill do processo) sem que ele fique bloqueado, isto é, no Minix, o RS poderia usar a função NOTIFY ao invés do SEND. Ao se trabalhar com drivers no Minix, é possível se observar outras situações anômalas:

•

O Minix não abaixa a prioridade do driver: Isso ocorre quando não se sobe o serviço com o period ajustado. Isso faz com que o RS não monitore o driver, portanto o Minix não sabe que o driver está em loop, portanto não é abaixada a prioridade. • Dependendo de onde se coloca o loop infinito, o Minix só trava na segunda vez que o driver é chamado. Isso ocorre por duas condições em conjunto: o period não for ajustado e o loop for posto após a mensagem de SUSPEND. Isso faz com que a primeira chamada do driver o coloca em loop imperceptível ao RS. Ao se fazer a segunda chamada, não há resposta do driver, pois este, ainda está no loop anterior, o FS fica travado e ocorre o mesmo da situação de travamento explicada durante este relatório. Portanto, podemos observar que há diversas maneiras de enganar o sistema operacional do Minix para que o tratamento de loops infinitos cause danos sérios ao sistema. Infelizmente ainda não existe a total confiabilidade do Minix como divulgado. IV. CONCLUSÃO. CONSIDERAÇÃO SOBRE O DESEMPENHO E ROBUSTEZ DO MINIX. Após a constatação de que diversos processos entravam em deadlock no Minix devido a um loop infinito em um driver no Minix3, contradizendo o artigo do Tanenbaum, a próxima pergunta é: um sistema operacional microkernel tende a ser mais robusto em relação ao monolítico mesmo com um desempenho inferior? O artigo [14] compara o microkernel a um navio que tem seu casco dividido em compartimentos, de forma que se um compartimento for danificado, os outros compartimentos mantém o navio flutuando; porém como observamos no deadlock apresentado, de nada adianta o microkernel continuar “vivo” se processos usuários necessários para responder às system calls morrerem. A resposta é que encontramos indícios de que o Minix3 não é mais robusto que o monolítico por ser microkernel, ou seja, por isolar um kernel funcionando e criar condições para que drivers sejam restartados. O motivo para isso está na complexidade em se remover drivers. Dado que a tabela de processos é distribuída, é necessário que diversas mensagens sejam trocadas com o simples objetivo de restartar os drivers; e esse fluxo de mensagens não é analisado de forma global. Portanto a simplicidade do código do Minix é somente aparente já que a complexidade com que as mensagens são trocadas não é de fato analisada. Porém notamos que, sistemas monolíticos também podem ser mais robustos. Uma forma de se criar uma versão aprimorada do Linux e mais robusta é uma que lidasse com deadlocks. O próprio livro do Tanenbaum [15] sugere técnicas para destravar um sistema que entrou em deadlock. Por exemplo: uma técnica é semelhante à que foi usada no Minix3 e consiste em pingar um processo para ver se ele responde; removendo-o caso ele não responda. Outra técnica consiste em montar um grafo de processos bloqueados esperando por recursos e observar se existe um ciclo fechado. No caso do Minix, o grafo pode modelar que processo espera mensagem de qual processo.

Outra pergunta é: a queda no desempenho compensa o aumento na robustez? Mesmo que houvesse de fato uma versão mais robusta que lidasse com o loop infinito em drivers de forma mais genérica, ou ainda, uma versão que pudesse detectar e lidar com deadlocks, não acreditamos que a queda de desempenho compensa o aumento da robustez e o argumento é bem simples. Já existem diversas técnicas para se lidar com deadlocks em sistemas operacionais, porém nenhuma dessas técnicas que aumentam a robustez do sistema operacional são utilizadas em sistemas operacionais monolíticos. O sistema operacional mais próximo de tratar de deadlocks que conhecemos é um sistema operacional montado na Escola Politécnica da USP usado em automação ferroviária. Esse sistema pingava os módulos e casos houvesse problemas, restartava todo o sistema. Sistemas operacionais convencionais não tratam de deadlocks porque eles são eventos raros e a queda de desempenho não justifica o aumento da robustez. Então de forma semelhante, consideramos que um possível aumento da robustez decorrente do uso de sistemas microkernel não venha a justificar a queda de desempenho. Isso pode ser útil somente em alguns tipos de sistemas onde a robustez é extremamente importante; mas como observamos nesse artigo, mesmo assim é difícil garantir o aumento da robustez em um sistema microkernel. É interessante observar que dentre os sistemas microkernel encontrados na literatura como Minix, Mach e L4, o L4 (que provém do L3) surgiu com o objetivo de melhorar o desempenho com que as mensagens são trocadas [16]; que é justamente o motivo pelo qual o Minix perde muito em desempenho. O artigo [14] advoga o uso de drivers rodando rodando em modo usuário com o objetivo de aumentar a robustez, mesmo que isso acarrete a perda de desempenho. Encontramos na literatura artigos que apoiam essa decisão, independentemente do sistema ser monolítico ou microkernel. Embora o Minix3 não tenha funcionado como o esperado, acreditamos que, com cuidado, seja possível construir um Minix que de fato funcione como previsto em [14]; porém isso só é válido para o caso dos drivers, não sendo válido para o FS ou o PM. Os drivers não costumam armazenar um bom volume de informações, mas um restart em um FS já é algo bem diferente. O FS armazena a parte da tabela de processos que diz qual arquivo está alocada a qual processo. Parece-nos extremamente complexo restartar o FS levando o sistema para uma situação de normalidade. Um restart no PM também pode ter consequências muito sérias já que ele armazena a informação sobre o uso da memória por parte dos processos. Na literatura, [14] enfatiza o uso de drivers em modo usuário. O argumento é de que a taxa de erros nos drivers é de 3 a 7 vezes mais alta do que o normal. Além disso, 70% do código de um kernel monolítico consiste em drivers. A taxa de erros nos drivers é mais alta, no caso do Windows, porque muitos drivers são escritos pelos fabricantes do hardware e não por uma equipe acostumada a escrever drivers para o Windows XP onde 85% das panes ocorem[8]. O artigo [8] comenta diversos projetos envolvendo os drivers. NOOKS é um projeto para o Linux que encapsula os drivers de forma a

impedir que erros nos drivers se propagem pelo sistema. Existe um projeto para Linux que faz o driver rodar em modo usuário com pequena queda de desempenho, mas ganho em robustez. O artigo [3] propõe uma forma de se rodar drivers no Linux escritos em Java. Ele argumenta que a maioria das panes em um sistema operacional ocorre em drivers e que a linguagem java permite se escrever código de forma mais segura. Assim, diversos trabalhos apontam que drivers rodando em modo usuário são mais robustos. Isso faz sentido, porque retirar um processo com um problema (ex: um loop infinito em um driver) é mais simples de tratar em modo usuário. Observando e testando o Minix3 não podemos afirmar que drivers com código errado são genericamente removidos pelo Reincarnation Server; ou seja, não podemos afirmar que o Minix3 seja tão robusto como é afirmado em [14]. Porém, supondo que a probabilidade de ocorrer um problema em um driver antes de ele responder ao FS seja relativamente baixa, então o Minix3 é de fato mais robusto. O artigo [13] propõe um sistema microkernel e trata das primitivas por ele oferecidas de uma forma matemática. Acreditamos que uma modelagem formal de como os processos interagem entre si pode levar a sistemas mais robustos. O fato de ser microkernel por si só não leva a concluir que o sistema operacional seja mais robusto pois seria necessário garantir que processos vitais (ex: FS e PM), mesmo que não rodando em modo kernel, são robustos. O fato da tabela de processos estar distribuída obriga diversos processos a se comuniquem continuamente. Assim, questionamos diversas afirmações em [8] quanto ao aumento da robustez devido ao microkernel. Uma forma objetiva para advogar em favor de sistemas monolíticos ou microkernel é deixar a argumentação teórica e usar estatística. Para isso, bastaria ter uma especificação de system calls como o padrão POSIX, comparar a taxa de falhas e o desempenho entre todos os sistemas operacionais que implementam o padrão POSIX ao rodarem certos aplicativos. Porém essa medida é difícil, uma vez que os sistemas operacionais não medem "taxa de falhas". No futuro pretendemos criar um medidor de taxa de falhas que seja implementada nos sistemas operacionais Linux e Minix (ambos seguem o POSIX), rodar os mesmos aplicativos em ambas as plataformas e depois comparar essas medidas. Por enquanto, apresentamos apenas um indício de que sistemas operacionais microkernel não implementam system calls de forma muito mais robusta do que sistemas monolíticos. Em relação ao ensino de sistemas operacionais com o Minix, os alunos acreditam ser importante estar em contato com um sistema de código aberto que permite ser estudado. Caso não tivéssemos acesso ao Minix, seria muito difícil observar um sistema microkernel e o quão robusto ele é, apesar da queda de desempenho. Apreciamos o Minix como uma boa ferramenta didática, mas o Minix3 ainda deve ser aprimorado para que possa lidar com falhas genéricas em drivers. REFERÊNCIAS [1]

G. Aguirre, M. Errecalde, R. Guerrero, C. Kavka, G. Leguizamon, M. Printista, and R. Gallard. Experiencing Minix as a didactical aid for operating systems courses. SIGOPS Oper. Syst. Rev., 25(3):32–39, 1991.

[2]

Charles L. Anderson and Minh Nguyen. A survey of contemporary instructional operating systems for use in undergraduate courses. J. Comput. Small Coll., 21(1):183–190, 2005. [3] Shan Chen, Lingling Zhou, Rendong Ying, and Yi Ge. Safe device driver model based on kernel-mode jvm. In VTDC ’07: Proceedings of the 3rd international workshop on Virtualization technology in distributed computing, pages 1–8, New York, NY, USA, 2007. ACM. [4] P. Daquino, W. Leao, and H. Omoto. Problemas em drivers no Minix3. http://www.pcs.usp.br/%jkinoshi/2008/projs/r3-pedrodaquinoRelatorio3.pdf, março 2009. [5] Wenliang Du and Ronghua Wang. Seed: A suite of instructional laboratories for computer security education. J. Educ. Resour. Comput., 8(1):1–24, 2008. [6] Stephen J. Hartley. Experience with Minix in an operating systems lab. SIGCSE Bull., 22(3):34–38, 1990. [7] J. H. Hays. An operating systems course using Minix. SIGCSE Bull., 21(4):11–12, 1989. [8] Jorrit N. Herder, Herbert Bos, Ben Gras, Philip Homburg, and Andrew S. Tanenbaum. Construction of a highly dependable operating system. In EDCC ’06: Proceedings of the Sixth European Dependable Computing Conference, pages 3–12, Washington, DC, USA, 2006. IEEE Computer Society. [9] Jorrit N. Herder, Herbert Bos, Ben Gras, Philip Homburg, and Andrew S. Tanenbaum. Minix 3: a highly reliable, self-repairing operating system. SIGOPS Oper. Syst. Rev., 40(3):80–89, 2006. [10] James Howatt. Operating systems projects: Minix revisited. SIGCSE Bull., 34(4):109–111, 2002. [11] R. A. Mark, P. Daquino, and R. Silva. Driver para o Minix. http://www.pcs.usp.br/jkinoshi/2008/projs/r3-pedrodaquinoRelatorio3.pdf março 2009. [12] N. Sautchuk, P. M. Kayatt, and R. Ruppel. Tame infinite loops. http://www.pcs.usp.br/%jkinoshi/2008/projs/r3-PedroKayatt.doc, março 2009. [13] Artem Starostin and Alexandra Tsyban. Correct microkernel primitives. Electron. Notes Theor. Comput. Sci., 217:169–185, 2008. [14] Andrew S. Tanenbaum, Jorrit N. Herder, and Herbert Bos. Can we make operating systems reliable and secure? Computer, 39(5):44–51, 2006. [15] Andrew S. Tanenbaum and Albert S. Woodhull. Operating Systems Design and Implementation (3rd Edition) (Prentice Hall Software Series). Prentice Hall, January 2006. [16] Liedtke, Jochen. "Improving IPC by kernel design". 14th ACM Symposium on Operating System Principles. Asheville, NC, USA. pp. 175–88, December 1993). Jorge Kinoshita é graduado em Engenharia Elétrica pela Universidade de São Paulo (USP), São Paulo, Brasil, em 1985. Obteve o título de mestre em Engenharia Elétrica pela Universidade de São Paulo em 1991 e de Doutor, em Engenharia Elétrica pela Universidade de São Paulo em 1997. Atualmente é professor da Universidade de São Paulo e suas pesquisas se concentram na área de sistemas operacionais e processamento de linguagem natural. Helio Tadashi Omoto é aluno do curso de Engenharia de Computação na Escola Politécnica da Universidade de São Paulo. Cursou também Engenharia de Computação no Politecnico di Milano, em Milão na Itália. Atualmente trabalha no Grupo Pão de Açucar como Trainee.

Pedro d’Aquino F. F. de Sá Barbuda recebeu o título de Engenheiro de Computação pela Escola Politécnica da Universidade de São Paulo (EPUSP) em 2009. Atualmente é aluno de Mestrado em Engenharia de Computação na mesma instituição. Suas áreas de interesse são sistemas operacionais, localização e mapeamento robótico e visão computacional. Wilson Leão Neto atualmente é aluno de Engenheira de Computação na Escola Politécnica da Universidade de São Paulo (EPUSP), previsão de formatura abril de 2011. Realizou um aproveitamento de créditos no Politecnico di Milano Itália (2008-2009). Suas áreas de interesse são sistemas operacionais, pesquisa operacional, inteligência artificial e sistemas de decisão.