So Exercicios a5

Sistemas Operacionais: Conceitos eMecanismos

Caderno de Exerccios

Prof. Carlos A. Maziero, Dr.DAINF UTFPR

2 de maio de 2014

Sistemas Operacionais: Conceitos e Mecanismosc Carlos Alberto Maziero, 2013

Sobre o autor: Carlos Alberto Maziero professor adjunto do DepartamentoAcadmico de Informtica da Universidade Tecnolgica Federal do Paran(UTFPR) desde julho de 2011. Anteriormente, foi professor titular doPrograma de Ps-Graduao em Informtica da Pontifcia UniversidadeCatlica do Paran (PUCPR), entre 1998 e 2011, e professor adjunto doDepartamento de Automao e Sistemas da Universidade Federal de SantaCatarina (UFSC), de 1996 a 1998. Formado em Engenharia Eltrica (UFSC,1988), tem Mestrado em Engenharia Eltrica (UFSC, 1990), Doutorado emInformtica (Universit de Rennes I - Frana, 1994) e Ps-Doutorado emSegurana da Informao (Universit degli Studi di Milano Italia, 2009).Tem atuao em pesquisa nas reas de sistemas operacionais, segurana desistemas e sistemas distribudos.

Este texto est licenciado sob a Licena Attribution-NonCommercial-ShareAlike 3.0 Unported da CreativeCommons (CC). Em resumo, voc deve creditar aobra da forma especificada pelo autor ou licenciante

(mas no de maneira que sugira que estes concedem qualquer aval avoc ou ao seu uso da obra). Voc no pode usar esta obra para finscomerciais. Se voc alterar, transformar ou criar com base nesta obra, vocpoder distribuir a obra resultante apenas sob a mesma licena, ou sobuma licena similar presente. Para ver uma cpia desta licena, visitehttp://creativecommons.org/licenses/by-nc-sa/3.0/.

Este texto foi produzido usando exclusivamente software livre: SistemaOperacional GNU/Linux (distribuies Fedora e Ubuntu), compilador de textoLATEX 2, gerenciador de referncias BibTeX, editor grfico Inkscape, criadoresde grficos GNUPlot e GraphViz e processador PS/PDF GhostScript, entreoutros.

Sumrio

1 Conceitos bsicos 3

2 Gerncia de atividades 8

3 Comunicao entre tarefas 15

4 Coordenao entre tarefas 20

5 Gerncia de memria 30

6 Gerncia de arquivos 39

7 Gerncia de entrada/sada 46

8 Segurana de sistemas 47

2

Captulo 1

Conceitos bsicos

1. Quais os dois principais objetivos dos sistemas operacionais?

2. Por que a abstrao de recursos importante para os desenvolvedoresde aplicaes? Ela tem utilidade para os desenvolvedores do prpriosistema operacional?

3. A gerncia de atividades permite compartilhar o processador, exe-cutando mais de uma aplicao ao mesmo tempo. Identifique asprincipais vantagens trazidas por essa funcionalidade e os desafios aresolver para implement-la.

4. O que caracteriza um sistema operacional de tempo real? Quais asduas classificaes de sistemas operacionais de tempo real e suasdiferenas?

5. O que diferencia o ncleo do restante do sistema operacional?

6. Seria possvel construir um sistema operacional seguro usando umprocessador que no tenha nveis de privilgio? Por qu?

7. O processador Pentium possui dois bits para definir o nvel de pri-vilgio, resultando em 4 nveis distintos. A maioria dos sistemasoperacionais para esse processador usa somente os nveis extremos (0e 3, ou 002 e 112). Haveria alguma utilidade para os nveis intermedi-rios?

8. Quais as diferenas entre interrupes, excees e traps?

3

4 cCarlos Maziero 1: Conceitos bsicos

9. Quais as implicaes de mascarar interrupes? O que pode ocorrer seo processador ignorar interrupes por muito tempo? O que poderiaser feito para evitar o mascaramento de interrupes?

10. O comando em linguagem C fopen uma chamada de sistema ouuma funo de biblioteca? Por qu?

11. Monte uma tabela com os benefcios e deficincias mais significativosdas principais arquiteturas de sistemas operacionais.

12. Relacione as afirmaes aos respectivos tipos de sistemas operacio-nais: distribudo (D), multi-usurio (M), desktop (K), servidor (S),embarcado (E) ou de tempo-real (T):

[ ] Deve ter um comportamento temporal previsvel, com prazos deresposta claramente definidos.

[ ] Sistema operacional usado por uma empresa para executar seubanco de dados corporativo.

[ ] So tipicamente usados em telefones celulares e sistemas eletr-nicos dedicados.

[ ] Neste tipo de sistema, a localizao fsica dos recursos do sistemacomputacional transparente para os usurios.

[ ] Todos os recursos do sistema tm proprietrios e existem regrascontrolando o acesso aos mesmos pelos usurios.

[ ] A gerncia de energia muito importante neste tipo de sistema.

[ ] Sistema que prioriza a gerncia da interface grfica e a interaocom o usurio.

[ ] Construdo para gerenciar de forma eficiente grandes volumesde recursos.

[ ] O MacOS X um exemplo tpico deste tipo de sistema.

[ ] So sistemas operacionais compactos, construdos para executaraplicaes especficas sobre plataformas com poucos recursos.

13. A operao em modo usurio permite ao processador executar somenteparte das instrues disponveis em seu conjunto de instrues. Quaisdas seguintes operaes no deveriam ser permitidas em nvel usurio?Por qu?

4


(a) Ler uma porta de entrada/sada

(b) Efetuar uma diviso inteira

(c) Escrever um valor em uma posio de memria

(d) Ajustar o valor do relgio do hardware

(e) Ler o valor dos registradores do processador

(f) Mascarar uma ou mais interrupes

14. Considerando um processo em um sistema operacional com proteode memria entre o ncleo e as aplicaes, indique quais das seguintesaes do processo teriam de ser realizadas atravs de chamadas desistema, justificando suas respostas:

(a) Ler o relgio de tempo real do hardware.

(b) Enviar um pacote atravs da rede.

(c) Calcular uma exponenciao.

(d) Preencher uma rea de memria do processo com zeros.

(e) Remover um arquivo do disco.

15. Coloque na ordem correta as aes abaixo, que ocorrem durante a exe-cuo da funo printf("Hello world") por um processo (observeque nem todas as aes indicadas fazem parte da seqncia).

[ ] A rotina de tratamento da interrupo de software ativadadentro do ncleo.

[ ] A funo printf finaliza sua execuo e devolve o controle aocdigo do processo.

[ ] A funo de biblioteca printf recebe e processa os parmetrosde entrada (a string Hello world).

[ ] A funo de biblioteca printf prepara os registradores parasolicitar a chamada de sistema write()

[ ] O disco rgido gera uma interrupo indicando a concluso daoperao.

[ ] O escalonador escolhe o processo mais prioritrio para execuo.

[ ] Uma interrupo de software acionada.

5


[ ] O processo chama a funo printf da biblioteca C.

[ ] A operao de escrita no terminal efetuada ou agendada pelarotina de tratamento da interrupo.

[ ] O controle volta para a funo printf em modo usurio.

16. Considere as afirmaes a seguir, relativas aos diversos tipos desistemas operacionais:

I. Em um sistema operacional de tempo real, a rapidez de resposta menos importante que a previsibilidade do tempo de resposta.

II. Um sistema operacional multi-usurios associa um proprietrioa cada recurso do sistema e gerencia as permisses de acesso aesses recursos.

III. Nos sistemas operacionais de rede a localizao dos recursos transparente para os usurios.

IV. Um sistema operacional de tempo real deve priorizar as tarefasque interagem com o usurio.

V. Um sistema operacional embarcado projetado para operar emhardware com poucos recursos.

Indique a alternativa correta:

(a) As afirmaes II e III esto corretas.

(b) Apenas a afirmao V est correta.

(c) As afirmaes III e IV esto erradas.

(d) As afirmaes III, IV e V esto erradas.

(e) Todas as afirmaes esto erradas.

Justifique as afirmaes julgadas erradas (Assim: VII est errada porque...):

17. Considere as afirmaes a seguir, relativas s diversas arquiteturas desistemas operacionais:

I. Uma mquina virtual de sistema contruda para suportar umaaplicao escrita em uma linguagem de programao especfica,como Java.

6


II. Um hipervisor convidado executa sobre um sistema operacionalhospedeiro.

III. Em um sistema operacional micro-ncleo, os diversos componen-tes do sistema so construdos como mdulos interconectadosexecutando dentro do ncleo.

IV. Ncleos monolticos so muito utilizados devido sua robusteze facilidade de manuteno.

V. Em um sistema operacional micro-ncleo, as chamadas de sistemaso implementadas atravs de trocas de mensagens.


(a) Todas as afirmaes esto erradas.

(b) As afirmaes II e III esto corretas.

(c) As afirmaes II e IV esto erradas.

(d) Apenas a afirmao V est correta.

(e) As afirmaes II e V esto corretas.


18. O utilitriostracedo UNIX permite observar a sequncia de chamadasde sistema efetuadas por uma aplicao. Em um terminal UNIX,execute strace date para descobrir quais os arquivos abertos pelaexecuo do utilitrio date (que indica a data e hora correntes). Porque o utilitrio date precisa fazer chamadas de sistema?

