Capítulo 8- Fundamentos de sistemas operacionais

Prévia do material em texto

Exercícios Práticos 
1 Cite duas diferenças entre endereços lógicos e físicos. 
Um endereço lógico não se refere a um endereço existente real, mas se refere a um endereço abstrato 
em um espaço de endereço lógico. Compare isso com um endereço físico que se refere a um endereço 
físico real na memória. Um endereço lógico é gerado pela CPU e traduzido para um endereço físico 
pela unidade de gerenciamento de memória (MMU). Portanto, os endereços físicos são gerados pela 
MMU. 
 
2 Considere um sistema em que um programa possa ser separado em duas partes: código e dados. A CPU 
sabe se deseja uma instrução (busca de instrução) ou dados (busca ou armazenamento de dados). 
Portanto, dois pares de registradores base limite são fornecidos: um para instruções e outro para dados. O 
par de registradores base​limite das instruções é automaticamente somente​de​leitura; 
assim, os programas podem ser compartilhados entre diferentes usuários. Discuta as vantagens e 
desvantagens desse esquema. 
A principal vantagem desse esquema é que ele é um mecanismo eficaz para o compartilhamento de 
código e dados. Por exemplo, somente uma cópia de um editor ou de um compilador precisa ser 
mantida na memória, e esse código pode ser compartilhado por todos os processos que precisam de 
acesso ao editor ou código do compilador. Outra vantagem é a proteção do código contra a 
modificação errônea. A única desvantagem é que o código e os dados precisam ser separados, o que 
normalmente é juntado em um código gerado pelo compilador. 
 
3 Por que os tamanhos de página são sempre potências de 2? 
Lembre-se de que a paginação é implementada dividindo-se um endereço em um número de página e 
deslocamento. É mais eficiente desmembrar o endereço em X bits de página e Y bits de deslocamento, 
em vez de realizar a aritmética sobre o endereço para calcular o número de página e deslocamento. 
Como cada posição de bit representa uma potência de 2, a divisão de um endereço entre os bits resulta 
em um tamanho de página que é uma potência de 2. 
 
4 Considere um espaço de endereçamento lógico de 64 páginas de 1.024 palavras cada uma, mapeado para 
uma memória física de 32 quadros. 
a. Quantos bits há no endereço lógico? ​13 bits 
b. Quantos bits há no endereço físico? ​15 bits 
 
5 Qual é o efeito de permitir que duas entradas em uma tabela de páginas apontem para o mesmo quadro de 
páginas na memória? Explique como esse efeito poderia ser usado para diminuir o período de tempo 
necessário à cópia de um grande montante de memória de um lugar para outro. Que efeito a atualização 
de algum byte em uma página teria na outra página? 
Permitindo que duas entradas em uma tabela de página apontem para o mesmo frame de página na 
memória, os usuários podem compartilhar código e dados. Se o código for reentrante, pode ser 
economizado muito espaço na memória através do uso compartilhado de grandes programas, como 
editores de texto, compiladores e sistemas de banco de dados. A “cópia” de grandes quantidades de 
memória poderia ser efetuada por meio de diferentes tabelas de página apontando para o mesmo local 
da memória. 
Porém, o compartilhamento de código não reentrante ou dados significa que qualquer usuário tendo 
acesso ao código poderá modificá-lo, e essas modificações seriam refletidas na “cópia” do outro 
usuário. 
 
6 Descreva um mecanismo pelo qual um segmento poderia pertencer ao espaço de endereçamento de dois 
processos diferentes. 
Como as tabelas de segmento são uma coleção de registradores de limite de base, os segmentos podem 
ser compartilhados quando as entradas na tabela de segmento de duas tarefas diferentes apontarem 
para o mesmo local físico. As duas tabelas de segmento precisam ter ponteiros de base idênticos, e o 
número do segmento compartilhado precisa ser o mesmo nos dois processos. 
 
