Problemas Clássicos

Produtor x Consumidor

Chamado de Produtor e o Consumidor (também conhecido como o problema do buffer limitado), consiste em um conjunto de processos que compartilham um mesmo buffer. Os processos chamados produtores põem informação no buffer. Os processos chamados consumidores retiram informação deste buffer.

Esse é um problema clássico em sistemas operacionais, que busca exemplificar de forma clara, situações de impasses que ocorrem no gerenciamento de processos de um sistema operacional. Para quem está iniciando na programação, esse problema se torna complexo, pois trabalhar com programação concorrente nem sempre é tão simples. Como sabemos, precisamos nos preocupar com acessos ilegais a certos recursos que são compartilhados entre os processos, e manter sincronismo entre os mesmos.

Para controlarmos o acesso a essas variáveis e termos sincronismo nas operações, vamos utilizar semáforos. Em ciência da computação, semáforo é uma variável especial protegida (ou tipo abstrato de dados) que tem como função o controle de acesso a recursos compartilhados (por exemplo, um espaço de armazenamento) num ambiente multitarefa. Com as variáveis do tipo pthread_mutex_t da biblioteca pthreads - Posix, podemos controlar esses dados com toda segurança. Outro controle importante é a demanda de processamento, espera ociosa, que o programa irá gerar, pois quando um processo não está liberado para gravar ou ler, deve entrar em estado de espera para não consumir processamento de graça, e deve ser avisado quando pode voltar a processar.

Problemas:

• O produtor insere em posição: Ainda não consumida

• O consumidor remove de posição: Já foi consumida

• Espera ociosa X Escalonamento do processo X Uso CPU

Solução:

• Exclusão mutua (semáforos)

• Fim da espera ociosa:

• Dormir (dow) /acordar (up) X Semáforos full/empty

• Mutex (Mutual exclusion)

Código na íntegra para solucionar este problema:

http://www.vivaolinux.com.br/artigo/O-Produtor-e-o-Consumidor/?pagina=5

Leitor x Escritor

Outra situação que ocorre com freqüência em sistemas concorrentes é o problema dos leitores/escritores. Neste caso, um conjunto de processos ou threads acessam de forma concorrente uma área de memória comum (compartilhada), na qual podem fazer leituras ou escritas de valores. As leituras podem ser feitas simultaneamente, pois não interferem umas com as outras, mas as escritas têm de ser feitas com acesso exclusivo à área compartilhada, para evitar condições de disputa. No exemplo da figura abaixo, os leitores e escritores acessam de forma concorrente uma matriz de inteiros M.

Solução: http://www.inf.ufsc.br/~bosco/ensino/ine5645/Leitores-Escritores.pdf

O jantar dos filósofos

É um problema clássico de acesso a recursos limitados, inventado em 1971 por Edsger Dijkstra como questão de exame.

O problema consiste em: Cinco filósofos estão sentados à volta de uma mesa. Cada filósofo alterna entre os estados de pensar e comer esparguete. Existe uma grande travessa de esparguete no centro da mesa. Para comer, o filósofo usa dois garfos, colocados nos dois lados (5 pratos, 5 garfos). Cada garfo pode ser usado pelo filósofo vizinho. Quando o filósofo quiser comer, ele tem que emprestar os garfos. O bloqueio ocorre se cada filósofo pegar um garfo e ficar à espera que o vizinho do outro lado liberte o segundo garfo.

Applet com a solução: http://www.inf.ufrgs.br/gppd/disc/inf01008/trabalhos/sem99-1/filosofos/applet.htm

Fontes: http://www.fatecsbc.edu.br/Dowload/sistemasoperacionais/socap04.pdf

http://computacaonaweb.blogspot.com/2008_11_01_archive.html

Links Relacionados:

1. http://ces33.wikidot.com/relas:alexandre

Links Interessantes

http://www.ibm.com/developerworks/linux/library/l-scheduler

http://devresources.linuxfoundation.org/craiger/hackbench

http://www.makelinux.net/reference?n=Scheduler

http://webee.technion.ac.il/courses/046209/Recitations/Linux_Scheduling.pdf

Test Kernel:
http://test.kernel.org/tko
http://test.kernel.org/autotest_slides.odp

Threads no Linux

O Linux não faz distinção entre threads e processos, pois todos os threads são implementados como um processo-padrão. A diferença consiste em que apenas os threads são capazes de compartilhar os recursos disponíveis.

