Bisakah Anda menjelaskan mengapa banyak utas membutuhkan kunci pada CPU single-core?

Asumsikan utas ini berjalan dalam cpu satu inti. Sebagai cpu hanya menjalankan satu instruksi dalam satu siklus. Yang mengatakan, bahkan berpikir mereka berbagi sumber daya cpu. tetapi komputer memastikan bahwa satu kali satu instruksi. Jadi, apakah kunci tidak diperlukan untuk multiplethreading?

Ini paling baik diilustrasikan dengan sebuah contoh.

Misalkan kita memiliki tugas sederhana yang ingin kita lakukan berkali-kali secara paralel, dan kita ingin melacak secara global berapa kali tugas itu dilakukan, misalnya menghitung penghitungan pada halaman web.

Ketika setiap utas sampai pada titik di mana ia menambah jumlah, pelaksanaannya akan terlihat seperti ini:

1. Baca jumlah klik dari memori ke dalam register prosesor
2. Tambahkan angka itu.
3. Tulis nomor itu kembali ke memori

Ingatlah bahwa setiap utas dapat ditangguhkan pada titik mana pun dalam proses ini. Jadi jika utas A melakukan langkah 1, dan kemudian ditangguhkan, diikuti oleh utas B yang melakukan ketiga langkah, ketika utas melanjutkan, registernya akan memiliki jumlah klik yang salah: registernya akan dipulihkan, ia akan dengan senang hati menambah nomor lama dari hit, dan simpan angka yang bertambah itu.

Selain itu, sejumlah utas lain dapat berjalan selama waktu utas ditangguhkan, sehingga utas penghitungan A pada akhirnya mungkin jauh di bawah jumlah yang benar.

Untuk alasan itu, penting untuk memastikan bahwa jika utas melakukan langkah 1, ia harus melakukan langkah 3 sebelum utas lainnya diizinkan untuk melakukan langkah 1, yang dapat diselesaikan oleh semua utas yang menunggu untuk mendapatkan kunci tunggal sebelum mereka memulai proses ini , dan membebaskan kunci hanya setelah proses selesai, sehingga "bagian kritis" kode ini tidak dapat disisipkan secara tidak benar, menghasilkan jumlah yang salah.

Tetapi bagaimana jika operasi itu atomik?

Ya, di tanah unicorn ajaib dan pelangi, di mana operasi kenaikan adalah atom, maka penguncian tidak diperlukan untuk contoh di atas.

Penting untuk disadari, bahwa kita hanya menghabiskan sedikit waktu di dunia unicorn ajaib dan pelangi. Di hampir setiap bahasa pemrograman, operasi kenaikan dipecah menjadi tiga langkah di atas. Itu karena, bahkan jika prosesor mendukung operasi peningkatan atom, operasi itu secara signifikan lebih mahal: harus membaca dari memori, memodifikasi nomor, dan menulisnya kembali ke memori ... dan biasanya operasi penambahan atom adalah operasi yang bisa gagal, artinya urutan sederhana di atas harus diganti dengan loop (seperti yang akan kita lihat di bawah).

Karena, bahkan dalam kode multithreaded, banyak variabel disimpan lokal ke utas tunggal, program jauh lebih efisien jika mereka menganggap masing-masing variabel lokal untuk satu utas, dan biarkan programmer menjaga melindungi keadaan bersama di antara utas. Terutama mengingat bahwa operasi atom biasanya tidak cukup untuk menyelesaikan masalah threading, seperti yang akan kita lihat nanti.

Variabel yang mudah menguap

Jika kita ingin menghindari kunci untuk masalah khusus ini, pertama-tama kita harus menyadari bahwa langkah-langkah yang digambarkan dalam contoh pertama kita sebenarnya bukan apa yang terjadi dalam kode kompilasi modern. Karena kompilator menganggap hanya satu utas yang memodifikasi variabel, setiap utas akan menyimpan salinan variabel yang di-cache sendiri, hingga register prosesor diperlukan untuk sesuatu yang lain. Selama ia memiliki salinan yang di-cache, ia menganggap tidak perlu kembali ke memori dan membacanya lagi (yang akan mahal). Mereka juga tidak akan menulis variabel kembali ke memori selama itu disimpan dalam register.

