Capítulo 9- Fundamentos de sistemas operacionais

Prévia do material em texto

Exercícios Práticos 
1 Sob que circunstâncias ocorrem erros de página? Descreva as ações realizadas pelo sistema 
operacional quando ocorre um erro de página. 
Uma falha de página ocorre quando acontece um acesso a uma página que não foi trazida para 
a memória principal. O sistema operacional verifica o acesso à memória, abortando o 
programa se o acesso for inválido. Se for válido, um quadro livre é localizado e a E/S é 
requisitada para ler a página necessária para o quadro livre. Ao terminar a E/S, a tabela de 
processos e a tabela de página são atualizadas e a instrução é reiniciada. 
 
2 Suponha que você tenha uma sequência de referências de página para um processo com m 
quadros (todos inicialmente vazios). A sequência de referências de página tem tamanho p, e nela 
ocorrem n números de página distintos. Responda a essas perguntas para qualquer algoritmo de 
substituição de páginas: 
a.O que é um limite inferior em relação ao número de erros de página? ​n 
b. O que é um limite superior em relação ao número de erros de página? ​p 
 
3 Considere a tabela de páginas mostrada na Figura 9.30 para um sistema com endereços virtuais e 
físicos de 12 bits e páginas de 256 bytes. A lista de quadros de páginas livres é D, E e F (isto é, D 
é a cabeça da lista, E é o segundo quadro e F é o último). 
Converta os endereços virtuais, a seguir, nos endereços físicos equivalentes em hexadecimais. Todos 
os números são dados em hexadecimal. (Um travessão para um quadro de página indica que a página 
não está em memória.) 
• 9EF = ​0EF 
• 111 = ​211 
• 700 = -00​ porém acontece algo q eu não sei, acho q meche com os espaços livres 
• 0FF= -FF ​porém acontece algo q eu não sei, acho q meche com os espaços livres 
 
 
4 Considere os algoritmos de substituição de páginas a seguir. Classifique esses algoritmos em uma 
escala de cinco pontos que vai de “ruim” a “perfeito” de acordo com sua taxa de erros de página. 
Separe os algoritmos que sofrem da anomalia de Belady dos que não são afetados por ela. 
a.Substituição LRU 
b. Substituição FIFO 
c. Substituição ótima 
d. Substituição da segunda chance 
Ordem Algoritmo Sobre da anomalia de Belady 
1 Ótimo não 
2 LRU não 
3 Segunda chance sim 
4 FIFO sim 
 
5 Discuta o suporte de hardware requerido para suportar a paginação por demanda. 
O suporte de hardware distingue entre as páginas que estão na memória e as páginas que estão 
no disco. Utiliza o esquema de bit válido/ inválido 
Bit válido: a página associada está na memória. 
Bit inválido: a página não é válida ou pode ser válida, mas não estar no disco. 
 
6 Um sistema operacional dá suporte a uma memória virtual paginada. O processador central tem 
um tempo de ciclo de 1 microssegundo. O acesso a uma página que não seja a página corrente 
tem o custo de 1 microssegundo adicional. As páginas têm 1.000 palavras, e o dispositivo de 
paginação é um tambor que gira a 3.000 rotações por minuto e transfere 1 milhão de palavras por 
segundo. As medidas estatísticas a seguir foram obtidas do sistema: 
● 1% de todas as instruções executadas acessava uma página diferente da página corrente. 
● Das instruções que acessavam outra página, 80% acessavam uma página que já estava na 
memória. 
● Quando uma nova página era requerida, a página substituída tinha sido modificada 50% das 
vezes. 
Calcule o tempo efetivo de instrução nesse sistema, supondo que o sistema esteja executando apenas 
um processo e que o processador fique ocioso durante as transferências executadas pelo tambor. 
 
7 Considere o array bidimensional A : 
int A[][] = new int[100][100]; 
em que A[0][0] está na locação 200 em um sistema de memória paginada com páginas de tamanho 
200. Um processo pequeno que manipula a matriz reside na página 0 (locações 0 a 199). 
Portanto,cada busca de instrução ocorrerá a partir da página 0. 
Para três quadros de páginas, quantos erros de página são gerados pelos seguintes loops de 
inicialização do array? Use a substituição LRU e suponha que o quadro de página 1 contenha o 
processo, e os outros dois estejam inicialmente vazios. 
a.for (int j = 0; j < 100; j++) 
for (int i = 0; i < 100; i++) 
A[i][j] = 0; 
50 
b. for (int i = 0; i < 100; i++) 
for (int j = 0; j < 100; j++) 
A[i][j] = 0; 
5000 
 