19. O utilitrioltracedo UNIX permite observar a sequncia de chamadasde biblioteca efetuadas por uma aplicao. Em um terminal UNIX,execute ltrace datepara descobrir as funes de biblioteca chamadaspela execuo do utilitrio date (que indica a data e hora correntes).Pode ser observada alguma relao entre as chamadas de biblioteca eas chamadas de sistema observadas no tem anterior?

7

Captulo 2

Gerncia de atividades

1. Explique o que , para que serve e o que contm um PCB - ProcessControl Block.

2. O que significa time sharing e qual a sua importncia em um sistemaoperacional?

3. Como e com base em que critrios escolhida a durao de um quantumde processamento?

4. Considerando o diagrama de estados dos processos apresentado nafigura a seguir, complete o diagrama com a transio de estado queest faltando (t6) e apresente o significado de cada um dos estados etransies.

e2

e1 e3 e4

e5

t1t2

t3t4t5

5. Indique se cada uma das transies de estado de tarefas a seguirdefinidas possvel ou no. Se a transio for possvel, d um exemplode situao na qual ela ocorre (N: Nova, P: pronta, E: executando, S:suspensa, T: terminada).

8

9 cCarlos Maziero 2: Gerncia de atividades

E P E S S E P N S T E T N S P S

6. Relacione as afirmaes abaixo aos respectivos estados no ciclo devida das tarefas (N: Nova, P: Pronta, E: Executando, S: Suspensa, T:Terminada):

[ ] O cdigo da tarefa est sendo carregado.

[ ] A tarefas so ordenadas por prioridades.

[ ] A tarefa sai deste estado ao solicitar uma operao de entrada/-sada.

[ ] Os recursos usados pela tarefa so devolvidos ao sistema.

[ ] A tarefa vai a este estado ao terminar seu quantum.

[ ] A tarefa s precisa do processador para poder executar.

[ ] O acesso a um semforo em uso pode levar a tarefa a este estado.

[ ] A tarefa pode criar novas tarefas.

[ ] H uma tarefa neste estado para cada processador do sistema.

[ ] A tarefa aguarda a ocorrncia de um evento externo.

7. Desenhe o diagrama de tempo da execuo do cdigo a seguir, informequal a sada do programa na tela (com os valores de x) e calcule adurao aproximada de sua execuo.

1 int main()2 {3 int x = 0 ;4

5 fork () ;6 x++ ;

9


7 sleep (5) ;8 wait (0) ;9 fork () ;

10 wait (0) ;11 sleep (5) ;12 x++ ;13 printf ("Valor de x: %d\n", x) ;14 }

8. Indique quantas letras X sero impressas na tela pelo programaabaixo quando for executado com a seguinte linha de comando:

a.out 4 3 2 1

Observaes:

a.out o arquivo executvel resultante da compilao do pro-grama.

A chamada de sistema fork cria um processo filho, clone doprocesso que a executou, retornando o valor zero no processofilho e um valor diferente de zero no processo pai.

1 #include 2 #include 3 #include 4 #include 5

6 int main(int argc, char *argv[])7 {8 pid_t pid[10];9 int i;

10

11 int N = atoi(argv[argc-2]);12

13 for (i=0; i


9. O que so threads e para que servem?

10. Quais as principais vantagens e desvantagens de threads em relao aprocessos?

11. Fornea dois exemplos de problemas cuja implementao multi-threadno tem desempenho melhor que a respectiva implementao sequen-cial.

12. Associe as afirmaes a seguir aos seguintes modelos de threads: a)many-to-one (N:1); b) one-to-one (1:1); c) many-to-many (N:M):

[ ] Tem a implementao mais simples, leve e eficiente.

[ ] Multiplexa os threads de usurio em um pool de threads de ncleo.

[ ] Pode impor uma carga muito pesada ao ncleo.

[ ] No permite explorar a presena de vrias CPUs pelo mesmoprocesso.

[ ] Permite uma maior concorrncia sem impor muita carga aoncleo.

[ ] Geralmente implementado por bibliotecas.

[ ] o modelo implementado no Windows NT e seus sucessores.

[ ] Se um thread bloquear, todos os demais tm de esperar por ele.

[ ] Cada thread no nvel do usurio tem sua correspondente dentrodo ncleo.

[ ] o modelo com implementao mais complexa.

13. Considerando as implementaes de threads N:1 e 1:1 para o trecho decdigo a seguir, a) desenhe os diagramas de execuo, b) informe asduraes aproximadas de execuo e c) indique a sada do programana tela. Considere a operao sleep() como uma chamada de sistema(syscall).

Significado das operaes:

thread_create: cria uma nova thread, pronta para executar. thread_join: espera o encerramento da thread informada como

parmetro.

11


thread_exit: encerra a thread corrente.

1 int y = 0 ;2

3 void threadBody4 {5 int x = 0 ;6 sleep (10) ;7 printf ("x: %d, y:%d\n", ++x, ++y) ;8 thread_exit();9 }

10

11 main ()12 {13 thread_create (&tA, threadBody, ...) ;14 thread_create (&tB, threadBody, ...) ;15 sleep (1) ;16 thread_join (&tA) ;17 thread_join (&tB) ;18 sleep (1) ;19 thread_create (&tC, threadBody, ...) ;20 thread_join (&tC) ;21 }

14. Explique o que escalonamento round-robin, dando um exemplo.

15. Considere um sistema de tempo compartilhado com valor de quantumtq e durao da troca de contexto ttc. Considere tarefas de entrada/sadaque usam em mdia p% de seu quantum de tempo cada vez querecebem o processador. Defina a eficincia E do sistema como umafuno dos parmetros tq, ttc e p.

16. Explique o que , para que serve e como funciona a tcnica de aging.

17. A tabela a seguir representa um conjunto de tarefas prontas parautilizar um processador:

Tarefa t1 t2 t3 t4 t5ingresso 0 0 3 5 7durao 5 4 5 6 4prioridade 2 3 5 9 6

12


Indique a seqncia de execuo das tarefas, o tempo mdio de vida(tournaround time) e o tempo mdio de espera (waiting time), para aspolticas de escalonamento a seguir:

(a) FCFS cooperativa

(b) SJF cooperativa

(c) SJF preemptiva (SRTF)

(d) PRIO cooperativa

(e) PRIO preemptiva

(f) RR com tq = 2, sem envelhecimento

Consideraes: todas as tarefas so orientadas a processamento; astrocas de contexto tm durao nula; em eventuais empates (idade,prioridade, durao, etc), a tarefa ti com menor i prevalece; valoresmaiores de prioridade indicam maior prioridade.

Para representar a sequncia de execuo das tarefas use o diagramaa seguir. Use para indicar uma tarefa usando o processador, para uma tarefa em espera na fila de prontos e para uma tarefa queainda no iniciou ou j concluiu sua execuo.

0 5 10 15 20

t1t2t3t4t5

t

18. Idem, para as tarefas da tabela a seguir:

Tarefa t1 t2 t3 t4 t5ingresso 0 0 1 7 11durao 5 6 2 6 4prioridade 2 3 4 7 9

19. Explique os conceitos de inverso e herana de prioridade.

13


20. Voc deve analisar o software da sonda Mars Pathfinder discutido nolivro-texto. O sistema usa escalonamento por prioridades preemptivo,sem envelhecimento e sem compartilhamento de tempo. Suponha queas tarefas tg e tm detm a rea de transferncia de dados durante todoo perodo em que executam. Os dados de um trecho de execuo dastarefas so indicados na tabela a seguir (observe que tg executa maisde uma vez).

Tarefa tg tm tcingresso 0, 5, 10 2 3durao 1 2 10prioridade alta baixa mdia

Desenhe o diagrama de tempo da execuo sem e com o protocolo deherana de prioridades e discuta sobre as diferenas observadas entreas duas execues.

14

Captulo 3

Comunicao entre tarefas

1. Quais so as vantagens e desvantagens das abordagens a seguir, sobas ticas do sistema operacional e do programador de aplicativos?

(a) comunicao bloqueante ou no-bloqueante(b) canais com buffering ou sem buffering(c) comunicao por mensagens ou por fluxo(d) mensagens de tamanho fixo ou varivel(e) comunicao 1:1 ou M:N

2. Explique como processos que comunicam por troca de mensagensse comportam em relao capacidade do canal de comunicao,considerando as semnticas de chamada sncrona e assncrona.

3. Em relao sincronizao na comunicao entre processos, podemosafirmar que:

I. Na comunicao semi-bloqueante, o emissor espera indefinida-mente pela possibilidade de enviar os dados.

II. Na comunicao sncrona ou bloqueante, o receptor espera atreceber a mensagem.

III. Um mecanismo de comunicao semi-bloqueante com prazot = equivale a um mecanismo bloqueante.

IV. Na comunicao sncrona ou bloqueante, o emissor retorna umamensagem de erro caso o receptor no esteja pronto para recebera mensagem.

15

16 cCarlos Maziero 3: Comunicao entre tarefas

V. A comunicao com semntica bloqueante usando canais sembuffer chamada Rendez-Vous.

As asseres corretas so:

(a) I, III

(b) II, III, V

(c) I, II, IV

(d) II, III

(e) III, IV, V


4. Em relao sincronizao na comunicao entre processos, podemosafirmar que:

I. Na comunicao semi-bloqueante, o emissor espera pelo enviodos dados, mas o receptor no.

II. Se o canal de comunicao tiver capacidade nula, emissor ereceptor devem usar mecanismos no-bloqueantes.

III. A comunicao no-bloqueante em ambos os participantes s vivel usando canais de comunicao com buffer no-nulo.

IV. Os pipes do UNIX so um bom exemplo de comunicao bloque-ante.

