Futex Basics

Futex (futex - abreviação de "Fast userspace mutex") é um mecanismo proposto pelos desenvolvedores Linux da IBM em 2002 e entrou no kernel no final de 2003. A idéia principal era fornecer uma maneira mais eficiente de sincronizar os threads do usuário com um número mínimo de chamadas para o kernel do SO.

Neste artigo, revisaremos os futexes, tentaremos entender os princípios de seu trabalho e também usá-los como tijolos para criar objetos de sincronização de nível superior (e familiares para nós).

Um ponto importante: os futexes são uma ferramenta de baixo nível; vale a pena usá-la diretamente apenas no desenvolvimento de bibliotecas fundamentais, como a biblioteca C / C ++ padrão. É muito improvável que você precise usar futex em um aplicativo regular.

Motivação

Antes do advento dos futexes, era necessário fazer chamadas do sistema (usando, por exemplo, semop ) cada vez para controlar o acesso a recursos compartilhados de vários encadeamentos, o que, como você sabe, consome muitos recursos, pois cada chamada requer a alternância do contexto do modo de usuário para o modo kernel. Com o aumento do número de núcleos nos processadores modernos e o aumento do número de threads no software aplicativo, isso se tornou um problema significativo. É ainda mais "ofensivo", uma vez que todas essas chamadas não possuem nenhuma função aplicada, não implementam nenhuma lógica comercial, mas apenas garantem a operação correta do restante do código.

A proposta de adicionar um novo conceito de "futex" ao sistema operacional foi baseada em uma observação simples: na maioria dos casos, uma tentativa de capturar um objeto de sincronização é bem-sucedida pela primeira vez. Os programadores escrevem o software de maneira que o menor tempo possível passe do bloqueio de um bloqueio para o desbloqueio, o que significa que há chances muito altas de que uma tentativa de capturar outro thread não encontre obstáculos. Quando um fluxo atinge um objeto de sincronização "livre", podemos capturá-lo sem fazer uma chamada do sistema usando operações atômicas relativamente baratas. E há uma chance muito grande de que a operação atômica funcione com sucesso.

Nesse caso raro, quando ainda tentamos acessar um recurso bloqueado por outro encadeamento, uma operação atômica retornará um erro. Nesse caso, temos duas opções. Podemos girar em algum bloqueio de rotação do modo de usuário, aguardando a liberação do recurso (que consumirá os recursos da CPU) ou pedir ao kernel que nos coloque no modo de suspensão, aguardando a liberação do recurso. É aqui que os futexes entram em cena.

Uso simples de futexes - expectativa e despertar

A chamada do sistema futex combina uma variedade de funcionalidades. Não consideraremos opções complexas aqui (algumas delas são tão elaboradas que nem são descritas na documentação oficial), mas focamos nas operações FUTEX_WAIT e FUTEX_WAKE. A descrição na documentação oficial servirá como uma boa base:

A chamada do sistema futex () fornece aos programas um método para aguardar que uma determinada condição se torne verdadeira. Normalmente, essa chamada do sistema usa uma construção de bloqueio no contexto da sincronização de memória compartilhada. Ao usar futexes, as principais operações de sincronização são executadas no espaço do usuário. Os programas de espaço do usuário executam a chamada do sistema futex () somente quando for necessário que o programa entre no modo de espera por um longo tempo até que a condição se torne verdadeira. Além disso, futex () pode ser usado para ativar processos ou threads que esperam uma condição específica.

Simplificando, um futex é uma construção do kernel que ajuda o código do usuário a sincronizar threads quando algo acontece. Alguns processos (ou threads) podem aguardar eventos em uma chamada FUTEX_WAIT, enquanto outros podem chamar esses eventos com FUTEX_WAKE. A espera funciona de maneira eficiente - os threads em espera são suspensos pelo kernel e não usam os recursos do processador até serem despertados quando ocorre um evento esperado.

Aproveite o tempo para ler a documentação na íntegra. Bem, ou pelo menos leia as seções sobre FUTEX_WAIT e FUTEX_WAKE.

Vejamos um exemplo simples que demonstra o uso básico de futexes para coordenar o trabalho de dois processos.

