Resumo S.O

COMEÇO DO CONTEÚDO DA P1

SO_Semana1.pdf

4) Processes

1. O que é um processo?

1. Um processo pode ser considerado similar a um programa em funcionamento. Já que, quando o processo não está em execução ele é apenas uma série de bytes parados no disco rígido.

💡 Basicamente um processo pode ser definido como um programa em execução. Quando não está em execução um programa é apenas um apanhado de bytes descansando no Disco rígido. Quando são executado ( através de um process API create ) eles se tornam um processo. Uma CPU pode estar executando milhares de processos ao "mesmo tempo" através da virtualização da CPU e time sharing.

2. Quais os estados de um processo?

• Running (Executando)
• Ready (Pronto para rodar, mas o S.O escolheu não rodar)
• Blocked (Não está pronto para rodar)

💡 Basicamente os estados de um processo são Running, Ready e Blocked . É necessário também citar que além desses três estados básicos processos também podem ter um estado inicial e um estado final.

3. É possível determinar em que ordem os processos executam em um SO? Essa ordem pode mudar de execução em execução, mesmo se os mesmos processos estejam executando todas as vezes?

1. De forma geral, não podemos fazer grandes premissas sobre qual processo irá executar primeiro, fenômeno que chamamos de não-determinismo. Sim, a ordem pode mudar, baseadas, por exemplo, num contexto geral dos outros processos, como mudanças de prioridade ou estado e etc.

4. Quais os dados devemos armazenar para poder gerenciar processos? Determine um exemplo de estrutura com esses dados

1. Lista de processos para processos em cada estado (ready, running e blocked) e informações adicionais (PCB) para os processos. Dados que são armazenados de forma geral: PID, Endereço de memória, Tamanho da memória do processo, entre outros.

5) Process API

1. Quais as três chamadas principais da API de um sistema UNIX são utilizadas para gestão de processos? Como cada uma delas funciona?

• fork() - cria um processo filho a partir de um processo pai

💡 As três principais chamadas de um sistema UNIX são Fork (), utilizado para basicamente criar um clone de um processo em execução, com as mesmas informações de contexto, com a única diferença sendo o retorno da função fork(), sendo o PID do filho no pai e 0 no filho

• wait() - espera até outro processo terminar

💡 Wait (), utilizado para esperar que certa execução se encerre, basicamente ele faz o que seu nome indica

• exec() - inicia um novo programa dentro de um processo

💡 Exec(), utilizado para substituir o processo atual totalmente pelo processo desejado, como não há resquícios do processo que chamou exec(), caso ele tenha sucesso, essa função nunca retorna.

2. Como funciona o fluxo de um programa que crie um processo? Como diferenciar se estamos no processo pai ou no processo filho? Como se dá o fluxo de cada um deles? Dica: a questão de fluxo tem relação com o estudado no capítulo anterior.

Load → Alocação de Memória → Iniciar a main →  fork()

Pode-se identificar usando o PID (Process Identifier)

fork() → Alocação → exec()

6) Direct Execution

1. Em que consiste o Limited Direct execution Protocol? Quais as questões que em que ele atua?

1. O limited Direct Protocol é um mecanismo criado para resolver a questão de time sharing inerente a virtualização da CPU. Basicamente ele atua proporcionando a execução direta do programa na CPU. Para evitar falhas de segurança, o Limited
   Direct Execution protocol introduz o User mode, modo em que os códigos são
   executados com diversas restrições sobre o que se pode fazer e caso o programa
   necessite de alguma operação privilegiada ele pode efetuar uma system call , que
   permite que o SO libere certas partes de dados ou funcionalidades exclusivas do modo kernel . Dessa forma, conclui-se também que o protocolo é adotado para fazer com que a virtualização da CPU ocorra da maneira mais eficiente possível em questão de velocidade, segurança e estabilidade.

2. Quais as maneiras de se mudar o contexto, ou seja, o processo que está em execução?

Fluxo das instruções

1. Existem três formas de se mudar o contexto (processo em execução), elas são:

• Forma cooperativa → System Call

→ Um processo amigável transfere controle para a CPU fazendo system calls para, por exemplo, abrir um arquivo e lê-lo ou criar um novo processo. Sistemas como esse geralmente incluem uma chamada de sistema yeld(), que serve somente para transferir o controle de volta ao sistema operacional para que ele possa rodar outro processo.

• Forma não-cooperativa → Timer Interrupt

→ Em caso de um processo que não esteja se comportando da forma adequada, o timer interrupt é acionado. Um sistema de timer é configurado para emitir uma interrupção após alguns milisegundos; quando a interrupção é emitida, o processo é parado e um interrupt handler pré-configurado no S.O entra em ação.

• E a conclusão do processo

3. Como salvar e restaurar o contexto? Quais dados são importantes?

1. Para ocorrer um context switch, o estado que o processo se encontra precisa ser salvo. Dessa forma, o S.O executa um código low-level em assembly para salvar os todos os registradores que o programa pode estar usando, principalmente o program counter, além de salvar outros dados como o Kernel Stack Pointer que são necessários para a execução. Esses dados geralmente são salvos numa estrutura de dados chamada process control block (PCB). Para restaurar, ocorre a restauração dos valores dos registradores, o switch de fato, alterando o processo antigo pelo novo e quando o SO executa as instruções return-from-trap a restauração está terminada.

SO_Semana2.pdf

7. CPU Scheduling

1. Como funciona o algoritmo FIFO? Quais as vantagens e desvantagens?

1. O algoritmo FIFO (First In First Out) ordena as tarefas em ordem de chegada, suas vantagens são ser um algoritmo simples e fácil de entender e implementar, as desvantagens são que ele é um algoritmo não preemptivo, ou seja, não existe prioridade entre os processos, além de ele não ter um tempo médio de espera otimizado, também pode gerar o efeito convoy, onde processos relativamente pequenos demoram a ser executados devido a um longo processo.

2. Como funciona o algoritmo SJB? Quais as vantagens e desvantagens?

1. O algoritmo SJB (Shortest Job First) ordena as tarefas com base no tempo de execução. Vantagens: Minimiza o tempo de espera, Problemas: pode gerar starvation (sequência de processos curtos não deixarem um processo maior executar) e convoy effect (processo grande)

3. Como funciona o algoritmo STCF? Quais as vantagens e desvantagens?

1. O algoritmo STCF (Shortest Time-to-Completion First) ordena as tarefas com base no tempo de conclusão, porém, de forma preemptiva (dando prioridade aos processos). Vantagens: É um algoritmo mais rápido que o SJB em alguns casos. Problemas: Mais difícil de ser implementado e o algoritmo pode ter um tempo de resposta muito ineficiente, já que os processos podem demorar muito para serem escalonados pela primeira vez.

4. Como funciona o algoritmo Round Robin? Quais as vantagens e desvantagens?

1. O algoritmo Round Robin ordena as tarefas com base na ordem de chegada e alterna entre elas a cada quantum (time-slice) de tempo. Vantagens: Elimina o problema de starvation ou efeito convoy, todas as tarefas pegam uma quantidade justa de alocação no CPU. Problemas: Esse método gasta mais tempo em context switching, a sua performance depende muito do quantum certo e encontrar um quanto certo é difícil.

5. O que a ocorrência de operações de I/O introduz no modelo de escalonamento?

1. Quando um processo solicita um I/O seu status fica como bloqueado até a conclusão do I/O , dessa maneira , por questões de otimização , o escalonador tem que tomar duas decisões , uma quando o processo entra em I/O e outra quando o processo retorna do I/O. Nos momentos onde o processo está bloqueado, o S.O faz um overlap e executa outro processo enquanto o I/O ainda não foi executado, salvando assim, recursos e tempo de processamento.

8. Multi-level Feedback

1. Como funciona o algoritmo MLFQ?

1. O algoritmo MLFQ adiciona queues de processos, cada uma podendo ter o seu próprio algoritmo de ordenação de tarefas. Além disso, ela coloca prioridade dentro das queues, fazendo as de maior prioridade serem executadas primeiro. Também são adicionadas funções para os processos poderem se mover dentro das queues, sendo assim, um processo que usa muito tempo de CPU vai ser movido para uma queue de baixa prioridade. É o esquema mais geral e complexo de todos apresentados.

9. Lottery Scheduling

1. Como funciona o escalonamento por loteria?

1. Baseada no contexto de tickets (uma abstração utilizada para representar a porcentagem de CPU que um processo deve receber). Funciona da seguinte forme: Dê a todas as tarefas um número de bilhetes (tickets) e escolha um número aleatório, o vencedor com (geralmente o que tem maior número de bilhetes) entra em execução. Ela alcança a justiça em termos de tempo de CPU disponível por processo probabilisticamente, após várias execuções da loteria.

2. Como funciona o escalonador do Linux, o Completely Fair Scheduler (CFS)?