V. Um mecanismo de comunicao semi-bloqueante com prazo t = 0equivale a um mecanismo bloqueante.


(a) I, II, IV

(b) II, III

(c) III, IV, V

(d) I, IV

(e) III, IV

16



5. Dadas as seguintes caractersticas dos mecanismos de comunicao:

I. A comunicao indireta (por canais) mais adequada para siste-mas distribudos.

II. Canais com capacidade finita somente so usados na definiode algoritmos, no sendo implementveis na prtica.

III. Na comunicao direta, o emissor envia os dados diretamente aum canal de comunicao.

IV. Na comunicao por fluxo, a ordem dos dados enviados peloemissor mantida do lado receptor.

V. Na comunicao por troca de mensagens, o ncleo transferepacotes de dados do processo emissor para o processo receptor.

As asseres erradas so:

(a) II, III

(b) I, III

(c) II, IV

(d) III, V

(e) I, IV



I. Na comunicao por troca de mensagens, o processo emissorcopia o contedo da mensagem no buffer do processo receptor.

II. O buffer do canal de comunicao entre dois processos distintos geralmente mantido pelo ncleo do sistema operacional.

III. Se a capacidade do buffer do canal de comunicao for consideradainfinita, somente o receptor pode se bloquear.

17


IV. As filas de mensagens POSIX so um exemplo de canal decomunicao com capacidade nula.

V. O protocolo de rede TCP um exemplo de comunicao por fluxode dados.

As asseres erradas so:

(a) I, III

(b) II, III

(c) I, IV

(d) II, IV

(e) II, V



I. A memria compartilhada prov mecanismos de sincronizaopara facilitar a comunicao entre os processos.

II. A troca de dados atravs de memria compartilhada maisadequada para a comunicao em rede.

III. Processos que se comunicam por memria compartilhada podemacessar a mesma rea da RAM.

IV. Os pipes Unix so um bom exemplo de comunicao M:N.

V. A comunicao atravs de memria compartilhada particular-mente indicada para compartilhar grandes volumes de dadosentre dois ou mais processos.


(a) I, III, V

(b) I, II

(c) III, IV

(d) II, IV

18


(e) III, V



I. Em um mecanismo de mailbox, cada mensagem enviada repli-cada a todos os receptores.

II. Em um canal de eventos, as mensagens enviadas so distribudasalternadamente entre os receptores.

III. As filas de mensagens POSIX so um bom exemplo de canal deeventos.

IV. Nas filas de mensagens POSIX, as mensagens transitam atravsde arquivos em disco criados especialmente para essa finalidade.

V. Em UNIX, um pipe um canal de comunicao unidirecional queliga a sada padro de um processo entrada padro de outro.


(a) I, III

(b) II

(c) III, IV

(d) V

(e) nenhuma delas


19

Captulo 4

Coordenao entre tarefas

1. Explique o que so condies de disputa, mostrando um exemplo real.

2. Em relao aos mecanismos de coordenao:

I. A estratgia de inibir interrupes para evitar condies dedisputa funciona em sistemas multi-processados.

II. Os mecanismos de controle de entrada nas regies crticas pro-vem excluso mtua no acesso s mesmas.

III. Os algoritmos de busy-wait se baseiam no teste contnuo de umacondio.

IV. Condies de disputa ocorrem devido s diferenas de velocidadena execuo dos processos.

V. Condies de disputa ocorrem quando dois processos tentamexecutar o mesmo cdigo ao mesmo tempo.


(a) I, III

(b) II, V

(c) II, III

(d) I, IV

(e) IV, V

20

21 cCarlos Maziero 4: Coordenao entre tarefas


3. Explique o que espera ocupada e por que os mecanismos que empregamessa tcnica so considerados ineficientes.

4. Em que circunstncias o uso de espera ocupada inevitvel?

5. Em relao aos mecanismos de coordenao:

I. Instrues do tipo Test&Set Lock devem ser implementadas peloncleo do SO.

II. O algoritmo de Peterson garante justia no acesso regio crtica.

III. Os algoritmos com estratgia busy-wait otimizam o uso da CPUdo sistema.

IV. Uma forma eficiente de resolver os problemas de condio dedisputa introduzir pequenos atrasos nos processos envolvidos.

V. Um semforo composto por um contador inteiro e uma fila deprocessos suspensos.


(a) I, III

(b) I, V

(c) II, V

(d) I, IV

(e) III, IV


6. Considere ocupado uma varivel inteira compartilhada entre doisprocessos A e B (inicialmente, ocupado = 0). Sendo que ambos osprocessos executam o trecho de programa abaixo, explique em quesituao A e B poderiam entrar simultaneamente nas suas respectivasregies crticas.

21


1 while (true) {2 regiao_nao_critica();3 while (ocupado) {};4 ocupado = 1;5 regiao_critica();6 ocupado = 0;7 }

7. Em que situaes um semforo deve ser inicializado em 0, 1 ou n > 1?

8. Por que no existem operaes read(s) e write(s) para ler ou ajustar ovalor corrente de um semforo?

9. Mostre como pode ocorrer violao da condio de excluso mtua seas operaes down(s) e up(s) sobre semforos no forem implementadasde forma atmica.

10. A implementao das operaes down(s) e up(s) sobre semforos deveser atmica, para evitar condies de disputa sobre as variveis internasdo semforo. Escreva, em pseudo-cdigo, a implementao dessasduas operaes, usando instrues TSL para evitar as condies dedisputa. A estrutura interna do semforo indicada a seguir. No necessrio detalhar as operaes de ponteiros envolvendo a filatask_queue.

1 struct semaphore2 {3 int lock = false ;4 int count ;5 task_t *queue ;6 }

11. Usando semforos, escreva o pseudo-cdigo de um sistema pro-dutor/consumidor com dois buffers limitados organizado na formaX B1 Y B2 Z, onde X, Y e Z so tipos de processos e B1 e B2so buffers independentes com capacidades N1 e N2, respectivamente,inicialmente vazios. Os buffers so acessados unicamente atravsdas operaes insere(Bi, item) e retira(Bi, item) (que no precisam serdetalhadas). O nmero de processos X, Y e Z desconhecido.

Devem ser definidos os cdigos dos processos X, Y e Z e os semforosnecessrios, com seus significados e valores iniciais.

22


12. O trecho de cdigo a seguir apresenta uma soluo para o problemado jantar dos filsofos, mas ele contm um erro. Explique o cdigo eexplique onde est o erro e porque ele ocorre. A seguir, modifique ocdigo para que ele funcione corretamente.

1 #define N 52

3 sem_t garfo[5] ; // 5 semforos iniciados em 14

5 void filosofo (int i)6 {7 while (1)8 {9 medita ();

10 sem_down (garfo [i]) ;11 sem_down (garfo [(i+1) % N]) ;12 come ();13 sem_up (garfo [i]) ;14 sem_up (garfo [(i+1) % N]) ;15 }16 }

13. Suponha trs robs (Bart, Lisa, Maggie), cada um controlado por suaprpria thread. Voc deve escrever o cdigo das threads de controle,usando semforos para garantir que os robs se movam sempre nasequncia Bart LisaMaggie Lisa Bart LisaMaggie , um rob de cada vez. Use a chamada move() para indicar ummovimento do rob. No esquea de definir os valores iniciais dasvariveis e/ou dos semforos utilizados. Solues envolvendo esperaocupada (busy wait) no devem ser usadas.

14. O Rendez-Vous um operador de sincronizao forte entre dois pro-cessos ou threads, no qual um deles espera at que ambos cheguemao ponto de encontro (rendez-vous, em francs). O exemplo a seguirilustra seu uso:

Processo AA1 () ;rv_wait (rv) ;A2 () ;rv_wait (rv) ;A3 () ;

Processo BB1 () ;rv_wait (rv) ;B2 () ;rv_wait (rv) ;B3 () ;

23


Considerando a relao a b como a ocorre antes de b e a relaoa b como a e b ocorrem sem uma ordem definida, temos as seguintesrestries de sincronizao:

(i, j),Ai B j>i e Bi A j>i (imposto pelo Rendez-Vous) (i, j),Ai A j>i e Bi B j>i (imposto pela execuo sequencial) (i, j),Ai B j=i (possibilidade de execuo concorrente)

Escreva o pseudo-cdigo necessrio para implementar Rendez-Vous,usando semforos ou mutexes. No esquea de inicializar as variveise semforos utilizados. Solues que incorram em espera ocupada(busy wait) no sero aceitas.

1 // estrutura que representa um RV2 typedef struct rv_t3 {4 ... // completar5 } rv_t ;6

7 // operador de espera no RV8 void rv_wait (rv_t *rv)9 {

10 ... // completar11 }12

13 // inicializao do RV14 void rv_init (rv_t *rv)15 {16 ... // completar17 }

15. Uma Barreira um operador de sincronizao forte entre N processosou threads, no qual eles esperam at que todos cheguem barreira. Oexemplo a seguir ilustra seu uso:

24


Processo AA1 () ;barrier_wait (b) ;A2 () ;barrier_wait (b) ;A3 () ;

Processo BB1 () ;barrier_wait (b) ;B2 () ;barrier_wait (b) ;B3 () ;

Processo CC1 () ;barrier_wait (b) ;C2 () ;barrier_wait (b) ;C3 () ;

Processo DD1 () ;barrier_wait (b) ;D2 () ;barrier_wait (b) ;D3 () ;

