Objectivos do Capitulo

Programação múltipla, tempo partilhado e processo paralelo criaram a noção de grupos cooperativos de processos sequenciais possíveis. Operações concorrentes em comum com relatos de grupos de processos permitiram uma única aplicação para obter vantagens do paralelismo entre o CPU e os dispositivos de ‘input/output’ (entrada e saida) num único processador e em colaboração CPUs num processador múltiplo. Porém múltiplos processos cooperativos introduzem o potencial para novos problemas no software de implementações, incluindo o ‘deadlock’ as existentes secções criticas e a possibilidade da não determinação nestas computações. Estes princípios acontecem quando dois ou mais processos intendem em competir, ou para partilhar cooperativamente, os recursos (incluindo informação). É importante perceber o potencial das interacções com os processos antes de desenhar máquinas que suportam essas interacções. Por isso a primeira parte deste capitulo discute a naturezas em geral dessas interacções. O resto foca nas ferramentas clássicas de sincronização, o semáforo, incluindo implementações técnicas. A sincronização é necessária nos uniprocessadores, multiprocessadores e redes. Porém o problema é suficientemente complexo por isso é tradicionalmente estudado no ambiente do uniprocessador. Nesta discussão, os resultados são generalizados para os multiprocessadores e para redes (capitulo 17). Os fundamentos da sincronização são endereçados na ordem em que eles foram derivados.

1.Interacção de Processos

Programas de Computador são realizações de series de algoritmos, passo-a-passo, procedimentos para concretizar alguma informação de processamento de tarefa. O uso da serie de algoritmos para especificar computações em serie tem dominado a programação por toda a metade do século. Este ambiente de computação tem focado no suporte de computação em serie. Enquanto a programação popular com o C e o C++ tem descuidado para a ocorrência de endereço, o que está subjacente á tecnologia do hardware tem sistematicamente movido bastante pela distribuição e computação paralela das máquinas. Pressões económicas têm levado os requerimentos das aplicações para o uso de hardware distribuído e paralelo. Este rumo aparente, por exemplo, manuseamento contemporâneo de informação de sistemas, ambiente de computação de escritório e aplicações numéricas. 

1.1.Secções Criticas

Suponha que uma aplicação é escrita para que dois processos, p1 e p2, executam concorrendo para o acesso comum de uma variável inteira, x. Por exemplo, p1 poderá manusear créditos para uma conta, enquanto p2 manuseia os débitos dessa mesma conta. O seguinte código exemplifica como os processos referenciam o balanço da partilha. 

Shared float balance;                 /* shared variable */
Code Schema For p1                  Code Schema For p2
         ….                                   …
balance=balance+amount;        balance=balance-amount;

Este alto nível de linguagem será compilada para uma pequena máquina de instruções, como as seguintes:

Schema For p1                Schema For p2
Load r1,balance               load r1,balance
Load r2,amount               load r2,amount
Load r1,r2                       sub r1,r2
Store r1,balance              store r1,balance

O problema da secção critica pode ocorrer quando as linhas de código são executadas. Supondo que p1 está a correr num uni-processador quando o intervalo de tempo expira. Em particular, supondo p1 está a executar a instrução:

Load r2,amount 

Se a marcação seguinte selecciona o processo p2 para correr e executa o seu código de linguagem máquina da linha “balance=balance-amount;” de instrução antes de p1 reganhe controlo do processador, assim a condição de “corrida”  existe entre p1 e p2. Se p1 ganha a corrida, os valores que ele tinha lido para a versão de R1 e R2 serão adicionados juntamente e escrita para a variável partilhada na memória sem danos. Se o p2 ganhe a corrida ele irá ler o valor original de “balance” computa a diferença entre “balance” e “amount”, e armazena a diferença na localização da memória contendo “balance”. P1 irá resumir usando o valor antigo de “balance” que foi previamente carregado para r1; o valor antigo foi salvado quando p1 foi removido do processador. O processo p1 irá computar a soma de “balance” e de “amount” e depois gera um valor diferente de “balance” de onde p2 escreveu quando p2 estava bloqueado. A actualização de “balance” por p2 será perdido. Os programas definindo p1 e p2 têm uma secção critica que respeita o seu uso da variável partilhada “balance”. Para p1 a secção critica é  computando a soma de “balance” e “amount”, mas para p2 a secção critica é computando a diferença entre “balance” e “amount”. A execução concorrente de dois processos não é garantidamente determinada, desde que diferentes execuções dos mesmos programas na mesma data poderá não produzir o mesmo resultado. Numa só execução, p1 poderá ganhar a corrida e na execução seguinte p2, este resulta num final diferente em qualquer variável partilhada. Não é possível detectar um problema considerando apenas p1’s programas ou só p2’s programas. O problema ocorre por causa da partilha, não por causa de algum erro na sequência de código. O problema da  secção critica pode ser evitada tendo, ou um processo na sua correspondente secção critica em qualquer tempo que ele precise para ele o ser e que espere o outro processo nesta secção critica. Com é que os dois processos podem cooperar para entrar nas suas secções criticas? Num sistema multiprogramado, qualquer interrupção causa problema, porque ele é capaz de por a correr o programador. Por causa do estado de operação de salvamento implícito com o contexto de troca, um processo pode resumir uma execução usando dados inconsistente carregado nos registos. Se o programador realize a ocorrência de uma interrupção pode levar para um resultado errado, ele ou ela pode desligar as interrupções do programa enquanto ele estava executando a parte critica desde processo. 