8 Considere a sequência de referências de página a seguir: 
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6. 
Quantos erros de página ocorreriam para os algoritmos de substituição abaixo, supondo a existência 
de um, dois, três, quatro, cinco, seis e sete quadros? Lembre-​se de que todos os quadros estão 
inicialmente vazios e, portanto, as primeiras páginas apresentarão um erro cada. 
• Substituição LRU 
• Substituição FIFO 
• Substituição ótima 
Número de frames LRU FIFO Ideal 
1 20 20 20 
2 18 18 15 
3 15 16 11 
4 10 14 8 
5 8 10 7 
6 7 10 7 
7 7 7 7 
 
9 Suponha que você queira usar um algoritmo de paginação que exija um bit de referência (como a 
substituição da segunda chance ou o modelo do conjunto de trabalho), mas o hardware não 
forneça um. Esquematize como você poderia simular um bit de referência, mesmo se um não 
fosse fornecido pelo hardware, ou explique por que não é possível fazer isso. Se for possível, 
calcule qual seria o custo. 
Você pode usar o bit válido/inválido no hardware para simular o bit de referência. 
Inicialmente, defina o bit como inválido. Na primeira referência, é gerada um trap para o 
sistema operacional. O sistema operacional definirá o bit de software como 1 e reiniciará o bit 
de válido/inválido como válido. 
10 Você inventou um novo algoritmo de substituição de páginas que você acha que pode ser ótimo. 
Em alguns casos de teste distorcidos, ocorre a anomalia de Belady. O novo algoritmo é ótimo? 
Explique sua resposta. 
Não. Um algoritmo ideal não sofrerá da anomalia de Belady porque, por definição, um al- 
goritmo ideal substitui a página que não será usada por mais tempo. A anomalia de Belady 
ocorre quando um algoritmo de substituição de página despeja uma página que será necessária 
no futuro imediato. Um algoritmo ideal não teria selecionado tal página. 
11 A segmentação é semelhante à paginação, mas usa “páginas” de tamanho variável. Defina dois 
algoritmos de substituição de segmentos, um baseado no esquema de substituição de páginas. 
● FIFO e o outro no esquema de substituição de páginas LRU. Lembre-​se de que, como os 
segmentos não têm o mesmo tamanho, o segmento que for selecionado para ser 
substituído pode ser muito pequeno para deixar locações consecutivas suficientes para o 
segmento requerido. Considere estratégias para sistemas em que os segmentos não 
possam ser relocados e estratégias para sistemas onde isso possa ocorrer. 
● FIFO. Encontre o primeiro segmento grande o suficiente para acomodar o segmento 
que chega. Se a relocação não for possível e nenhum segmento for grande o bastante, 
selecione umacombinação de segmentos cujas memórias são contíguas, que são “mais 
próximas do primeiro da lista” e que podem acomodar o novo segmento. Se a relocação 
for possível, reorganize a memória de modo que os primeiros N segmentos, grandes o 
suficiente para o segmento que chega, sejam contíguos na memória. Acrescente 
qualquer espaço restante à lista de espaço livre nos dois casos. LRU. Selecione o 
segmento que não foi usado pelo maior período de tempo e que seja grande o suficiente, 
acrescentando qualquer espaço restante à lista de espaço livre. Se nenhum segmento for 
grande o suficiente, selecione uma combinação dos segmentos “mais antigos” que 
estejam contíguos na memória (se a relocação não estiver disponível) e que sejam 
grandes o suficiente. Se a relocação estiver disponível, reorganize os N segmentos mais 
antigos para serem contíguos na memória e substitua-os pelo novo segmento. 
12 Considere um sistema de computação paginado por demanda em que o grau de 
multiprogramação esteja correntemente fixado em quatro. O sistema foi recentemente medido 
para determinar a utilização da CPU e do disco de paginação. Três resultados alternativos são 
mostrados abaixo. O que está ocorrendo em cada caso? O grau de multiprogramação pode ser 
aumentado para aumentar a utilização da CPU? A paginação está ajudando? 
a.13% de utilização da CPU; 97% de utilização do disco. ​Está ocorrendo o thrashing.abaixa a 
multiprogramaçao 
b. 87% de utilização da CPU; 3% de utilização do disco. ​A utilização de CPU é suficientemente 
alta para deixar as coisas como estão, um grau maior de multiprogramação. 
c. 13% de utilização da CPU; 3% de utilização do disco. ​Aumente o grau de multiprogramação. 
 
