Sistemas de Operação
Licenciatura em Engenharia Informática
Exame de Época Especial – 04/09/2006 – Duração: 3h00m
Nome:
Total de páginas: 10+
Número:
páginas
E-mail:
• Prova sem consulta.
• A interpretação do enunciado faz parte da avaliação. Explicite nas suas respostas todas as hipóteses
assumidas.
• A indicação do email é opcional, mas se o fizer, por favor, indique-o de forma bem legível.
• O tempo é limitado a 3 horas. Quando este terminar, por favor entregue imediatamente a prova a
um dos vigilantes.
• Tanto a questão 5 como a questão 10 têm ambas duas alíneas. Em cada uma delas deve resolver
apenas uma das alíneas à sua escolha e inutilizar (riscar) a alínea que não respondeu!
Resumo da classificação:
Q-1 [1.5] =
Q-3 d) [0.5] =
Q-8 [1.5] =
Q-12 a) [1.5] =
Q-2 a) [0.5] =
Q-4 a) [0.5] =
Q-9 [1.5] =
Q-12 b) [1.0] =
Q-2 b) [0.5] =
Q-4 b) [0.5] =
Q-10 [1.5] =
Q-12 c) [0.5] =
Q-3 a) [0.5] =
Q-5 [1.5] =
Q-11 a) [0.5] =
Q-13 [2.0] =
Q-3 b) [0.5] =
Q-6 [1.0] =
Q-11 b) [0.5] =
Q-3 c) [0.5] =
Q-7 [1.0] =
Q-11 c) [0.5] =
Q-1 [1.5 val.] Comente a seguinte frase: “A política de escalonamento FIFO não se adequa às
exigências dos sistemas interactivos, pelo que é raramente utilizado nos S.O. generalistas actuais”.
Q-2 Considere as seguintes políticas de escalonamento, no que se refere ao valor do quantum Q
atribuído aos processos:
i) Q é fixo e idêntico para todos os processos.
ii) Q é variável e idêntico para todos os processos.
iii) Q é fixo mas único a cada processo.
iv) Q é variável e único a cada processo.
a) [0.5 val.] Ordene as políticas de escalonamento acima por ordem crescente do seu overhead na
troca de contexto em tempo de execução. (É apenas necessário indicar a ordem, mais nada!)
b) [0.5 val.] Ordene as políticas de escalonamento acima por ordem crescente da adaptabilidade do
tempo de resposta a variações na carga global do sistema. (É apenas necessário indicar a ordem,
mais nada!)
Q-3 Um processo que corra no S.O. Linux, quando não está a executar, está bloqueado/suspenso
num de vários estados possíveis. Para cada um dos estados “pronto (ready)”, “bloqueado (blocked)”,
“suspenso-pronto (suspended-ready)” e “suspenso-bloqueado (suspended-blocked)”, indique:
a) [0.5 val.] Como o processo foi parar a esse estado?
b) [0.5 val.] É possível, e se sim, é provável, que um processo fique indefinidamente bloqueado nesse
estado?
2
c) [0.5 val.] Que eventos podem fazer o processo transitar desse estado para outro (e qual o novo
estado)?
d) [0.5 val.] Assuma que o escalonador de processos tem um erro (bug) que originou que o PCB
(Process Control Block) de um processo aparecesse duas vezes na fila de prontos. Algumas das
implicações deste erro serão de gravidade baixa/moderada enquanto outras serão de gravidade
elevada. Apresente, justificando, uma implicação de cada tipo!
Q-4 Explique porque é que, no pacote tiny threads. . .
a) [0.5 val.] Não era preciso salvar o conteúdo do PC (IP) quando se trocava o contexto de um thread
para outro.
3
b) [0.5 val.] Não era preciso salvar os registos generalistas, excepto o EBP.
Q-5 [1.5 val.] As duas alíneas seguintes são exclusivas. Resolva apenas uma delas à sua escolha!
O espaço destina-se à resolução de qualquer uma delas. Inutilize (risque) a pergunta que não
respondeu
a) Explique o que se entende por “alcance do TLB” e indique (justificando) duas formas de o aumentar!
b) Apresente duas razões que justifiquem a necessidade de garantir que algumas páginas estão bloqueadas em memória, não podendo, portanto, ser paged-out para o disco.
Q-6 [1.0 val.] Qual a relação entre o mapa de memória de um processo e a sua tabela de páginas?
4
Q-7 [1.0 val.] Descreva o que entende por “ficheiros mapeados em memória (memory-mapped
files)” e como é que esta técnica é suportada pelo S.O.!
Q-8 [1.5 val.] Em condições de carga muito reduzida, todos os algoritmos de escalonamento de
pedidos de acesso ao disco acabam por degenerar num mesmo algoritmo! Qual é esse algoritmo e
porquê?
Q-9 [1.5 val.] Diga o que entende por “disk interleaving”! Que problema esta técnica tenta resolver?
5
Q-10 [1.5 val.] As duas alíneas seguintes são exclusivas. Resolva apenas uma delas à sua escolha! O espaço destina-se à resolução de qualquer uma delas. Inutilize (risque) a pergunta que não
respondeu
a) Considere um sistema de ficheiros A, baseado em i-nodes, com capacidade de endereçamento
directo, indirecto, duplamente-indirecto e triplamente-indirecto. Considere um sistema de ficheiros B, também baseado em i-nodes, mas apenas com capacidade de endereçamento triplamenteindirecto. Como o tamanho máximo de um ficheiro em A é apenas marginalmente maior que o
tamanho máximo de um ficheiro em B, explique porque é que os sistemas de ficheiros (indexados)
são normalmente do tipo A e não do tipo B!
b) Para que serve o campo “contador de referências reference count” existente no i-node do sistema
de ficheiros ext2/ext3?
Q-11 Alguns sistemas de ficheiros suportam“ficheiros esparsos”, outros não!
a) [0.5 val.] Diga o que entende por ficheiro esparso!
b) [0.5 val.] Dê um exemplo de uma aplicação que possa beneficiar da existência/suporte ficheiros
esparsos.
6
c) [0.5 val.] Indique se os sistemas de ficheiros ext2 e a FAT12 suportam ficheiros esparsos. Justifique
a sua resposta, quer ela seja positiva ou negativa!
Q-12 Um serviço de sincronização de processos baseado em barreiras é composto de duas chamadas
ao sistema: barrier_init e barrier. A chamada barrier_init, com o seguinte protótipo:
int barrier_init(const char *name, int n_procs);
cria uma barreira dado o seu nome e o número de processos a sincronizar e devolve o seu identificador. Caso já exista uma barreira com o mesmo nome, esta não é criada, sendo apenas devolvido
o identificador. Portanto, qualquer processo que queira utilizar este serviço de sincronismo tem de
começar por invocar a função barrier_init para criar ou indicar em que barreira quer sincronizar.
A chamada barrier tem o protótipo:
void barrier(int bid);
e permite a um processo suspender numa barreira, identificada por bid, até que o número de processos
a sincronizar a tenham atingido.
Para o ajudar na implementação das alíneas abaixo, considere que tem à sua disposição a seguintes
funções:
int new_barrier(char * name, int, wait_queue_head_t);
int get_barrier(char * name);
int free_barrier(int bid);
int get_remainder(int bid);
void add_suspended(int bid);
int get_wait_queue_head(int bid);
em que:
• new_barrier cria uma estrutura com os elementos passados como argumentos e retorna um
identificador (maior que 0) para essa estrutura;
• get_barrier retorna o identificador da barreira, caso esta exista, e 0, caso contrário;
• free_barrier liberta a memória reservada para a estrutura mapeada pelo identificador dado
como argumento;
• get_remainder retorna o número de processos que ainda devem suspender na barreira;
• add_suspended informa a barreira, de forma atómica, da suspensão de um processo;
• get_wait_queue_head retorna a fila onde estão suspensos os processos.
7
a) [1.5 val.] Implemente duas chamadas ao sistema barrier_init e barrier.
Nota: A macro DECLARE_WAIT_QUEUE_HEAD declara um variável do tipo wait_queue_head_t.
int sys_barrier_init(const char *name, int n_procs) {
}
void sys_barrier(int bid) {
}
b) [1.0 val.] Implemente a função barrier_end executada por um processo de controle aquando
da chegada de todos os processos à barreira.
void barrier_end(int id) {
}
8
c) [0.5 val.] Apresente as macros que permitem encapsular as chamadas ao sistema barrier_init
e barrier.
Q-13 [2 val.] No âmbito do terceiro trabalho prático considere as seguintes constantes, estruturas
de dados, variáveis globais e funções:
#define
#define
#define
#define
#define
INODES_PER_BLOCK (DISK_BLOCK_SIZE/sizeof(fs_inode_t))
POINTERS_PER_BLOCK (DISK_BLOCK_SIZE/sizeof(int))
DIR_ENTRIES_PER_BLOCK (DISK_BLOCK_SIZE/sizeof(fs_directory_t))
POINTERS_PER_INODE 5
MAX_FILENAME_SIZE
12
/* Entrada no ficheiro associado a um directório */
typedef struct fs_directory_s {
int inode;
char name[MAX_FILENAME_SIZE];
} fs_directory_t;
/* Estrutura de um inode */
typedef struct fs_inode_s
{
int isvalid;
int size;
int direct[POINTERS_PER_INODE];
int indirect;
} fs_inode_t;
/* Tipo de blocos*/
typedef union fs_block_u
{
fs_superblock_t super;
fs_inode_t
inode[INODES_PER_BLOCK];
fs_directory_t directory[DIR_ENTRIES_PER_BLOCK];
int
indirect[POINTERS_PER_BLOCK];
char
data[DISK_BLOCK_SIZE];
} fs_block_t;
/* Retorna um bloco livre, ou -1 caso não exista */
int find_free_block();
Implemente a função fs_get_block que dado um i-node e o número de entrada (logical_block)
na qual está, ou deve ser colocado, o bloco em que se vai escrever. A função verifica se a entrada dada
aponta para um bloco, se sim retorna-o, se não, cria um novo bloco actualiza a informação do i-node
em concordância.
9
fs_block_t fs_get_block (fs_inode_t *inode,
{
fs_block_t block;
int physical_block =
;
int logical_block) {
if (physical_block == FREE) { /* Vamos adicionar dados a um bloco novo */
/* Arranjar um bloco livre para os dados */
physical_block = find_free_block ();
if (physical_block == 0)
return NULL; /* Não havia mais blocos livres */
if (logical_block < POINTERS_PER_INODE) { /* É um bloco directo */
}
else { /* É um bloco indirecto */
}
memset (block.data, 0, DISK_BLOCK_SIZE);
}
else
/* Vamos ler o bloco que já existe */
disk_read (
,
);
/* Retornar o bloco */
return block;
}
10