1.2.Deadlock

 Numa secção  de deadlock, dois ou mais processos vão para um estado onde cada onde está segurando um recurso que o outro está requisitando. Já que uma operação de “request” bloqueia o “caller” até que o recurso se torne alojado, nem o processo terá o desejo de recurso alojado e ambos permaneceram nos estado bloqueados para sempre. No processo de sincronização, nó focamos no caso em que o recurso está fechado ou numa secção critica. O Capitulo 10 considera o problema geral pelo que onde um recurso pode se qualquer recurso no sistema.

 2.Coordenação de Processos

 O necessitar de interacções entre processos aponta para o necessitar de sincronismo, e o sincronismo introduz os problemas da secção critica e dos “deadlocks”. “FORK”, “JOIN” e “QUIT” foram introduzidas no capitulo 6 como mecanismos de criação e destruição de processos. Eles também podem ser usados para sincronizar partes de uma computação concorrente. No diagrama seguinte é representado como a computação usa o FORK, JOIN e o QUIT para alcançar concorrência. O processo inicial cria um processo de usuário, A, fazendo uma operação de FORK. Processa A e executa FORK para executar o processo B. A e B e depois JOIN, deixando apenas um processo a correr, diz B. Depois B executa um FORK para criar o processo C. Processo B e o C executa concorrendo e depois  um JOIN, deixando apenas um processo outra vez diz B.

Finalmente, o processo B executa um QUIT para completar a computação. Neste exemplo, existe 3 processos distintos no esquema da aplicação (ignorando o processo inicial).A figura ao lado representa uma aproximação diferente usando um operador de sincronização similar ao do mecanismo do LOCK introduzido na secção anterior. As duas aproximações nas figuras também podem ser usados mas fazer a mesma computação com a mesma quantidade de operação de “overlapped” . Qual a aproximação preferida? Já que a introdução do FORK, JOIN e do QUIT, desenhadores de sistemas operativos têm observado que a criação de processos e suas destruições tendem para ser operações caras porque requerem manipulação de descrição de processos, protecção de mecanismo e gestão de mecanismos de memórias. Porém a operação de sincronização pode se difícil como um requisito de recursos no recurso consumido tal como um par de variáveis boleanas, e podem ser implementadas mais eficientemente. Por causa do número dos ciclos da máquina para a criação/destruição existe 3 ou mais ordens de maior magnitude e depois para a sincronização, a tendência para sistemas operativos contemporâneos é para introduzir mecanismos de sincronização para complementar o processo de criação/destruição de operações.

Existem 3 aproximações básicas para implementação de estratégias de Sincronização:

·        Usar apenas software vulgar de algoritmos e variáveis partilhadas.

·        Ligue e desligue interrupções nas situações criticas como representado e explicado atrás.

·        Incorpore mecanismos especializados no hardware e/ou no suporte de sincronização do sistema operativo.

 3.Semáforos

 Um semáforo é um tipo de dados de um sistema operativo abstracto que executa operações similares ao das funções ENTER e EXIT. Antes de discutir os princípios das operações de semáforos, esta secção descreve o comportamento dos semáforos. Já atrás discutido, um processo não pode entrar na secção critica de outro processo já se na sua secção critica. Quando um processo está prestes a entrar na sua secção critica, primeiro determina se outro processo está na zona critica. Se está, o segundo processo sincroniza a sua operação bloqueando-o até que o primeiro processo saia da secção critica. Uma solução aceitável para o problema da secção critica é necessário seguir os seguintes tópicos:

·        Só um processo de cada vez é permitido estar na secção critica.

·        Supondo que uma secção critica está livre. Se um conjunto de processos indica a necessidade de entrar na secção critica, então apenas aqueles processos batalhando para a secção critica participar na selecção do processo para entrar a secção critica.

·        Assim que um processo tente entrar na secção critica, não pode se posto indefinidamente nem que outro processo esteja na secção critica.

·        Depois de um processo requisitar a entrada na secção critica, apenas um numero de outros processos podem ser autorizados a entrar a sua secção critica antes de o processo original entrar na secção critica.

 3.1.Princípios de Operações

 Um semáforo, s, é uma variável não negativa alterada ou testada apenas por uma ou duas rotinas indivisíveis:

V(s):[s=s+1]
P(s):[while (s=0) {wait}; s=s-1]

Os parentes rectos limitando as operações nas rotinas de acesso indica que as operações são operações indivisíveis, ou atómicas. Na operação V, o processo que executa a rotina não pode ser interrompido até que ele tenha terminado a rotina. A operação P é mais complexa. Se ‘s’ é maior que ‘0’, ele é testado e decrementado como um operador indivisível. Porém , se for igual a ‘0’, o processo executando a operação P pode ser interrompido quando se executa um comando WAIT no espaço do ‘loop’ WHILE.

3.2.Considerações Práticas

Existem poucas considerações práticas relacionadas á implementação de semáforos. O resto desta secção é sobre como implementar semáforos, para evitar ‘busy-waiting’ nos semáforos, e para vêr os recursos dos semáforos. Tambêm considerado um importante detalhe relacionado com a implementação da operação V: activo contra comportamento passivo.  

3.2.1Implentação de semáforos

            Quando um processo bloqueia num semáforo, a interrupção é activada; apenas estão desactivados quando o valor dos semáforos é manipulada. Tem dois importantes efeitos:

·        Minimos efeitos no sistema de ‘input/output’

·        Enquanto um processo mantém um semáforo, previne-se apenas competições de outros processos que não correm na secção critica. Todos os outros processos não são afectados pelo facto que outro processo está na sua secção critica.

Semáforos podem ser implementados sem desactivar interrupções  se o Hardware fizer uma pequena provisão especial. Uma directa implementação das instruções P e V é um pouco dificil por causa da necessidade para acomodar o ‘loop’ na operação P. Por sua vez, uma implementação de um uniprocessador apenas quererá lidar com o calendário para a implementação de P, enrão parte da instrução será implementada no hardware e parte no software. O sistema operativo pode criar um recurso abstracto para cada semáforo. Então ele usa gestores de recursos para bloquear processos quando eles executarem um processo P  como que eles tivessem executado uma operação ‘request’ num recurso convencional. Os factos tornam como o recurso da gestão do semáforo pode simular correctamente implementações de acesso aos semáforos sem usar interrupções.

A instrução TS (test-and-set) é o caminho dominante para concluir o efeito de P e V. A TS é uma instrução simples que pode ser incluida no reportório da máquina sem muito custo. A localização da memória da TS, causa que a localização da memória m para ser carregada no registo do CPU e a memória para ser escrita com o valor ‘true’.

3.2.2.Implementação activa e passiva de semáforos

 4.MultiProcessadores de Memória partilhada

 As secções 1 e 3 descreveram uma técnica de implementação de semáforos desligando as interrupções. Num multiprocessador de memória partilhada, é insuficiente, já que desligando as interrupções num CPU não afecta as interrupções noutros CPUs. Por isso multiprocessadores de memória partilhada comercias usam todos instruções especializadas como a TS para implementar semáforos. Num multiprocessador de memória partilhada, a memória pode ser programada para o suporte ao TS. Quando um processo usa a tecnologia de ‘busy-wait’, o único processador que não consegue processar outro trabalho é o único em que o processo bloqueado é executado. Outro processo capaz de executar a operação V pode ser corrido num diferente processador. Por isso o ‘busy-wait’ é um mecanismo de rápido reconhecimento no instante que o processo de torna desbloqueado. Em alguns casos, é preferível o uso de N processadores para que seja feito um ‘pool’ á variável s.hold para que detecte o momento mais breve em que o processo bloqueado se torne desbloqueado. Sistemas operativos para estes processadores são sistemas que tipicamente suportam este cenário incluindo ‘spin locks’ no interface do sistema operativo. Um ‘spin lock’ é um procedimento que repetidamente executa uma instrução TS para testar e especificada variável. Para completar o ‘lock’ do interface da máquina abstracta, serão feitos chamamentos para criar um ‘lock’, para fechar e abrir, e para bloquear a fechadura(‘lock’), e muitas vezes num chamamento de não bloqueio da fechadura. Este ultimo chamamento é usado se um processo detecta que está fechado fora de uma zona critica, pode executar outra operações.

 5.Resumo

 As técnicas básicas de sincronização são discutidas neste capitulo são o fundamento de processos concorrentes. Semáforos são o mecanismo básico adjacente à sincronização. De um ponto de vista pragmático, semáforos podem ser implementados num sistema operativo se o hardware fornecer uma simples suporte, como a instrução TS. A implementação mais directa de um semáforo (usando a instrução TS) leva a ‘busy-waiting. Esta espera pode ser endereçada construindo a implementação de semáforo para que intercala com o controlador de tarefas. Quando um processo entra na fase ‘busy-wainting’, ele deverá indicar ao controlador de tarefas. Este capitulo define a fundação da sincronização e discute a complexidade em lidar com o sincronismo usando os semáforos. O próximo capitulo refere-se á sincronização abstracta.