13 Temos um sistema operacional para um sistema de computação que usa registradores base e 
limite, mas modificamos a máquina para fornecer uma tabela de páginas. As tabelas de páginas 
podem ser definidas para simular registradores base e limite? Como elas podem ser definidas ou 
por que não podem sê​-lo? 
A tabela de página pode ser configurada para simular os registradores de base e limite des- 
de que a memória seja alocada em segmentos de tamanho fixo. Desse modo, a base de um 
segmento pode ser entrada na tabela de página e o bit de válido/inválido usado para indicar 
essa parte do segmento como residente na memória. Haverá algum problema com a 
fragmentação interna. 
Exercícios 
14 Suponha que um programa tenha acabado de referenciar um endereço na memória virtual. 
Descrevaum cenário em que cada uma das situações abaixo possa ocorrer. (Se esse cenário não 
puder ocorrer, explique por quê.) 
• Omissão do TLB sem erro de página - ​A omissão de TLB com nenhuma página falhada foi 
trazida para a memória, mas foi removido do TLB 
• Omissão de TLB com erro de página - ​falta de página e TLB ocorreu. 
• Sucesso do TLB sem erro de página - ​está na memória e no TLB. A maioria provavelmente uma 
referência recente. 
• Sucesso do TLB com erro de página - ​O sucesso do TLB e oerro na página não podem ocorrer. 
O TLB é um cache da página mesa. Se uma entrada não estiver na tabela de páginas, ela não 
estará no TLB. 
 
15 Uma visão simplificada de estados dos threads é Pronto, Em Execução e Bloqueado, em que um 
thread está pronto e esperando para ser incluído no schedule, está sendo executado no 
processador, ou está bloqueado (por exemplo, está esperando por I/O). Isso é ilustrado na Figura 
9.31. Supondo que um thread esteja no estado Em Execução, responda às perguntas a seguir e 
explique sua resposta: 
a. O thread mudará de estado se incorrer em um erro de página? Se mudar, para que estado passará? 
Em um erro de página, o estado da thread é configurado para bloqueado como uma operação 
de E/S que é necessário para levar a nova página à memória. 
 
b. O thread mudará de estado se gerar uma omissão do TLB que seja resolvida na tabela de páginas? 
Se mudar, para que estado passará? 
Na omissão do TLB, o segmento continua em execução se o endereço for resolvido na tabela de 
páginas. 
c.O thread mudará de estado se uma referência de endereço for resolvida na tabela de páginas? Se 
mudar, para que estado passará? 
A thread continuará a ser executado se o endereço for resolvido no tabela de páginas. 
 
16 Considere um sistema que use a paginação por demanda pura. 
a.Quando um processo inicia a sua execução pela primeira vez, como você caracterizaria a taxa de 
erros de página? 
Inicialmente bastante alto, pois as páginas necessárias ainda não foram carregadas na 
memória. 
 
b. Uma vez que o conjunto de trabalho de um processo seja carregado na memória, como você 
caracterizaria a taxa de erros de página? 
Deve ser bastante baixo, pois todas as páginas necessárias são carregadas em memória. 
 
c. Suponha que um processo altere sua localidade, e o tamanho do novo conjunto de trabalho seja 
grande demais para ser armazenado na memória livre disponível. Identifique algumas opções que 
os projetistas de sistemas poderiam selecionar para manipular essa situação. 
(1) Ignore isso; 
(2) obter mais memória física; 
(3) recuperar páginas mais agressivamente devido à alta taxa de erro da página. 
 
17 O que é o recurso de cópia​ após​ gravação, e sob que circunstâncias seu uso é benéfico? Que 
suporte de hardware é requerido para sua implementação? 
Quando dois processos acessam o mesmo conjunto de valores de programa (por exemplo, o 
segmento de código do binário de origem), então é útil mapear as páginas correspondentes para 
os espaços de endereço virtual de dois programas de forma protegida contra escrita. Quando 
uma escrita realmente acontecer, então uma cópia deve ser feita para permitir que os dois 
programas 
acesse individualmente as diferentes cópias sem interferir com cada de outros. O suporte de 
hardware necessário para implementar é simplesmente o seguinte: em cada acesso à memória, 
a tabela de páginas precisa ser consultada Para verificar se a página está protegida contra 
gravação. Se é realmente escrever protegido, uma armadilha ocorreria e o sistema operacional 
poderia resolver o problema. 
 