Kita dapat kembali ke situasi yang kita berikan dalam contoh pertama (dengan semua masalah threading yang sama yang kita identifikasi di atas) dengan menandai variabel sebagai volatile , yang memberitahu kompiler bahwa variabel ini sedang dimodifikasi oleh orang lain, dan karenanya harus dibaca dari atau ditulis ke memori setiap kali diakses atau dimodifikasi.

Jadi variabel yang ditandai sebagai volatile tidak akan membawa kita ke tanah operasi kenaikan atom, itu hanya membuat kita sedekat yang kita kira sudah.

Membuat atom kenaikan

Setelah kami menggunakan variabel volatil, kami dapat membuat atom kenaikan operasi kami dengan menggunakan operasi set bersyarat tingkat rendah yang didukung sebagian besar CPU modern (sering disebut bandingkan dan atur atau bandingkan dan tukar ). Pendekatan ini diambil, misalnya, di kelas AtomicInteger Java :

197       /**
198        * Atomically increments by one the current value.
199        *
200        * @return the updated value
201        */
202       public final int incrementAndGet() {
203           for (;;) {
204               int current = get();
205               int next = current + 1;
206               if (compareAndSet(current, next))
207                   return next;
208           }
209       }

Loop di atas berulang kali melakukan langkah-langkah berikut, hingga langkah 3 berhasil:

1. Baca nilai variabel volatil langsung dari memori.
2. Tambahkan nilai itu.
3. Ubah nilainya (dalam memori utama) jika dan hanya jika nilai saat ini dalam memori utama sama dengan nilai yang kita baca pada awalnya, menggunakan operasi atom khusus.

Jika langkah 3 gagal (karena nilai diubah oleh utas berbeda setelah langkah 1), itu lagi membaca variabel langsung dari memori utama dan mencoba lagi.

Meskipun operasi membandingkan dan menukar mahal, itu sedikit lebih baik daripada menggunakan penguncian dalam kasus ini, karena jika utas ditangguhkan setelah langkah 1, utas lain yang mencapai langkah 1 tidak harus memblokir dan menunggu utas pertama, yang dapat mencegah pengalihan konteks yang mahal. Ketika utas pertama dilanjutkan, ia akan gagal dalam upaya pertamanya untuk menulis variabel, tetapi akan dapat melanjutkan dengan membaca kembali variabel, yang lagi-lagi kemungkinan lebih murah daripada pengalih konteks yang diperlukan dengan penguncian.

Jadi, kita bisa sampai ke tanah penambahan atom (atau operasi lain pada satu variabel) tanpa menggunakan kunci aktual, melalui perbandingan dan swap.

Jadi kapan penguncian sangat diperlukan?

Jika Anda perlu memodifikasi lebih dari satu variabel dalam operasi atom, maka penguncian akan diperlukan, Anda tidak akan menemukan instruksi prosesor khusus untuk itu.

Selama Anda mengerjakan variabel tunggal, dan Anda siap untuk pekerjaan apa pun yang telah Anda lakukan untuk gagal dan harus membaca variabel dan memulai lagi, perbandingan-dan-swap akan cukup baik.

Mari kita perhatikan contoh di mana setiap utas pertama menambahkan 2 ke variabel X, dan kemudian mengalikan X dengan dua.

Jika X awalnya adalah satu, dan dua utas berjalan, kami berharap hasilnya adalah (((1 + 2) * 2) + 2) * 2 = 16.

Namun, jika utas saling berhubungan, kita bisa, bahkan dengan semua operasi menjadi atom, sebagai gantinya kedua penambahan terjadi terlebih dahulu, dan multiplikasi muncul setelahnya, menghasilkan (1 + 2 + 2) * 2 * 2 = 20.

Ini terjadi karena penggandaan dan penambahan bukan operasi komutatif.

Jadi, operasi itu sendiri menjadi atom tidak cukup, kita harus membuat kombinasi operasi atom.

Kita bisa melakukannya dengan menggunakan penguncian untuk membuat serialisasi proses, atau kita bisa menggunakan satu variabel lokal untuk menyimpan nilai X ketika kita mulai perhitungan kita, variabel lokal kedua untuk langkah-langkah perantara, dan kemudian gunakan bandingkan-dan-tukar untuk atur nilai baru hanya jika nilai X saat ini sama dengan nilai asli X. Jika kita gagal, kita harus memulai dari awal lagi dengan membaca X dan melakukan perhitungan lagi.

