Problema de despertar perdido - como o UNIX lida com ele [fechado]

1

(Eu dou contexto para a minha pergunta primeiro, a questão em si é na parte inferior, onde diz PERGUNTA em negrito).

Tome dois processos A e B. A verifica uma condição, vê que ela não está satisfeita e vai dormir / bloquear. B satisfaz a condição e acorda A. Se tudo acontece nessa ordem, então não temos problemas.

Agora, se o agendador for:

  1. A checks condition, it's not satisfied
  2. B satisfies condition, wake A up
  3. A goes to sleep/blocks

depois perdemos o despertar que B executa para A.

Eu me deparei com esse problema no contexto da implementação de um semáforo de bloqueio (ou seja, um que coloca o thread wait () em sleep / bloqueia em vez de deixá-lo aguardar). Várias fontes dão soluções para isso, entre elas:

Andrew Tanenbaum, Sistemas Operacionais Modernos, 4a edição, p. 130:

The essence of the problem here is that a wakeup sent to a process that is not (yet) sleeping is lost. If it were not lost, everything would work. A quick fix is to modify the rules to add a wakeup waiting bit to the picture. When a wakeup is sent to a process that is still awake, this bit is set. Later, when the process tries to go to sleep, if the wakeup waiting bit is on, it will be turned off, but the process will stay awake. The wakeup waiting bit is a piggy bank for storing wakeup signals. The consumer clears the wakeup waiting bit in every iteration of the loop.

Este artigo na revista Linux ("Kernel Korner - Dormir no Kernel", Linux Journal # 137) menciona algo parecido:

This code avoids the lost wake-up problem. How? We have changed our current state to TASK_INTERRUPTIBLE, before we test the condition. So, what has changed? The change is that whenever a wake_up_process is called for a process whose state is TASK_INTERRUPTIBLE or TASK_UNINTERRUPTIBLE, and the process has not yet called schedule(), the state of the process is changed back to TASK_RUNNING.

Thus, in the above example, even if a wake-up is delivered by process B at any point after the check for list_empty is made, the state of A automatically is changed to TASK_RUNNING. Hence, the call to schedule() does not put process A to sleep; it merely schedules it out for a while, as discussed earlier. Thus, the wake-up no longer is lost.

Pelo que entendi, isso basicamente diz "você pode marcar um processo como querer ir dormir / bloquear de tal forma que um despertar posterior possa cancelar a chamada tardia de bloqueio / soneca".

Por fim, estas anotações de aula nos parágrafos anteriores A partir de "O pseudo-código abaixo mostra a implementação de um tal semáforo, chamado de semáforo de bloqueio:" dá código para um semáforo de bloqueio e usa uma operação atômica "Release_mutex_and_block (csem.mutex);". Eles afirmam que:

Please notice that the P()ing process must atomically become unrunnable and release the mutex. This is becuase of the risk of a lost wakeup. Imagine the case where these were two different operations: release_mutex(xsem.mutex) and sleep(). If a context-switch would occur in between the release_mutex() and the sleep(), it would be possible for another process to perform a V() operation and attempt to dequeue_and_wakeup() the first process. Unfortunately, the first process isn't yet asleep, so it missed the wake-up -- instead, when it again runs, it immediately goes to sleep with no one left to wake it up.

Operating systems generally provide this support in the form of a sleep() system call that takes the mutex as a parameter. The kernel can then release the mutex and put the process to sleep in an environment free of interruptions (or otherwise protected).

PERGUNTA: Os processos no UNIX têm alguma maneira de marcá-los como "Estou pensando em ir dormir", ou um "bit de espera de ativação" como Tanenbaum chama? Existe uma chamada de sistema (sleep) (mutex) que atomicamente libera um mutex e, em seguida, coloca o processo em suspensão / bloqueia?

Provavelmente é um pouco aparente que eu não estou familiarizado com as chamadas do sistema e geralmente internos do SO; se houver qualquer suposição falsa aparente em minha pergunta ou uso indevido de terminologia, eu ficaria feliz em tê-los apontado para mim.

    
por G. Bach 18.07.2017 / 18:34

1 resposta

1

A solução clássica do Unixy é deixar o sinal de "despertar" consistir em escrever um byte para um canal que o processo de espera tentará ler.

(Se os processos não tiverem um ancestral comum que possa ajudar a configurar isso, um pipe nomeado pode ser usado).

O processo de espera pode então usar o select () syscall (ou uma de suas alternativas redesenhadas mais recentes, como pselect ou poll / epoll) para atomicamente executar "esperar até que algo esteja pronto para ler tal e tal descritor de arquivo ". Quando ele acordar, ele lerá e descartará tudo o que houver para ler, e então verificará o que o trabalho está pronto para isso.

    
por 18.07.2017 / 18:43