18 Determinado computador fornece a seus usuários um espaço de memória virtual de 2^32 bytes. O 
computador tem 2^18 bytes de memória física. A memória virtual é implementada por 
paginação, e o tamanho da página é de 4.096 bytes. Um processo de usuário gera o endereço 
virtual 11123456. Explique como o sistema estabelece a locação física correspondente. 
Diferencie operações de software e de hardware. 
O endereço virtual em formato binário é 
0001 0001 0001 0010 0011 0100 0101 0110 
Uma vez que o tamanho da página é 2^12, o tamanho da tabela da página é 2^20. Portanto, a 
ordem baixa 12 bits "0100 0101 0110" são usados como deslocamento para a página, enquanto 
os 20 bits restantes "0001 0001 0001 0010 0011" são usados como deslocamento na tabela de 
páginas. 
 
19 Suponha que tenhamos uma memória paginada por demanda. A tabela de páginas é mantida em 
registradores. São necessários 8 milissegundos para manipular um erro de página, se um quadro 
vazio está disponível ou se a página substituída não foi modificada, e20 milissegundos, se a 
página substituída foi modificada. O tempo de acesso à memória é de 100 nanossegundos. 
Suponha que a página a ser substituída seja modificada 70% das vezes. Qual é a taxa de erros 
de página máxima aceitável para um tempo efetivo de acesso de não mais do que 200 
nanossegundos? 
0.2 sec ​= ​(1 ​− ​P​) ​× ​0.1 ​_​sec + (0.3​P​) ​× ​8 millisec + (0.7​P​) ​× ​20 millisec 
0.1 ​= −​0​.​1​P ​+ 2400 ​P ​+ 14000 ​P 
0.1 ​= ​16,400 ​P 
P ​= ​0.000006 
 
20 Quando ocorre um erro de página, o processo que está solicitando a página deve ser bloqueado 
enquanto espera que a página seja trazida do disco para a memória física. Suponha que exista um 
processo com cinco threads de nível de usuário e que o mapeamento de threads de usuário para 
threads do kernel seja um​ para​um. Se um thread de usuário incorre em um erro de página ao 
acessar sua pilha, os outros threads de usuário pertencentes ao mesmo processo também seriam 
afetados pelo erro de página — isto é, eles também precisariam esperar que a página que gerou o 
erro seja trazida para a memória? Explique. 
Sim, porque há apenas um thread de kernel para todas as threads do usuário, que blocos de 
segmento do kernel enquanto espera que a erro de página seja resolvida. 
Uma vez que não há outros threads do kernel para os threads de usuário disponíveis, todos os 
outras threads de usuário no processo são afetados pelo erro de página. 
21 Considere a sequência de referências de página a seguir: 
7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0, 1. 
Supondo uma paginação por demanda com três quadros, quantos erros de página ocorreriam para os 
algoritmos de substituição a seguir? 
● Substituição LRU ​18 
● Substituição FIFO ​17 
● Substituição ótima ​13 
Eu, iranildo, aprendi isto: 21 e a 22. 
22 A tabela de páginas mostrada na Figura 9.32 é para um sistema com endereços virtuais e físicos 
de 16 bits e páginas de 4.096 bytes. O bit de referência é posicionado em 1 quando a página é 
referenciada. Periodicamente, um thread zera todos os valores do bit de referência. Um travessão 
para um quadro de página indica que a página não está em memória. O algoritmo de substituição 
de páginas é o LRU localizado, e todos os números são fornecidos em decimais. 
a.Converta os endereços virtuais a seguir (em hexadecimais) para os endereços físicos 
equivalentes. Você pode fornecer respostas em hexadecimal ou decimal. Posicione também o bit 
de referência da entrada apropriada na tabela de páginas. 
Auxilio, to pondo aqui, mas na prova não tem não: 
1 2 3 4 5 6 7 8 9 ​10 11 12 13 14 15 16 17 
1 2 3 4 5 6 7 8 9 ​A B C D E F G H 
• 0x​E​12C = ​converte o E de hexadecimal para decimal q dá 14-> olha na página o q tem no 14-> daí 
tem 3, então converte em hexadecimal, q dá 3 ​= 0x​3​12C 
• 0x​3​A9D = ​converte o 3 de hexadecimal para decimal q dá 3-> olha na página o q tem no 3-> daí tem 
10, então converte em hexadecimal, q dá A​ ​= 0x​A​A9D 
• 0x​A​9D9= ​converte o A de hexadecimal para decimal q dá 10-> olha na página o q tem no 10-> daí 
tem 5, então converte em hexadecimal, q dá 5 ​= ​0x​5​9D9 
• 0x​7​001= ​converte o 7 de hexadecimal para decimal q dá 7-> olha na página o q tem no 7-> daí tem 
15, então converte em hexadecimal, q dá F ​= ​0x​F​001 
• 0x​A​CA1 = ​converte o A de hexadecimal para decimal q dá 10-> olha na página o q tem no 10-> daí 
tem 5, então converte em hexadecimal, q dá 5 =​0x​5​CA1 
b.Usando os endereços acima como ponto de partida, forneça um exemplo de endereço lógico (em 
hexadecimal) que resulte em erro de página. 
As únicas opções são as páginas 4, 8, 12 e 13. Assim, os endereços de exemplo incluem qualquer 
coisa que comece com a seqüência hexadecimal ​0x4..., 0x8..., 0xC..., and 0xD.... 
c. Em que conjunto de quadros de página o algoritmo de substituição LRU fará uma seleção para 
resolver um erro de página? 
Quaisquer entradas de tabela de página que tenham um bit de referência de zero. Isso inclui os 
seguintes quadros {9, 1, 14, 13, 8, 0, 4} 
23 Suponha que você esteja monitorando a taxa segundo a qual o ponteiro do algoritmo do relógio 
se move. (O ponteiro indica a página candidata à substituição.) O que você pode dizer sobre o 
sistema se observar o comportamento a seguir: 
a.O ponteiro está se movendo rapidamente. 
Se o ponteiro estiver se movendo rapidamente, o programa acessará um grande número de 
páginas simultaneamente. É muito provável que durante o período entre o ponto em que o bit 
correspondente a uma página é desmarcado e é verificado novamente, a página é acessada 
novamente e, portanto, não pode ser substituído. Isso resulta em mais digitalização das páginas 
antes de uma vítima página é encontrada. 
b. O ponteiro está se movendo lentamente. 
Se o ponteiro estiver em movimento lento, o sistema de memória virtual está encontrando 
páginas candidatas para substituição extremamente eficiente, indicando que muitas das 
páginas residentes não estão sendo acessadas. 
 