Considerando a relao a b como a ocorre antes de b e a relaoa b como a e b ocorrem sem uma ordem definida, temos as seguintesrestries de sincronizao:

(i, j),X , Y,Xi Y j>i (imposto pela barreira) (i, j),Xi X j>i (imposto pela execuo sequencial) (i, j),X , Y,Xi Y j=i (possibilidade de execuo concorrente)

Escreva o pseudo-cdigo necessrio para implementar barreiras paraN processos, usando semforos ou mutexes. No esquea de inicializaras variveis e semforos utilizados. Solues que incorram em esperaocupada (busy wait) no sero aceitas.

1 // estrutura que representa uma barreira2 typedef struct barrier_t3 {4 ... // completar5 } barrier_t ;6

7 // operador de espera no RV8 void barrier_wait (barrier_t *barrier)9 {

10 ... // completar11 }12

13 // inicializao de barreira para N processos14 void barrier_init (barrier_t *barrier, int N)15 {

25


16 ... // completar17 }

16. Implemente uma soluo em C para o problema do produtor/consu-midor, usando threads e semforos no padro POSIX.

17. Implemente uma soluo em C para o problema do produtor/consu-midor, usando threads e variveis de condio no padro POSIX.

18. Implemente uma soluo em C para o problema dos leitores/escritorescom priorizao para escritores, usando threads e semforos POSIX.

19. Implemente uma soluo em C para o problema dos leitores/escritorescom priorizao para escritores, usando threads e rwlocks POSIX.

20. Explique cada uma das quatro condies necessrias para a ocorrnciade impasses.

21. Na preveno de impasses:

(a) Como pode ser feita a quebra da condio de posse e espera?

(b) Como pode ser feita a quebra da condio de excluso mtua?

(c) Como pode ser feita a quebra da condio de espera circular?

(d) Como pode ser feita a quebra da condio de no-preempo?

22. Como pode ser detectada a ocorrncia de impasses, considerandodisponvel apenas um recurso de cada tipo?

23. Uma vez detectado um impasse, quais as abordagens possveis pararesolv-lo? Explique-as e comente sua viabilidade.

24. Em relao aos impasses:

I. As condies necessrias para a ocorrncia de impasses so:excluso mtua, posse e espera, no-preempo e espera circular.

II. A condio de no-preempo indica que os processos envolvidosno impasse devem ser escalonados de forma no-preemptiva.

III. A condio de no-preempo pode ser detectada graficamente,no grafo de alocao de recursos.

26


IV. A deteco e recuperao de impasses bastante usada, pois astcnicas de recuperao so facilmente aplicveis.

V. A condio de excluso mtua pode ser quebrada atravs do usode processos gerenciadores de recursos ou de reas de spool.


(a) II

(b) I, V

(c) I, III

(d) III, IV

(e) II, V



I. A quebra da condio de no-preempo s pode ser aplicada arecursos simples como arquivos e semforos.

II. A quebra da condio de posse e espera consiste em forar todosos processos a solicitar seus recursos em uma ordem global nicae pr-fixada.

III. As condies necessrias para a ocorrncia de impasses sotambm suficientes se houver somente um recurso de cada tipono conjunto de processos considerado.

IV. A resoluo de impasses atravs de rollback s pode ser imple-mentada em processos que executem I/O ou interao com ousurio.

V. Uma vez detectado um impasse, ele pode ser facilmente resolvidoatravs da preempo dos recursos envolvidos.


(a) III, V

(b) I

27


(c) I, V

(d) III

(e) II, IV



I. Impasses ocorrem porque vrios processos tentam usar o proces-sador ao mesmo tempo.

II. O algoritmo de deteco de impasses deve ser executado coma maior freqncia possvel, a fim de evitar que um impasse jformado se alastre.

III. O principal problema com a quebra da condio de posse e espera que a taxa de uso dos recursos pode se tornar bastante baixa.

IV. Os sistemas operacionais atuais provem vrios recursos de baixonvel para o tratamento de impasses.

V. Podemos encontrar impasses em sistemas de processos queinteragem unicamente por mensagens.


(a) I, II

(b) II

(c) III, V

(d) V

(e) III, IV


27. Nos grafos de alocao de recursos da figura a seguir, indique o(s)ciclo(s) onde existe um impasse:

28


t1 t2

r1

r2

r3

r4t3

t4

(a)

t1

t2

r1

r2r3

(b)

28. A figura a seguir representa uma situao de impasse em um cruza-mento de trnsito. Todas as ruas tm largura para um carro e sentidonico. Mostre que as quatro condies necessrias para a ocorrnciade impasses esto presentes nessa situao. Em seguida, defina umaregra simples a ser seguida por cada carro para evitar essa situao;regras envolvendo algum tipo de informao centralizada no devemser usadas.

29

Captulo 5

Gerncia de memria

1. Explique a diferena entre endereos lgicos e endereos fsicos e asrazes que justificam seu uso.

2. Explique em que consiste a resoluo de endereos nos seguintesmomentos: codificao, compilao, ligao, carga e execuo.

3. Como organizado o espao de memria de um processo?

4. O que uma MMU Memory Management Unit?

5. Seria possvel e/ou vivel implementar as converses de endereosrealizadas pela MMU em software, ao invs de usar um hardwarededicado? Por que?

6. Analise as seguintes afirmaes relativas ao uso da memria RAMpelos processos:

I. Os endereos fsicos gerados pelo processador so convertidosem endereos lgicos atravs da MMU - Memory ManagementUnit.

II. O acesso a endereos de memria invlidos notificado aoprocessador atravs de interrupes geradas pela MMU.

III. A rea de memria TEXT contm o cdigo-fonte a ser compiladoe executado pelo processo.

IV. A rea de memria DATA usada para armazenar todas as vari-veis e constantes usadas pelo processo.

30

31 cCarlos Maziero 5: Gerncia de memria

V. A rea de memria HEAP usada para as alocaes dinmicas dememria, sendo usada atravs de funes como malloc e free.

VI. A rea de memria STACK contm as pilhas do programa principale das demais threads do processo.


(a) As afirmaes II e III esto corretas.

(b) As afirmaes I e V esto corretas.

(c) Apenas a afirmao III est correta.

(d) As afirmaes II e V esto corretas.

(e) As afirmaes IV e VI esto corretas.

Justifique as afirmaes julgadas erradas (Assim: XIV est errada porque...):

7. Explique as principais formas de alocao de memria.

8. Explique como feita a translao entre endereos lgicos e fsicose o mecanismo de tratamento de falta de pgina em um sistema dememria virtual paginada.

9. Por que os tamanhos de pginas e quadros so sempre potncias de 2?

10. Analise as seguintes afirmaes relativas s tcnicas de alocao dememria:

I. Na alocao em parties fixas, a MMU composta basicamentede um registrador e um somador.

II. Na alocao contgua, a rea de memria acessvel a cada processo definida por um registrador base e um registrador limite.

III. A tcnica de alocao contgua imune a problemas de fragmen-tao externa.

IV. A alocao por segmentos resolve o problema da fragmentaoexterna.

V. Na alocao por segmentos, cada endereo de memria com-posto de duas partes: segmento e deslocamento.

31


VI. A alocao por pginas resolve o problema da fragmentaoexterna.


(a) As afirmaes II, III e VI esto corretas.

(b) As afirmaes I, II, V e VI esto corretas.

(c) Apenas a afirmao V est correta.

(d) As afirmaes IV e VI esto corretas.

(e) Todas as afirmaes esto corretas.


11. Considerando a tabela de segmentos abaixo (com valores em decimal),calcule os endereos fsicos correspondentes aos endereos lgicos0:45, 1:100, 2:90, 3:1.900 e 4:200.

Segmento 0 1 2 3 4Base 44 200 0 2.000 1.200Limite 810 200 1.000 1.000 410

12. Considerando a tabela de pginas abaixo, com pginas de 500 bytes1,informe os endereos fsicos correspondentes aos endereos lgicos414, 741, 1.995, 4.000 e 6.633, indicados em decimal.

pgina 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15quadro 3 12 6 9 2 0 5 7 1

13. Considere um sistema com endereos fsicos e lgicos de 32 bits, queusa tabelas de pginas com trs nveis. Cada nvel de tabela de pginasusa 7 bits do endereo lgico, sendo os restantes usados para o offset.Cada entrada das tabelas de pginas ocupa 32 bits. Calcule, indicandoseu raciocnio:

1Um tamanho de pgina de 500 bytes permite fazer os clculos mentalmente, sem anecessidade de converter os endereos para binrio e vice-versa, bastando usar divisesinteiras (com resto) entre os endereos e o tamanho de pgina.

32


(a) O tamanho das pginas e quadros, em bytes.

(b) O tamanho mximo de memria que um processo pode ter, embytes e pginas.

(c) O espao ocupado pela tabela de pginas para um processo comapenas uma pgina de cdigo, uma pgina de dados e umapgina de pilha. As pginas de cdigo e de dados se encontramno inicio do espao de endereamento lgico, enquanto a pilhase encontra no final do mesmo.

(d) Idem, caso todas as pginas do processo estejam mapeadas namemria.

14. Analise as seguintes afirmaes relativas alocao paginada:

I. Um endereo lgico com N bits dividido em P bits para onmero de pgina e N P bits para o deslocamento em cadapgina.

II. As tabelas de pginas multinveis permitem mais rapidez naconverso de endereos lgicos em fsicos.

III. O bit de referncia R associado a cada pgina ligado pelaMMU sempre que a pgina acessada.