1. Ele é uma estrutura de árvore que se auto ajusta, ordenada pelo virtual run time. Conforme os processos são executados, eles acumulam vruntime e quando um novo escalonamento for necessário, o CFS pegará o processo com o menor vruntime para rodar em sequência. É importante ressaltar que o CFS adota um sistema de Niceness para indicar as prioridades dos processos, alterando o vruntime para dar a prioridade específica. Além disso, o CFS organiza os processos sendo executados em uma Red-Black-Tree, uma estrutura para ordenar os processos baseados no seu vruntime.

10. Multi-CPU Scheduling

1. O que são os conceitos de localidade temporal e espacial?

1. São conceitos que baseiam o funcionamento dos caches. A ideia por trás da localidade temporal é que ao acessar uma informação, é provável que ela seja acessada novamente num futuro próximo e a ideia por trás da localidade espacial é que se um programa acessou dados em um endereço X, é provável que acesse outros itens próximos a X também. A partir desses conceitos, os sistemas de
   hardware podem fazer um estimativa bem precisa dos dados à armazenar na memória cache.

2. Qual o problema introduzido na questão de escalonamento em multiprocessadores quando pensamos em sincronização?

1. Com relação a sincronização , um dos principais problemas que enfrentamos é relacionado ao fato de múltiplos CPUs estarem acessando ( e alterando ) dados compartilhados e estruturas compartilhadas. Dessa forma, é necessária a implementação de um mecanismo de limitação de acesso a esses recursos ,como
   LOCKS para garantir que as informações acessadas estão corretas. Adicionar essas travas resolve o problema da sincronização, entretanto, cria um problema de escalabilidade.

3. Como funciona o Single Queue Multiprocessor Scherduler (SQMS)? Quais os problemas apresentados por esse algoritmo?

1. Ele vai funcionar reaproveitando os escalonadores de um único processador, alocando todos os processos em uma única fila e repassando para cada CPU. Problemas: Falta de escalabilidade e problemas com cache affinity. O primeiro problema é que para garantir seu funcionamento, é necessário adicionar alguma forma de locking no código, contudo, a adição de locks reduz a performance do sistema, ainda mais quando o número de CPUs sobe. Já o segundo problema seria que é mais eficiente para um processo que seja executado em um processador que tem suas informações armazenadas já em sua memória cache, dessa maneira é necessário que o SQMS implemente um mecanismo de cache affinity , para
   executar, se possível, no mesmo CPU que estava anteriormente. O algoritmo é simples de implementar, mas claramente não se mostra escalável e não preserva a afinidade de cache de maneira exemplar.

4. Como funciona o Multi Queue Multiprocessor Scherduler (MQMS)? Quais os problemas apresentados por esse algoritmo?

1. Ao contrário do SQMS, o MQMS não possui apenas uma fila global, mas cada processador tem uma fila própria de processos. Cada queue vai seguir uma disciplina de schedule particular. Quando uma tarefa entra, ela é escalonada em uma queue independentemente, evitando alguns problemas do SQMS já que ele proporciona uma afinidade de cache inata. Entretanto, ele acaba por apresentar um novo problema: o load imbalance, que consiste em basicamente uma distribuição incorreta de tempo da CPU, quando, por exemplo, uma CPU está se dedicando a um processo apenas, e outras CPU está executando múltiplos processos. Para resolver esse problema, temos que fazer o que é chamado de Migration, migrando assim que necessário, um processo de uma CPU para outra, atingindo dessa forma, o equilíbrio.

SO_Semana3.pdf

13) Address Spaces

1. O que é espaço de endereçamento?

1. Espaço de endereçamento é uma abstração da memória física, basicamente a visão que o programa tem da memória disponível para seu uso do sistema. O código do programa, a stack e a heap estão dispostos dentro desse espaço de endereçamento. É importante ressaltar que tal espaço é a abstração que o sistema operacional está fornecendo para o programa em execução, já que o programa não pode ter acesso livre e direto a memória física.

2. Em um modelo simples que não contempla multiprogramação, qual a direção de crescimento da heap? E da stack? Qual a razão dessas direções?

1. A direção do crescimento do heap é para baixo, já a direção de crescimento da stack é para cima, eles precisam crescer em direções opostas para garantir o maior aproveitamento e funcionamento da memória e a ordem heap-stack foi adotada por convenção.

3. Quais as preocupações em termos de transparência, eficiência e proteção devemos ter em mente quando se trata de gestão de memória?

Transparência - O S.O deve implementar a memória virtual de uma forma que é invisível para o programa. Dessa forma, o programa não deve saber que a memória é virtualizada e deve agir como se tivesse a sua própria memória física privada.

Eficiência - O S.O deve ser o mais eficiente possível, tanto em termos de tempo quando de espaço. Para implementar isso, ele precisará da ajuda do hardware (Ex: TLB).

Proteção - O S.O deve proteger os processos uns dos outros tanto quanto proteger o próprio S.O dos processos. O processo não deve ter acesso aos conteúdos da memória de outros processos ou do S.O, garantindo o isolamento entre processos.

14) Memory API

1.Entender as questões envolvidas nas chamadas de malloc(), free(), principalmente o tratamento de retorno, a não alocação de memória antes de utilizá-la, as consequências de não desalocar memória alocada dinamicamente

malloc() - Ao passar um tamanho ou ele é bem sucedido e te passa um ponteiro para o espaço recém alocado na heap ou falha e retorna NULL

free() - Ao passar um ponteiro retornado por malloc(), ela libera o espaço em memória referente aquele ponteiro.

Erros comuns -

→ Não alocar a memória antes de utilizá-la (segmentation fault)

→ Não alocar o espaço suficiente (buffer overflow → erro imprevisível)

→ Esquecer de inicializar a memória alocada (leitura de valor desconhecido)

→ Esquecer de liberar a memória (memory leak)

15) Address Translation

1. Em que consiste realocação dinâmica? Como ela funciona? Quais são as funcionalidades de hardware necessárias para que este método possa ser utilizado?

1. A realocação dinâmica consiste no processo de conversão de espaço de  endereçamento em endereço físico, temos então, a possibilidade de movimentar o espaço de endereçamento. Um ponto interessante é que a realocação poder ser feita mesmo depois que o processo já tenha iniciado o que dá a ela esse nome. Para seu funcionamento, ela precisa de hardware, um registrador chamado base que é usado para transformar endereços virtuais (gerados pelo programa) em endereços físicos e um registrador chamado bounds (ou limits) que garante que esses endereços estão dentro dos limites do espaço de endereçamento. Tais
   registradores são armazenados no MMU (Memory Management Unit) parte do
   processador que ajuda na tradução do endereço de memória.

2. Como se dá o fluxo da Limited Direct Execution Protocol (Dynamic Relocation)?

1. Ao bootar, primeiro ocorre a inicialização da trap table, depois, o hardware salva os endereços para os handlers (system call, timer, illegal mem-access e illegal instruction), após isso, inicia-se o interrupt timer, iniciando o timer a cada X ms. Por fim, temos a inicialização da process table e da free list para os processos. Depois, o S.O precisa alocar espaço para um processo, setar os registradores base e bound e executar uma return-from-trap. Em seguida, ele restaura os registradores do processo, entra em user mode, realiza outras instruções com o registrador PC e inicia o processo, que vai buscar e executar suas instruções. Por fim, caso não haja swiches entre processos, o processo executará até o final, onde sua memória será desalocada e sua entrada na lista de processos será apagada.

16) Segmentation

1. Qual a razão para se utilizar segmentação?

1. Utilizando uma arquitetura de memória mais simples, pode-se notar uma grande quantidade de memória desperdiçada entre a stack e heap e o motivo de se usar segmentação é solucionar o problema de programas que, sem segmentação, necessitariam de todo o espaço de endereçamento residente na memória e com a criação dos segmentos lógicos esse desperdício é evitado.

2. Como se define qual o segmento utilizado a partir de um endereço dado?

1. Podemos definir o o segmento utilizado com base no endereço das seguintes formas:

• Explícita - Alocando-se alguns bits mais significativos do endereço para indiciar o segmento referente. Para separar entre código, heap e stack precisaríamos de dois bits, contudo, alguns sistemas, para evitar desperdício, colocam o código no mesmo segmento heap para poderem utilizar apenas um bit como indicador.
• Implícita - O hardware determina o segmento notando de que forma o endereço foi formado. Se foi gerado pelo program counter → o endereço está dentro do segmento de código, se o endereço é baseado na stack ou base pointer, deve estar dentro do segmento stack, quaisquer outros endereços devem estar no heap.

17)  Free Space Management

1. Quais as estruturas de dados utilizadas para gerenciar espaços livres em memória?

1. Para gerenciar os espaços livres em memória são usadas listas (free lists ou segregated lists) que vão conter referências para todos os blocos de espaço livre na região controlada da memória. Para mapear os espaços livres a lista deve conter basicamente o endereço de início e tamanho desse espaço, caso uma memória seja solicitada o lista efetuará o chamado “spliting” e achará um chunk suficiente e dividi-lo em dois. Quando algum chunk for liberado, checam-se os vizinhos e caso eles estejam livres também, ocorre a fusão, efeito chamado "colaescing"