24 Discuta situações em que o algoritmo de substituição de páginas menos​ frequentemente​ 
utilizadas (LFU) gere menos erros de página do que o algoritmo de substituição de páginas 
menos​ recentemente​ utilizadas (LRU). Discuta também sob que circunstâncias o oposto acontece. 
Considere a seguinte seqüência de acessos de memória em um sistema que pode armazenar 
quatro páginas na memória: 1 1 2 3 4 5 1. Quando a página 5 é acessada, o algoritmo de 
substituição de página com menos uso freqüente substituiria uma página diferente de 1 e, 
portanto, não ocorreria uma falha na página quando a página 1 é acessado novamente. Por 
outro lado, para a sequência "1 2 3 4 5 2," o algoritmo mais usado recentemente funciona 
melhor. 
 
25 Discuta situações em que o algoritmo de substituição de páginas mais​ frequentemente​ utilizadas 
(MFU) gere menos erros de página do que o algoritmo de substituição de páginas menos​ 
recentemente​utilizadas (LRU). Discuta também sob que circunstâncias o oposto acontece. 
Considere a seqüência em um sistema que contém quatro páginas na memória: 1 2 3 4 4 4 5 1. 
Os algoritmos de substituição de página mais utilizados com freqüência página 4 enquanto 
buscava a página 5, enquanto o algoritmo LRU destrói a página 1. Isso é improvável que 
aconteça muito na prática. Para a sequência "1 2 3 4 4 4 5 1, "o algoritmo LRU toma a decisão 
certa. 
 
26 O sistema VAX/VMS usa um algoritmo de substituição FIFO para páginas residentes e um pool 
de quadros livres de páginas recentemente utilizadas. Suponha que o pool de quadros livres seja 
gerenciado com o uso da política de substituição LRU. Responda as perguntas a seguir: 
a.Se um erro de página ocorrer e a página não existir no pool de quadros livres, como é gerado 
espaço livre para a página recém​ solicitada? 
Quando ocorre uma erro de página e se a página não existir no pool de quadro livre, então uma 
das páginas no pool de quadros livres é despejado em disco, criando espaço para que uma das 
páginas residentes seja mudou-se para o pool de quadros livres. A página acessada é então 
movida para o conjunto de residentes. 
b. Se um erro de página ocorrere a página existir no pool de quadros livres, como o conjunto de 
páginas residentes e o pool de quadros livres são gerenciados de modo a criar espaço para a página 
solicitada? 
Quando ocorre uma falha na página e se a página existe no quadro livre pool, então é movido 
para o conjunto de páginas residentes, enquanto um das páginas residentes são movidas para o 
pool de quadros livres. 
c. Para que estado o sistema degenerará se o número de páginas residentes for estabelecido em um? 
Quando o número de páginas residentes é definido como um, então o sistema degenera o 
algoritmo de substituição da página usado no Pool de quadro livre, que normalmente é 
gerenciado de forma LRU. 
 