Ada beberapa trade-off yang terlibat: saat kalkulasi menjadi lebih lama, maka kemungkinan besar thread yang berjalan akan ditangguhkan, dan nilainya akan dimodifikasi oleh utas lainnya sebelum kami melanjutkan, yang berarti kegagalan menjadi jauh lebih mungkin, yang menyebabkan pemborosan. waktu prosesor. Dalam kasus ekstrim dari sejumlah besar utas dengan perhitungan berjalan sangat lama, kita mungkin memiliki 100 utas membaca variabel dan terlibat dalam perhitungan, di mana dalam kasus ini hanya yang pertama selesai akan berhasil menulis nilai baru, 99 lainnya masih akan selesaikan perhitungan mereka, tetapi temukan setelah selesai bahwa mereka tidak dapat memperbarui nilai ... pada titik mana mereka masing-masing akan membaca nilai dan memulai perhitungan lebih dari itu. Kami kemungkinan memiliki 99 utas yang tersisa mengulangi masalah yang sama, menghabiskan banyak waktu prosesor.

Serialisasi lengkap bagian kritis melalui kunci akan jauh lebih baik dalam situasi itu: 99 utas akan ditangguhkan saat mereka tidak mendapatkan kunci, dan kami akan menjalankan setiap utas sesuai urutan kedatangan di titik kunci.

Jika serialisasi tidak kritis (seperti dalam kasus kenaikan kami), dan perhitungan yang akan hilang jika memperbarui nomor gagal minimal, mungkin ada keuntungan signifikan yang dapat diperoleh dari menggunakan operasi perbandingan-dan-tukar, karena operasi itu lebih murah daripada mengunci.

Pertimbangkan kutipan ini:

Beberapa orang, ketika dihadapkan dengan suatu masalah, berpikir, "Saya tahu, saya akan menggunakan utas," dan kemudian dua mereka memiliki poblesms

Anda tahu, bahkan jika 1 instruksi berjalan pada CPU pada waktu tertentu, program komputer terdiri lebih dari sekadar instruksi perakitan atom. Jadi misalnya, menulis ke konsol (atau file) berarti Anda harus mengunci untuk memastikannya berfungsi seperti yang Anda inginkan.

Tampaknya banyak jawaban berusaha menjelaskan penguncian, tapi saya pikir apa yang dibutuhkan OP adalah penjelasan tentang apa sebenarnya multitasking itu.

Ketika Anda memiliki lebih dari satu utas yang berjalan pada suatu sistem bahkan dengan satu CPU, ada dua metodologi utama yang menentukan bagaimana utas-utas ini akan dijadwalkan (yaitu ditempatkan untuk menjalankan ke dalam CPU inti-tunggal Anda):

• Cooperative Multitasking - Digunakan di Win9x diperlukan setiap aplikasi untuk secara eksplisit menyerahkan kontrol. Dalam hal ini, Anda tidak perlu khawatir tentang penguncian karena selama Thread A mengeksekusi beberapa algoritma, Anda akan dijamin bahwa itu tidak akan pernah terputus.
• Preemptive Multitasking - Digunakan di sebagian besar OS modern (Win2k dan yang lebih baru). Ini menggunakan rentang waktu dan akan menyela utas meskipun mereka masih melakukan pekerjaan. Ini jauh lebih kuat karena satu utas tidak pernah dapat menggantung seluruh mesin Anda, yang merupakan kemungkinan nyata dengan multitasking kooperatif. Di sisi lain, sekarang Anda perlu khawatir tentang kunci karena pada waktu tertentu, salah satu utas Anda dapat terputus (yaitu preempted) dan OS mungkin menjadwalkan utas yang berbeda untuk dijalankan. Saat mengkode aplikasi multithreaded dengan perilaku ini, Anda HARUS mempertimbangkan bahwa di antara setiap baris kode (atau bahkan setiap instruksi), sebuah thread yang berbeda dapat dijalankan. Sekarang, bahkan dengan satu inti, penguncian menjadi sangat penting untuk memastikan keadaan data Anda yang konsisten.