2. Em caso de utilização de lista de livres, onde esta pode ser armazenada? Como funciona este armazenamento?

1. As listas livres serão armazenadas no próprio espaço livre, dentro da memória. O header, minimamente, guarda o tamanho da região alocada e pode conter informação adicional para agilizar procedimentos. A lista é inicializada
   de forma que cada elemento terá um endereço , tamanho e apontará para o próximo elemento, para iniciar a lista deve utilizar a system call mmap() , utilizada para retornar
   um ponteiro para um espaço vazio.

3. Quais os algoritmos utilizados para se alocar um processo em um pedaço de memória? Como eles funcionam?

• Best Fit - Primeiro, procure através da lista livre e encontre os blocos de memória livre que são tão grandes quanto ou maiores que o requisitado, retorne o menor do grupo de candidatos
• Worst Fit - O oposto da Best Fit, encontre os maiores blocos de memória livre e retorne o maior
• First Fit - Encontra o primeiro bloco que é grande o suficiente e retorna a quantidade necessária ao usuário
• Next Fit - Ao invés de sempre começar no primeiro, o algorítimo next fit mantém um ponteiro extra, a ideia é procurar mais uniformemente.

Existem, além desses, outros algoritmos possíveis, esses são:

Segregated Lists - Onde caso uma aplicação tenha uma requisição que seja feita constantemente , uma lista é separada para atribuir objetos daquele tamanho específico , todas outras requisições são encaminhadas para uma lista mais geral.

Buddy Alocation - Quando uma requisição de memória é feita, a busca por espaço livre recursivamente divide o espaço por dois até obter o menor bloco que possa alocar o espaço solicitado.

FIM DO CONTEÚDO DA P1

INÍCIO DO CONTEÚDO DA P2

SO_Semana4.pdf

18) Introduction to Paging

1. O que são páginas? O que são page-frames?

A ideia básica é que cada programa tem seu próprio espaço de endereçamento,
o qual é dividido em blocos chamados de páginas. Dessa forma, páginas são unidades de tamanho fixo do espaço de endereçamento, correspondentemente, nós vemos a memória física como um array de slots de tamanho fixo que chamamos de page-frames.

2. Em um sistema de endereços virtuais com paginação, como um endereço virtual é manipulado, ou seja, como se define a qual página um endereço pertence? O que é o offset do endereço?

1. Para gravar onde cada página virtual do espaço de endereçamento é colocada, o S.O salva uma page table, que tem como função principal guardar traduções de endereço para cada página virtual. Para traduzir, temos dois componentes:

• Virtual Page Number (VPN)
• Offset

O offset é definido como o conjunto de bytes que apontam em qual posição dentro da página o elemento de interesse está.

Com o VPN, nós podemos indexar a page-table e com isso, encontrar qual physical frame a página virtual reside.

💡 Em um sistema de endereços virtuais com paginação, o SO mantém uma tabela de páginas para cada processo. O papel dessa tabela é armazenar a tradução de endereços, ou seja, a qual page frame cada página corresponde. Um endereço virtual é divido em duas partes, o número da página virtual (VPN) e o offset, que corresponde ao byte da página indicada pelo endereço. O tamanho do endereço virtual é relativo ao seu espaço, assim um espaço virtual de X bytes precisa de um endereço de log_2X bytes. Nesse endereço, se o tamanho da página for Y, os log_2Y bits mais a direita do endereço correspondem ao offset. Com esses dados, o SO determina quais bits do endereço virtual indicam a página que deve ser traduzida com o auxílio da tabela de páginas e, em seguida, concatenada com o offset original para formar o endereço de memória física.

3. O que são tabela de páginas? O que compõe uma entrada típica de tabela de página?

1. Para gravar onde cada página virtual do espaço de endereçamento é colocada na memória física, o S.O geralmente guarda estruturas de dados conhecidas como page tables. Sua principal função é guardar traduções de endereço para cada página virtual do espaço de endereçamento, fazendo com que nós saibamos onde na memória física cada página reside. Tipicamente, uma page-table terá uma page-table entry para cada tradução física, mais quaisquer outras coisas possivelmente úteis. A forma mais simples de uma page-table é chamada de linear page table, que é basicamente um array. O S.O indexa o array com o VPN e olha o page-table entry para aquele index com objetivo de encontrar o physical frame number desejado.

Para o conteúdo do PTE, temos alguns bits:

• Um bit de validação é comum, para indicar se aquela tradução é válida
• Também podemos ter alguns bits para proteção, indicando se pode-se ler, escrever ou executar a partir daquilo
• Um present bit, indicando se a página está na memória física ou em disco
• Um dirty bit também é comum, indicando se a página foi modificada desde que entrou na memória
• Um bit de referência é as vezes usado para determinar quais páginas são populares e devem permanecer na memória.

19) Paging: Faster Translations (TLBs)

1. O que é uma TLB? Qual o principal problema que ela resolve?

1. Ela é parte da unidade de gerenciamento de memória (MMU) do chip e é, basicamente, um cache de traduções de endereços (virtuais para físicos) muito usados. Foi criada para resolver o problema do acesso lento a memória principal e com isso, para acelerar as traduções de endereço, foi adicionada uma unidade chamada translation-lookaside buffer ou TLB. Para cada referência à memória virtual, primeiro, o hardware checa o TLB para ver se a tradução desejada está dentro dele e, caso esteja, a tradução é executada mais rapidamente, sem consultar a page-table.

2. Entenda o algoritmo de fluxo da TLB.

O algoritmo de fluxo da TLB ocorre da seguinte forma:

Extraia o VPN do endereço virtual e cheque se o TLB tem uma tradução para ele.

Se sim, temos um TLB hit (ou seja, o TLB possui a tradução). Podemos agora extrair o PFN da entrada correta do TLB, concatenar isso no offset do endereço virtual original e formar o endereço físico, acessando a memória se os checks de proteção não falharem.

Se não, temos um TLB miss (ou seja, o TLB não possui a tradução). O hardware, então, acessa a page table para encontrar a tradução e atualiza o TLB com a nova tradução. Quando finalmente, o TLB estiver atualizado, o hardware tenta novamente a instrução e a tradução é encontrada.

3. Como é gerenciado um TLB miss?

1. Quanto um TLB miss ocorre, a page table precisa ser acessada para encontrar a tradução e, uma referência extra de memória (ou mais, com page tables mais complexas) aparece. Sobre quem lida com o TLB miss, temos duas respostas, ou o hardware ou o software.

Antigamente, o hardware tinha sets de complexas instruções e lidava com o TLB miss inteiramente, precisando saber exatamente onde as page tables estão localizadas na memória, assim como seu formato. Em um miss, o hardware iria caminhas através da page table, encontrar a entrada correta e extrair a tradução desejada.

Arquiteturas mais modernas tem um sistema de software para gerenciar o TLB. Em um TLB miss, o hardware simplesmente levanta uma exception que pausa o fluxo corrente de instruções, eleva o privilégio para kernel mode e pula para um trap handler. O código do trap handler vai procurar a tradução na page table e atualizar o TLB e finalmente, dar um return from trap.

4. Qual a diferença entre os bits invalid presentes na estrada de tabela de página e na TLB?

1. Numa page table, quando uma entrada é marcada como inválida, significa que a página não foi alocada pelo processo e não deve ser acessada por um programa em bom funcionamento. A resposta usual quando uma página inválida é acessada é matar o processo.

Por outro lado, um bit inválido na TLB simplesmente se refere pra dizer que a entrada TLB não tem uma tradução válida dentro de si. Um exemplo é que, quando o S.O dá boot, por exemplo, um estado inicial comum é setar o as entradas do TLB para inválidas já que, nenhuma tradução de endereço foi inserida no cache.

5. O que ocorre com o conteúdo da TLB quando ocorre uma mudança de contexto?

1. Num context switch, os conteúdos do TLB podem ser ajustados da seguinte forma:

Uma forma possível é simplesmente limpar (flush) o TLB em context switches, assim, limpando o TLB antes de executar cada processo. Em um sistema baseado em software, isso pode ser feito com uma instrução explícita e privilegiada para o hardware. Dessa forma, limpando o TLB, temos uma solução, entretanto, também temos um custo, já que a cada context switch, o S.O terá que enfrentar vários TLB misses. Para evitar esse problema, alguns sistemas adicionam hardware para habilitar o compartilhamento do TLB entre context swithes. Em particular, alguns sistemas proveem um identificador de espaço de endereçamento (ASID), similar a um PID porém geralmente com bits a menos, para garantir que traduções de processos diferentes sejam armazenadas sem confusão.

6. Qual o conteúdo típico de uma entrada de TLB?

1. O conteúdo tipico de uma entrada TLB é:

• Alguns bits para o VPN
• Um Global Bit, usado para páginas que são globalmente compartilhadas
• O ASID, que o S.O pode usar para distiguir espaços de endereçamento
• Alguns bits para Coherence, que determinam como uma página é colocada em cache pelo hardware
• Um bit sujo, que é marcado quando a página for escrita
• Um valid bit que mostra para o hardware se tem ou não uma tradução válida presente na entrada
• Também temos um page mask field que suporta tamanhos de páginas variados.
• E alguns bits não usados.

💡 Cada entrada contém informações sobre uma página, incluindo o número da página virtual, um bit que é configurado quando a página é modificada, o código de proteção (ler/escrever/permissões de execução) e o quadro de página física na qual a página está localizada. Esses campos têm uma correspondência de um para um com os campos na tabela de páginas, exceto pelo número da página virtual, que não é necessário na tabela de páginas. Outro bit indica se a entrada é válida (isto é, em uso) ou não.

20) Paging: Faster Translations (TLBs)

1. Qual o problema ocorre com tabelas de páginas conforme o tamanho do espaço de endereçamento?

1. Page tables são muito grandes e consomem muita memória. Por exemplo, vamos assumir um espaço de endereçamento de 32 bits, com 4kb de páginas e um page-table entry de 4 bytes. O espaço de endereçamento vai ter algo próximo de um milhão de páginas virtuais e temos uma page-table entry por página, dessa forma, nossa page table tem algo próximo de 4MB. Geralmente, temos uma page-table POR PROCESSO e, imaginando um sistema moderno, com centenas de processos rodando simultaneamente, ficaria completamente inviável alocar todo esse espaço somente para page-tables. Uma solução simples para esse problema poderia ser aumentar o tamanho das páginas, reduzindo assim o espaço ocupado pelas tabelas. Porém essa abordagem gera um novo problema, páginas maiores podem provocar fragmentação interna. Aplicações podem alocar páginas para usar apenas poucos bits, lotando rapidamente a memória.

2. Como funciona tabela de página com segmentação?

1. Nas tabelas de página por segmentação, ao invés de termos uma única page table para todo o espaço de endereçamento do processo, temos uma por segmento lógico (code, heap e stack). Na segmentação original, tínhamos um registrador base (para nos informar onde cada segmento estava na memória física) e um registrador limite (para nos informar o tamanho de tal segmento). No nosso híbrido, ainda teremos essas estruturas no MMU. Aqui, nós usaremos o base para guardar o endereço físico da page-table daquele segmento e o limite será usado para indicar o fim daquela page-table (quantas páginas válidas ela tem).

3. Como funciona tabela de página multinível? Como os endereços virtuais são tratados neste caso?

1. A ideia por trás de uma page table multi-level é simples: evitar manter todas as tabelas de páginas na memória o tempo inteiro. Para isso, primeiro dividimos a page table em unidades do tamanho de páginas. Depois, se uma página cheia de PTEs for inválida não aloque aquela página. Para rastrear se uma página é válida (e se for válida, onde está na memória), usamos uma nova estrutura chamada page directory. Dessa forma, o page directory pode ser usado tanto para dizer onde uma página da page-table está quanto para dizer que toda a página da page table não possui páginas válidas.

4. Entenda o algoritmo de fluxo de controle de tabela de página com a introdução das tabelas multiníveis

1 VPN = (VirtualAddress & VPN_MASK) >> SHIFT
2 (Success, TlbEntry) = TLB_Lookup(VPN)
3 if (Success == True) // TLB Hit
4 if (CanAccess(TlbEntry.ProtectBits) == True)
5 Offset = VirtualAddress & OFFSET_MASK
6 PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
7 Register = AccessMemory(PhysAddr)
8 else
9 RaiseException(PROTECTION_FAULT)
10 else // TLB Miss
11 // first, get page directory entry
12 PDIndex = (VPN & PD_MASK) >> PD_SHIFT
13 PDEAddr = PDBR + (PDIndex * sizeof(PDE))
14 PDE = AccessMemory(PDEAddr)
15 if (PDE.Valid == False)
16 RaiseException(SEGMENTATION_FAULT)
17 else
18 // PDE is valid: now fetch PTE from page table
19 PTIndex = (VPN & PT_MASK) >> PT_SHIFT
20 PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))
21 PTE = AccessMemory(PTEAddr)
22 if (PTE.Valid == False)
23 RaiseException(SEGMENTATION_FAULT)
24 else if (CanAccess(PTE.ProtectBits) == False)
25 RaiseException(PROTECTION_FAULT)
26 else
27 TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
28 RetryInstruction()

Antes de qualquer acesso ocorrer, o hardware primeiro checa o TLB. Em um hit, o endereço físico é formado diretamente sem acessar a page table. Em um miss, o hardware precisa primeiro conseguir o Page Directory Entry e verificar se ele é válido. Caso não, ele levanta um Segmentation Fault, caso sim, ele pode formar o endereço PTE usando o page-table index combinado com o endereço do PDE de segundo nível. Caso possa ser acessado, deve-se atualizar a TLB com esse novo endereço e reexecutar a instrução.

5. O que são tabelas invertidas. O livro faz apenas uma discussão muito superficial, portanto fica como tarefa pesquisarem a estrutura e funcionamento dessas tabelas. Esse trabalho deve ser escrito e enviado para o professor, individualmente.

1. Uma tabela invertida é uma estrutura de dados global que vai englobar todos os processos. Em sua forma mais simples, uma tabela invertida vai conter uma entrada por página física num array linear. Como a tabela é dividida entre todos os processos, cada entrada precisa conter o ID do processo dono da página. Além disso, como cada página física é mapeada virtualmente, cada entrada terá que conter um VPN, ao invés de um physical, em sua forma linear. Dessa forma, a forma Linear ocupa menos espaço, porém, a busca através dos itens se torna mais demorada. Além da forma linear, existe outra forma, a Hashed Inverted Page Table que adiciona um nível extra, anterior a própria page table, chamado hash anchor table. Essa tabela é, no mínimo, tão larga quanto a page table e mapeia os IDs dos processos e VPNs. Para a tradução de um endereço virtual, o ID e o VPN de um processo são "hashados" para entrar na hash anchor table. Assim, a forma Hashed ocupa mais espaço, porém, a busca é acelerada com uso de apontadores.

SO_Semana5.pdf

21) Beyond Physical Memory: Mechanisms

1. Como funciona o espaço de swap?

1. O espaço de swap é definido como o espaço reservado em disco para mover as páginas para frente e para trás. Ele tem esse nome por que fazemos o swap de páginas da memória pro disco e vice-versa. Para realizar essas operações, o S.O precisará lembrar o endereço de disco de uma página dada (disk address).

Além disso, o tamanho do espaço de swap também é importante, já que ele determina o número máximo de páginas de memória que podem estar em uso pelo sistema.

Dessa forma, usando o swap space, podemos fingir que o sistema tem uma memória maior do que ele realmente tem.

2. O que é um page-fault? Como ele é gerenciado (entender o algoritmo de fluxo de controle)?

1. O page fault é uma interrupção disparada quando um programa decide acessar uma página que não está na memória física. Se quisermos permitir que as páginas sejam trocadas no disco, precisamos verificar se a página está presente na memória física. Dessa maneira, o hardware ou o software (dependendo de como temos o TLB) verificará isso com uma informação que é contida em cada page-table entry, o present bit. Se esse bit estiver setado em 1, significa que a página está presente na memória física e o processo normal do TLB continua. Se estiver setado em 0, a página não está na memória, mas sim no disco, em algum lugar.

22) Beyond Physical Memory: Policies

1. Como funciona a política ótima de substituição de alocação de páginas em page-frames?

A política ótima de substituição nos leva para o menor número de misses possível. Foi desenvolvida por Belady e funciona substituindo a página que irá ser acessada mais longe no futuro, resultando no menor número possível de cache misses. Entretanto, ela é muito difícil de ser implementada.

2. Como funciona a política FIFO de substituição de alocação de páginas em page-frames?

Inicialmente, muitos sistemas tentavam fugir da complexidade de implementação de algo ótimo e acabavam implementado políticas de substituição muito simples. Esse é o caso da substituição FIFO (first-in, first-out), onde páginas são simplesmente colocadas numa fila quando entram no sistema. Quando uma substituição ocorre, a página no final da fila (a primeira a entrar) é substituida.

3. Como funciona a política Randômica de substituição de alocação de páginas em page-frames?

Outra forma simples de substituição é a randômica. Nela, simplesmente pegamos uma página aleatória para ser substituída. Em alguns pontos, ela é similar ao FIFO, já que é simples de entender e implementar, porém, não tenta ser inteligente em quais blocos devem ser despejados. Dessa forma, é lógico que o desempenho dessa política está totalmente jogado ao acaso.

4. Como funciona a política LRU de substituição de alocação de páginas em page-frames?

O principal problema das alternativas anteriores (Fifo e randômica) é que eles podem remover uma página importante, mesmo ela sendo referenciada novamente em algum futuro próximo. Dessa forma, precisamos de algo mais inteligente na hora de substituir e então, temos a política LRU (Least Recently Used → Menos recentemente usado), armazenando um histórico e ordenando com base na proximidade temporal do uso. Essa política então, substituirá a página menos recentemente usada, sendo baseada no princípio da localidade.