Processo filho:

1. Aguarda 0xA no slot de memória geral
2. Grava o valor 0xB nesse slot

Processo pai no momento:

1. Grava um valor 0xA em um slot de memória compartilhada
2. Aguarda 0xB aparecer nele

Tal "aperto de mão" entre dois processos. Aqui está o código:

int main(int argc, char** argv) { int shm_id = shmget(IPC_PRIVATE, 4096, IPC_CREAT | 0666); if (shm_id < 0) { perror("shmget"); exit(1); } int* shared_data = shmat(shm_id, NULL, 0); *shared_data = 0; int forkstatus = fork(); if (forkstatus < 0) { perror("fork"); exit(1); } if (forkstatus == 0) { //   printf("child waiting for A\n"); wait_on_futex_value(shared_data, 0xA); printf("child writing B\n"); //  0xB         *shared_data = 0xB; wake_futex_blocking(shared_data); } else { //   printf("parent writing A\n"); //  0xA         *shared_data = 0xA; wake_futex_blocking(shared_data); printf("parent waiting for B\n"); wait_on_futex_value(shared_data, 0xB); // Wait for the child to terminate. wait(NULL); shmdt(shared_data); } return 0; } 

Preste atenção às chamadas POSIX para alocar memória compartilhada entre processos. Não foi possível usar a alocação de memória usual aqui, pois mesmo o mesmo endereço de ponteiros em diferentes processos apontaria para diferentes blocos de memória (exclusivos para cada processo).

Deve-se notar que este exemplo se desvia um pouco dos cânones, porque o futex foi originalmente criado para aguardar uma mudança em um determinado significado "de algo específico para qualquer coisa" e não "de algo para algo específico". Dei esse exemplo para demonstrar essa possibilidade e, a seguir, consideraremos a versão básica (nela implementamos o mutex).

E aqui está o código da função wait_on_futex_value:

 void wait_on_futex_value(int* futex_addr, int val) { while (1) { int futex_rc = futex(futex_addr, FUTEX_WAIT, val, NULL, NULL, 0); if (futex_rc == -1) { if (errno != EAGAIN) { perror("futex"); exit(1); } } else if (futex_rc == 0) { if (*futex_addr == val) { //    return; } } else { abort(); } } } 

A principal tarefa dessa função (além, na verdade, da chamada do sistema futex) é um ciclo no qual executamos quando acordamos falsos (não estamos interessados ​​em nós). Isso pode acontecer quando um novo valor, mas não o esperado por nós, é instalado no slot de memória compartilhada. Bem, ou no caso em que outro processo foi despertado antes do nosso (isso não pode acontecer no nosso caso particular, mas de uma maneira mais geral é possível).

A semântica do Futex é algo bastante complicado! A chamada FUTEX_WAIT retornará imediatamente se o valor no endereço futex não for igual ao argumento passado val. No nosso caso, isso pode acontecer se o processo filho for aguardar antes que o pai escreva o valor 0xA no slot. O futex nesse caso retorna o valor EAGAIN.

E aqui está o código da função wake_futex_blocking:

 void wake_futex_blocking(int* futex_addr) { while (1) { int futex_rc = futex(futex_addr, FUTEX_WAKE, 1, NULL, NULL, 0); if (futex_rc == -1) { perror("futex wake"); exit(1); } else if (futex_rc > 0) { return; } } } 

Este é um invólucro de bloqueio sobre FUTEX_WAKE que rapidamente funcionará e retornará um valor, não importa quantos ouvintes esperem. No nosso exemplo, isso é usado como parte de um "aperto de mão", mas outros usos são possíveis.

Futex são filas do kernel para código personalizado.

Simplificando, um futex é uma fila orientada por kernel para resolver tarefas de código personalizadas. Ele permite que o código do usuário solicite ao kernel que suspenda a execução de seu thread até que um evento ocorra, e ao outro thread ao mesmo tempo para sinalizar esse evento e ativar todos os threads que o aguardam. Mencionamos anteriormente a capacidade de organizar um bloqueio de rotação no modo de usuário, aguardando que alguma condição fosse atendida. No entanto, a fila no kernel é uma alternativa muito melhor, pois nos salva de bilhões de instruções desperdiçadas do processador executadas em um loop de espera.

Aqui está o diagrama do artigo "Uma visão geral e atualização do futex" no LWN:



No código do kernel do Linux, os futexes são implementados no arquivo kernel / futex.c. O kernel armazena uma tabela de hash onde as chaves são endereços - para encontrar rapidamente a fila desejada e adicionar o processo de chamada a ela. Tudo, é claro, não é tão simples - afinal, o próprio kernel precisa sincronizar o acesso aos dados internos, além de suportar todo tipo de opções adicionais para o futeksov.

Espera por tempo limitado com FUTEX_WAIT

A chamada do sistema futex possui um parâmetro de tempo limite que permite ao usuário especificar quanto tempo está pronto para aguardar. Aqui está um exemplo completo em que isso é implementado, mas aqui está a parte principal:

 printf("child waiting for A\n"); struct timespec timeout = {.tv_sec = 0, .tv_nsec = 500000000}; while (1) { unsigned long long t1 = time_ns(); int futex_rc = futex(shared_data, FUTEX_WAIT, 0xA, &timeout, NULL, 0); printf("child woken up rc=%d errno=%s, elapsed=%llu\n", futex_rc, futex_rc ? strerror(errno) : "", time_ns() - t1); if (futex_rc == 0 && *shared_data == 0xA) { break; } } 

Se a espera for atrasada em 500 ms, a função futex será encerrada e, na próxima iteração do loop, podemos responder de alguma forma a isso (exibir algo na tela, gravar no log, continuar a espera ou parar).

Usando um futex para implementar um mutex

Iniciamos este artigo com o fato de que futexes são úteis na implementação de objetos de sincronização de nível superior. Vamos tentar usá-los (assim como os átomos) para implementar o mutex clássico. A implementação abaixo é baseada no código do artigo "Futexes são complicados", escrito por Ulrich Drepper.

Neste exemplo, eu uso o C ++, principalmente pela capacidade de usar atômicos do padrão C ++ 11. Você pode encontrar o código completo aqui , mas a parte mais importante é:

 class Mutex { public: Mutex() : atom_(0) {} void lock() { int c = cmpxchg(&atom_, 0, 1); // If the lock was previously unlocked, there's nothing else for us to do. // Otherwise, we'll probably have to wait. if (c != 0) { do { // If the mutex is locked, we signal that we're waiting by setting the // atom to 2. A shortcut checks is it's 2 already and avoids the atomic // operation in this case. if (c == 2 || cmpxchg(&atom_, 1, 2) != 0) { // Here we have to actually sleep, because the mutex is actually // locked. Note that it's not necessary to loop around this syscall; // a spurious wakeup will do no harm since we only exit the do...while // loop when atom_ is indeed 0. syscall(SYS_futex, (int*)&atom_, FUTEX_WAIT, 2, 0, 0, 0); } // We're here when either: // (a) the mutex was in fact unlocked (by an intervening thread). // (b) we slept waiting for the atom and were awoken. // // So we try to lock the atom again. We set teh state to 2 because we // can't be certain there's no other thread at this exact point. So we // prefer to err on the safe side. } while ((c = cmpxchg(&atom_, 0, 2)) != 0); } } void unlock() { if (atom_.fetch_sub(1) != 1) { atom_.store(0); syscall(SYS_futex, (int*)&atom_, FUTEX_WAKE, 1, 0, 0, 0); } } private: // 0 means unlocked // 1 means locked, no waiters // 2 means locked, there are waiters in lock() std::atomic<int> atom_; }; 

Nesse código, a função cmpxhg é um invólucro simples para um uso mais conveniente dos átomos:

 // An atomic_compare_exchange wrapper with semantics expected by the paper's // mutex - return the old value stored in the atom. int cmpxchg(std::atomic<int>* atom, int expected, int desired) { int* ep = &expected; std::atomic_compare_exchange_strong(atom, ep, desired); return *ep; } 

Este exemplo de código contém muitos comentários explicando a lógica de sua operação. Isso não vai doer, porque há um risco significativo de que você queira escrever uma versão um pouco mais simples, mas completamente incorreta. Quanto a este código - também não é perfeito em tudo. Por exemplo, ele tenta fazer uma suposição sobre um dispositivo interno do tipo std :: atomic, convertendo seu conteúdo em int * para passar para a chamada futex. Geralmente não é esse o caso. O código compila e roda no Linux x64, mas não temos garantia de compatibilidade com outras plataformas. Para obtê-lo, precisamos adicionar uma camada de dependência de plataforma para átomos. Como esse não é o tópico deste artigo (e também porque é muito improvável que você misture futexes em um módulo C ++), omitimos essa implementação. Isto é apenas uma demonstração!

Mutexes Glibc e bloqueios de baixo nível

Então chegamos ao ponto em que o glibc implementa threads POSIX, parte do qual é o tipo pthread_mutex_t. Como eu disse no começo deste artigo, o futex não é exatamente o que um desenvolvedor comum precisará. Eles são usados ​​por bibliotecas de tempo de execução ou algo altamente especializado para implementar primitivas de sincronização de nível superior. Nesse contexto, é interessante observar a implementação do mutex para NPTL . No código glibc, esse é o arquivo nptl / pthread_mutex_lock.c.

O código é bastante complicado devido à necessidade de suportar vários tipos de mutexes, mas podemos encontrar blocos bastante familiares, se desejado. Você também pode dar uma olhada nos arquivos sysdeps / unix / sysv / linux / x86_64 / lowlevellock.he nptl / lowlevellock.c. O código é um pouco confuso, mas ainda é fácil a combinação de chamadas de comparação e troca e de futex.

O comentário inicial do arquivo systeds / nptl / lowlevellock.h já deve ser bem entendido por você:

 /* Low-level locks use a combination of atomic operations (to acquire and release lock ownership) and futex operations (to block until the state of a lock changes). A lock can be in one of three states: 0: not acquired, 1: acquired with no waiters; no other threads are blocked or about to block for changes to the lock state, >1: acquired, possibly with waiters; there may be other threads blocked or about to block for changes to the lock state. We expect that the common case is an uncontended lock, so we just need to transition the lock between states 0 and 1; releasing the lock does not need to wake any other blocked threads. If the lock is contended and a thread decides to block using a futex operation, then this thread needs to first change the state to >1; if this state is observed during lock release, the releasing thread will wake one of the potentially blocked threads. .. */ 

Ir para futexes de tempo de execução

O Rantime Go não usa libc (na maioria dos casos). Portanto, ele não pode confiar na implementação de encadeamentos POSIX. Em vez disso, ele chama diretamente chamadas de sistema de nível inferior. Isso o torna um bom exemplo do uso de futexes. Como não há como chamar pthread_mutex_t, você deve escrever sua própria substituição. Vamos ver como isso é feito, vamos começar com o tipo sync.Mutex visível para o usuário (em src / sync / mutex.go).

O método Lock desse tipo tenta usar a operação de troca atômica para capturar rapidamente o bloqueio. Se você precisar esperar, chama runtime_SemacquireMutex, que chama runtime.lock. Essa função é definida em src / runtime / lock_futex.go e declara várias constantes que podem lhe parecer familiares:

 const ( mutex_unlocked = 0 mutex_locked = 1 mutex_sleeping = 2 ... ) // Possible lock states are mutex_unlocked, mutex_locked and mutex_sleeping. // mutex_sleeping means that there is presumably at least one sleeping thread. 

O runtime.lock também está tentando capturar o bloqueio usando uma função atômica. Isso faz sentido, já que runtime.lock é chamado em muitos locais do tempo de execução Go, mas parece-me que seria possível otimizar o código removendo duas chamadas consecutivas da função atômica ao chamar runtime.lock do Mutex.lock.

Se você precisar esperar, a função dependente da plataforma futexsleep será chamada, definida para Linux no arquivo src / runtime / os_linux.go. Essa função faz uma chamada de sistema futex com o código FUTEX_WAIT_PRIVATE (neste caso, isso é adequado, pois o tempo de execução do Go fica em um processo).