Existem ainda os threads do kernel que são úteis para o kernel executar operações em segundo plano. Esses threads existem apenas no espaço do kernel e não tem um endereço, mas são programáveis e antecipados como processos normais, além de serem invocados apenas a partir de um outro thread através da função kernel threads().

Estados do Processo

 

Fluxo dos estados do processo

Escalonador Linux

O escalonador LINUX é baseado em time-sharing, ou seja, atua na divisão do tempo de processador entre os processos.

Scheduler é o programa encarregado de agendar os processos, isto é, ele deve escolher o próximo processo que vai rodar, deve decidir quando o tempo de um processo terminou, o que fazer com um processo quando ele requisita I/O e assim por diante. Ele é chamado de vários pontos do programa, como após colocar o processo corrente em uma fila de espera, no final de uma chamada de sistema ou qualquer outro momento em que se faz necessário escalonar os processos. Ao ser chamado, o scheduler tem uma seqüência de ações que devem ser tomadas para que seu trabalho possa ser feito. Essas ações se dividem em:

• Kernel Work: o scheduler deve realizar uma série de rotinas especifícas do kernel, e deve tratar da fila de esperas de tarefas do scheduler.

• Seleção de processo: o scheduler deve escolher o processo que irá rodar. A prioridade é o meio pelo qual ele escolhe.

• Troca de processos: o scheduler salva as condições que o processo atual apresenta (contexto específico do processo) e carrega o contexto do novo processo que irá rodar.

Em ambientes multiprocesados (SMP - Simultaneous Multi Processing), cada processador tem um scheduler para tratar separadamente quais processos irão rodar nele. Dessa forma, cada processo guarda informação sobre o processador atual e o último processador em que rodou. Processos que já tenham rodado em um processador tem preferência em relação aqueles que não tenham rodado ali ainda. Essa implementação permite um ligeiro acréscimo de ganho no desempenho do sistema.

O escalonador possui 140 níveis de prioridade (quanto menor o número, maior é a prioridade). Prioridades de 1 a 100 são para processos de tempo real; de 101 a 140 para os demais processos de usuário (interativos ou não interativos). Nos níveis de prioridade 101 a 140, os processos recebem

fatias de tempo de 20 ms.

• Os processos de tempo real podem ser FIFO ou Round Robin, e possuem uma prioridade estática.

• Processos FIFO executam até voluntariamente liberarem a CPU (o nível de prioridade é mantido e não são preemptivos).

• Processos Round Robin recebem fatias de tempo. Quando todos terminam suas fatias, é dada outra fatia e eles continuam rodando no mesmo nível de prioridade.

• A prioridade dos processos de usuário é a soma de sua prioridade básica (valor de seu nice) e seu bonus dinâmico, que varia de +5 a –5.

Thread de migração

•  Em cada processador roda uma thread de migração, cuja função é movimentar processos de um processador para outro. Como existe uma ready list por processador, a idéia é evitar que processadores fiquem ociosos enquanto outros estão sobrecarregados.
• A thread de migração é chamada periodicamente, a cada tick do relógio, e também explicitamente quando o sistema fica desbalanceado.

Políticas de Escalonamento

Existem critérios para o escalonamento dos processos em Linux:

• Policy: Pode haver duas políticas de escalonamento round-robin e first-in-first-out (FIFO).

• Priority: A prioridade do processo é dada de acordo com o tempo que ele gastou para executar (em jiffies). Jiffies é uma variável que indica a quantidade de tempo que um processo pode ser executado, onde cada valor atribuído depende de cada máquina. Quanto maior o tempo em uma execução anterior, menor a prioridade do processo.

• Real time priority: Esse recurso é usado para processo de tempo real. Através disso, os processos de tempo real podem ter prioridade relativa dentro desse conjunto. A prioridade pode ser alterada através de chamadas do sistema.

• Counter: É a quantidade de tempo (em jiffies) que os processos têm permissão para rodar. É setada a prioridade quando o processo é rodado pela primeira vez e decrementada a cada tick do clock.

Algoritmos de Escalonamento

No código do linux (arquivos include/linux/sched.h e kernel/sched.c) é possível encontrar quatro classes de escalonamento disponíveis: SCHED NORMAL, SCHED FIFO, SCHED RR e SCHED BATCH, é a partir delas que o escalonador escolhe um processo para ser executado.