5. Entenda as cargas de trabalho de cada um deles.

Sem Localidade: Não importa muito qual política você escolheu já que, todos os métodos vão performar da mesma maneira com o hit rate exatamente determinado pelo tamanho do cache. Outra conclusão importante é, já que o cache é largo o bastante para caber todas as cargas de trabalho, todas convergem para um 100% hit rate.

O 80-20: Ele já exibe localidade, 80% das referências são feitas à 20% das páginas (páginas quentes). Os outros 20% são feitos aos 80% restantes das páginas (páginas frias). Apesar do FIFO e do Random irem até que bem, o LRU se aproxima mais do ótimo, entretanto, mostra que a informação histórica do LRU não é perfeita.

Looping sequencial: Referimos a 50 páginas em sequência (de 0 a 49) e então, loopamos, repetindo esses acessos para um total de 10000 acessos à 50 páginas unicas. Nesse, a random se sai melhor, se aproximando do optimal.

6. Qual o problema com LRU? Porque faz sentido se falar de LRU aproximado? Como ele funciona?

O principal problema com o LRU é a dificuldade de implementá-lo. Isso ocorre pois o sistema teria que manter o histórico de cada referência de memória feita pelo sistema, que poderiam trazer uma grande redução na perfomance. Poderíamos tentar suprir esse problema com hardware, entretanto, conforme o número de páginas num sistema aumenta, scanear por todas as páginas para achar a página absoluta menos recentemente usada toma muito tempo, dessa forma, temos uma nova alternativa: aproximar o LRU.

Aproximando o LRU temos uma ideia mais possível do ponto de vista computacional, ainda precisamos de um suporte do hardware da forma de um use bit (ou reference bit). Temos um use bit por página do sistema e os use bits estão na memória em algum lugar (por exemplo na per-process page). Toda vez que uma página for referenciada (lida ou escrita), o use bit é setado pelo hardware para 1. A responsabilidade de limpar os use bits (trazendo eles de volta para 0), entretanto, é do S.O.

O S.O então, usará os use bits para fazer a política de substituição funcionar usando, por exemplo, um clock algorithm. Imagine que todas as páginas do sistema foram arrajadas numa lista circular. Um ponteiro do relógio aponta para alguma página específica para começar (não importando muito qual). Quando uma substituição ocorrer, o sistema operacional verifica se a página P atualmente apontada tem um bit de uso 1 ou 0. Se 1, implica que a página P foi recentemente usada e não é um bom candidato para a substituição. Dessa forma, o use bit de P é stado para 0 (limpo) e o ponteiro do relógio é incrementado para a próxima pagina (P+1). O algoritmo continua até encontrar um bit de uso definido como 0, o que implica que esta página não foi usada recentemente, substituindo-a.

23) Complete Virtual Memory Systems

1. Considerando os conteúdos cobertos nos capítulos anteriores, estudem os exemplos implementados em sistemas de gestão de memórias reais apresentados neste capítulo.

SO_Semana6.pdf

26) Concurrency: An Introduction

1. Qual a principal diferença encontrada no espaço de endereçamento quando se utiliza o modelo de múltiplas threads?

No modelo de espaço de endereçamento de uma única thread, existe apenas uma stack, usualmente residindo no final do espaço de endereçamento. Entretanto, no modelo multi-threaded, cada thread executa independentemente e ao invés de uma única stack no espaço de endereçamento, teremos uma por thread.

2. Qual o ganho que temos quando utilizamos threads?

Os principais ganhos que temos usando threads são dois:

• O primeiro e principal ganho é simples, paralalelismo. Imaginando um programa em execução, ter processos dividindo as tarefas entre processadores agiliza muito a velocidade de execução.
• O segundo é um pouco mais sutil: evitar o progresso de um programa devido à um I/O devagar. Já que, enquanto uma thread espera o I/O, o CPU scheduler pode mudar para outras threads que já estão prontas para execução.

3. Entenda o código de criação de threads (pg. 4) e os fluxos de execução dados no exemplo (pg. 5).

1 #include <stdio.h>
2 #include <assert.h>
3 #include <pthread.h>
4 #include "common.h"
5 #include "common_threads.h"
6
7 void *mythread(void *arg) {
8 printf("%s\n", (char *) arg);
9 return NULL;
10 }
11
12 int
13 main(int argc, char *argv[]) {
14 pthread_t p1, p2;
15 int rc;
16 printf("main: begin\n");
17 Pthread_create(&p1, NULL, mythread, "A");
18 Pthread_create(&p2, NULL, mythread, "B");
19 // join waits for the threads to finish
20 Pthread_join(p1, NULL);
21 Pthread_join(p2, NULL);
22 printf("main: end\n");
23 return 0;
24 }

O programa cria duas threads que irão rodar a função mythread(), através de diferentes argumentos (string A ou a string B). Depois de criadas, um comando pthread_join() é executado pela main thread para cada thread extra, garantindo que tanto a thread1 quanto a thread2 irão rodar até o final. Ao chegar ao final, temos um print "main:end" e terminamos. Temos ao todo, então, 3 threads: a main thread T1 e T2. Vamos agora, examinar um dos possíveis fluxos de execução.

4. O que é uma Race Condition (Condição de corrida)? Porquê isso ocorre? Entender o exemplo da pg. 10.

Uma condição de corrida significa que os resultados irão depender do timing da execução do código. Com um pouco de má sorte ( por exemplo, um context switch que ocorreu em pontos prematuros na execução), temos um resultado errado. Na verdade, podemos ter um resultado diferente cada vez que executamos, tendo um resultado indeterminado, onde a saída é desconhecida e provavelmente diferente ao longo de diferentes execuções. Ela ocorre em casos de múltiplas threads executando uma seção crítica de código. Uma seção crítica é um pedaço de código que acessa um recurso compartilhado (por exemplo, uma variável) e não pode ser executada concorrentemente por mais de uma thread.

5. O que constitui o conceito de atomicidade?

A ideia por trás de fazer uma série de ações se tornarem atômicas pode ser expressa por uma frase simples "tudo ou nada". Dessa forma, imaginando uma ação onde o hardware garante que sua execução será atômica, quando a instrução for executada, ela irá performar como desejado já que não poderá ser interrompida durante sua execução. Dessa forma, se uma interrupção ocorrer, ou a instrução foi executada até ser completa ou não foi executada.

27) Interlude: Thread API

1. Entender a API pthreads

Para início da discussão sobre como usar a API pthreads, vamos falar sobre a criação de novas threads:

A primeira coisa que você deve ser capaz de fazer para escrever um programa multi-threaded é criar novas threads e dessa forma, uma interface para criação das mesmas deve existir. No POSIX ela ocorre da seguinte maneira:

#include <pthread.h>
int pthread_create(pthread_t *thread, 
const pthread_attr_t *attr, 
void *(*start_routine)(void*), 
void *arg);

A declaração usa 4 argumentos, thread, attr, start_routine e arg.

• thread - Ponteiro para uma estrutura do tipo pthread_t (usamos essa estrutura para interagir com a thread)
• attr - Usado para especificar quaisquer atributos que essa thread tenha, como o stack size ou informações sobre scheduling.
• start_routine - O terceiro argumento na verdade é um ponteiro de função, um nome de uma função passado para a thread iniciar
• arg - O argumento passado para a função quando a thread iniciar sua execução.

Além disso, podemos precisar de funções para esperar uma thread terminar. Para isso, temos a rotina pthread_join()

Para ela, são passados dois argumentos:

• O primeiro é do tipo pthread_t e é usado para especificar qual thread esperar
• O segundo é um ponteiro para o valor de retorno que você espera obter.

Outro ponto de interesse e talvez o mais útil é um conjunto de funções providas pela library thread do POSIX e são para prover exclusão mútua para uma seção crítica via travas (locks). O mais básico par de rotinas é o: int pthread_mutex_lock nome_da_trava e int pthread_mutex_unlock nome_da_trava. Sua função é permitir que seções críticas de código não sejam acessadas em momentos indevidos pelas threads, travando o funcionamento de uma ou outra com base na chamada.

Mais um aspecto importante são as variáveis condicionais, que são úteis para quando precisamos sinalizar coisas entre as threads (como a finalização de algo para uma thread continuar com sua execução). Duas rotinas são usadas para isso:

int pthread_cond_wait (nome_da_variávelcondicional, nome_da_trava) → esperar o sinal

int pthread_cond_signal (nome_da_variávelcondicional) → sinalizar

28) Locks

1. O que constitui um lock? Como declarar e inicializar um lock na API pthreads?

Em programas com multi-threads, é necessário que as execuções ocorram atomicamente. Para resolver o problema de acessos não sincronizados, são criadas as locks. As locks são só variáveis que guardam o estado da trava em qualquer instante de tempo. Esses estados podem ser Disponível (ou destrancada, ou livre) onde nenhuma thread segura a lock ou Adquirida (ou trancada, presa) onde uma thread segura a lock e portanto, deve estar na seção de código em questão. Para utilizar uma trava, basta adicionar alguns códigos em torno da seção crítica de código. Para declará-la usamos a sintaxe:

1 pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
2
3 Pthread_mutex_lock(&lock); // wrapper; exits on failure
4 balance = balance + 1;
5 Pthread_mutex_unlock(&lock);

O nome usado pela biblioteca POSIX para uma trava é mutex, já que ela é usada para prover mutual exclusion (exclusão mútua) entre as threads.

2. Quais os problemas em permitir que um processo que execute em userlevel desabilite interrupções?

Uma das primeiras soluções para prover exclusão mútua foi desabilitar interrupções para seções críticas de código. Existem entretanto, inúmeras negativas nesse procedimento:

1. Essa abordagem requer que qualquer thread realize uma operação privilegiada e dessa forma, precisamos confiar que o programa não fará nada malicioso, por exemplo, monopolizando a CPU ou entrando num loop infinito, fazendo com que o S.O nunca retome o controle.
2. Essa abordagem não funciona em multiprocessadores. Se múltiplas threads estão executando em CPUs diferentes e cada uma tentar entrar na seção crítica, não importa se as interrupções estão desligadas, threads irão conseguir executar em outro processador e dessa forma entrar na seção crítica.
3. Desligar as interrupções por períodos longos de tempo pode levar às interrupções serem perdidas, o que leva a sérios problemas sistemáticos.
4. E por último e menos importante, essa abordagem pode ser ineficiente.

3. Entenda o spin lock e suas desvantagens.

É o tipo de trava mais simples de se construir e simplesmente gira, usando ciclos da CPU, até a trava ficar disponível. Para funcionar corretamente em um único processador, requer um preemptive scheduler (escalonador que vai parar a thread via timer para inciar outra thread diferente). Sem ser preemptivo, spin locks não fazer muito sentido num único CPU já que uma thread girando num CPU nunca vai soltar a execução. Suas principais desvantagens são:

• Não prover nenhuma garantia de justiça, já que uma thread pode ficar girando eternamente (podendo levar à starvation)
• Performance em casos de CPU único ruim, desperdiçando ciclos de CPU.

4. Entenda o compare-and-swap e suas desvantagens.

A ideia básica para o compare-and-swap é testar se o valor que está no endereço especificado por ptr é igual a expected; se sim, atualize a localização da memória apontada por ptr com o novo valor. Se não, não faça nada. Em ambos os casos, retorne o valor original naquele local de memória, permitindo assim que o código que chamou o compare-and-swap saber se foi bem-sucedido ou não. Suas desvantagens são parecidas com as da spin lock.

5. Entenda o Load-Linked and Store-Conditional.

Algumas plataformas proveem um par de instruções que trabalham em conjunto para ajudar a construir seções críticas. Na arquitetura MIPS, por exemplo, temos as instruções load-linked e store-conditional que podem ser usadas para construir travas e outros componentes de concorrência. O load-linked opera de maneira muito semelhante a uma instrução de carregamento típica e simplesmente busca um valor da memória e o coloca em um registrador. A principal diferença vem com o armazenamento condicional, que só tem sucesso (e atualiza o valor armazenado no endereço apenas vinculado à carga) se não houver armazenamento intervencionista para o endereço ocorreu. No caso de sucesso, o store-conditional retorna 1 e atualiza o valor de ptr para value; se falhar, o valor em ptr não é atualizado e 0 é retornado.

6. Entenda o Fetch-And-Add.

Uma última primitiva de hardware é a instrução de busca e adição (fetch-and-add), que incrementa atomicamente um valor enquanto retorna o valor antigo em um endereço específico.

Em vez de um único valor, esta solução usa um tíquete e uma variável de giro em combinação para construir um bloqueio. A operação básica é bastante simples: quando um thread deseja adquirir um bloqueio, ela primeiro faz uma busca e adição atômica no valor do tíquete; esse valor agora é considerado a "vez" desta discussão (minha vez). O lock-> turn globalmente compartilhado é então usado para determinar em qual thread é a vez; quando (myturn == turn) para um determinado tópico, é a vez desse tópico entrar na seção crítica. O desbloqueio é realizado simplesmente incrementando a curva de modo que o próximo segmento de espera (se houver) possa agora entrar na seção crítica.

7. O que faz a primitiva yield()?

Uma thread pode estar em um de três estados (running, ready, ou blocked); yield()é simplesmente uma chamada de sistema que move quem fez a chamada do estado de execução para o estado pronto e, assim, promove outra thread para execução. Assim, a thread que fez um yield() essencialmente se retira da lista dos em execução.

8. Entenda as primitivas e tipos fornecidos pelo Solaris e Linux no contexto de locks.

O Linux fornece um futex que é semelhante à interface Solaris, mas fornece mais funcionalidades in-kernel. Especificamente, cada futex tem associado a ele uma localização de memória física específica, bem como uma fila por futex in-kernel .

Os callers podem usar chamadas futex para dormir ou acordar conforme necessário. Especificamente, duas chamadas estão disponíveis. A chamada futex-wait(address, expected) coloca a thread que a chamou em hibernação, assumindo o valor em address é igual ao expected. Se não for igual, a chamada retorna imediatamente. E a chamada futex_wake(address) desperta uma thread que está esperando na fila.

29) Lock-based Concurrent Data Structures

Entenda os mecanismos de locks aplicado às estruturas de dados apresentadas. Não cobriremos especificamente este conteúdo nas avaliações, mas ele ajuda a sedimentar os conceitos estudados nos capítulos anteriores e aumenta o desempenho de desenvolvedores.

SO_Semana7.pdf

30) Condition Variables

1. O que são variáveis condicionais? Entender o código da pg. 3.

Uma variável condicional é uma fila explícita que as threads podem se colocar quando algum estado de execução não está como deveria. Alguma outra thread, quando muda esse estado, pode então acordar uma (ou mais) dessas threads em espera e, assim, permitir que elas continuem rodando (sinalizando a condição).

Para declarar uma variável condicional, basta escrever algo como pthread_cond_t nome_da_variável, lembrando que ela também necessita de uma inicialização própria.

Associadas a variável condicional, temos duas operações:

• wait() - Executada quando a thread quer se colocar para dormir
• signal() - Executada quando a thread mudou algo no programa e então, quer acordar outra thread que estava esperando por essa condição.

1 int done = 0;
2 pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
3 pthread_cond_t c = PTHREAD_COND_INITIALIZER;
4
5 void thr_exit() {
6 Pthread_mutex_lock(&m);
7 done = 1;
8 Pthread_cond_signal(&c);
9 Pthread_mutex_unlock(&m);
10 }
11
12 void *child(void *arg) {
13 printf("child\n");
14 thr_exit();
15 return NULL;
16 }
17
18 void thr_join() {
19 Pthread_mutex_lock(&m);
20 while (done == 0)
21 Pthread_cond_wait(&c, &m);
22 Pthread_mutex_unlock(&m);
23 }
24
25 int main(int argc, char *argv[]) {
26 printf("parent: begin\n");
27 pthread_t p;
28 Pthread_create(&p, NULL, child, NULL);
29 thr_join();
30 printf("parent: end\n");
31 return 0;
32 }

Explicação do código

2. Entender o problema do produtor consumidor.

Imagine uma ou mais threads produtoras e uma ou mais threads consumidores. Os produtores geram dados e os colocam em um buffer; os consumidores pegam os ditos itens do buffer e os consomem de alguma forma. Como o buffer é um recurso compartilhado, devemos, é claro, requerer acesso sincronizado a ele, para que não surja uma condição de corrida. Para isso, iremos usar duas funções: a função put() para por e a função get() para limpar. Agora imagine que temos apenas um único produtor e um único consumidor. Obviamente, as rotinas put () e get () têm seções críticas dentro , pois put () atualiza o buffer e get () lê a partir dele. Contudo, colocar um lock em torno do código não funciona; precisamos de algo mais (conditional variables).

3. Entender os problemas existentes nos códigos das pg. 7 e 9

1 void *producer(void *arg) {
2 int i;
3 int loops = (int) arg;
4 for (i = 0; i < loops; i++) {
5 put(i);
6 }
7 }
8
9 void *consumer(void *arg) {
10 while (1) {
11 int tmp = get();
12 printf("%d\n", tmp);
13 }
14 }

// Problemas -> Não temos variáveis condicionais nem travas seções
// críticas 30.07