d. Para que estado o sistema degenerará se o número de páginas no pool de quadros livres for zero? 
Quando o número de páginas no pool de quadros livres é zero, então o sistema degenera em um 
algoritmo de substituição de página FIFO. 
 
27 Considere um sistema de paginação por demanda com as seguintes medidas de tempo de 
utilização: 
Utilização da CPU 20% 
Disco de paginação 97,7% 
Outros dispositivos de I/O 5% 
 
Para cada uma das situações a seguir, diga se ela irá (ou poderá vir a) melhorar a utilização da 
CPU.Explique suas respostas. 
a.Instalação de uma CPU mais rápida. 
b. Instalação de um disco de paginação maior. 
c.Aumento do grau de multiprogramação.d. Diminuição do grau de multiprogramação. 
e. Instalação de mais memória principal. 
f. Instalação de um disco rígido mais rápido ou de múltiplos controladores com múltiplos discos 
rígidos. 
g. Adição da pré-​paginação aos algoritmos de busca de páginas. 
h. Aumento do tamanho da página. 
 
O sistema obviamente está gastando a maior parte do seu tempo paginando, indicando a 
sobrealocação de memória. Se o nível de multiprogramação for reduzido, processos residentes 
causariam falha de página com menos freqüência e a utilização da CPU melhoraria. Outra 
maneira de melhorar o desempenho seria obter mais memória física ou um tambor de 
paginação mais rápido. 
a. Instalar uma CPU mais rápida – Não. 
b. Instalar um disco de paginação maior – Não. 
c. Aumentar o grau de multiprogramação – Não. 
d. Diminuir o grau de multiprogramação – Sim. 
e. Instalar mais memória principal – Provavelmente melhora a utilização de CPU porque mais 
páginas podem permanecer residentes e não exigir paginação de ou para os discos. 
f. Instalar um disco rígido mais rápido ou múltiplos controladores com múltiplos discos rígidos. 
Também é uma melhoria, pois à medida que o gargalo do disco é removido pela resposta mais 
rápida e maior throughput para os discos, a CPU receberá mais dados mais rapidamente. 
g. Acrescentar a pré-paginação aos algoritmos de busca de página – Novamente, a CPU 
receberá mais dados mais rapidamente, de modo que será mais utilizada. Isso só acontece se a 
ação de paginação for favorável à pré-paginação (ou seja, se o acesso for seqüencial). 
h. Aumentar o tamanho da página – Aumentar o tamanho da página resultará em menos 
falhas de página se os dados estiverem sendo acessados seqüencialmente. Se o acesso aos dados 
for mais ou menos aleatório, pode haver mais ação de paginação, pois menos páginas podem 
ser mantidas na memória e mais dados são transferidos por falha de página. Assim, essa 
mudança tanto pode diminuir a utilização quanto aumentá-la. 
 
28 Suponha que um computador forneça instruções que possam acessar locações de memória 
usando o esquema de endereçamento indireto de um nível. Que sequência de erros de página 
ocorre quando todas as páginas de um programa estão correntemente não residentes e a primeira 
instrução do programa seja uma operação de carga de memória indireta? O que acontece quando 
o sistema operacional está usando uma técnica de alocação de quadros por processo e somente 
duas páginas sejam alocadas a esse processo? 
Os erros de página a seguir ocorrem: erro na página para acessar as instruções,um erro na 
página para acessar a localização da memória que contém um ponteiro para a localização da 
memória alvo e uma falha na página quando a memória alvo localizada é acessada. O sistema 
operacional gerará três páginas erradas com a terceira página que substitui a página que 
contém as instruções. 
Se a instrução precisa ser recuperada novamente para repetir a captura instruções, a sequência 
de falhas da página continuará indefinidamente. 
Se a instrução for armazenada em cache em um registro, ele poderá executar completamente 
após a falha da terceira página. 
 
