156242499-Lista-de-exercicios-Sistemas-Operacionais-Resolvida

Prévia do material em texto

Lista de exercícios Sistemas Operacionais 
Resolvida
1. Os serviços e funções oferecidas por um sistema operacional podem ser 
divididas em duas categorias. Descreva brevemente as duas categorias e 
discuta como elas se diferem.
• Conveniência
Execução de programas
Operações de I/O
Sistema de arquivos
Detecção de erros
• Eficiência
Alocação de recursos
Proteção
Contabilizações
2. Liste 5 (cinco) serviços, oferecidos por um sistema operacional, que são 
projetados para tornar o sistema de computação mais conveniente para os 
usuários.
1. Gerenciamento de processos, criação, fechamento, escalonamento, prioridades e 
comunicação entre eles.
2. Gerenciamento da memória principal: Alocação, desalocação, proteção e 
abstração da memória virutal.
3. Gerenciamento dos sistemas de I/O.
4. Conexão em rede: Conexão com os dispositivos e implementação dos protocolos 
de rede.
5. Sistema de proteção (autorização a usuários).
6. Implementação de sistema de arquivos.
3. O que são System Calls, cite 4 exemplos.
Constituem uma interface entre o processo e o sistema operacional.
Exemplos:
• Inicia ou finaliza processo
• Altera atributos dos processos
• Espera sinal
• Abre ou fecha arquivo
• Lê relógio do sistema
• Envia ou recebe mensagens
4. Os sistemas operacionais podem ser construídos de diferentes maneiras. 
Descreva as principais arquiteturas existentes.
Do ponto de vista de projeto (arquitetura), segundo Tanenbaum (1999):
* Núcleo monolítico ou monobloco: o núcleo consiste em um único processo 
executando numa memória protegida executando as principais funções.
* Micronúcleo ou modelo cliente-servidor: o núcleo consiste de funções mínimas 
(comunicação e gerenciamento de processos), e outras funções, como sistemas de 
arquivos e gerenciamento de memória, são executadas no espaço do usuário como 
serviços; as aplicações (programas) são os clientes.
5. Descreva as ações tomadas pelo kernel para fazer a troca de contexto 
entre processos.
A troca de contexto exige que o estado do processo antigo (a sair do processamento) 
seja salvo e que o estado do processo novo (a entrar no processamento) seja carregado. 
O contexto é representado no PCB que inclui o valor dos registradores.
6. Explique o que são os anéis de execucação. Qual a diferença entre código 
executando no nível 0 e em outros níveis.
São extenções dos processadores que possibilitam separar os códigos sendo executados 
na CPU por camadas. Nos CHIPs Intel Vão de RING0 (Kernel), passado por RING1 
(Drivers), RING2 (Drivers) até RING3 (Aplicativos). O Kernel do Linux e do Windows 
XP usam somente o RING0 e RING3. O código executado em RING0 é o que tem mais 
privilégios (ou seja mais acesso ao hardware).
7. O que são processos, e quais os estados que podem assumir?
São programas em execução na memória.
* Novo
* Em execução
* Em espera
* Pronto
* Terminado
8. O que são threads? Em que diferem de processos convecionais?
Um thread é uma unidade básica de execução na CPU. Um único processo pode ter 
diferentes threads. Cada thread compreende um ID, um contador de programa, um 
conjunto de registradores e uma pilha. 
8.1. As principais seções de um processo são Pilha, Heap, Dados e Código. 
Quais destas seções podem e/ou devem ser compartilhadas entre threads?
Os threads do mesmo processo compartilham com outros sua seção de código, sua seção 
de dados, arquivos abertos e sinais.
8.2. Qual a diferença de threads em nível de usuário e em nível de SO
Thread em nível de SO é implementada em uma biblioteca pelo Sistema Operacional 
por exemplo pthreads no Linux. Utilizando-a as threads em nível de SO são como 
processos independentes para o escalonador, também se o sistema tiver mais de 1 
processador elas podem ser executadas 1 em cada processador.
As threads em nível de usuário é uma implementação da aplicação em que 
voluntariamente um thread se retira do processamento e cede espaço a outra thread. Para 
o sistema operacional é apenas 1 processo.
9. Mostre um exemplo de uso do fork(). Explique quais são os valores 
retornados pela função.
int i; 
i=fork(); 
if(i==0) 
{ 
printf("Processo Filho\n"); 
} 
else if(i>0) 
{ 
printf("Processo Pai, que criou um filho numero: %i\n", i); 
}
10. Na criação de processos utilizando fork() um novo processo é criado com 
a imagem do processo pai. Como o kernel Linux evita a necessidade de 
realizar esta cópia no momento da chamada do fork?
Sim, uma otimização do Kernel do Linux implementa Copy-on-write. Consistem em 
compartilhar os dados somente referenciando a mesma área nos forks criados pelo 
mesmo processo. Ao modificar alguma das páginas uma cópia da página é feita.
11. O que significa escalonamento preemptivo?
Envolve o uso de interrupções para suspender o processo em execução no momento e 
invoca um escalonador para determinar qual o próximo processo que deve ser 
executado. Sendo assim todo processo terá um tempo de execução na CPU em algum 
momento.
12. O que significa dizer que o Kernel também é preemptivo?
Significa dizer que operações de kernel (serviços ou funções) podem ser interrompidas.
13. O que é starvation? Mostre um algoritmo que poderia levar a essa 
condição.
Ocorre quando um processo depende de um recurso e seu acesso é negado 
perpétuamente. Sem este recurso o processo não pode terminar sua tarefa.
14. O que é um deadlock? Mostre um um algoritmo que pode entrar em 
deadlock.
Ocorre quando, um processo (ou mais) está em posse de um recurso não compartilhado 
e esperando por outro recurso em posse de outro processo que também aguarda um 
recurso. Essa espera pode ser do processo anterior ou outro processo de forma que feche 
um ciclo. E conseqüentemente estes processos não sofrem preempção.
15. Quais dos seguintes algoritmos de escalonamento podem levar a 
"starvation" e porque?
a) First-come, Fist-served
Pode ocorrer inanição (starvation), se o primeiro processo (que chega primeiro) da fila 
for longo. Então o tempo de espera médio de todos os outros processos será muito 
grande.
b) Shortest job first
É o algoritmo ótimo (do ponto de vista computacional) no tempo de espera. O maior 
tempo de espera será o processo com maior pico de CPU.
c) Round Robin
Depende exclusivamente do tamanho do quantum da CPU. Se for muito grande será 
equivalente a FCFS, mas se for pequeno será a sensação de dividir a CPU pelo numero 
de processos.
d) Priority
Um processo que esteja pronto para executar, mas não tennha a posse da CPU pode ser 
considerado bloqueado. Um algoritmo por prioridades pode deixar alguns processos de 
baixa prioridade esperando indefinidamente pela CPU.
16. Que técnica é usada para evitar que um processo em um algoritmo de 
escalonamento por Multilevel Feedback-Queue nunca execute?
Define-se que os processos que estão esperando por muito tempo na fila de menor 
prioridade são promovidos com maior prioridade.
17. O que deve ser considerando ao escrever um algoritmos de 
escalonamento em um sistema SMP?
Primeiramente deve ser considerado que os processadores são idênticos (ou 
homogêneos), esta diferença mudaria toda a abordagem. Depois pode-se criar uma fila 
de processos para cada processador, ou se for uma fila deve se evitar que 2 
processadores peguem o mesmo processo ou que algum processo se perca da fila.
18. Explique como funcionava o escalonador de prioridades no Kernel Linux 
(de 2.6 até 2.6.23)
1. Escalonador por prioridade dinâmica.
2. Heurística para dizer se o processo é IO bound, CPU bound ou interativo.
3. Quantum varia durante o tempo e processos.
4. É O(1)
5. Todo processo tem prio estática entre 100 e 139 e dinâmica entre 100 e 139 
(menor valor é maior prioridade)
6. Quantum base é => Prio_estat > 120 ? (140-Prio_estat)*20 : (140-Prio_estat) * 5
7. Prioridade dinâmica => max(100, min(prio_estat – bonus + 5, 139))
19. Explique o algoritmo de escalonamento Completely 
Fair Scheduler que atualmente é utilizando no kernel 
Linux.
1. Não tem 1 fila,
2. Dividir n CPU's entre os processos igualmente3. linha do tempo de execução
4. Redblack tree O(log(n))
5. Relógio preciso de nano segundos
6. Relógio para incrementar este tempo baseado no wallclock / 
núm de processos esperando para executar
7. Quando executa decrementa waiting time
8. Prioridade → padrão do decaimento do waiting time
20. Mostre como funciona a solução de alternância estrita. Explique qual é 
sua limitação na prática.
Esta é uma solução a qual obriga que a região crítica seja dada a um dos processos por 
vez,
em uma estrita alternância. 
O problema com a solução de alternância estrita é que requer que os dois processos se 
alternem precisamente, o que significa que o número de acessos de cada processo deve 
ser exatamente igual ao do outro. Além disso pode acontecer de um dos processos não 
poder prosseguir normalmente. Pois após entregar a seção crítica para o outro processo 
não pode mais pedi-la novamente. 
21. O que é o problema da Região Crítica? Mostre um exemplo onde não 
tratá-lo poderia levar a um erro.
Região crítica é um segmento de código que enquanto está em execução não é permitido 
a nenhum outro processo sua execução ao mesmo tempo. Pode ser a operação em 
tabelas, arquivos e assim por diante.
22. Mostre e explique o funcionamento da solução de Peterson.
O algoritmo de Peterson é um algoritmo de programação concorrente para exclusão 
mútua, que permite a dois ou mais processos ou subprocessos compartilharem um 
recurso sem conflitos, utilizando apenas memória compartilhada para a comunicação 
(Wikipedia).
flag[0] = 0; 
flag[1] = 0; 
turn;
P0: flag[0] = 1;
turn = 1;
while (flag[1] == 1 && turn == 1)
{
// busy wait
}
// critical section
...
// end of critical section
flag[0] = 0;
P1: flag[1] = 1;
turn = 0;
while (flag[0] == 1 && turn == 0)
{
// busy wait
}
// critical section
...
// end of critical section
flag[1] = 0;
O algoritmo utiliza duas variáveis, flag e turn. O valor de flag 1 indica que o processo 
quer entrar na região crítica. A variável turn guarda o ID do processo com a vez. A 
entrada na região crítica é garantida para P0 se P1 não quiser entrar na região crítica ou 
se P1 deu prioridade para P0 atribuindo o valor de turn para 0. 
Este algoritmo satisfaz os 3 problemas de regiões críticas: a exclusão mútua, o 
progresso e espera limitada.
23. O que são semáforos? Mostre um exemplo de uso.
É uma ferramenta de sincronização generalizável. É uma variável inteira que a parte de 
sincronização é acessada somente por duas operações wait e signal.
void wait(S){
while (s<=0); // loop sem operação
s--;
}
void signal(s){
s++;
}
Exemplo de uso:
do{
wait(mutex);
<SEÇÃO CRITICA>
signal(mutex);
<SEÇÃO REMANESCENTE>
}while(1);
24. Mostre uma solução usando semáforos para o problema "Bounded-
Buffer"
/* PRODUTOR*/
do{
wait(empty);
wait(mutex);
insere_buffer(elemento);
signal(mutex);
signal(full);
}while(1);
/*CONSUMIDOR*/
do{
wait(full);
wait(mutex);
remove_buffer(elemento);
signal(mutex);
signal(empty);
}while(1);
25. Mostre uma solução usando semáforos para o problema "Readers-Writers" 
26. Mostre uma solução usando semáforos para o problema "Dining-
Philosophers" 
27. Resolva pelo menos 3 problemas de sincronização do Livro "The Little Book of 
Semaphores".
28. O que é copy-on-write e sob quais circunstâncias ela é útil?
Consistem em compartilhar os dados somente referenciando a mesma área. Ao se 
modificar alguma das páginas uma cópia da página é feita. E somente aquela página que 
é alterada fica “diferente” do resto. É útil pois torna programa implementados com forks 
mais leves.
1. Explique a diferença entre fragmentação interna e 
externa.
(wikipédia)
A fragmentação interna é a perda de espaço dentro de uma área de 
tamanho fixo. Numa memória secundária, ela ocorre quando um 
arquivo ou fragmento de arquivo não ocupa completamente o espaço 
da unidade de alocação destinado a ele, causando desperdício de 
espaço. Cada unidade de alocação não pode comportar fragmentos 
de arquivos diferentes.
A fragmentação externa ocorre em sistemas de arquivo quando 
muitos arquivos de tamanhos diferentes são criados, modificados em 
seu tamanho, e/ou eliminados. O efeito é pior se um arquivo que é 
dividido em muitas pequenas partes for eliminado, porque isto deixa 
regiões pequenas de espaço livre.
Quanto maior for o tamanho dos clusters no sistema de arquivos 
usado e maior for o número de arquivos pequenos armazenados, 
maior é o índice de fragmentação interna, que além de perda de 
espaço, causa perda de desempenho, já que teremos áreas vazias 
entre os arquivos armazenados nos discos magnéticos.
2. Dadas partições de memória de 100KB, 500KB, 200KB, 
300KB e 600KB (em ordem), como cada um dos 
algoritmo: Fist-fit, best-fit e worst-fit, alocariam 
processos de 212Kb, 417Kb, 112KB e 426KB? Qual dos 
algoritmos faria o uso mais eficiente de memória.
First Fit acomoda espaço na memória pelo começo da memória 
disponível até o fim, até encontrar o primeiro espaço livre que seja 
grande o suficiente. Se não retorna erro.
Best Fit tenta determinar o melhor lugar para alocar os dados. A 
definição de melhor varia nas implementações, mas por exemplo 
pode ser escolhido o espaço que deixaria menor resíduo no final do 
bloco.
Worst Fit. O algoritmo seleciona o maior espaço possível que a 
informação pode ser armazenada (maior que a informação). É o 
completamente oposto do best-fit que procura o menor espaço 
possível.
3. Explique os seguintes algoritmos para substituição de 
páginas (page replacement): FIFO, Optimal e LRU. No 
caso do LRU, você deve explicar quais são as políticas de 
aproximação para o LRU.
FIFO é uma fila normal onde o primeiro que entra é o primeiro que 
sai. É simples e tem desempenho ruim (pode aumentar o 
paginamento com aumento de memória o que é absurdo)
Optimal: Quando uma página precisa ser trocada, o sistema 
operacional troca a página que o seu próximo uso será num futuro 
distante. Por exemplo, uma página que não será usada nos próximos 
6 segundos será trocada por uma página que será usada em 0.4 
segundos.
LRU: Quando uma página é usada é marcada como referenciada. Em 
certo momento por interrupção de relógio, atribui-se a página os bits 
de não referenciados. Então divide-se a página em 4 classes, 
referenciado ou não e modificado ou não.
4. Como funciona o mapeamento de arquivos em 
memória, qual a vantagem de utilizar esse modo de 
acesso.
É o mapeamento de um arquivo como se fosse um array em 
memória. É eficiênte porque utiliza leitura preguiçosa só lendo os 
dados que realmente precisam ser lidos. No Posix pode ser feito por 
mmap()
5. O que é o modo de alocação de memória "Buddy 
System". Qual a sua desvantagem?
O modo de alocação Buddy System divide a memória em pedaços 
com tamanho potência de 2. Existe um limite superior (maior bloco 
que pode ser alocado) e inferior (menor bloco que pode ser alocado). 
Quando é feita uma requisição arredonda-se o tamanho requisitado e 
se o tamanho é maior que a metade do bloco inicial então o bloco 
inteiro é alocado. Senão o bloco é dividido em dois "buddies" e assim 
recursivamente.
O método de liberar a memória é eficiente e relativamente rápido. 
Tipicamente é implementado por uma árvore binária que representa 
blocos usados e não usados. Contudo ainda existem problemas de 
fragmentação interna.
6. O que é o mecanismo de alocação chamado SLAB?
A idéia fundamental por trás do SLAB é baseada na observação de 
que alguns objetos do kernel são frequentemente criados e 
destruídos e após isso nunca mais são necessários.
Isso implica que cada alocação de memória para estes objetos as 
vezes custa uma busca best-fit. E ainda a desalocação do espaço de 
memória após a destruição do objeto causa fragmentação.
Na implementação do SLAB existe cache e uma estrutura Slab que 
pode ser empty, partial, full. Como ele aloca somenteo espaço 
necessário a fragmentação interna não existe.
7. O que é o Overcommit de memória?
Overcommit de memória é uma função do kernel que permite alocar 
mais memória do que realmente é disponível. A idéia por de trás 
dessa funcionalidade é de que alguns aplicativos alocam mais espaço 
que precisam, mas nunca usam. Isso permite que se rode mais 
aplicativos que cabem na memória, mas ele não podem usar a 
memória, caso isso aconteça estes aplicativos são fechados.
8. Qual a relação entre o espaço de endereçamento 
virtual e utilização da memória física?
O endereçamento virtual agrega tando endereços armazenados em 
memória secundária quando endereços resididos na memória ram.
9. O que significa dizer que a memória virtual de um 
processo é 50MB, a memória residente 20MB e a memória 
compartilhada 10MB.
Significa que 20 mb estão na memória RAM, e 10 mb é compartilhado 
com outro processo por ter gerado (ou sido gerado) por um Fork e 
estas páginas não sofreram escrita ainda.
10. Quais as vantagens e desvantagens de guardar o 
nome do programa criador junto aos atributos do 
arquivo?
Vantagem: Livra o sistema operacional de saber com qual aplicativo 
deve ser aberto o arquivo, facilita também a vida do usuário por ter 
acesso rápido e simples a leitura e edição do arquivo.
Desvantagem: Um terceiro pode alterar o arquivo para apontar para 
um programa mal intencionado.
11. Na semântica de sistema de arquivos do Unix o que 
acontece quando um arquivo que está aberto é removido?
Ele não ficará mais acessível aos programas que quiserem o acessar 
logo após o momento de remoção. Porém continuará acessível por 
aqueles programas que já estavam com o arquivo aberto no 
momento da remoção.
Para cada arquivo o file system mantem um contador que indica 
quantos procesos o estão usando, quando é removido o arquivo se o 
contador não for 0 é apagado somente o acesso ao mesmo, mas o 
arquivo é mantido no disco até que todos os processos se encerrem.
12. No NFS (Network File System) o que é o "Silly 
Rename"? Porque surgem os arquivos .nfsXXXXXX ?
(Segundo NFS FAQ)
Aplicações em Unix geralmente criam arquivos de rascunho e 
removem sua ligação. Quando fazem isso o arquivo passa a não ser 
visível no sistema de arquivos para quando a aplicação fechar o 
arquivo este ser removido. Conhecido como "delete on last close", é 
comum em aplicações Unix.
Pela forma como o NFS foi especificado, não existe maneira de 
apagar o arquivo do sistema, o deixando disponível para aplicações. 
O que o NFS faz é emular este comportamento renomeando o arquivo 
para algo como ".nfsXXXXX". que esconde o arquivo para seu uso. 
Isso é conhecido como "silly rename." Após o fechamento do 
processo o arquivo é apagado. Ou fica residual em caso de crash da 
aplicação.
O NFS é stateless, e não sabe quais arquivos estão sendo utilizados, 
assim pra manter compatibilidade com os programas linux (onde um 
arquivo aberto pode ser excluído sem problemas) ele renomeia o 
arquivo e deixa ele oculto, quem estava com o arquivo aberto 
continua lendo deste .nfsX
13. Sobre métodos de alocação de espaço, responder:
a) Como funciona a alocação de espaço contígua? Que 
problemas apresenta?
Cada arquivo ocupa um conjunto de blocos contíguos no disco. 
Somente é necessário armazenar a localização inicial (número do 
bloco) e o tamanho do arquivo (quantidade de blocos). Pode ser feito 
mapeamento de endereço lógico para o físico, mas os arquivos não 
podem crescer.
A alocação de espaço contígua requer que cada arquivo ocupe um 
conjunto de blocos contíguos no disco. Os endereços de disco 
definem um ordenamento linear no disco. Com isso, o número de 
operações de busca no disco, exigidos para acesso a arquivos 
alocados contiguamente, é mínimo, assim como o tempo de busca 
quando uma operação de busca for necessária.
Como problemas encontrados na alocação contígua temos:
- a dificuldade de encontrar espaço para um novo arquivo. Sistemas 
de gerenciamento de espaço livre devem ser utilizados para realizar 
esta operação, mas tais sistemas geram fragmentação externa;
- a dificuldade de determinar a quantidade de espaço necessário para 
um arquivo. Pela falta de conhecimento na hora da criação do 
arquivo, ou para futura ampliação do mesmo. Em geral, o espaço 
necessário é superestimado. Gerando assim fragmentação interna.
b) Como funciona a alocação de espaço por 
encadeamento (linked allocation). Quais os problemas 
apresentados por este método?
Cada arquivo é uma lista encadeada de blocos em disco. Os blocos 
podem ser espalhados no disco. Tem pouca perda de espaço porém 
não tem acesso direto, tem que percorrer a lista.
O diretório contém um ponteiro para o primeiro e último blocos do 
arquivo. E cada bloco contém um ponteiro para o proximo bloco. Não 
gera fragmentação externa.
Como problemas encontrados na alocação por encadeamento temos:
- O principal problema é que ela so pode ser efetivamente utilizada 
para arquivos de acesso sequencial.
- O espaço perdido com a alocação dos ponteiros, logo, cada arquivo 
irá requerer um pouco mais de espaço do que necessitaria em outra 
situação.
- O problema da confiabilidade, como a integridade do arquivo é 
mantida por intermedio de ponteiros espalhados por todo o disco, se 
um desses ponteiros for corrompido, pode-se ter grandes perdas de 
dados ou de espaço livre.
c) Como funciona a FAT (File-Allocation Table) usado pelo 
MS-DOS, qual a diferença em relação à alocação por 
encadeamento simples?
A FAT usa uma tabela de alocação de arquivos, esta tabela fica 
alocada em uma seção do disco no inicio de cada partição. A FAT tem 
uma entrada para cada bloco do disco e é indexada pelo número do 
bloco. A entrada da tabela, indexada pela entrada do arquivo no 
diretório, contém o número do bloco do próximo bloco no aquivo. 
Assim continua até o bloco que contém o identificador de fim de 
arquivo. Ao contrario da alocação por encadeamento a FAT não utiliza 
um espaço em cada bloco do disco como ponteiro (utiliza os blocos 
com valor igual a zero na tabela que representam blocos livres).
e) Em um sistema de arquivos usando uma FAT o que 
acontece se ocorrer a corrupção total da tabela de 
alocação de arquivos?
Se a tabela FAT (tabela 1) corromper, existe uma tabela 2 de backup 
usada pelo scandisk.
f) Como funciona a alocação de espaço indexada? Que 
problemas da alocação usando encadeamento ela tenta 
resolver?
A alocação indexada utiliza ponteiros, como a alocação por 
encadeamento, mas agora todos esses ponteiros são armazenados 
juntos em um bloco de índices. Cada arquivo possui seu próprio bloco 
de índices que é um array de endereços de blocos de disco. O 
diretório contém o endereço do bloco de índices, e a í-esima entrada 
do bloco de índices aponta para o í-esimo bloco do arquivo. Desta 
maneira é possível realizar com facilidade o acesso direto ao arquivo.
A alocação indexada tenta resolver o problema da falta de eficiência 
no acesso direto a arquivos, que ocorre quando se usa a alocação por 
encadeamento.
f) Dentro da alocação indexada quais são os mecanismos 
usados para guardar os índices?
A alocação indexada causa um desperdício de espaço em disco por 
conta do armazenamento do bloco de índices. Pois um bloco inteiro 
de índices deve ser armazenado para cada arquivo, mesmo que 
apenas um ou dois ponteiros sejam realmente utilizados. Para reduzir 
esse desperdício devem ser utilizados blocos de tamanho menor para 
armazenar os índices. Mas blocos menores limitam a indexação de 
grandes arquivos. Para resolver este problema alguns mecanismos 
são usados para guardar os índices. Eles são:
 - Esquema encadeado: Diversos blocos de índices encadeados, no 