IV. O cache TLB usado para manter pginas frequentemente usadasna memria.

V. O bit de modificao M associado a cada pgina ligado peloncleo sempre que um processo modificar o contedo da mesma.

VI. O cache TLB deve ser esvaziado a cada troca de contexto entreprocessos.


(a) As afirmaes I, III e IV esto corretas.

(b) As afirmaes II, V e VI esto corretas.

(c) Apenas a afirmao III est correta.

(d) As afirmaes I, III e VI esto corretas.

(e) Todas as afirmaes esto corretas.

33



15. Explique o que TLB, qual a sua finalidade e como seu funciona-mento.

16. Por que necessrio limpar o cache TLB aps cada troca de contextoentre processos? Por que isso no necessrio nas trocas de contextoentre threads?

17. Um sistema de memria virtual paginada possui tabelas de pginacom trs nveis e tempo de acesso memria RAM de 100 ns. Osistema usa um cache TLB de 64 entradas, com taxa estimada deacerto de 98%, custo de acerto de 10 ns e penalidade de erro de 50 ns.Qual o tempo mdio estimado de acesso memria pelo processador?Apresente e explique seu raciocnio.

18. Explique o que fragmentao externa. Quais formas de alocao dememria esto livres desse problema?

19. Explique o que fragmentao interna. Quais formas de alocao dememria esto livres desse problema?

20. Em que consistem as estratgias de alocao first-fit, best-fit, worst-fit enext-fit?

21. Considere um sistema com processos alocados de forma contgua namemria. Em um dado instante, a memria RAM possui os seguintesburacos, em seqncia e isolados entre si: 5K, 4K, 20K, 18K, 7K, 9K,12K e 15K. Indique a situao final de cada buraco de memria apsa seguinte seqncia de alocaes: 12K 10K 5K 8K 10K.Considere as estratgias de alocao first-fit, best-fit, worst-fit e next-fit.

22. Considere um banco de memria com os seguintes buracos no-contguos:

B1 B2 B3 B4 B5 B610MB 4MB 7MB 30MB 12MB 20MB

Nesse banco de memria devem ser alocadas reas de 5MB, 10MB e2MB, nesta ordem, usando os algoritmos de alocao First-fit, Best-fitou Worst-fit. Indique a alternativa correta:

34


(a) Se usarmos Best-fit, o tamanho final do buraco B4 ser de 6Mbytes.

(b) Se usarmos Worst-fit, o tamanho final do buraco B4 ser de 15Mbytes.

(c) Se usarmos First-fit, o tamanho final do buraco B4 ser de 24Mbytes.

(d) Se usarmos Best-fit, o tamanho final do buraco B5 ser de 7 Mbytes.

(e) Se usarmos Worst-fit, o tamanho final do buraco B4 ser de 9Mbytes.

23. Considerando um sistema de 32 bits com pginas de 4 KBytes e umTLB com 64 entradas, calcule quantos erros de cache TLB so geradospela execuo de cada um dos laos a seguir. Considere somente osacessos matriz buffer (linhas 5 e 9), ignorando pginas de cdigo,heap e stack. Indique seu raciocnio.

1 unsigned char buffer[4096][4096] ;2

