Dasar-dasar Futex

Futex (futex - kependekan dari "Fast userspace mutex") adalah mekanisme yang diusulkan oleh pengembang Linux dari IBM pada tahun 2002 dan memasuki kernel pada akhir tahun 2003. Gagasan utamanya adalah menyediakan cara yang lebih efisien untuk menyinkronkan utas pengguna dengan jumlah panggilan minimum ke kernel OS.

Pada artikel ini, kami akan meninjau futex, mencoba memahami prinsip-prinsip pekerjaan mereka, dan juga menggunakannya sebagai batu bata untuk membangun objek sinkronisasi level tinggi (dan akrab bagi kami).

Poin penting: futex adalah alat tingkat rendah, layak digunakan secara langsung hanya ketika mengembangkan pustaka dasar, seperti pustaka C / C ++ standar. Sangat tidak mungkin bahwa Anda akan perlu menggunakan futex dalam aplikasi reguler.

Motivasi

Sebelum munculnya futex, perlu untuk melakukan panggilan sistem (menggunakan, misalnya, semop ) setiap kali untuk mengontrol akses ke sumber daya bersama dari beberapa utas, yang, seperti yang Anda tahu, padat sumber daya, karena setiap panggilan memerlukan pengalihan konteks dari mode pengguna ke mode kernel. Dengan peningkatan jumlah core pada prosesor modern dan peningkatan jumlah utas dalam perangkat lunak aplikasi, ini telah menjadi masalah yang signifikan. Itu bahkan lebih "ofensif", mengingat bahwa semua panggilan ini tidak membawa fungsi yang diterapkan, tidak menerapkan logika bisnis, tetapi hanya menjamin operasi yang benar dari sisa kode.

Proposal untuk menambahkan konsep baru "futex" ke OS didasarkan pada pengamatan sederhana: dalam banyak kasus, upaya untuk menangkap objek sinkronisasi berhasil pertama kali. Pemrogram menulis perangkat lunak sedemikian rupa sehingga sesedikit mungkin waktu beralih dari mengunci kunci untuk membukanya, yang berarti ada peluang yang sangat tinggi bahwa upaya untuk menangkap utas lainnya tidak akan menemui hambatan. Saat aliran mencapai objek sinkronisasi "bebas", kami dapat menangkapnya tanpa membuat panggilan sistem menggunakan operasi atom yang relatif murah. Dan ada peluang yang sangat besar bahwa operasi atom akan berhasil dengan sukses.

Dalam kasus yang jarang terjadi, ketika kami masih mencoba mengakses sumber daya yang diblokir oleh utas lainnya, operasi atom akan mengembalikan kesalahan. Dalam hal ini, kami memiliki dua opsi. Kita dapat memutar di beberapa kunci-spin dari mode pengguna, menunggu rilis sumber daya (yang akan memakan sumber daya CPU), atau meminta kernel untuk menempatkan kita ke mode tidur, menunggu rilis sumber daya. Di sinilah futex datang ke tempat kejadian.

Penggunaan sederhana dari futex - harapan dan kebangkitan

Panggilan sistem futex menggabungkan cukup beragam fungsi. Kami tidak akan mempertimbangkan opsi rumit di sini (beberapa di antaranya sangat rumit sehingga bahkan tidak dijelaskan dalam dokumentasi resmi), tetapi fokus pada operasi FUTEX_WAIT dan FUTEX_WAKE. Deskripsi dalam dokumentasi resmi akan menjadi dasar yang baik:

Panggilan sistem futex () menyediakan program dengan metode untuk menunggu kondisi tertentu menjadi kenyataan. Biasanya, panggilan sistem ini menggunakan konstruksi pemblokiran dalam konteks sinkronisasi memori bersama. Saat menggunakan futex, operasi sinkronisasi utama dilakukan di ruang pengguna. Program ruang pengguna hanya menjalankan panggilan sistem futex () bila program perlu memasuki mode siaga untuk waktu yang lama hingga kondisinya menjadi benar. Juga, futex () dapat digunakan untuk membangunkan proses atau utas yang mengharapkan kondisi tertentu.

Sederhananya, futex adalah konstruksi kernel yang membantu kode pengguna menyinkronkan utas ketika sesuatu terjadi. Beberapa proses (atau utas) dapat menunggu acara dalam panggilan FUTEX_WAIT, sementara yang lain dapat memanggil acara ini dengan FUTEX_WAKE. Menunggu berfungsi dengan efisien - utas menunggu ditangguhkan oleh kernel dan tidak menggunakan sumber daya prosesor sampai terbangun ketika peristiwa yang diharapkan terjadi.

Luangkan waktu untuk membaca dokumentasi secara keseluruhan. Ya, atau setidaknya baca bagian tentang FUTEX_WAIT dan FUTEX_WAKE.