7 O compartilhamento de segmentos entre processos, sem a exigência de que eles tenham o mesmo número 
de segmento, é possível em um sistema de segmentação vinculado dinamicamente. 
a. Defina um sistema que permita a vinculação estática e o compartilhamento de segmentos sem 
demandar que os números dos segmentos sejam iguais. 
b. Descreva um esquema de paginação que permita que as páginas sejam compartilhadas sem 
requerer que os números das páginas sejam iguais. 
Esses dois problemas se reduzem a um programa sendo capaz de referenciar seu próprio código e seus 
dados sem conhecer o número de segmento ou página associado ao endereço. O MULTICS solucionou 
esse problema associando quatro registradores a cada processo. Um registrador tinha o endereço do 
segmento de programa atual, outro tinha um endereço de base para a pilha, outro tinha um endereço 
de base para os dados globais, e assim por diante. A idéia é que todas as referências têm de ser 
indiretas, através de um registrador que é mapeado para o segmento ou número de página atual. 
Alterando esses registradores, o mesmo código pode ser executado para diferentes processos sem a 
mesma página ou números de segmento. 
 
8 No IBM/370, a proteção à memória é fornecida pelo uso de ​chaves​. Uma chave é um valor de 4 bits. 
Cada bloco de memória de 2 K tem uma chave (a chave de armazenamento) associada a ele. A CPU 
também tem uma chave (a chave de proteção) associada a ela. Uma operação de armazenamento é 
permitida somente se as duas chaves são iguais ou se seu valor é zero. Quais dos esquemas de 
gerenciamento da memória a seguir poderiam ser usados com sucesso com esse hardware? 
a. Máquina crua ​Proteção desnecessária, define chave do sistema como 0. 
b. Sistema monousuário ​Define chave do sistema como 0 quando estiver no modo supervisor. 
c. Multiprogramação com um número fixo de processos ​Tamanhos de região precisam ser 
fixados em incrementos de 2Kbytes, aloca chave com blocos de​ ​memória. 
d. Multiprogramação com um número variável de processos ​Tamanhos de região precisam ser 
fixados em incrementos de 2Kbytes, aloca chave com blocos de​ ​memória. 
e. Paginação ​Tamanhos de frame precisam ser em incrementos de 2Kbytes, aloca chave com 
páginas. 
f. Segmentação ​Tamanhos de segmento precisam ser em incrementos de 2Kbytes, aloca chave 
com segmentos. 
Exercícios 
9 Explique a diferença entre fragmentação interna e externa. 
A fragmentação interna é a área em uma região ou em uma página que não é usada pela tarefa 
ocupando essa região ou página. Esse espaço está indisponível para uso pelo sistema até que essa tarefa 
tenha terminado e a página ou região seja liberada. 
 
10 Considere o processo a seguir para a geração de binários. Um compilador é usado para gerar o código 
objeto dos módulos individuais, e um linkage editor é usado para combinar vários módulosobjeto em um 
único binário de programa. Como o linkage editor altera a vinculação de instruções e dados a endereços 
da memória? Que informações precisam ser passadas do compilador ao linkage editor para facilitar as 
tarefas de vinculação da memória do linkage editor? 
O editor de ligação precisa substituir os endereços simbólicos não resolvidos com osendereços reais 
associados às variáveis no binário final do programa. Para realizar isso, os módulos devem 
acompanhar as instruções que se referem a símbolos não resolvidos. Durante a ligação, cada módulo 
recebe uma seqüência de endereços no binário geral do programa e, quando isso foi executado, as 
referências não resolvidas aos símbolos exportados por este binário podem ser corrigidas em outros 
módulos, pois todos os outros módulos contêm a lista de instruções que precisam ser Ser corrigido. 
 