29 Suponha que sua política de substituição (em um sistema paginado) seja examinar cada página 
regularmente e descartar a página se ela não tiver sido usada desde a última verificação. O que 
você ganharia e o que perderia usando essa política em vez da substituição LRU ou da segunda 
chance? 
Esse algoritmo poderia ser implementado com o uso de um bit de referência. Após cada exame, 
o bit é definido como zero; Regressar a um se a página for referenciada. O algoritmo 
selecionaria uma página arbitrária para substituição do conjunto de páginas não utilizadas 
desde o último exame. 
A vantagem desse algoritmo é a sua simplicidade - é preciso manter um outro tipo de bit de 
referência. A desvantagem deste algoritmo que ele ignora a localidade, usando apenas um curto 
período de tempo para determinar se deve descartar uma página ou não. Por exemplo, uma 
página pode ser parte do conjunto de trabalho de um processo, mas pode ser despejada porque 
não foi referenciada desde o último exame (ou seja, nem todas as páginas no conjunto de 
trabalho podem ser referenciadas entre os exames). 
30 Um algoritmo de substituição de páginas deve minimizar o número de erros de página. Podemos 
obter essa minimização distribuindo páginas muito usadas de modo uniforme por toda a 
memória, em vez de fazê​-las competir por um pequeno número de quadros de páginas. Podemos 
associar a cada quadro de página um contador do número de páginas associadas a esse quadro. 
Assim, para substituir uma página, podemos procurar o quadro de página com a menor contagem. 
a.Defina um algoritmo de substituição de páginas usando essa ideia básica. Resolva especificamente 
esses problemas: 
i. Qual é o valor inicial dos contadores? 
ii. Quando os contadores são incrementados? 
iii. Quando os contadores são decrementados? 
iv. Como a página a ser substituída é selecionada? 
Defina um algoritmo de substituição de página resolvendo os problemas de: 
i. Valor inicial dos contadores – 0. 
ii. Os contadores são aumentados – sempre que uma nova página é associada a esse quadro. 
iii. Quando os contadores são diminuídos – sempre que uma das páginas associadas a esse 
quadro não é mais exigida. 
iv. Como é selecionada a página a ser substituída – encontre um quadro com o menor contador. 
Use FIFO para desempatar. 
b. Quantos erros de página ocorrem em seu algoritmo para a sequência de referência, a seguir, com 
quatro quadros de páginas? 1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2. 
14 falhas de página. 
c.Qual é o número mínimo de erros de página de uma estratégia ótima de substituição de páginas, 
para a sequência de referênciada parte b com quatro quadros de páginas? 
11 falhas de página. 
 
31 Considere um sistema de paginação por demanda com um disco de paginação que tenha um 
tempo médio de acesso e de transferência de 20 milissegundos. Os endereços são traduzidos por 
meio de uma tabela de páginas na memória principal, com tempo de acesso de 1 microssegundo 
por acesso à memória. Portanto, cada referência feita à memória através da tabela de páginas 
exige dois acessos. 
Para melhorar esse tempo, adicionamos uma memória associativa que reduz o tempo de acesso a uma 
referência de memória se a entrada da tabela de páginas estiver na memória associativa. 
Suponha que 80% dos acessos sejam feitos na memória associativa e que, do restante, 10% 
(ou 2% do total) provoquem erros de página. Qual é o tempo de acesso efetivo à memória? 
tempo efetivo de acesso = (0,8) × (1 µsec) + (0,1) × (2 µsec) + (0,1) × (5002 µsec) 
= 501,2 µsec 
= 0,5 milissegundos 
32 Qual é a causa da atividade improdutiva (Thrashing)? Como o sistema a detecta? Uma vez que 
ela seja detectada, o que o sistema pode fazer para eliminar esse problema? 
O thrashing é causado pela falta de alocação do número mínimo de páginas exigidas por 
um processo, forçando-o a gerar falha de página continuamente. O sistema pode detectar o 
thrashing avaliando o nível de utilização de CPU comparado com o nível de multiprogramação. 
Ele pode ser eliminado reduzindo-se o nível de multiprogramação. 
 
33 É possível que um processo tenha dois conjuntos de trabalho, um representando dados e outro 
representando código? Explique. 
Sim, de fato, muitos processadores fornecem dois TLB por esse mesmo motivo. 
Por exemplo, o código que está sendo acessado por um processo pode reter o mesmo conjunto 
de trabalho por um longo período de tempo. No entanto, os dados que o código acessa podem 
mudar, refletindo assim uma alteração no conjunto de trabalho para acessos de dados. 
 