Mari kita lihat contoh sederhana yang menunjukkan penggunaan dasar futex untuk mengoordinasikan pekerjaan dua proses.

Proses anak:

1. Menunggu 0xA di slot memori umum
2. Menulis nilai 0xB ke slot ini

Proses induk saat ini:

1. Menulis nilai 0xA ke slot memori bersama
2. Menunggu 0xB muncul di dalamnya

Seperti "jabat tangan" antara dua proses. Ini kodenya:

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; } 

Perhatikan panggilan POSIX untuk mengalokasikan memori bersama antar proses. Kami tidak dapat menggunakan alokasi memori yang biasa di sini, karena bahkan alamat pointer yang sama dalam proses yang berbeda sebenarnya akan menunjuk ke blok memori yang berbeda (unik untuk setiap proses).

Perlu dicatat bahwa contoh ini agak menyimpang dari kanon, karena futex pada awalnya dibuat untuk menunggu perubahan dalam arti tertentu "dari sesuatu yang spesifik untuk apa pun", dan bukan "dari sesuatu ke sesuatu yang spesifik". Saya memberikan contoh ini untuk menunjukkan kemungkinan seperti itu, dan di bawah ini kami akan mempertimbangkan versi dasar (di atasnya kami menerapkan mutex).

Dan inilah kode fungsi 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(); } } } 

Tugas utama dari fungsi ini (selain itu, sebenarnya, panggilan sistem futex) adalah siklus di mana kita menjalankan ketika kita bangun palsu (tidak tertarik pada kita). Ini bisa terjadi ketika nilai baru, tetapi tidak kami harapkan, dipasang di slot memori bersama. Baik, atau dalam kasus ketika proses lain dibangunkan lebih awal dari kita (ini tidak bisa terjadi dalam kasus khusus kita, tetapi dengan cara yang lebih umum itu mungkin).

Semantik Futex adalah hal yang cukup rumit! Panggilan FUTEX_WAIT akan segera kembali jika nilai pada alamat futex tidak sama dengan val argumen yang diteruskan. Dalam kasus kami, ini bisa terjadi jika proses anak pergi menunggu sebelum orang tua menulis nilai 0xA di slot. Futex dalam hal ini mengembalikan nilai EAGAIN.

Dan di sini adalah kode fungsi 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; } } } 

Ini adalah pembungkus pemblokiran di atas FUTEX_WAKE yang akan dengan cepat bekerja dan mengembalikan nilai, tidak peduli berapa banyak pendengar yang mengharapkannya. Dalam contoh kami, ini digunakan sebagai bagian dari "jabat tangan," tetapi penggunaan lain mungkin dilakukan.

Futex adalah antrian kernel untuk kode khusus.

Sederhananya, sebuah futex adalah antrian yang digerakkan oleh kernel untuk menyelesaikan tugas kode kustom. Ini memungkinkan kode pengguna untuk meminta kernel untuk menunda eksekusi utasnya sampai suatu peristiwa terjadi, dan ke utas lainnya pada saat yang sama untuk memberi sinyal pada acara ini dan membangunkan semua utas yang menunggunya. Sebelumnya kami menyebutkan kemampuan untuk mengatur spin-lock dalam mode pengguna, menunggu beberapa kondisi terpenuhi. Namun, antrian di kernel adalah alternatif yang jauh lebih baik, karena ini menyelamatkan kita dari miliaran instruksi prosesor yang terbuang yang dijalankan dalam satu lingkaran tunggu.

Berikut adalah diagram dari artikel "Tinjauan umum dan pembaruan" di LWN:



Dalam kode kernel Linux, futex diimplementasikan dalam file kernel / futex.c. Kernel menyimpan tabel hash di mana kunci adalah alamat - untuk dengan cepat menemukan antrian yang diinginkan dan menambahkan proses panggilan ke dalamnya. Semuanya, tentu saja, tidak begitu sederhana - lagipula, kernel itu sendiri perlu menyinkronkan akses ke data di dalamnya, plus mendukung segala macam opsi tambahan untuk futeksov.

Waktu tunggu terbatas dengan FUTEX_WAIT

Panggilan sistem futex memiliki parameter batas waktu yang memungkinkan pengguna menentukan berapa lama mereka siap untuk menunggu. Berikut ini adalah contoh lengkap di mana ini diterapkan, tetapi di sini adalah bagian kunci:

 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; } } 

Jika menunggu ditunda selama 500 ms, maka fungsi futex akan berakhir, dan pada iterasi berikutnya dari loop kita entah bagaimana dapat bereaksi terhadap ini (menampilkan sesuatu di layar, menulis ke log, melanjutkan menunggu atau berhenti).

Menggunakan futex untuk mengimplementasikan mutex