11 Dadas seis partições de memória de 300 KB, 600 KB, 350 KB, 200 KB, 750 KB e 125 KB (em ordem), 
como os algoritmos do primeiro apto, do mais apto e do menos apto colocariam processos de tamanhos 
115 KB, 500 KB, 358 KB, 200 KB e 375 KB (em ordem)? Classifique os algoritmos em termos da 
eficiência com que usam a memória. 
A. Primeiro ajuste: 
B. 115 KB é colocado em partição de 300 KB, deixando (185 KB, 600 KB, 350 KB, 
200 KB, 750 KB, 125 KB) 
C. 500 KB é colocado em partição de 600 KB, deixando (185 KB, 100 KB, 350 KB, 
200 KB, 750 KB, 125 KB) 
D. 358 KB é colocado em partição de 750 KB, deixando (185 KB, 100 KB, 350 KB, 
200 KB, 392 KB, 125 KB) 
E. 200 KB é colocado em partição de 350 KB, deixando (185 KB, 100 KB, 150 KB, 
200 KB, 392 KB, 125 KB) 
F. 375 KB é colocado em partição 392 KB, deixando (185 KB, 100 KB, 150 KB, 
200 KB, 17 KB, 125 KB) 
G. Melhor ajuste: 
H. 115 KB é colocado em partição de 125 KB, deixando (300 KB, 600 KB, 350 KB, 
200 KB, 750 KB, 10 KB) 
Eu. 500 KB é colocado em partição de 600 KB, deixando (300 KB, 100 KB, 350 KB, 
200 KB, 750 KB, 10 KB) 
J. 358 KB é colocado em partição de 750 KB, deixando (300 KB, 100 KB, 350 KB, 
200 KB, 392 KB, 10 KB) 
K. 200 KB é colocado em partição de 200 KB, deixando (300 KB, 100 KB, 350 KB, 0 
KB, 392 KB, 10 KB) 
eu. 375 KB é colocado em partição 392 KB, deixando (300 KB, 100 KB, 350 KB, 0 
KB, 17 KB, 10 KB) 
M. Pior ajuste: 
N. 115 KB é colocado em partição de 750 KB, deixando (300 KB, 600 KB, 350 KB, 
200 KB, 635 KB, 125 KB) 
O. 500 KB é colocado em partição de 635 KB, deixando (300 KB, 600 KB, 350 KB, 
200 KB, 135 KB, 125 KB) 
P. 358 KB é colocado em uma partição de 600 KB, deixando (300 KB, 242 KB, 350 KB, 
200 KB, 135 KB, 125 KB) 
Q. 200 KB é colocado em partição de 350 KB, deixando (300 KB, 242 KB, 150 KB, 
200 KB, 135 KB, 125 KB) 
R. 375 KB devem aguardar 
Neste exemplo, apenas o pior ajuste não permite que um pedido seja satisfeito. 
Poder-se-ia argumentar que o melhor ajuste é mais eficiente, pois deixa o 
Maiores buracos após a alocação. No entanto, as corridas de melhor ajuste no momento O (n) e 
O primeiro ajuste é executado em tempo constante O (1). 
 
12 A maioria dos sistemas permite que um programa aloque mais memória para o seu espaço de 
endereçamento durante a execução. A alocação de dados nos segmentos de programas do heap é um 
exemplo desse tipo de alocação de memória. O que é necessário para suportar a alocação dinâmica de 
memória nos seguintes esquemas? 
a. Alocação de memória contígua. ​Alocação de memória contígua: pode exigir a deslocalização 
de todo o programa, uma vez que não há espaço suficiente para o programa aumentar o 
espaço de memória alocado. 
b. Segmentação pura. ​Segmentação pura: também pode exigir a deslocalização do segmento 
que precisa ser estendido, uma vez que não há espaço suficiente para o segmento aumentar 
seu espaço de memória alocado. 
c. Paginação pura. ​Paginação pura: a alocação incremental de novas páginas é possível neste 
esquema sem exigir a deslocalização do espaço de endereço do programa. 
 
13 Compare os esquemas de alocação contígua, segmentação pura e paginação pura para a organização da 
memória em relação às questões a seguir: 
a. Fragmentação externa 
b. Fragmentação interna 
c. Possibilidade de compartilhar código entre processos 
O esquema contíguo de alocação de memória sofre de fragmentação externa, pois os espaços de 
endereço são alocados de forma contígua e os furos se desenvolvem à medida que os processos antigos 
morrem e novos processos são iniciados. Ele também não permite que os processos compartilhem 
código, uma vez que o segmento de memória virtual de um processo não é dividido em segmentos de 
grãos finos não contíguos. A segmentação pura também sofre de fragmentação externa à medida que 
um segmento de um processo é colocado de forma contígua na memória física e a fragmentação 
ocorreria quando segmentos de processos mortos são substituídos por segmentos de novos processos. A 
segmentação, no entanto, permite que os processos compartilhem o código; Por exemplo, dois 
processos diferentes poderiam compartilhar um segmento de código, mas segmentos de dados 
distintos. A paginação pura não sofre de fragmentação externa, mas sofre de fragmentação interna. Os 
processos são alocados na granularidade da página e se uma página não é completamente utilizada, ela 
resulta em fragmentação interna e um desperdício correspondente de espaço. A paginação também 
permite que os processos compartilhem código na granularidade das páginas. 
 