caso, o ultimo endereço do bloco de índices é nulo (caso o bloco 
represente todo o arquivo)ou é um ponteiro para outro bloco de 
índices (para grandes arquivos).
 - Índice multinível: Um bloco de índices de primeiro nível aponta 
para um conjunto de blocos de índices de segundo nível, que por sua 
vez aponta para os blocos do arquivo. Esta abordagem poderia ser 
estendida para um terceiro ou quarto níveis dependendo do tamanho 
máximo de arquivo requerido.
 - Esquema combinado: Utiliza uma combinação dos dois esquemas 
anteriores.
g) O que são i-nodes? Em qual mecanimos de alocação 
indexada eles se enquadram?
I-node é o primeiro bloco encontrado quando se faz o acesso a um 
arquivo e consite em uma estrutura de dados que relaciona os 
atributos e os endereços em disco dos blocos do arquivo , este bloco 
de índice utiliza um mecanismo de alocação indexada do tipo 
combinada. Em geral utiliza-se um esquema onde os 12 primeiros 
ponteiros apontam para blocos diretos, ou seja, que contem dados do 
arquivo; os outros 3 ponteiros apontam para blocos indiretos. O 
primeiro ponteiro para um bloco indireto é o endereço de um bloco 
indireto simples (um bloco de índices que não contém dados, mas 
endereços de blocos que contêm dados). Depois existe um ponteiro 
para um bloco indireto duplo (contém o endereço de um bloco que 
contém os endereços de blocos que contêm ponteiros para os blocos 
de dados reais). O último ponteiro conteria o endereço de um bloco 
indireto triplo.
14. Considere um sistema com i-nodes com 15 ponteiros. 
Nestes i-nodes os 12 primeiros são usados para alocação 
direta; o 13 ponteiro para alocação simples indireta; o 14 
para alocação dupla indireta e o 15 para alocação tripla-
indireta. Considere ainda que cada bloco tem 512Kb. 
Como ficaria a estrutura de inodes para armazenar um 
arquivo de 129024 bytes (252 blocos)?
Pra salvar um arquivo de 252 blocos, no caso, seria os primeiros 12 
blocos do primeiro i-node ocupado, depois mais 15 blocos do i-node 
nível 1. Depois vem o i-node de nível 2, que ficaria os quinze níveis 
dele apontando cada um para um inode distinto, e cada i-node destes 
teria 15 blocos; Ou seja, mais 225 blocos, e totalizando 242 blocos, 
faltam 10. O i-node de nível 3 apontaria para um de nível dois, que 
usaria apenas um de seus apontadores, pra um de nível 1, que 
salvaria 10 blocos nele.
[] -> 1 bloco
[] -> 1 bloco
[] -> 1 bloco
[] -> 1 bloco
[] -> 1 bloco
[] -> 1 bloco
[] -> 1 bloco
[] -> 1 bloco
[] -> 1 bloco
[] -> 1 bloco
[] -> 1 bloco
[] -> 1 bloco
[] -> [] x15-> 12 blocos
[] -> [] x15-> [] x15 -> 225 blocos
[] -> [] x1 -> [] x1 -> [] x10 -> 10 blocos
No total você ocuparia 268 i-nodes
15. Qual a diferença de simbolic links e hard links? E 
como é a implentação de cada um? Como é feito o 
controle de remoção de arquivo em cada caso?
Existem dois conceitos de "links" no Unix, usualmente nomeadas de 
symbolic link e hard link.
Um hard link é exatamente um nome para o arquivo (E um arquivo 
pode ter vários nomes. Aquilo só é apaguado do disco somente 
quando o último nome é removido.)
Um symlink é totalmente diferente: é um pequeno arquivo especial 
que contém o nome de caminho. Assim, a ligação fraca pode apontar 
arquivos em diferentes sistemas de arquivos (talvez NFS montadas 
de diferentes máquinas), e não precisa de ponto para o arquivo 
existente atualmente. Quando acessado (com a chamada de sistema 
open ou stat, uma referência para o symlink é substituída pelo kernal 
do sistema operacional com uma referência para o arquivo nomeado 
no nome de caminho. (De qualquer forma, com rm ou unlink a 
ligação é removida, não o arquivo que ela aponta).
16. Considere um sistema onde o espaço livre é 
gerênciado por uma lista de espaço livre. Suponha que o 
ponteiro para a lista de espaços-livres foi perdido. Esta 
lista pode ser reconstruída? Explique sua resposta.
Uma possível solução seria veirificar todos os blocos utilizados pelos 
diretórios/arquivos/sistema e considerar os outros como livres.
Deve-se pensar no fato de que ao um arquivo ser deletado, não 
necessariamente os dados que ele tem são deletados nos blocos 
(geralmente que eu saiba não, é apenas deletado a ligação para ele). 
Então a solução de percorrer por todos os blocos e pegar os livres 
não funciona.
17. Quais são os métodos para gerênciamento de espaço 
livre em disco?
- Vetor de Bits (bitmap)
Cria um vetor onde cada posição corresponde a um bloco do disco, e 
possui valor 0 para livre e 1 para ocupado.
Vantagem: simplicidade e eficiência para encontrar o primeiro bloco 
livre.
Desvantagem: ineficiente ao menos que sejam mantido na memória 
principal (senão fica muito custoso o acesso repetidamente ao disco) 
e ocupa muito espaço
- Lista Encadeada
Desvantagem:para varrer a lista é preciso ler cada bloco
-Vetor de bits:
A lista de espaço livre é implementada como um mapa de bits ou um 
vetor de bits. Cada bloco é representado por 1 bit. Se o bloco estiver 
livre o bit será 1; se o bloco estiver alocado o bit será 0. A principal 
vantagem é que é relativamente simples e eficiente encontrar o 
primeiro bloco livre, ou n blocos livres consecutivos no disco.
Mas são ineficientes a não ser que todo o vetor seja mantido na 
memória principal.
-Lista Encadeada:
Encadear todos os blocos de disco livres, mantendo um ponteiro ao 
primeiro bloco livre em uma posição especial no disco e 
armazenando-os em cache na memória. Esse primeiro bloco contém 
um ponteiro ao próximo bloco livre de disco, e assim por diante.
Não é eficiente, para percorrer a lista, precisamos ler cada bloco, o 
que requer tempo substancial de I/O.
-Agrupamento:
Armazena os endereços de n blocos livres no primeiro bloco livre. Os 
primeiros n-1 desses blocos estão realmente livres. O bloco final 
contém os endereços de outros n blocos livres, e assim por diante. 
Assim os endereços de um grande número de blocos livres podem ser 
rapidamente encontrados.
-Contadores:
Em vez de manter uma lista de n endereços de disco livres, mantêm 
o endereço do primeiro bloco livre e o número n de blocos contíguos 
livres que seguem esse primeiro bloco. Cada entrada na lista de 
espaço livre consiste então em um endereço de disco e um 
contador.Embora cada entrada exija mais espaço que um endereço 
de disco simples, a lista global fica mais curta. Aproveita o fato de 
que em geral vários blocos contíguos podem ser alocados ou 
liberados simultaneamente.
18. Quais as estapas de um checkagem de consistência 
de um file system?
A verificação de consistência compara os dados na estrutura de 
diretório com os blocos de dados no disco e tenta corrigir quaisquer 
inconsistências encontradas. Os algoritmos de alocação e gerência de 
espaço livre determinam os tipos de problemas que o verificador 
poderá encontrar e qual será a taxa de sucesso na correção desses 
problemas. Um possível teste é verificar no número de hardlinks 
apontando para o inode.
19. Como funcionam os sistema de arquivos baseados em 
Journaling? Quais suas vantagem? O que tentam 
garantir?
Um sistema de arquivos com journaling dá permissão ao Sistema 
Operacional de manter um log (journal), de todas as mudanças no 
sistema de arquivos antes de escrever os dados no disco. 
Normalmente este log é um log circular alocado em uma área 
especial do sistema de arquivos. Por ser mais bem localizado em 
espaço menor costuma ter melhor desempenho também.
Este tipo de sistema de arquivos tem a oferecer uma melhor 
probabilidade de não sofrer corrupção de dados no caso de o sistema 
travar ou faltar energia, e uma recuperação mais rápida, pois não 
necessita verificar todo o disco, somente aqueles que pertenciam a 
um log que não fora fechado devidamente.
20. Explique os seguintes algoritmos de escalonamento 
de requisições de disco: FCSF, SSTF (Shortest-Seek First), 
SCAN, C-SCAN e LOOK.
FCSF atende as requisiçõesem fila, SSTF escolhe o endereço com 
menor deslocamento, e isso pode causa inanição.
Scan é o método elevador, o ponteiro do disco percorre de um lado 
para o outro atendendo as requisições. O C-SCAN é similar mas só 
funciona em um sentido e é melhor no tempo de resposta médio. O 
Look é como o SCAN é implementado na prática que não vai até o fim 
do disco mas só até o último endereço requisitado.
21. Quais sao os algoritmos de escalonamentos 
disponíveis atualmente do kernel Linux? Descreva cada 
um deles.
NOOP
É o escalonador de I/O mais simples do Linux. Ele insere todas as 
requisições de I/O é uma fila FIFO (First In First Out) não ordenada.
O escalonador assume que a otimização do desempenho de I/O será 
feito em alguma outra camada da hierarquia de I/O (por exemplo, no 
dispositivo de blocos, por um controlador RAID "inteligente" ou por 
um controlador externo como um subsistema de armazenamento 
(storage).
O NOOP é melhor para dispositivos de estado sólido (SSD - Solid 
State Devices) como memória flash ou, em linhas gerais, dispositivo 
que não dependam de movimento mecânico para acesso aos dados 
(como a tecnologia tradicional de "disco rígido" que depende do 
tempo de acesso - seek time - e da latência rotacional). Dispositivos 
não-mecânicos não necessitam de reordenamento de múltiplas 
requisições de I/O, uma técnica que agrupa as requisiçòes de I/O que 
estão fisicamente próximas no disco, dessa forma reduzindo o tempo 
médio de acesso e a variabililidade do tempo de "serviço" (pense em 
servir algo) de I/O.
ANTICIPATORY
O objetivo é aumentar a eficiência de utilização do disco 
"antecipando" operações de leitura síncrona.
"Deceptive idleness" é uma situação onde um processo parece ter 
terminado a leitura do disco quando na verdade está processando 
dados enquanto se prepara para a próxima operação de leitura. Isto 
fará com que um escalonador que procura reduzir trabalho mude 
para outro processo não relacionado. Esta situação é prejudicial à 
vazão de leituras síncronas, pois sobrecarrega o trabalho de "acesso". 
A solução do escalonador Anticipatory para o "Deceptive idleness" é 
fazer uma pausa por um pequeno tempo (alguns milisegundos) após 
uma operação de leitura em antecipação a outra requisição de leitura 
fisicamente próxima.
O Anticipatory pode reduzir o desempenho em discos usando TCQ 
(Tagged Command Queuing), discos de alto desempenho e conjuntos 
(arrays) RAID feitos via hardware. Este escalonador foi o padrão no 
Linux entre o kernel 2.6.0 e o 2.6.18, sendo substituído pelo CFQ.
DEADLINE
A principal meta deste escalonador é tentar garantir um tempo inicial 
para atender uma requisição. Ele faz isso impondo uma "deadline" 
em todas as operações de I/O para evitar "starvation" dos recursos. 
São mantidas duas filas de "deadline" além das filas ordenadas 
(ambas de leitura e escrita). As filas de "deadline" são minimamente 
ordenadas por seu tempo de expiração, enquanto que as filas 
ordenadas usam o número do setor para definir a ordem.
Antes de atender a próxima requisição, o Deadline decide qual fila 
usará. Filas de leitura recebem prioridade maior porque os processos 
usalmente "param" em operações de leitura. Em seguida, o 
escalonador verifica se a primeira requisição na fila "deadline" 
expirou, se não ele serve uma sequência de requisições da fila 
ordenada. Nos dois casos, o escalonador também serve uma 
sequência de requisições seguindo a requisição escolhida na fila 
ordenada.
Por padrão, as requisições de leitura expiram em 500ms, requisições 
de escrita em 5 segundos.
A documentação indica que este é o escalonador recomendado para 
sistemas de bancos de dados, especialmente em discos que 
trabalham com TCQ (Tagged Command Queuing) ou quaisquer 
sistemas com discos de alto desempenho.
CFQ (Completely Fair Queuing): 1 fila de I/O por processo, o 
objetivo é ser justo entre os processos.
O CFQ funciona colocando requisições síncronas enviadas pelos 
processos em uma certa quantidade de filas por-processo e então 
alocando espaços de tempo para que cada uma das filas acesse o 
disco. A quantidade de tempo e o número de requisições que uma fila 
pode enviar depende da prioridade de IO de um determinado 
processo.
Requisições assíncronas para todos os processos são processadas em 
conjunto em um número menor de filas que estão separadas por 
prioridade (uma fila por prioridade).
Embora o CFQ não faça explicitamente escalonamento de I/O 
anticipatório, ele atinge o mesmo efeito de ter boa vazão para o 
sistema como um todo, permitindo que uma fila de processo "não 
faça nada" (idle) ao final de um IO síncrono e, dessa forma, 
"antecipando" IOs próximos vindos do mesmo processo.
O CFQ pode ser considerado uma extensão natural da ação de 
conceder "fatias de tempo de IO" a um processo.
22. Compare RAID0, RAID1, RAID5 e RAID6.
RAID0 grava blocos espalhados pelo disco, o que dá baixa 
confiabilidade e alto desempenho. O espaço total é a soma de todos 
os discos.
RAID1 grava os blocos duplicados nos discos, garante alta 
confiabilidade e desempenho ruim. Em especial a escrita se tiver 1 
disco lento, fica tudo lento. Espaço total é o espaço de 1 disco.
RAID5 faz paridade dos blocos, para isso tem que ter ao menos 3 
discos. Com 1 bloco e a paridade (ou 2 blocos) é possível refazer o 
outro bloco. As paridades ficam espalhadas nos discos.
RAID6 2 Paridades. Podem falhar 2 discos e espaço é (n-2)*x
23. Suponha que você possui 4 discos rígidos de 750GB. 
Quanto espaço disponível você obteria usando RAID5 e 
quanto espaço você obteria com RAID6? Quantos discos 
poderiam falhar em cada um destes casos?
Com RAID5 para cada 2 blocos tem 1 bloco de paridade. Então, como 
os blocos estão espalhados, você teria 2000GB de espaço utilizável e 
1 disco podendo falhar. Com RAID6 teria 1 paridade a mais que dá 
(4-2)*750 = 1500GB de espaço utilzável, mas podendo falhar 2 
discos. 
Questão – Sistemas Operacionais – 
Escalonamento
Depois de espairecer um pouco com os mapas mentais sobre História do Egito e da Grécia, 
voltemos aos mapas mentais para concursos de TI.
Questão – FCC – DPE – SP – Agente de Defensoria – Analista de 
Sistemas /2010
tags: FCC, Agente de Defensoria, Analista de Sistemas, concursos 
TI, Sistemas Operacionais, Processos; Algoritmo de 
Escalonamento;
Os processos no sistema operacional que possuem um timer, chamado de quantum, onde 
todos os processos ganham o mesmo valor de quantum para rodarem na CPU, caracterizam o 
escalonamento de processos do tipo
a) RR – Round-Robin.
b) FIFO – First in, first out.
c) FCFS – First come, first served.
d) SJF – Shortest Job First.
e) SRT – Shortest Remaining Time.
Comentário
O Escalonamento permite que o Sistema Operacional faça o compartilhamento do CPU entre 
os os processos.
Os principais algoritmos de escolamento são os citados na questão.
Mapas Mentais
Mapas mental dos algoritmos de escalonamento
E agora o mapa mental do principal algoritmo de escalonamento – Roud-Robin. Neste 
algoritmo duas informações importantíssimas: Fatia de tempo (Timeslice/Quantum) e 
Preempitivo.
http://blog.mapasequestoes.com.br/mapa-mental-historia-do-egito/
Mapa Mental - Sistemas Operacionais - Escalonamento - Round-Robin
Gabarito: A
	Questão – Sistemas Operacionais – Escalonamento