SCHED NORMAL

Podemos considerar este tipo de escalonamento como convencional já que a ênfase é no timesharing (compartilhamento do tempo).

A fatia de tempo (ou fatia quantum) é um valor numérico que indica quanto tempo uma

determinada tarefa pode ser executada antes de ser antecipada (antes de ceder o processador a outro processo). O escalonador do Linux calcula a fatia de tempo necessária a uma tarefa a partir do seu comportamento, por exemplo, processos de E/S necessitam de um tempo menor do que processos vinculados ao processador. Para resolver esse conflito, o Linux mantém valores de fatia de tempo e prioridade relativamente altas para os processos vinculados à E/S (100 ms), em contra-partida, os processos não precisam utilizar toda a sua fatia de tempo de uma só vez (podem utiliza-la em intervalos) quando ela acaba o processo é considerado expirado e para ser escalonado novamente esperar que todos os outros tenham também a sua fatia esgotada.

Quando um processo expira é necessário que ele tenha a sua fatia de tempo recalculada (já que agora ela corresponde a zero), para facilitar o cálculo (que até então era feito utilizando um complexo loop) as novas versões do Linux (a partir da série 2.5) se utilizam de dois arrays de prioridade (um para processos ativos e outro para processos expirados). Esse recurso é útil porque reduz a complexidade do cálculo e o tempo perdido com o mesmo.

O escalonador deve conhecer o comportamento de uma dada tarefa para determinar a sua prioridade e a sua fatia de tempo, ele obtém essa informação observando quanto tempo esse processo passa dormindo e quanto tempo fica em estado executável (esse valor é armazenado na variável sleep avg na task struct) e assim calcula a sua fatia de tempo concedendo bônus ou penalizando-o dependendo de como utilizou o seu tempo. O Linux trabalha também com uma regra para evitar que processos obtenham uma fatia de tempo ilimitada.

Cálculo da fatia de tempo do processo

SCHED FIFO

A estratégia FIFO (First In, First Out) implementada no kernel do Linux consiste no conceito: primeiro processo de tempo-real a entrar é o primeiro a sair. Os processos FIFO de tempo real não podem ser antecipados por outro processo que não seja FIFO de tempo real, esses processos também não trabalham com fatias de tempo, ou seja, eles podem dispor do processador praticamente o tempo que necessitarem.

SCHED RR

A política SCHED RR (Round Robin _ alternância circular) funciona do mesmo modo que a FIFO, entretanto com ela os processos de tempo real podem ser interrompidos pelo relógio, ou melhor, eles executam durante uma determinada fatia do tempo do processador, assim que o tempo acaba eles são postos no final da fila de execução. Esta estratégia garante uma atribuição justa do tempo de processador para todos os processos Round Robin.

SCHED BATCH

Esta política está presente no código-fonte do Linux apenas a partir do kernel 2.6.16, e é uma política similar a utilizada em SCHED NORMAL, com exceção de que ela sempre tende a fazer o escalonador supor que o processo é vinculado ao rocessador, por esse motivo ele sofrerá penalidades que o desfavorecem nas decisões de escalonamento. Esta é uma estratégia útil para tarefas que não são interativas mas não desejam reduzir o seu valor bom.

Prioridades

O Linux trabalha com dois tipos de prioridade:

• Estática – exclusiva de processos em tempo real, neste caso a prioridade é definida pelo usuário e não é modificada pelo escalonador. Somente usuários com privilégios especiais no sistema podem definir processo de tempo real.

• Dinâmica – aplicada aos demais , sendo sua prioridade calculada em função da prioridade base do processo e a quantidade de tempo que lhe resta para execução.

Os processos de prioridade estática recebem prioridade maior que os de dinâmica.
As faixas de prioridade variam numa escala de -20 a +20. A prioridade padrão de uma tarefa é 0, com -20 sendo a mais alta. Só o administrador pode reajustar a prioridade de um processo para ser menor que 0, mas os usuários normais podem ajustar prioridades no alcance positivo. Este é usando após o comando 'renice', entretanto internamente o Linux usa um quantum contador de tempo (em ' jiffies') registrado no task_struct.
Processos novos herdam a prioridade de seus pais.

[Vídeo] Como usar o System Monitor do Ubuntu