14 Em um sistema com paginação, um processo não pode acessar memória que ele não possui. Por quê? 
Como o sistema operacional poderia permitir o acesso a outras memórias? Por que ele deveria ou não 
fazer isso? 
Um endereço em um sistema de paginação é um número de página lógico e um deslocamento. A página 
física é encontrada com a pesquisa de uma tabela com base no número de página lógico, para produzir 
um número de página físico. Como o sistema operacional controla o conteúdo dessa tabela, ele pode 
limitar um processo a acessar apenas as páginas físicas alocadas ao processo. 
Não existe um meio de um processo se referir a uma página que não possui, pois a página não estará 
na tabela de página. Para permitir tal acesso, um sistema operacional simplesmente precisa permitir 
que as entradas para a memória que não a do processo, sejam incluídas na tabela de página do 
processo. Isso é útil quando dois ou mais processos precisam trocar dados – eles simplesmente lêem e 
escrevem nos mesmos endereços físicos (que podem estar em endereços lógicos variáveis). Isso gera 
uma comunicação entre processos muito eficiente. 
15 Explique por que sistemas operacionais móveis como o iOS e o Android não suportam permuta. 
Existem três razões: Primeiro, é que esses dispositivos móveis normalmente usam memória flash com 
capacidade limitada e a troca é evitada devido a essa restrição de espaço. Em segundo lugar, a 
memória flash pode suportar um número limitado de operações de gravação antes de se tornar menos 
confiável. Por fim, tipicamente o rendimento é fraco entre main memory e memória flash. 
16 Embora o Android não suporte a permuta em seu disco de inicialização, é possível definir um espaço de 
permuta usando uma placa de memória SD não volátil separada. Por que o Android não permite a 
permuta em seu disco de inicialização mas a permite em um disco secundário? 
Principalmente porque o Android não deseja que seu disco de inicialização seja usado como espaço de 
troca pelos motivos delineados na pergunta anterior - o disco de inicialização tem capacidade de 
armazenamento limitada. No entanto, o Android suporta trocas, é só que os usuários devem fornecer 
seupróprio cartão SD separado para o espaço de troca. 
17 Compare a paginação com a segmentação no que diz respeito a quanto de memória é requerido para que 
as estruturas de tradução de endereços convertam endereços virtuais em endereços físicos. 
Paging requer mais gastos gerais de memória para manter as estruturas de tradução. A segmentação 
requer apenas dois registros por segmento: um para manter a base do segmento e o outro para manter 
a extensão do segmento. Pagar, por outro lado, requer uma entrada por página, e essa entrada fornece 
o endereço físico em que a página está localizada. 
18 Explique por que os identificadores de espaços de endereçamento (ASIDs) são usados. 
ASIDs fornecem proteção de espaço de endereço no TLB, além de suportar entradas TLB para vários 
processos diferentes, ao mesmo tempo. 
19 Os programas binários em muitos sistemas são tipicamente estruturados como descrito a seguir. O código 
é armazenado começando com um pequeno endereço virtual fixo, como 0. O segmento de código é 
seguido pelo segmento de dados que é usado para armazenar as variáveis do programa. Quando o 
programa começa a ser executado, a pilha é alocada na outra extremidade do espaço de endereçamento 
virtual e pode crescer em direção a endereços virtuais menores. Qual é a importância dessa estrutura para 
os seguintes esquemas? 
a. Alocação de memória contígua 
b. Segmentação pura 
c. Paginação pura 
1) A atribuição de memória contida exige que o sistema operacional aloque toda a extensão do espaço 
de endereço virtual para o programa quando ele começa a ser executado. Isso pode ser muito maior do 
que os requisitos reais de memória do processo. 
2) A segmentação pura dá a flexibilidade do sistema operacional para atribuir uma pequena extensão 
a cada segmento no tempo de inicialização do programa e estender o segmento, se necessário. 
3) A paginação pura não exige que o sistema operacional alimente a extensão máxima do espaço de 
endereço virtual para um processo no momento da inicialização, mas ainda exige que o sistema 
operacional aloque uma tabela de página grande que abranja todo o espaço de endereço virtual do 
programa. Quando um programa precisa expandir a pilha ou o heap, ele precisa alocar uma nova 
página, mas a entrada da tabela de página correspondente é pré-atribuída. 
 