34 Considere o parâmetro Δ usado para definir a janela do conjunto de trabalho no modelo do 
conjunto de trabalho. Quando Δ é definido com um valor pequeno, qual é o efeito sobre a 
frequência de erros de página e o número de processos ativos (não suspensos) em execução 
corrente no sistema? Qual é o efeito quando Δ é definido com um valor muito alto? 
Quando ​Δ está configurado para um valor pequeno, o conjunto de páginas residentes para um 
processo pode ser subestimado, permitindo que um processo seja agendado mesmo que todas 
as suas páginas necessárias não sejam residentes. Isso pode resultar em uma grande 
quantidade de falhas na página. Quando ​Δ está configurado para um valor grande, o conjunto 
residente de um processo é superestimado e isso pode impedir que muitos processos sejam 
agendados, mesmo que as páginas necessárias sejam 
Residente.No entanto, uma vez que um processo está agendado, é improvável que gerar falhas 
na página, uma vez que o seu conjunto de residentes foi superestimado. 
35 Em um segmento de 1.024 KB, a memória é alocada com o uso do sistema de pares. Usando a 
Figura 9.359.26 como guia, desenhe uma árvore ilustrando como as solicitações de memória a 
seguir são alocadas: 
• Solicitação de 6 K 
• Solicitação de 250 bytes 
• Solicitação de 900 bytes 
• Solicitação de 1.500 bytes 
• Solicitação de 7 KB 
 
Em seguida, modifique a árvore de acordo com as liberações de memória a seguir. Execute a fusão 
sempre que possível: 
• Liberação de 250 bytes 
• Liberação de 900 bytes 
• Liberação de 1.500 bytes 
A alocação a seguir é feita pelo sistema Buddy: a solicitação de 240 bytes é atribuída a um 
segmento de 256 bytes. A solicitação de 120 bytes é atribuída a um segmento de 128 bytes, a 
solicitação de 60 bytes é atribuída a um segmento de 64 bytes e a solicitação de 130 bytes é 
atribuída a um segmento de 256 bytes. Após a atribuição, os seguintes tamanhos de segmento 
estão disponíveis: 64 bytes, 256 bytes, 1K, 2K, 4K, 8K, 16K, 32K, 64K, 128K, 256K e 512K. 
Após os lançamentos da memória, o único segmento em uso seria um segmento de 256 bytes 
contendo 130 bytes de dados. Os seguintes segmentos serão gratuitos: 256 bytes, 512 bytes, 1K, 
2K, 4K, 8K, 16K, 32K, 64K, 128K, 256K e 512K. 
 
36 Um sistema suporta threads de nível de usuário e de nível de kernel. O mapeamento nesse 
sistema é do tipo um ​para​ um (há um thread do kernel correspondente a cada thread de usuário). 
Um processo multithreaded é composto por (a) um conjunto de trabalho para o processo inteiro 
ou (b) um conjunto de trabalho para cada thread? Explique. 
Um conjunto de trabalho para cada segmento. Isso ocorre porque cada thread do kernel tem 
sua própria seqüência de execução, gerando assim sua seqüência de endereços única. 
 
37 O algoritmo de alocação de slabs usa um cache separado para cada tipo de objeto diferente. 
Supondo que haja um cache por tipo de objeto, explique por que esse esquema não escala bem 
com múltiplas CPUs. O que poderia ser feito para resolver esse problema de escalabilidade? 
Isso tem sido um problema com o alocador slab - escalabilidade fraca com várias CPUs. O 
problema vem de salvar o cache global quando ele está sendo acessado. Isso tem o efeito de 
serializar acessos de cache em sistemas multiprocessador. O Solaris abordou isso introduzindo 
um cache por CPU, em vez de uma única dor global. 
 
38 Considere um sistema que aloque páginas de diferentes tamanhos a seus processos. Quais são as 
vantagens de um esquema de paginação desse tipo? Que modificações no sistema de memória 
virtual fornecem essa funcionalidade? 
 
O programa pode ter um grande segmento de código ou usar matrizes de grande porte como 
dados. Essas partes do programa podem ser alocadas para páginas maiores, diminuindo as 
despesas gerais de memória associadas a uma tabela de páginas. 
O sistema de memória virtual teria que manter várias listas de páginas gratuitas para os 
diferentes tamanhos e também precisa ter um código mais complexo para a tradução de 
endereços para levar em consideração diferentes tamanhos de página.