Mengapa sebagian besar implementasi mutex tidak adil?

Pemahaman saya adalah bahwa implementasi mutex yang paling populer (misalnya std :: mutex dalam C ++) tidak menjamin keadilan - yaitu, mereka tidak menjamin bahwa dalam kasus pertengkaran, kunci akan diperoleh oleh utas dalam urutan yang mereka inginkan. disebut kunci (). Bahkan, mungkin saja (walaupun mudah-mudahan tidak umum) bahwa dalam kasus pertengkaran tinggi, beberapa utas yang menunggu untuk memperoleh mutex mungkin tidak akan pernah mendapatkannya.

Ini kelihatannya seperti perilaku yang tidak membantu bagi saya - bagi saya tampaknya mutex yang adil akan menghasilkan perilaku yang lebih sesuai dengan apa yang diinginkan / diharapkan seorang programmer.

Alasan yang diberikan mengapa mutex biasanya tidak diterapkan untuk menjadi adil adalah "kinerja", tetapi saya ingin lebih memahami apa artinya - khususnya, bagaimana merelaksasi persyaratan keadilan mutex meningkatkan kinerja? Sepertinya mutex "adil" akan sepele untuk diterapkan - cukup kunci () tambahkan utas panggilan ke ujung daftar tertaut mutex sebelum meletakkan utas untuk tidur, lalu buka () pop utas berikutnya dari kepala daftar yang sama dan bangunkan.

Wawasan mutex-implementasi apa yang saya lewatkan di sini, yang akan menjelaskan mengapa dianggap layak mengorbankan keadilan untuk kinerja yang lebih baik?

Jawaban Jim Sawyer menunjuk ke satu jawaban: Ketika Anda memiliki utas dengan prioritas yang berbeda, perilaku "adil" akan salah. Ketika Anda memiliki banyak utas yang dapat berjalan, utas prioritas tertinggi umumnya adalah utas yang harus dijalankan.

Namun, ada sedikit rahasia yang dibahas tentang implementasi sistem operasi yang harus Anda ketahui, yaitu bahwa kadang-kadang sistem operasi menjalankan kode sebagai pengguna dengan membajak utas pengguna. Untuk alasan keamanan, sebagian besar sistem operasi yang melakukan ini hanya melakukannya saat utas diblokir. Ketika sistem operasi selesai, utas ditangguhkan kembali, dan ini biasanya memiliki efek memindahkan utas ke bagian belakang antrian tunggu.

Contoh khas adalah penangan sinyal di Unix, perangkap sistem asinkron di VMS, atau panggilan prosedur asinkron di Windows NT. Ini semua pada dasarnya adalah hal yang sama: Sistem operasi perlu memberi tahu proses pengguna bahwa beberapa peristiwa terjadi, dan ini ditangani dengan menjalankan kode di ruang pengguna.

Banyak layanan sistem operasi seperti asynchronous I / O sering diimplementasikan di atas fasilitas ini.

Contoh lain adalah jika prosesnya di bawah kendali seorang debugger. Dalam hal ini, sistem debugging dapat mengeksekusi kode sebagai tugas pengguna karena berbagai alasan.

'Pembalikan prioritas' adalah salah satu alasan mengapa keadilan dapat tidak diinginkan. Proses dengan prioritas rendah mengenai mutex yang terkunci dan tertidur. Kemudian proses prioritas yang lebih tinggi memukulnya, dan juga tidur. Ketika mutex dibuka, proses mana yang harus mendapatkan kunci berikutnya?

Mutex yang adil akan menghabiskan lebih banyak dari masa hidupnya terkunci daripada mutex yang tidak adil, semua yang lain sama. Karena utas yang melepaskan Mutex tidak adil selalu dapat membukanya. Tetapi utas yang melepaskan mutex yang adil hanya dapat membukanya saat antrian pelayan kosong. Jika tidak, utas pelepas harus membiarkan mutex terkunci demi utas utas berikutnya, alias utas pertama pada antrian pelayan, yang kemudian dikeringkan dan dibangunkan. Mutex tetap terkunci setidaknya sampai utas yang baru terbangun dijadwalkan pada CPU, yang bisa lama jika ada banyak utas yang saat ini dapat dijalankan.

Dan jika utas pelepas segera mencoba untuk mendapatkan kembali mutex yang sama, ia harus menempatkan dirinya di belakang antrian pelayan dan pergi tidur. Ini tidak akan terjadi jika utas tidak melepaskan mutex untuk memulai. Karenanya ini memberikan insentif untuk bagian kritis yang lebih "serakah".