20 Supondo um tamanho de página de 1 KB, quais são os números e deslocamentos de página para as 
referências de endereço a seguir (fornecidas como números decimais): 
a. 3085 ​page (Número da página) = 3; offset (deslocamento) = 13 
b. 42095​ page = 41; offset = 111 
c. 215201 ​page = 210; offset = 161 
d. 650000 ​page = 634; offset = 784 
e. 2000001 ​page = 1953; offset = 129 
 
21 O sistema operacional BVT tem um endereço virtual de 21 bits, mas, em certos dispositivos embutidos, 
ele tem apenas um endereço físico de 16 bits. Ele também tem um tamanho de página de 2 KB. Quantas 
entradas existem em cada uma das opções a seguir? 
a. Uma tabela de páginas convencional com um único nível 
Tabela de página convencional de nível único terá 210 = 1024 entradas. 
b. Uma tabela de páginas invertida 
A tabela de página invertida terá 25 = 32 entradas. 
 
22 Qual é o montante máximo de memória física? ​216 = 65536 (or 64-KB.) 
23 Considere um espaço de endereçamento lógico de 256 páginas com um tamanho de página de 4 KB, 
mapeado para uma memória física de 64 quadros. 
a. Quantos bits são requeridos no endereço lógico?​ 12 + 8 = 20 bits. 
b. Quantos bits são requeridos no endereço físico? ​12 + 6 = 18 bits. 
 
24 Considere um sistema de computação com um endereço lógico de 32 bits e tamanho de página de 4 KB. 
O sistema suporta até 512 MB de memória física. Quantas entradas haveria em cada um dos itens a 
seguir? 
a. Uma tabela de páginas convencional com um único nível. ​220 entries. 
b. Uma tabela de páginas invertida. ​512 K K/4K = 128K entries. 
 
25 Considere um sistema de paginação com a tabela de páginas armazenada na memória. 
a. Se uma referência à memória leva 50 nanossegundos, quanto tempo leva uma referência à 
memória paginada? 
400 nanossegundos; 200 nanossegundos para acessar a tabela de página e 200 nanossegundos para 
acessar a palavra na memória. 
b. Se adicionarmos TLBs, e 75% de todas as referências à tabela de páginas estiverem nos TLBs, 
qual será o tempo efetivo de referência à memória? (Suponha que para encontrar uma entrada da 
tabela de páginas nos TLBs sejam necessários 2 nanossegundos, se a entrada estiver presente.) 
Tempo de acesso efetivo = 0,75 × (200 nanossegundos) + 0,25 × (400 nanossegundos) = 250 
nanossegundos. 
 
26 Por que a segmentação e a paginação são, às vezes, combinadas em um esquema? 
A segmentação e a paginação normalmente são combinadas a fim de melhorar ambas. A paginação 
segmentada é útil quando a tabela de página se torna muito grande. Uma grande seção contígua da 
tabela de página que não é usada pode ser encolhida para uma única entrada da tabela de segmento, 
com um endereço de tabela de página igual a zero. A segmentação paginada trata do caso em que 
existem segmentos muito longos, que exigem muito tempo para alocação. Paginando os segmentos, 
reduzimos a memória desperdiçada devido à fragmentação externa, além de simplificar a alocação. 
 
27 Explique por que o compartilhamento de um módulo reentrante é mais fácil quando é usada a 
segmentação em vez da paginação pura. 
Como a segmentação é baseada em uma divisão lógica da memória, e não física, os segmentos de 
qualquer tamanho podem ser compartilhados com apenas uma entrada nas tabelas de segmento de 
cada usuário. Com a paginação, é preciso haver uma entrada comum nas tabelas de página para cada 
página que é compartilhada. 
28 Considere a tabela de segmentos a seguir: 
Segmento Base Tamanho 
0 219 600 
1 2300 14 
2 90 100 
3 1327 580 
4 1952 96 
 