Kami memulai artikel ini dengan fakta bahwa futex memiliki kegunaan praktis dalam implementasi objek sinkronisasi tingkat tinggi. Mari kita coba menggunakannya (juga atomik) untuk mengimplementasikan mutex klasik. Implementasi di bawah ini didasarkan pada kode dari artikel "Futexes Tricky" yang ditulis oleh Ulrich Drepper.

Untuk contoh ini, saya menggunakan C ++, terutama untuk kemampuan menggunakan atom dari standar C ++ 11. Anda dapat menemukan kode lengkap di sini , tetapi bagian terpenting adalah:

 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_; }; 

Dalam kode ini, fungsi cmpxhg adalah pembungkus sederhana untuk penggunaan atom yang lebih mudah:

 // 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; } 

Contoh kode ini berisi banyak komentar yang menjelaskan logika operasinya. Ini tidak akan sakit, karena ada risiko yang signifikan bahwa Anda ingin menulis versi yang sedikit lebih sederhana, tetapi sepenuhnya salah. Adapun kode ini - juga tidak sempurna dalam segala hal. Sebagai contoh, ia mencoba membuat asumsi tentang perangkat internal dari tipe std :: atomic, melemparkan isinya ke int * untuk meneruskan panggilan futex. Ini biasanya tidak demikian. Kode mengkompilasi dan berjalan di Linux x64, tetapi kami tidak memiliki jaminan kompatibilitas dengan platform lain. Untuk mendapatkannya, kita perlu menambahkan lapisan ketergantungan platform untuk atom. Karena ini bukan topik artikel ini (dan juga karena sangat tidak mungkin bahwa Anda akan mencampur futex dalam modul C ++ yang sama) kami akan mengabaikan implementasi ini. Ini hanya demonstrasi!

Mutib glibc dan kunci tingkat rendah

Jadi kita sampai pada titik di mana glibc mengimplementasikan thread POSIX, yang sebagian adalah tipe pthread_mutex_t. Seperti yang saya katakan di awal artikel ini, futex bukanlah hal yang dibutuhkan oleh pengembang biasa. Mereka digunakan oleh pustaka runtime atau sesuatu yang sangat khusus untuk mengimplementasikan primitif sinkronisasi tingkat tinggi. Dalam konteks ini, menarik untuk melihat implementasi dari mutex untuk NPTL . Dalam kode glibc, ini adalah file nptl / pthread_mutex_lock.c.

Kode ini cukup rumit karena kebutuhan untuk mendukung berbagai jenis mutex, tetapi kita dapat menemukan blok yang cukup akrab jika diinginkan. Anda juga dapat melihat file sysdeps / unix / sysv / linux / x86_64 / lowlevellock.h dan nptl / lowlevellock.c. Kode ini agak membingungkan, tetapi kombinasi panggilan to-and-exchange dan futex masih mudah.

Komentar awal dari file systeds / nptl / lowlevellock.h harus sudah dipahami dengan baik oleh Anda:

 /* 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. .. */ 

Pergi runtime futex

Rantime Go tidak menggunakan libc (dalam banyak kasus). Dengan demikian, tidak dapat mengandalkan implementasi utas POSIX. Sebagai gantinya, ia langsung memanggil panggilan sistem tingkat bawah. Ini membuatnya menjadi contoh yang baik menggunakan futex. Karena tidak ada cara untuk memanggil pthread_mutex_t, Anda harus menulis penggantinya sendiri. Mari kita lihat bagaimana ini dilakukan, mari kita mulai dengan tipe sync.Mutex yang terlihat oleh pengguna (di src / sync / mutex.go).

Metode Kunci jenis ini mencoba menggunakan operasi pertukaran atom untuk menangkap kunci dengan cepat. Jika ternyata Anda perlu menunggu, ia memanggil runtime_SemacquireMutex, yang memanggil runtime.lock. Fungsi ini didefinisikan dalam src / runtime / lock_futex.go dan mendeklarasikan beberapa konstanta yang mungkin Anda kenal:

 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. 

runtime.lock juga mencoba menangkap kunci menggunakan fungsi atom. Ini masuk akal, karena runtime.lock dipanggil di banyak tempat Go runtime, tetapi bagi saya tampaknya mungkin untuk mengoptimalkan kode dengan menghapus dua panggilan berurutan dari fungsi atom saat memanggil runtime.lock dari Mutex.lock.

Jika ternyata Anda harus menunggu, fungsi platform-dependent futexsleep disebut, yang didefinisikan untuk Linux dalam file src / runtime / os_linux.go. Fungsi ini membuat panggilan sistem futex dengan kode FUTEX_WAIT_PRIVATE (dalam hal ini, ini cocok, karena runtime Go hidup dalam satu proses).