3 for (int i=0; i


ocorre uma falta de pgina a cada 1.000.000 (106) de acessos memria.Considere que a memria RAM sempre tem espao livre para carregarnovas pginas. Apresente e explique seu raciocnio.

27. Repita o exerccio anterior, considerando que a memria RAM estsaturada: para carregar uma nova pgina na memria necessrioantes abrir espao, retirando outra pgina.

28. Considere um sistema de memria com quatro quadros de RAM e oitopginas a alocar. Os quadros contm inicialmente as pginas 7, 4 e 1,carregadas em memria nessa seqncia. Determine quantas faltas depgina ocorrem na seqncia de acesso {0, 1, 7, 2, 3, 2, 7, 1, 0, 3}, paraos algoritmos de escalonamento de memria FIFO, OPT e LRU.

29. Repita o exerccio anterior considerando um sistema de memria comtrs quadros de RAM.

30. Um computador tem 8 quadros de memria fsica; os parmetrosusados pelo mecanismo de memria virtual so indicados na tabela aseguir:

pgina carga na memria ltimo acesso bit R bit Mp0 14 58 1 1p1 97 97 1 0p2 124 142 1 1p3 47 90 0 1p4 29 36 1 0p5 103 110 0 0p6 131 136 1 1p7 72 89 0 0

Qual ser a prxima pgina a ser substituda, considerando os algorit-mos LRU, FIFO, segunda chance e NRU? Indique seu raciocnio.

31. Considere um sistema com 4 quadros de memria. Os seguintesvalores so obtidos em dez leituras consecutivas dos bits de refernciadesses quadros: 0101, 0011, 1110, 1100, 1001, 1011, 1010, 0111, 0110e 0111. Considerando o algoritmo de envelhecimento, determine ovalor final do contador associado a cada pgina e indique que quadroser substitudo.

36


32. Em um sistema que usa o algoritmo WSClock, o contedo da filacircular de referncias de pgina em tc = 220 indicado pela tabelaa seguir. Considerando que o ponteiro est em p0 e que = 50, qualser a prxima pgina a substituir? E no caso de = 100?

pgina ltimo acesso bit R bit Mp0 142 1 0p1 197 0 0p2 184 0 1p3 46 0 1p4 110 0 0p5 167 0 1p6 97 0 1p7 129 1 0

33. Considere as seguintes afirmaes sobre memria virtual:

I. Por Localidade de referncias entende-se o percentual de pgi-nas de um processo que se encontram na memria RAM.

II. De acordo com a anomalia de Belady, o aumento de memria deum sistema pode implicar em pior desempenho.

III. A localidade de referncia influencia significativamente a veloci-dade de execuo de um processo.

IV. O algoritmo LRU implementado na maioria dos sistemas ope-racionais, devido sua eficincia e baixo custo computacional.

V. O compartilhamento de pginas implementado copiando-seas pginas a compartilhar no espao de endereamento de cadaprocesso.

VI. O algoritmo timo define o melhor comportamento possvel emteoria, mas no implementvel.

As afirmaes corretas so:

(a) II, III e VI

(b) I, II e IV

(c) II, IV e V

37


(d) I, IV e V

(e) IV, V e VI


34. Construa um simulador de algoritmos de substituio de pgina. Osimulador deve receber como entrada a sequncia de referncias apginas de memria e gerar como sada o nmero de faltas de pginageradas, para os algoritmos OPT, FIFO e LRU.

35. Construa um simulador de algoritmos de alocao de memria con-tgua. O simulador deve produzir aleatoriamente uma sequnciade blocos de memria de tamanhos diferentes, simular sua alocaoe gerar como sada o nmero de fragmentos livres de memria, ostamanhos do menor e do maior fragmentos e o tamanho mdio dosfragmentos. Devem ser comparadas as estratgias de alocao first-fit,next-fit, best-fit e worst-fit.

38

Captulo 6

Gerncia de arquivos

1. Enumere os principais atributos de um arquivo.

2. Enumere as principais operaes sobre arquivos.

3. Apresente e comente as principais formas de atribuio de tipos aosarquivos. Quais so as vantagens e desvantagens de cada uma?

4. Analise as seguintes afirmaes relativas a formatos de arquivos:

I. Um magic number consiste de um atributo numrico separadoque identifica o tipo de arquivo.

II. A forma mais comum de identificao de tipo de arquivo o usode extenses ao seu nome.

III. Arquivos de texto em sistemas DOS e UNIX diferem nos caracteresde controle usados para identificar o fim de arquivo.

IV. Para a maioria dos ncleos de sistema operacional, arquivos soquase sempre vistos como meras sequncias de bytes.

V. ELF e PE so dois formatos tpicos de arquivos de configurao.

VI. O padro MIME usado no Linux para identificao de tipos dearquivos pelo sistema operacional.

As alternativas corretas so:

(a) II e IV

(b) II e V

39

40 cCarlos Maziero 6: Gerncia de arquivos

(c) I e III

(d) IV e V

(e) III e VI


5. O que um ponteiro de arquivo? Para que ele serve?

6. Comente as principais formas de acesso a arquivos. Qual o uso maisapropriado para cada uma delas?

7. Quais as principais estruturas de diretrios empregadas em sistemasoperacionais?

8. Do ponto de vista lgico, quais as principais diferenas entre a estruturade diretrios Unix e Windows?

9. Explique os tipos de referncias possveis a arquivos em uma estruturade diretrios.

10. Explique as formas de referncia a arquivos direta, absoluta e relativa.

11. Analise as seguintes afirmaes relativas ao uso de arquivos:

I. No acesso sequencial, o ponteiro de posio corrente do arquivo reiniciado a cada operao.

II. O acesso direto pode ser implementado usando o acesso sequen-cial e operaes de posicionamento do ponteiro do arquivo.

III. No acesso mapeado em memria, o contedo do arquivo copiado para a memria RAM durante a sua abertura.

IV. O acesso indexado raramente implementado pelo ncleo emsistemas operacionais desktop, sendo mais frequente em ambientesmainframe.

V. Travas de uso exclusivo e compartilhado implementam um mo-delo de sincronizao de tipo produtor/consumidor no acesso aoarquivo.

40


VI. Segundo a semntica de compartilhamento UNIX, o contedode um arquivo considerado imutvel durante um compartilha-mento.


(a) II e IV

(b) II e V

(c) III e V

(d) I e IV

(e) III e VI


12. Um conjunto de processos p1, p2, p3 e p4 abrem em leitura/escrita umarquivo compartilhado contendo um nmero inteiro, cujo valor inicial 34. As operaes realizadas pelos processos so indicadas na tabelaa seguir no formato [t, op], onde t o instante da operao e op aoperao realizada:

p1 p2 p3 p4[0, open] [3, open] [7, open] [9, open]

[2,write 41] [6,write 27] [8, read X] [11, read Y][6, close] [8, close] [9,write 4] [12, close]

[10, close]

Considerando a semntica de sesso para o compartilhamento dearquivos, determine os valores de X e Y, explicando seu raciocnio.Cada operao de escrita no arquivo substitui o valor anterior.

13. Enumere principais problemas a resolver na implementao de umsistema de arquivos.

14. Apresente a arquitetura de gerncia de arquivos presente em umsistema operacional tpico, explicando seus principais elementos cons-tituintes.

41


15. Explique o que alocao contgua de arquivos, apresentando suasvantagens e desvantagens.

16. No contexto de alocao de arquivos, o que significa o termo best-fit?

17. Explique a alocao de arquivos em listas encadeadas, apresentandosuas principais vantagens e desvantagens.

18. Explique a estrutura do sistema de arquivos conhecido como FAT,comentando sobre suas qualidades e deficincias.

19. Por que a alocao de arquivos em listas encadeadas consideradapouco robusta? O que pode ser feito para melhorar essa caracterstica?

20. Explique o esquema de alocao indexada de arquivos usando ndicesmulti-nveis.

21. O que fragmentao interna e fragmentao externa? Por que elasocorrem?

22. Analise o impacto das fragmentaes interna e externa nos sistemasde alocao contgua, indexada e por lista encadeadas.

23. Considere um sistema operacional hipottico que suporte simultane-amente as estratgias de alocao contgua, encadeada e indexadapara armazenamento de arquivos em disco. Que critrios devem serconsiderados para decidir a estratgia a usar para cada arquivo emparticular?

24. Avalie as seguintes afirmaes sobre as tcnicas de alocao de arqui-vos:

I. A alocao contgua muito utilizada em sistemas desktop, porsua flexibilidade.

II. A alocao FAT uma alocao encadeada na qual os ponteirosde blocos foram transferidos para um vetor de ponteiros.

III. Na alocao indexada os custos de acesso seqencial e aleatrioa blocos so similares.

IV. Na alocao contgua, blocos defeituosos podem impedir o acessoaos demais blocos do arquivo.

42


V. Na alocao contgua, o custo de acesso a blocos aleatrios alto.

VI. Apesar de complexa, a alocao indexada muito usada emdesktops e servidores.

As afirmaes corretas so:

(a) II, III e VI

(b) I, III e IV

(c) I, IV e V

(d) II, IV e V

(e) IV, V e VI


25. Considerando um arquivo com 500 blocos em disco, calcule quantasleituras e quantas escritas em disco so necessrias para (a) inserirum novo bloco no incio do arquivo ou (b) inserir um novo bloco nofinal do arquivo, usando as formas de alocao de blocos contgua,encadeada e indexada.

Alocao Contgua Encadeada IndexadaOperaes leituras escritas leituras escritas leituras escritasInserir um novobloco no inciodo arquivoInserir um novobloco no final doarquivo

Observaes:

(a) Considere somente as operaes de leitura e escrita nos blocosdo prprio arquivo e no i-node; a tabela de diretrio sempre estem memria;

43


(b) Para a alocao contgua, assuma que no h espao livre depoisdo arquivo, somente antes dele;

(c) Para a alocao encadeada, assuma que a tabela de diretriocontm apenas um ponteiro para o incio do arquivo no disco.Os ponteiros dos blocos esto contidos nos prprios blocos;

(d) Para a alocao indexada, considere i-nodes com somente umnvel, contendo somente os ponteiros para os blocos de dados. Oi-node est no disco.

26. Considere um disco rgido com capacidade total de 1 Mbyte, divididoem 1.024 blocos de 1.024 bytes cada. Os dez primeiros blocos do discoso reservados para a tabela de parties, o cdigo de inicializao(boot) e o diretrio raiz do sistema de arquivos. Calcule o tamanhomximo de arquivo (em bytes) que pode ser criado nesse disco paracada uma das formas de alocao a seguir, explicando seu raciocnio:

(a) Alocao contgua.

(b) Alocao encadeada, com ponteiros de 64 bits contidos nosprprios blocos.

(c) Alocao indexada, com i-nodes contendo somente ponteirosdiretos de 64 bits; considere que o i-node no contm meta-dados,somente ponteiros, e que ele ocupa exatamente um bloco dodisco.

27. Considerando a tabela FAT (File Allocation Table) a seguir, indique:

(a) o nmero de blocos ocupados pelo arquivo relat.pdf;

(b) o tamanho (em blocos) do maior arquivo que ainda pode sercriado nesse disco;

(c) quais arquivos esto ntegros e quais esto corrompidos porblocos defeituosos (bad blocks);

(d) quantos blocos do disco esto perdidos, ou seja, no so usadospor arquivos nem esto marcados como livres ou defeituosos.

Na tabela, a letra R indica bloco reservado (Reserved), F indica blocolivre (Free), L indica o ltimo bloco de um arquivo (Last) e B indicabloco defeituoso (Bad).

44


6

177

F8

159

6810

1311

530

R1

R2

R3

R4

R5

F18

F19

F12

F13

L14

6315

L16

F17

2626

1127

5528

F29

3630

F31

3520

3321

L22

F23

3824

L25

F38

839

F32

4333

B34

F35

B36

2037

F46

F47

F48

4049

F40

2141

3242

F43

5044

B45

L56

F57

F58

7259

F50

L51

4552

F53

5854

F55

B

arquivo incio

readme.txticone.gifretrato.jpg

format.exe

programa.ccarta.doc

relat.pdf

7614296316773

66

F67

6068

2469

F60

4461

F62

F63

5164

F65

F76

4177

F78

L79

F70

F71

F72

1073

2774

F75

F

28. O sistema de arquivos indexado do sistema Minix possui os seguintescampos em cada i-node:

meta-dados (tipo, dono, grupo, permisses, datas e tamanho) 7 ponteiros diretos 1 ponteiro indireto 1 ponteiro duplamente indireto

A implementao bsica desse sistema de arquivos considera blocosde 1.024 bytes e ponteiros de 32 bits. Desenhe o diagrama do sistemade arquivos e calcule o tamanho mximo de arquivo que ele suporta,indicando seu raciocnio.

29. O sistema de arquivos indexado ext2fs, usado no Linux, possui osseguintes campos em cada i-node:

meta-dados (tipo, dono, grupo, permisses, datas e tamanho) 12 ponteiros diretos 1 ponteiro indireto 1 ponteiro duplamente indireto 1 ponteiro triplamente indireto

A implementao bsica do ext2fs considera blocos de 1.024 bytes eponteiros de 64 bits. Desenhe o diagrama do sistema de arquivos edetermine o tamanho mximo de arquivo que ele suporta, indicandoseu raciocnio.

30. Explique como efetuada a gerncia de espao livre atravs de bitmaps.

45

Captulo 7

Gerncia de entrada/sada

1. Considere um escalonador de disco com os seguintes pedidos deleitura de blocos em sua fila, nessa ordem: 95, 164, 36, 68, 17 e 115.Determine todos os deslocamentos da cabea de leitura do disco paraatender esses pedidos e o nmero total de blocos percorridos, paraas polticas FCFS, SSTF, SCAN, C-SCAN, LOOK e C-LOOK. O discotem 200 setores, numerados de 0 a 199, e a cabea de leitura acabou depercorrer os blocos 76 e 50, nessa ordem.

46

Captulo 8

Segurana de sistemas

1. Analise as seguintes afirmaes relativas s propriedades da segurana:

I. A Confidencialidade consiste em garantir que as informaes dosistema estaro criptografadas.

II. A Integridade consiste em garantir que as informaes do sistemas podero ser modificadas por usurios autorizados.

III. A Disponibilidade implica em assegurar que os recursos do sistemaestaro disponveis para consulta por qualquer usurio.

IV. A Autenticidade implica em assegurar que os dados das entida-des atuantes no sistema sejam verdadeiros e correspondam sinformaes do mundo real que elas representam.

V. A Irretratabilidade implica em garantir que nenhuma ao possaser desfeita no sistema.


(a) II e IV

(b) II e V

(c) I e III

(d) I e IV

(e) III e V


47

48 cCarlos Maziero 8: Segurana de sistemas

2. Analise as seguintes afirmaes relativas aos princpios de segurana:

I. Princpio do Privilgio Mnimo: os processos devem receber omnimo possvel de privilgios, para minimizar os riscos em casode bugs ou erros.

II. Princpio do Default Seguro: os acessos permitidos devem serexplicitados; caso um acesso no seja explicitamente permitido,ele deve ser negado.

III. Princpio da Separao de Privilgios: os privilgios dos usurioscomuns devem ser separados dos privilgios do administradordo sistema.

IV. Princpio do Projeto Aberto: a robustez do mecanismo de proteono deve depender de segredos de programao.

V. Princpio da Facilidade de Uso: o uso dos mecanismos de seguranadeve ser fcil e intuitivo para os usurios.


(a) I, II, III e IV

(b) I, II, IV e V

(c) II, III, IV e V

(d) I, III, IV e V.

(e) Todas


3. Relacione as situaes abaixo a ataques diretos (C)onfidencialidade,(I)ntegridade, (D)isponibilidade ou (A)utenticidade, justificando suasescolhas.

[ ] Um programa que permite injetar pacotes falsos na rede.

[ ] Um ataque de negao de servios atravs da rede.

[ ] Um processo spyware que vasculha os arquivos do sistema embusca de senhas.

[ ] int main { while (1) fork(); }

48


[ ] Um site malicioso que imita um site bancrio.

[ ] Um programa quebrador de senhas.

[ ] Um processo que modifica o arquivo de sistema /etc/hosts pararedirecionar acessos de rede.

[ ] Um programa baixado da Internet que instala um malware ocultono sistema operacional.

[ ] Uma pgina Web cheia de arquivos Flash para sobrecarregar oprocessador.

[ ] Um programa de captura de pacotes de rede.

4. O cdigo a seguir apresenta uma vulnerabilidade de segurana. Indi-que qual essa vulnerabilidade e explique como ela pode ser usadapor um atacante.

1 #include 2 #include 3 #include 4

5 int confirma (char * pergunta)6 {7 char resp[20] ;8

9 printf ("%s (sim/nao): ", pergunta) ;10 scanf ("%s", &resp[0]) ;11 if (! strcmp (resp, "sim")) return (1) ;12 return (0) ;13 }14

15 int main ()16 {17 ...18

19 if (confirma ("Devo apagar os valores?"))20 {21 ...22 }23 ...24 }

5. Relacione os tipos de malwares s suas respectivas descries:

49


(V)rus, (W)orm, (T)rojan, (R)ootkit, (B)ackdoor, (E)xploit

[ ] Pode operar no nvel dos comandos, das bibliotecas, do ncleodo sistema operacional ou mesmo abaixo dele.

[ ] Tcnicas de engenharia social geralmente so empregadas parainduzir o usurio a executar esse tipo de programa.

[ ] um programa que se propaga entre sistemas usando vulnerabi-lidades em seus servios.

[ ] um trecho de cdigo que se infiltra em programas executveis,usando-os como suporte para sua execuo e propagao.

[ ] um programa construdo para demonstrar ou explorar umavulnerabilidade de um sistema.

[ ] Pode usar sistemas de e-mail ou de mensagens instantneas parasua propagao.

[ ] um programa que facilita a entrada do intruso em um sistemaj invadido, ou que permite seu comando remotamente.

[ ] Programa usado para esconder a presena de um intruso nosistema.

[ ] Sua execuo depende da execuo do programa hospedeiro.

[ ] um programa usado para enganar o usurio e faz-lo instalaroutros malwares.

[ ] Pode usar suportes de execuo internos (macros) de editores detexto para sua propagao.

[ ] Costuma infectar pendrives plugados em portas USB.

6. Na srie de TV Futurama (escrita por Matt Groening, o mesmo autordos Simpsons) usada uma escrita cifrada denominada Alien Language.Essa codificao pode ser decifrada atravs da tabela a seguir:

50


Explique qual o tipo de criptografia empregado na Alien Language eindique qual o tamanho do espao de chaves da mesma.

7. O texto em portugus a seguir foi cifrado usando o cifrador de Csar.Encontre o texto original e a chave usada para cifr-lo; explique seuprocedimento.

Kjqne fvzjqj vzj ywfsxkjwj t vzjxfgj j fuwjsij t vzj jsxnsf.Htwf Htwfqnsf.

Para facilitar seu trabalho, a tabela a seguir traz a frequncia decaracteres tpica de textos na lngua portuguesa:

letra freq% letra freq% letra freq% letra freq% letra freq%A 14,63 B 1,04 C 3,88 D 4,99 E 12,57F 1,02 G 1,30 H 1,28 I 6,18 J 0,40K 0,02 L 2,78 M 4,74 N 5,05 O 10,73P 2,52 Q 1,20 R 6,53 S 7,81 T 4,34U 4,63 V 1,67 W 0,01 X 0,21 Y 0,01Z 0,47

8. O cifrador de Vigenre um mtodo de cifragem que combina vrioscifradores de Csar em sequncia. Ele constitui um exemplo simplesde cifrador polialfabtico. Para as operaes de cifragem/decifragem usada uma tabela denominada tabula rasa:

51


Para cifrar uma mensagem, primeiro se escolhe uma palavra-chavequalquer, que repetida at ter o mesmo comprimento da mensagem.Em seguida, cada caractere da mensagem original codificado usandouma cifra de substituio (cifrador de Csar). A cifra a usar paraum caractere definida pela linha da tabula rasa indicada pela letracorrespondente da palavra-chave. Um exemplo de cifragem usando apalavra-chave bicicleta indicado a seguir:

Mensagem aberta Atacare m os ao amanhecer de sexta-feiraPalavra-chave bicicle t ab ic icletabic ic letab icicl

Mensagem cifrada bbckcci f ot iq iolraedmt lg diqtb-ngqtl

Use o cifrador de Vigenre para cifrar a mensagem secreta Encontra-mos aliens usando a palavra-chave missao:

Msg aberta E n c o n t r a m o s a l i e n sPalavra-chave

Msg cifrada

52


9. Alice precisa enviar a imagem ISO de um CD confidencial a seusamigos Bob, Carol e David. Como o arquivo muito grande, ela ocarregou em um servidor de arquivos acessvel remotamente. Contudo,esse servidor pode ser invadido e as comunicaes entre eles podemser capturadas. Como Alice pode cifrar o arquivo ISO de forma quesomente Bob, Carol e David possam abri-lo, cada um com sua prpriachave?

10. Recentemente foi noticiado na imprensa que certificados digitais emi-tidos pela Autoridade Certificadora holandesa DigiNotar haviam sidofalsificados e estavam sendo usados por um governo do oriente mdiopara monitorar as comunicaes de seus cidados. Considerando ocertificado falso do servio de e-mails do Google (mail.google.com),explique:

(a) Neste contexto, em que consiste um certificado falso?

(b) Qual a utilidade de um certificado falso na interceptao decomunicaes?

(c) Por que somente os usurios do navegador Chrome (produzidopelo prprio Google) detectaram o certificado falso, enquantousurios de outros navegadores no perceberam nada?

11. O provedor de contedo TOL (Tabajara OnLine) decidiu implementarum novo mecanismo de segurana em suas pginas web. Esse meca-nismo consiste em adicionar uma etiqueta oculta (HTML tag) em cadapgina, contendo o nome do autor (name), a data de produo (date)e uma assinatura digital s. Essa assinatura constituida pelo hashcriptogrfico do nome do autor e da data (hash(name + date)), cifradousando a chave privada do autor da pgina. O contedo da pginaWeb em si no cifrado. As chaves pblicas dos autores registradospodem ser obtidas em http://www.tol.com.br/pubkeys.html.

Responda:

(a) Que objetivo tinham em mente os proponentes desse mecanismo?

(b) Esse esquema seguro? Por que?

(c) Se o esquema no for seguro, indique um possvel ataque aomesmo; caso seja seguro, explique por que esse mesmo ataqueno funcionaria.

53


12. Analise as seguintes afirmaes relativas s tcnicas de autenticao:

I. Nas estratgias de autenticao SYK, o sistema autentica o usuriocom base em informaes fornecidas pelo mesmo.

II. Nas estratgias de autenticao SYH, o sistema usa dados coleta-dos do usurio para fazer sua autenticao.

III. Nas estratgias de autenticao SYA, o usurio autenticado combase em suas caractersticas fsicas.


(a) I e II

(b) II e III

(c) I e III

(d) Nenhuma delas

(e) Todas elas


13. Analise as seguintes afirmaes relativas s tcnicas de autenticao:

I. Para estar devidamente protegidas, as senhas armazenadas nosistema devem ser cifradas com criptografia simtrica.

II. A autenticao multi-fator consiste em autenticar o usuriousando duas senhas simultaneamente.

III. A autenticao por tcnicas biomtricas deve usar caractersti-cas fsicas universais, singulares, permanentes e mensurveis dosusurios.

IV. Os tokens de segurana usados no acesso a servios bancriospela Internet implementam um esquema de senhas baseado emdesafio-resposta.

V. PAM e SSPI so infraestruturas de autenticao modulares usadasem sistemas operacionais de mercado.


54


(a) II e IV

(b) II e V

(c) I e III

(d) IV e V

(e) III e V


14. Qual a funo do sal usado em sistemas de autenticao por se-nhas? Explique como o sal usado; sua explicao deve conter umdiagrama.

15. Analise as seguintes afirmaes relativas aos modelos de controle deacesso:

I. Nos modelos de controle de acesso obrigatrios, o controle definido por regras globais incontornveis, que no dependemdas identidades dos sujeitos e objetos nem da vontade de seusproprietrios ou mesmo do administrador do sistema.

II. Os modelos de controle de acesso discricionrios se baseiamna atribuio de permisses de forma individualizada, ou seja,pode-se conceder ou negar a um sujeito especfico a permissode executar uma ao sobre um dado objeto.

III. O Modelo da matriz de controle de acesso uma forma derepresentao lgica de polticas discricionrias.

IV. O modelo de Bell-LaPadula uma forma de representar pol-ticas de controle de acesso obrigatrias que tenham foco emconfidencialidade de dados.

V. O modelo de Biba uma forma de representar polticas de controlede acesso obrigatrias que tenham foco em integridade de dados.

VI. Os modelos de controle de acesso baseados em papis permitemdesvincular os usurios das permisses sobre os objetos, atravsda definio e atribuio de papis.


55


(a) I, II, IV

(b) II, III, VI

(c) I, II, III, V

(d) Nenhuma delas

(e) Todas elas


16. Analise a seguinte matriz de controle de acesso:

f ile1 f ile2 program1 socket1Alice read read execute write

write writeremoveowner

Beto read read readwrite write owner

removeowner

Carol read execute readwrite

Davi read write read readwriteowner

Assinale a alternativa correta:

(a) O usurio Beto pode alterar as permisses dos recursos f ile1 eprogram1

(b) O usurio Alice tem a seguinte lista de capacidades:{ f ile1 : (read,write, remove, owner), f ile2 : (read,write), program1 :(read, execute), socket1 : (write) }

(c) A lista de controle de acesso de f ile2 : {Alice : (read,write),Beto :(read,write, remove),Carol : (read),Davi : (write) }

56


(d) A lista de capacidades de Beto : { f ile1 : (read,write), f ile2 :(read,write, remove, owner), program1 : (read, owner) }

(e) Nenhuma das anteriores

17. Escreva as listas de controle de acesso (ACLs) equivalentes s listas decapacidades a seguir:

CL(Alice) = { f ile1 : (read,write, remove, owner),f ile2 : (read),program1 : (execute),socket1 : (read,write) }

CL(Beto) = { f ile1 : (read),f ile2 : (read,write, remove, owner),program1 : (read, execute, owner) }

CL(Carol) = { f ile2 : (read,write),program1 : (execute),socket1 : (read,write) }

CL(Davi) = { f ile1 : (read),f ile2 : (write),program1 : (read, execute),socket1 : (read,write, owner) }

18. Relacione as expresses a seguir aos modelos de controle de acesso deBell (L)aPadula, (B)iba ou da (M)atriz de controle de acesso. Consideres um sujeito, o um objeto, h(s) o nvel de habilitao ou de integridadedo sujeito e c(o) a classificao do objeto.

[ ] request(si, o j,write) h(si) c(o j)[ ] request(si, o j,write) write Mi j[ ] request(si, o j, read) h(si) c(o j)[ ] request(si, o j, read) read Mi j[ ] request(si, o j,write) h(si) c(o j)

57


[ ] request(si, o j, read) h(si) c(o j)19. Preencha a matriz de controle de acesso que corresponde seguinte

listagem de arquivo em um ambiente UNIX:

-rwxr-x--- 2 maziero prof 14321 2010-07-01 16:44 script.sh-rw------- 2 lucas aluno 123228 2008-12-27 08:53 relat.pdf-rwxr-x--x 2 daniel suporte 3767 2010-11-14 21:50 backup.py-rw-rw-r-- 2 sheila prof 76231 2009-18-27 11:06 cmmi.xml-rw-r----- 2 mariana aluno 4089 2010-11-09 02:14 teste1.c

Observaes:

Composio do grupo prof: {maziero, sheila} Composio do grupo suporte: {maziero, daniel} Composio do grupo aluno: {lucas, daniel, mariana} Preencha os campos da matriz com os caracteres r, w, x e

-.

script.sh relat.pdf backup.py cmmi.xml teste1.c

maziero

lucas

daniel

sheila

mariana

58


20. Em um sistema de documentao militar esto definidos os seguintesusurios e suas respectivas habilitaes:

Usurio HabilitaoMarechal Floriano Ultrassecreto

General Motors SecretoMajor Nelson Confidencial

Sargento Tainha RestritoRecruta Zero Pblico

Considerando operaes sobre documentos classificados, indiquequais das operaes a seguir seriam permitidas pelo modelo de controlede acesso de Bell-LaPadula:

[ ] Sargento Tainha cria o documento secreto comunicado.txt

[ ] Recruta Zero l o documento ultrassecretosalarios-dos-generais.xls

[ ] General Motors escreve um memorando pblicoaviso-sobre-ferias.doc.

[ ] Major Nelson escreve um documento confidencialavarias-no-submarino.doc.

[ ] Marechal Floriano l o documento restrito comunicado.txt.

[ ] General Motors l o documento secretovendas-de-carros-2010.doc.

[ ] Sargento Tainha l o documento restrito plano-de-ataque.pdf.

[ ] Major Nelson l o documento confidencialprocessos-navais.html.

[ ] Marechal Floriano escreve o documento secretonovas-avenidas.doc.

[ ] Recruta Zero escreve o documento ultrassecreto meu-diario.txt.

21. As listas de controle de acesso (ACLs) e as listas de capacidades (CLs)a seguir so complementares, mas esto incompletas. Complete-ascom as regras faltantes.

59


ACL(o1) = { (u1 : rwx) }ACL(o2) = { (u2 : r) }ACL(o3) = { (u1 : r) (u4 : rw) }ACL(o4) = { (u2 : rw) (u3 : r) }

CL(u1) = { (o2 : rw) (o4 : r) }CL(u2) = { (o1 : rx) }CL(u3) = { (o1 : rx) }CL(u4) = { (o4 : rwx) }

22. Considerando o modelo de controle de acesso de Bell & LaPadula,indique que tipo de acesso (R, W, RW ou ) um usurio u pode ter sobreos documentos abaixo identificados. Considere que h(u) = secreto eque C(u) = {vendas, rh}.

[ ] d1: c(d1) = ultrassecreto e C(d1) = {vendas}[ ] d2: c(d2) = publico e C(d2) = {rh, f inanceiro}[ ] d3: c(d3) = secreto e C(d3) = {rh}[ ] d4: c(d4) = reservado e C(d4) = {rh, vendas}[ ] d5: c(d5) = con f idencial e C(d5) = { }

23. Muitas vezes, usurios precisam executar aes que exigem privilgiosadministrativos, como instalar programas, reconfigurar servios, etc.Neste contexto, analise as seguintes afirmaes:

I. No mecanismo UAC User Access Control dos sistemas Windows,um usurio administrativo inicia sua seo de trabalho com seusprivilgios de usurio normal e recebe mais privilgios somentequando precisa efetuar aes que os requeiram.

II. Alguns sistemas operacionais implementam mecanismos de mu-dana de credenciais, atravs dos quais um processo pode mudarde proprietrio.

III. As POSIX Capabilities so uma implementao do mecanismode capabilities para sistemas operacionais que seguem o padroPOSIX.

60


IV. Alguns sistemas operacionais separam os usurios em usuriosnormais ou administrativos, atribuindo aos ltimos permissespara efetuar tarefas administrativas, como instalar programas.

V. Alguns sistemas operacionais implementam processos monitoresque recebem pedidos de aes administrativas vindos de pro-cessos com baixo privilgio, que so avaliados e possivelmenteatendidos.

VI. Os flags setuid e setgid do UNIX implementam um mecanismode permisses temporrias.


(a) I, II, IV, VI

(b) II, III, VI

(c) I, II, III, V

(d) I, II, IV, V

(e) Todas elas


24. O diagrama abaixo representa os principais componentes da infraestru-tura de controle de acesso de um sistema operacional tpico. Identifiquee explique elementos representados pelas caixas tracejadas.

61


sujeitos objetos

outrossujeitos

ousistemas

arquivos

processosthreads

transaes

informaes externas(horrio, etc)

acessos aesnega

permite

eventos

Illenihild ubitatquinullamscientiamhabet(Nadaduvidaquemnadasabe)Illenihildubitatquinullamscientiamhabet(Nadaduvidaquemnadasabe)Illenihildubitatquinullamscientiamhabet(Nadaduvi

1

2 3

4 5

6 7 8

25. A listagem a seguir apresenta alguns programas executveis e arquivosde dados em um mesmo diretrio de um sistema UNIX, com suasrespectivas permisses de acesso:

- rwx r-s --- 2 marge family indent- rwx r-x --x 2 homer family more- rws r-x --x 2 bart men nano- rwx r-x --- 2 lisa women sha1sum

- rw- r-- --- 2 lisa women codigo.c- rw- rw- --- 2 marge family dados.csv- rw- r-- --- 2 bart men prova.pdf- rw- rw- --- 2 homer family relatorio.txt- rw- --- --- 2 bart men script.sh

Os programas executveis precisam das seguintes permisses deacesso sobre os arquivos aos quais so aplicados para poder executar:

more, sha1sum: leitura

62


nano, indent: leitura e escritaConsiderando os grupos de usurios men = {bart, homer,moe}, women ={marge, lisa,maggie} e f amily = {homer,marge, bart, lisa,maggie}, indi-que quais dos comandos a seguir sero permitidos e quais seronegados. O prompt indica qual usurio/grupo est executando ocomando:

[ ] lisa:women> nano codigo.c

[ ] lisa:women> more relatorio.txt

[ ] bart:men> nano relatorio.txt

[ ] bart:men> sha1sum prova.pdf

[ ] marge:women> more relatorio.txt

[ ] marge:women> indent codigo.c

[ ] homer:men> sha1sum prova.pdf

[ ] homer:men> nano dados.csv

[ ] moe:men> sha1sum relatorio.txt

[ ] moe:men> nano script.sh

26. Sistemas de deteco de intruso (IDS - Intrusion Detection Systems)podem ser classificados sob vrias perspectivas. Explique como osIDSs so classificados segundo:

(a) A origem dos dados analisados;

(b) O momento da anlise dos dados;

(c) A forma de anlise dos dados.

63

Conceitos bsicosGerncia de atividadesComunicao entre tarefasCoordenao entre tarefasGerncia de memriaGerncia de arquivosGerncia de entrada/sadaSegurana de sistemas

Documents

So Exercicios a5