1 int loops; // must initialize somewhere...
2 cond_t cond;
3 mutex_t mutex;
4
5 void *producer(void *arg) {
6 int i;
7 for (i = 0; i < loops; i++) {
8 Pthread_mutex_lock(&mutex); // p1
9 if (count == 1) // p2
10 Pthread_cond_wait(&cond, &mutex); // p3
11 put(i); // p4
12 Pthread_cond_signal(&cond); // p5
13 Pthread_mutex_unlock(&mutex); // p6
14 }
15 }
16
17 void *consumer(void *arg) {
18 int i;
19 for (i = 0; i < loops; i++) {
20 Pthread_mutex_lock(&mutex); // c1
21 if (count == 0) // c2
22 Pthread_cond_wait(&cond, &mutex); // c3
23 int tmp = get(); // c4
24 Pthread_cond_signal(&cond); // c5
25 Pthread_mutex_unlock(&mutex); // c6
26 printf("%d\n", tmp);
27 }
28 }

/* Problemas -> 
if statement -> while (mesa semantics)
só uma variável condicional
1 - 1 funciona */

//30.08

O problema ocorre quando outro consumidor (Tc2) consome o valor existente no buffer. Agora, assumindo que Tc1 execute, antes de retornar do wait() ele readquire a trava e então retorna. Ele então, chama get(), mas não há buffers para consumir. Claramente, Tc1 não deveria consumir já que Tc2 consumiu primeiro os valores que haviam no buffer.

4. Entender as retificações existentes no código da pg. 11.

💡 No código da página 11, foi feito uma retificação, temos que na página 09, foi usado um condição if que faz a verificação uma única vez, neste caso o consumidor acorda (mantendo o bloqueio) e verifica novamente o estado da variável compartilhada imediatamente, e se caso nesse ponto o buffer estiver vazio, o consumidor simplesmente volta a dormir novamente. E o contrário também é valido, dessa vez para o produtor.

No código da página 11, foi feito uma retificação, temos que na página 09, o problema ocorreu quando dois consumidores executaram primeiro (Tc1 e Tc2) e ambos vão dormir. Então, o produtor executa, coloca o valor no buffer e acorda um dos consumidores. O produtor então, volta e tenta recolocar mais dados no buffer, entretanto, como o buffer agora está cheiro, o produtor é colocado para esperar. Agora então, temos um consumir pronto para executar e duas threads dormindo, esperando uma condição. O consumidor Tc1 acorda retornando de um wait() recheca as condições e encontrando o buffer cheio, consome os valores. O consumidor então, sinaliza a condição acordando APENAS UMA thread que está dormindo, entretanto, qual thread ele deve acordar? Ele deveria acordar o produtor, mas o cenário onde ele acorda outro consumidor também existe e aí teríamos um problema.

While → Mesa semantics

5. Entender o código para buffer com várias posições

No código, são criadas duas variáveis condicionais, e dessa maneira, as threads do produtor esperam a condição empty e os sinais fill. Por outro lado, os threads do consumidor aguardam o fill e sinalizam empty. Fazendo isso, o segundo problema onde todos os consumidores dormirem é evitado por design: um consumidor nunca pode acordar acidentalmente um consumidor e um produtor nunca pode acordar um produtor acidentalmente.

int buffer[MAX];
2 int fill_ptr = 0;
3 int use_ptr = 0;
4 int count = 0;
5
6 void put(int value) {
7 buffer[fill_ptr] = value;
8 fill_ptr = (fill_ptr + 1) % MAX;
9 count++;
10 }
11
12 int get() {
13 int tmp = buffer[use_ptr];
14 use_ptr = (use_ptr + 1) % MAX;
15 count--;
16 return tmp;
17 }

• Funções put e get corretas

1 cond_t empty, fill;
2 mutex_t mutex;
3
4 void *producer(void *arg) {
5 int i;
6 for (i = 0; i < loops; i++) {
7 Pthread_mutex_lock(&mutex); // p1
8 while (count == MAX) // p2
9 Pthread_cond_wait(&empty, &mutex); // p3
10 put(i); // p4
11 Pthread_cond_signal(&fill); // p5
12 Pthread_mutex_unlock(&mutex); // p6
13 }
14 }
15
16 void *consumer(void *arg) {
17 int i;
18 for (i = 0; i < loops; i++) {
19 Pthread_mutex_lock(&mutex); // c1
20 while (count == 0) // c2
21 Pthread_cond_wait(&fill, &mutex); // c3
22 int tmp = get(); // c4
23 Pthread_cond_signal(&empty); // c5
24 Pthread_mutex_unlock(&mutex); // c6
25 printf("%d\n", tmp);
26 }
27 }

• Sincronização produtor/consumidor correta

31) Semaphores

1. O que é um semáforo? Quais as operações executadas sobre eles?

Um semáforo é um objeto com um valor inteiro que podemos manipular com duas rotinas; no padrão POSIX, essas rotinas são sem_wait() e sem_post(). Como o valor inicial do semáforo determina seu comportamento, antes de chamar qualquer rotina para interagir com o semáforo, devemos primeiro inicializá-lo com algum valor.

1 int sem_wait(sem_t *s) {
2 /*decrement the value of semaphore s by one
3 wait if value of semaphore s is negative*/
4 }
5
6 int sem_post(sem_t *s) {
7 /*increment the value of semaphore s by one
8 if there are one or more threads waiting, wake one*/
9 }

As operações de incrementar e decrementar devem ser operações atômicas, ou indivisíveis, ou seja, enquanto um processo estiver executando uma dessas duas operações, nenhum outro processo pode executar outra operação sob o mesmo semáforo, devendo esperar que o primeiro processo encerre a sua operação sob o semáforo. Essa obrigação evita condições de disputa entre vários processos.

2. O que é um semáforo binário?

O semáforo binário é um objeto com valores restritos de 0 ou 1. Um semáforo binário é bem útil quando usado como uma trava, já que as travas só tem dois estados (seguro e não seguro).

3. Como se usa semáforos com a finalidade de gerar ordem de execução?

Neste padrão de uso, muitas vezes encontramos uma thread esperando que algo aconteça, e outro thread fazendo que algo aconteça e sinalize que aconteceu, despertando assim a thread em espera. Estamos, portanto, usando o semáforo como uma primitiva de ordenação. Para se usar semáforos com a finalidade de gerar ordem de execução, o pai simplesmente chama a rotina sem_wait() e seu filho chama a rotina sem_post() para esperar a condição de seu filho terminar sua execução se tornar verdadeira.

Entretanto, uma pergunta pode surgir: Qual o valor inicial do semáforo nesse caso?

E a resposta para isso é que o valor inicial precisa ser setado para 0 e ao longo da execução pode variar para 1 e -1.

4. Entender o uso de semáforos no problema do produtor consumidor. Entender os erros nas implementações das pg. 7 e 9.

→ A utilização de semáforos garante os dois tipos básicos de sincronização: - Exclusão Mútua e Sinalização

→ O problema do produtor/consumidor consiste de

– um processo que produz dados

– para serem consumidos por outro processo.

Os dados  são  armazenados temporariamente num buffer enquanto esperam para serem utilizados.

→ 31.10 Primeira tentativa de solução: Introduzimos dois semáforos empty e full que as threads usarão para indicar quando uma entrada do buffer está vazia ou preenchida, respectivamente. Nessa primeira tentativa, o produtor primeiro espera o buffer ficar vazio para inserir dados nele (esse exemplo, pensado com somente um buffer no array, ou seja, MAX = 1, retorna os resultados esperados). Problema: Race condition em casos onde MAX > 1 (mais de um buffer no array). Imagine que dois produtores estão chamando put() ao mesmo tempo. Assumimos que o produtor P1 executa primeiro e começa a preencher a primeira entrada do buffer. Antes que ele tenha chance de aumentar o contador, ele é interrompido e o produtor P2 inicia, sobrescrevendo os dados o elemento de posição 0 no buffer, resultando numa perda de dados. Solução: Adicionar exclusão mútua, colocando travas em torno das regiões críticas put() e get().

→ Solução 2: Adicionar exclusão mútua, já que o preenchimento do buffer e a incrementação são seções críticas. Dessa forma, vamos usar o semáforo binário para colocar algumas travas nas regiões críticas. Essa ideia parece muito boa, entretanto, cai no problema das Deadlocks. Ele ocorre pois o consumidor segura a mutex e está esperando para alguém sinalizar enquanto o produtor poderia sinalizar, mas está esperando pela mutex. Dessa forma, ambos estão presos, esperando um pelo outro, um deadlock clássico.

5. Porquê o código apresentado na pg 10 funciona?

O código na página 10 funciona pois reduzimos o escopo da lock, movendo tanto a aquisição quanto a liberação da mutex para somente em torno da região crítica, colocando os sinais full e empty para fora do escopo. Caso isso não ocorra, temos um clássico exemplo de deadlock, onde ambos estão presos, esperando um pelo outro.

6. Entender os problemas do leitor escritor.

O problema dos leitores e escritores de forma simples é um problema onde se tem uma região critica onde threads podem ler (somente querer saber o que consta na região crítica) ou escrever (querer alterar valor na região crítica), levando em considerações alguns critérios.

Premissas:

➢ Leitor é aquele processo que acessa, mas não altera a informação.

➢ Escritor é aquele que acessa a informação e faz alterações na mesma.

Com isso temos os seguintes problemas:

➢ Leitores x Sinalização