Masalahnya bukan terletak pada operasi individu, tetapi tugas yang lebih besar yang dijalankan oleh operasi.

Banyak algoritma ditulis dengan asumsi bahwa mereka berada dalam kendali penuh dari negara tempat mereka beroperasi. Dengan model eksekusi berurutan yang diurutkan seperti yang Anda gambarkan, operasi dapat dilakukan secara sewenang-wenang satu sama lain, dan jika mereka berbagi status, ada risiko bahwa negara tersebut berada dalam bentuk yang tidak konsisten.

Anda dapat membandingkannya dengan fungsi-fungsi yang sementara waktu dapat merusak invarian untuk melakukan apa yang mereka lakukan. Selama kondisi perantara tidak dapat diamati dari luar, mereka dapat melakukan apa pun yang mereka inginkan untuk mencapai tugas mereka.

Saat Anda menulis kode konkuren, Anda perlu memastikan bahwa status yang diperjuangkan dianggap tidak aman kecuali Anda memiliki akses eksklusif ke sana. Cara umum untuk mencapai akses eksklusif adalah menyinkronkan primitif sinkronisasi, seperti memegang kunci.

Hal lain yang cenderung diakibatkan oleh sinkronisasi primer pada beberapa platform adalah mereka mengeluarkan hambatan memori, yang memastikan konsistensi memori antar-CPU.

Kecuali untuk pengaturan 'bool' tidak ada jaminan (setidaknya dalam c) bahwa membaca atau menulis variabel hanya membutuhkan satu instruksi - atau lebih tepatnya tidak dapat diganggu di tengah membaca / menulisnya

Berbagi memori.

Ini definisi ... utas : sekelompok proses bersamaan, dengan memori bersama.

Jika tidak ada memori bersama, mereka biasanya disebut sebagai proses old-school-UNIX .
Mereka mungkin membutuhkan kunci, kadang-kadang, ketika mengakses file bersama.

(memori bersama di kernel mirip UNIX memang biasanya diimplementasikan menggunakan deskriptor file palsu yang mewakili alamat memori bersama)

CPU menjalankan satu instruksi pada satu waktu, tetapi bagaimana jika Anda memiliki dua atau lebih CPU?

Anda benar bahwa kunci tidak diperlukan, jika Anda dapat menulis program sedemikian rupa sehingga mengambil keuntungan dari instruksi atom: instruksi yang pelaksanaannya tidak terputus pada prosesor yang diberikan, dan bebas dari gangguan oleh prosesor lain.

Kunci diperlukan ketika beberapa instruksi perlu dilindungi dari gangguan, dan tidak ada instruksi atom yang setara.

Misalnya, memasukkan node ke daftar yang ditautkan dua kali lipat memerlukan pembaruan beberapa lokasi memori. Sebelum penyisipan, dan setelah penyisipan, invarian tertentu memegang tentang struktur daftar. Namun, selama penyisipan, invarian-invarian itu untuk sementara rusak: daftarnya ada dalam kondisi "sedang dibangun".

Jika utas lain berbaris melalui daftar saat invarian, atau juga mencoba memodifikasinya ketika keadaan seperti itu, struktur data mungkin akan menjadi rusak dan perilaku tidak dapat diprediksi: mungkin perangkat lunak akan macet, atau melanjutkan dengan hasil yang salah. Oleh karena itu, penting bagi utas untuk bagaimanapun setuju untuk tetap saling menjauh ketika daftar sedang diperbarui.

Daftar yang dirancang dengan tepat dapat dimanipulasi dengan instruksi atom, sehingga kunci tidak diperlukan. Algoritma untuk ini disebut "bebas kunci". Namun, perhatikan bahwa instruksi atom sebenarnya adalah bentuk penguncian. Mereka secara khusus diimplementasikan dalam perangkat keras, dan bekerja melalui komunikasi antar prosesor. Mereka lebih mahal daripada instruksi serupa yang tidak atom.

Pada multiprosesor yang tidak memiliki kemewahan instruksi atom, primitif untuk pengecualian bersama harus dibangun dari akses memori sederhana dan loop pemungutan suara. Masalah seperti itu telah dikerjakan oleh orang-orang seperti Edsger Dijkstra dan Leslie Lamport.