Quais são os endereços físicos para os seguintes endereços lógicos? 
1. 0,430 ​219 + 430 = 649 
2. 1,10 ​2.300 + 10 = 2.310 
3. 2.500 ​Referência ilegal, intercepta para o sistema operacional 
4. 3.400 ​1.327 + 400 = 1.727 
5. 4.112 ​Referência ilegal, intercepta para o sistema operacional 
 
29 Qual é a finalidade da paginação das tabelas de páginas? 
Em certas situações, a paginação de tabela podem tornar-se suficientemente grandes para que 
paginação das tabelas de página, pode-se simplificar o problema de alocação de memória (assegurando 
que tudo seja alocado como páginas de tamanho fixo em oposição a pedaços de tamanho variável) e 
também permitir o intercâmbio de Porções de paginação de tabela que não são usadas atualmente. 
30 Considere o esquema de paginação hierárquica usado pela arquitetura VAX. Quantas operações de 
memória são executadas quando um programa de usuário executa uma operação de carga na memória? 
Quando uma operação de carga de memória é executada, existem três operações de memória que 
podem ser executadas. Uma é traduzir a posição onde a entrada da tabela de página para a página 
pode ser encontrada (uma vez que as próprias tabelas de páginas são paginadas). O segundo acesso é 
acessar a entrada da tabela de página em si, enquanto o terceiro acesso é a operação de carga de 
memória real. 
31 Compareo esquema de paginação segmentada com o esquema de tabelas de páginas com hash para a 
manipulação de grandes espaços de endereçamento. Sob que circunstâncias um esquema é preferível ao 
outro? 
Quando um programa ocupa apenas uma pequena porção do seu grande espaço de endereço virtual, 
uma tabela de página hash pode ser preferida por seu tamanho menor. A desvantagem com as tabelas 
de página hashed é o problema que surge devido a conflitos no mapeamento de várias páginas na 
mesma entrada da tabela de página hash. Se muitas páginas se mapearem para a mesma entrada, 
então, percorrendo a lista correspondente a essa entrada da tabela de hash pode ter uma sobrecarga 
significativa; Essas despesas gerais são mínimas no esquema de paginação segmentado, onde cada 
entrada na tabela de página mantém informações sobre apenas uma página. 
32 Considere o esquema de tradução de endereços da Intel mostrado na ​Figura 8.22​. 
a. Descreva todos os passos executados pelo Intel Pentium na tradução de um endereço lógico para 
um endereço físico. ​O seletor é um índice na tabela de descritor de segmento. O resultado do 
descritor de segmento mais o deslocamento original é usado para produzir um endereço 
linear com um diretório, página e deslocamento. O diretório é um índice em um diretório de 
página. A entrada do diretório da página seleciona a tabela de páginas e o campo da página 
é um índice na tabela de páginas. A entrada da tabela de página, além do deslocamento, é o 
endereço físico. 
b. Quais as vantagens, para o sistema operacional, de um hardware que forneça essa complicada 
tradução de memória? ​Esse mecanismo de tradução de página oferece flexibilidade para 
permitir que a maioria dos sistemas operacionais implementem seu esquema de memória 
em hardware, em vez de ter que implementar algumas partes em hardware e alguns em 
software. Porque pode ser feito em hardware, é mais eficiente (e o kernel é mais simples). 
c. Existe alguma desvantagem nesse sistema de tradução de endereços? Se houver, quais são elas? 
Se não houver, por que esse esquema não é usado por todos os fabricantes? ​A tradução de 
endereços pode levar mais tempo devido às pesquisas de várias tabelas que podem invocar. 
Caches ajuda, mas ainda haverá falta de cache. 
Problemas de Programação 
33 Suponha que um sistema tenha um endereço virtual de 32 bits com um tamanho de página de 4 KB. 
Escreva um programa em C que receba um endereço virtual (em decimal) na linha de comando e faça​o 
exibir o número e o deslocamento de página do endereço dado. Como exemplo, seu programa seria 
executado assim: 
./a. out 1998 
E exibiria: 
The address 19986 contains: 
page number = 4 offset 
= 3602 
Escrever esse programa demandará o uso do tipo de dado apropriado para armazenar 32 bits. 
Encorajamos você a usar tipos de dados ​unsigned​.