• Se considera que sempre há algo a ler

• Se a leitura for sequencial, o final de arquivo é um caso normal

➢ Escritores x Sinalização.

• Se considera que sempre há espaço (disco, ...) para acréscimo de dados

• Em caso mais realista o escritor recebe um aviso de overflow e não fica bloqueado;

Com isso, temos:

➢ vários processos leitores utilizando ao mesmo tempo a informação compartilhada e uma vez que nenhum desses processos realiza alterações nas informações e este acesso deverá ser exclusivo a este processo, já que usualmente um leitor não poderá ler durante a escrita, os leitores podem facilmente fazer os escritores passarem fome (starve). Dessa forma, então,  principal problema é com relação à justiça. Se um leitor adquiriu uma read lock, mais leitores poderão adquirir ela também, entretanto, se qualquer thread quiser adquirir uma write lock, ela terá de esperar até que todos os leitores estejam terminados, já que o último leitor a sair da seção crítica chamaria um sem_post() e liberaria um escritor esperando para adquirir uma trava.

7. Entender o problema dos filósofos famintos

A configuração básica para o problema é esta: suponha que há cinco “filósofos” sentados ao redor de uma mesa. Entre cada par de filósofos está um único garfo (e, portanto, cinco no total). Cada um dos filósofos tem momentos em que pensa, e não precisa de nenhum garfo, e horários onde comem. Para comer, um filósofo precisa de dois garfos, ambos o que está à esquerda e o que está à direita. A contenção para estes bifurcações e os problemas de sincronização decorrentes são o que torna este um problema que estudamos em programação concorrente.

Aqui está o loop básico para cada filósofo assumindo que cada um tem um identificado de thread único p de 0 a 4:

while(1){
	think();
	get_forks();
	eat();
	put_forks();
}

O desafio principal é, portanto, escrever as rotinas get_forks() e put_forks() de uma forma que não tenha deadlock, nenhum filósofo fique faminto (nunca tendo o que comer) e a concorrência seja alta (o máximo de filósofos comam ao mesmo tempo de forma possível).

A primeira solução descrita pelo livro é fazer o filósofo simplesmente pegar o garfo a sua esquerda, entretanto, essa solução gera o problema de deadlock já que os filósofos ficarão esperando eternamente um outro filósofo soltar o garfo.

A maneira mais simples de atacar esse problema é mudar a forma como os garfos são adquiridos por pelo menos um dos filósofos. Especificamente, vamos supor que o filósofo 4 (o de número mais alto) recebe os garfos em uma ordem diferente da outros; o código put_forks() permanece o mesmo. Porque o último filósofo tenta agarrar à direita antes da esquerda, não há situação em que cada filósofo pega um garfo e fica preso esperando outro; o ciclo de espera é quebrado.

32) Common Concurrency Problems

1. Entender o bug causado por violação de atomicidade

O bug causado por violação de atomicidade ocorre quando uma thread acessa o conteúdo de seção crítica de código, influenciando no resultado da execução de outras threads e violando o conceito de atomicidade.

→ Definição formal: Uma região de código tem intenção de ser atômica, mas a atomicidade não é reforçada durante a execução.

→ Solução: Adição de locks para a região crítica.

2. Entender o bug causado por violação de ordem de execução

→ Definição formal: A ordem desejada entre dois grupos de acessos de memória é invertida ( por exemplo, A deve sempre ser executado antes de B, porém a ordem não é reforçada durante a execução)

→ Solução: Adição de variáveis condicionais para inserir sincronização.

3. Entender o que é um deadlock. Quais as condições para a ocorrência do mesmo?

Deadlock é um problema clássico que aparece em muitos sistemas concorrentes. Ela ocorre quando, por exemplo, uma thread 1 está segurando uma trava e esperando por outra trava. Infelizmente, a thread 2, que segura a trava 2 está esperando pela trava 1 ser solta. Como cada thread espera pela outra nenhuma das duas continua a execução.

Condições para Deadlock:

• Mutual exclusion: Threads obtém controle exclusivo de recursos que elas requerem (ex: thread pega um lock)
• Hold-and-wait: Threads seguram recursos alocados para ela (ex: locks que elas já adquiriram) enquanto esperam por recursos adicionais (ex: locks que elas querem adquirir)
• No preemption: Recursos (ex: locks) não podem ser removidas forçadamente de threads que estão segurando eles.
• Circular wait: Existe uma cadeia circular de threads de tal forma que cada thread segura um ou mais recursos (ex: travas) que estão sendo requeridas por uma thread seguinte na cadeia.

4. Entender as prevenções baseadas no tratamento das condições de ocorrência.

→ Circular Wait: Provavelmente a técnica de prevenção mais prática (e certamente aquela que é mais frequentemente empregada) é escrever seu código de trava de forma que você nunca irá induzir uma espera circular. A maneira mais direta de fazer isso é fornecer uma ordenação total na aquisição da trava. Por exemplo, se houver apenas duas travas no sistema (L1 e L2), você pode evitar o deadlock sempre adquirindo L1 antes de L2. Essa ordem estrita garante que nenhuma espera cíclica surja; portanto, nenhum deadlock.

Em sistemas mais complexos, lógicamente, mais de duas locks existem e dessa forma, uma ordenação total é difícil de atingir. Nesses casos, uma ordenação parcial pode ser uma forma fácil de estruturar a aquisição de travas de forma a evitar o deadlock.

→ Hold and Wait: O requisito de hold and wait para deadlocks pode ser evitado adquirindo todas as travas de uma só vez, atomicamente. Na prática, se faz algo parecido com:

1 pthread_mutex_lock(prevention); // begin acquisition
2 pthread_mutex_lock(L1);
3 pthread_mutex_lock(L2);
4 ...
5 pthread_mutex_unlock(prevention); // end

Ao pegar primeiro a trava prevention, este código garante que nenhuma troca de thread inoportuna pode ocorrer no meio da aquisição da trava e, portanto, o deadlock pode mais uma vez ser evitado. Claro, isto requer que a qualquer momento que uma thread obtém uma trava, ela primeiro adquire a trava de prevenção global. Por exemplo, se outra thread estava tentando capturar as travas L1 e L2 em uma ordem diferente, estaria tudo bem, porque estaria segurando a trava de prevenção enquanto o faz.

→ No Preemption: Como geralmente vemos as travas como retidas até que destravar seja chamada, várias aquisições de travas muitas vezes nos trazem problemas porque, ao esperar por uma trava estamos segurando outra. Muitas bibliotecas de thread fornecem um conjunto mais flexível de interfaces para ajudar a evitar essa situação. Especificamente, a rotina pthread_mutex_trylock () ou pega a trava (se estiver disponível) e retorna sucesso ou retorna um código de erro indicando que a trava está retida; no último caso, você pode tentar novamente mais tarde se quiser pegar essa trava. Tal interface pode ser usada dessa forma para garantir a construção de um código sem deadlocks:

1 top:
2 pthread_mutex_lock(L1);
3 if (pthread_mutex_trylock(L2) != 0) {
4 pthread_mutex_unlock(L1);
5 goto top;
6 }

→ Mutual Exclusion: A técnica de prevenção final seria evitar a necessidade de exclusão mútua em geral. Em geral, sabemos que isso é difícil, porque o código que desejamos executar realmente tem seções críticas. Então o que nós podemos fazer? Herlihy teve a ideia de que era possível projetar várias estruturas de dados sem travas. A ideia por trás da abordagem sem travas (e abordagens relacionadas, como a sem espera) é simples: usando poderosas instruções de hardware, você pode construir estruturas de dados de uma maneira que não requeira travamento explícito.

5. Entender o Deadlock Avoidance via Scheduling

Em vez de prevenção de deadlock, em alguns cenários, evitar as deadlock é preferível. Evitar requer algum conhecimento global de quais travas vários encadeamentos podem pegar durante sua execução e, subsequentemente, programar esses encadeamentos de forma a garantir que nenhum conflito ocorra.

Ex:

6. O que compõe a estratégia de detectar e recuperar no contexto de deadlocks?

Uma última estratégia é permitir que deadlocks ocorram ocasionalmente e então tomar uma atitude quando ela for detectada. Por exemplo, se um S.O travar uma vez por ano, você simplesmente reiniciaria ele e continuaria seu trabalho. Se as dealocks são raras, essa solução parece muito pragmática.

Muitos sistemas de bancos de dados implementam essa estratégia, executando um detector de deadlocks periodicamente e reinicializando em pontos problemáticos (com ou sem a presença de um humano).

33) Event-based Concurrency (Advanced)

O conteúdo deste capítulo não será coberto em avaliações, mas indico responder as seguintes perguntas:

1. Entender o funcionamento do select().

2. Qual o problema para o modelo de concorrência baseada em eventos tratada via loop trazido pelas chamadas bloqueantes?

3. Porquê gerenciamento de estado é essencial para o modelo de concorrência baseada em eventos tratada via loop?

FIM DO CONTEÚDO DA P2

Trabalho S.O

P3