Bagian 1

Jelasnya, Ketidakmampuan meminimalkan kebutuhan akan penguncian dalam pemrograman multi-prosesor, tetapi apakah itu menghilangkan kebutuhan itu, atau adakah contoh di mana kekekalan saja tidak cukup? Sepertinya saya bahwa Anda hanya dapat menunda proses dan merangkum keadaan begitu lama sebelum sebagian besar program benar-benar harus melakukan sesuatu (memperbarui penyimpanan data, menghasilkan laporan, melemparkan pengecualian, dll.). Bisakah tindakan seperti itu selalu dilakukan tanpa kunci? Apakah tindakan semata-mata membuang setiap objek dan membuat yang baru alih-alih mengubah yang asli (pandangan kasar tentang keabadian) memberikan perlindungan absolut dari pertikaian antar-proses, atau adakah kasus sudut yang masih membutuhkan penguncian?

Saya tahu banyak programmer fungsional dan ahli matematika suka berbicara tentang "tidak ada efek samping" tetapi di "dunia nyata" semuanya memiliki efek samping, bahkan jika itu waktu yang diperlukan untuk menjalankan instruksi mesin. Saya tertarik pada jawaban teoretis / akademik dan jawaban praktis / dunia nyata.

Jika imutabilitas aman, mengingat batasan atau asumsi tertentu, saya ingin tahu apa sebenarnya batas "zona aman". Beberapa contoh batas yang mungkin:

• I / O
• Pengecualian / kesalahan
• Interaksi dengan program yang ditulis dalam bahasa lain
• Interaksi dengan mesin lain (fisik, virtual, atau teoritis)

Terima kasih khusus kepada @JimmaHoffa untuk komentarnya yang memulai pertanyaan ini!

Bagian 2

Pemrograman multi-prosesor sering digunakan sebagai teknik optimasi - untuk membuat beberapa kode berjalan lebih cepat. Kapan lebih cepat menggunakan kunci vs objek tidak berubah?

Mengingat batas yang ditetapkan dalam Hukum Amdahl , kapan Anda dapat mencapai kinerja over-semua yang lebih baik (dengan atau tanpa pengumpul sampah diperhitungkan) dengan objek tidak berubah vs mengunci yang bisa berubah?

Ringkasan

Saya menggabungkan dua pertanyaan ini menjadi satu untuk mencoba mencapai di mana kotak pembatas adalah untuk Kekekalan sebagai solusi untuk masalah threading.

Ini adalah pertanyaan aneh yang benar-benar luas jika dijawab sepenuhnya. Saya akan fokus untuk membereskan beberapa hal spesifik yang Anda tanyakan.

Kekekalan adalah trade off desain. Itu membuat beberapa operasi lebih sulit (mengubah keadaan dalam objek besar dengan cepat, membangun sedikit demi sedikit objek, menjaga keadaan berjalan, dll.) Mendukung yang lain (lebih mudah men-debug, alasan lebih mudah tentang perilaku program, tidak perlu khawatir tentang hal-hal yang berubah di bawah Anda saat bekerja secara bersamaan, dll.). Ini pertanyaan terakhir yang kami pedulikan dengan pertanyaan ini, tetapi saya ingin menekankan bahwa ini adalah alat. Alat yang baik yang sering memecahkan lebih banyak masalah daripada yang disebabkannya (dalam kebanyakan program modern ), tetapi bukan peluru perak ... Bukan sesuatu yang mengubah perilaku intrinsik program.

Sekarang, apa manfaatnya bagi Anda? Satu hal yang tidak dapat diubah membuat Anda satu hal: Anda dapat membaca objek yang tidak dapat diubah secara bebas, tanpa khawatir keadaannya berubah di bawah Anda (dengan asumsi itu benar-benar tidak dapat diubah ... Memiliki objek yang tidak dapat berubah dengan anggota yang dapat berubah biasanya merupakan pemecah kesepakatan). Itu dia. Ini membebaskan Anda dari keharusan mengelola konkurensi (melalui kunci, snapshot, partisi data atau mekanisme lainnya; fokus pertanyaan asli pada kunci adalah ... Tidak benar diberi ruang lingkup pertanyaan).

Ternyata banyak benda yang membaca objek. IO melakukannya, tetapi IO itu sendiri cenderung tidak menangani penggunaan bersamaan dengan baik. Hampir semua pemrosesan melakukan, tetapi objek lain mungkin bisa berubah, atau pemrosesan itu sendiri mungkin menggunakan keadaan yang tidak ramah terhadap concurrency. Menyalin suatu objek adalah masalah besar yang tersembunyi dalam beberapa bahasa karena salinan lengkap (hampir) tidak pernah merupakan operasi atom. Di sinilah objek abadi membantu Anda.

Adapun kinerja, itu tergantung pada aplikasi Anda. Kunci (biasanya) berat. Mekanisme manajemen konkurensi lainnya lebih cepat tetapi memiliki dampak tinggi pada desain Anda. Secara umum , desain yang sangat konkuren yang menggunakan objek yang tidak dapat diubah (dan menghindari kelemahannya) akan berkinerja lebih baik daripada desain yang sangat bersamaan yang mengunci objek yang bisa berubah. Jika program Anda ringan bersamaan maka itu tergantung dan / atau tidak masalah.

Tetapi kinerja seharusnya tidak menjadi perhatian utama Anda. Menulis program bersamaan sulit . Debugging program bersamaan sulit . Objek yang tidak dapat berubah membantu meningkatkan kualitas program Anda dengan menghilangkan peluang kesalahan penerapan manajemen konkurensi secara manual. Mereka mempermudah debugging karena Anda tidak mencoba melacak status dalam program bersamaan. Mereka membuat desain Anda lebih sederhana dan dengan demikian menghilangkan bug di sana.

Singkatnya: kekekalan membantu tetapi tidak akan menghilangkan tantangan yang diperlukan untuk menangani konkurensi dengan benar. Bantuan itu cenderung meresap, tetapi keuntungan terbesar adalah dari perspektif kualitas daripada kinerja. Dan tidak, kekekalan tidak secara ajaib meminta Anda untuk mengelola konkurensi di aplikasi Anda, maaf.

Sebuah fungsi yang menerima beberapa nilai dan mengembalikan beberapa nilai lainnya, dan tidak mengganggu apa pun di luar fungsi tersebut, tidak memiliki efek samping, dan karenanya aman untuk digunakan. Jika Anda ingin mempertimbangkan hal-hal seperti bagaimana cara menjalankan fungsi mempengaruhi konsumsi daya, itu masalah yang berbeda.

Saya berasumsi bahwa Anda merujuk ke mesin Turing-lengkap yang mengeksekusi semacam bahasa pemrograman yang terdefinisi dengan baik, di mana detail implementasi tidak relevan. Dengan kata lain, tidak masalah apa yang dilakukan stack, jika fungsi yang saya tulis dalam bahasa pemrograman pilihan saya dapat menjamin kekekalan dalam batas-batas bahasa. Saya tidak berpikir tentang tumpukan ketika saya memprogram dalam bahasa tingkat tinggi, saya juga tidak harus.

Untuk menggambarkan bagaimana ini bekerja, saya akan menawarkan beberapa contoh sederhana dalam C #. Agar contoh-contoh ini benar, kita harus membuat beberapa asumsi. Pertama, bahwa kompiler mengikuti spesifikasi C # tanpa kesalahan, dan kedua, bahwa ia menghasilkan program yang benar.

Katakanlah saya ingin fungsi sederhana yang menerima koleksi string, dan mengembalikan string yang merupakan gabungan dari semua string dalam koleksi yang dipisahkan oleh koma. Implementasi sederhana dan naif dalam C # mungkin terlihat seperti ini:

public string ConcatenateWithCommas(ImmutableList<string> list)
{
    string result = string.Empty;
    bool isFirst = false;

    foreach (string s in list)
    {
        if (isFirst)
            result += s;
        else
            result += ", " + s;
    }
    return result;
} 

Contoh ini tidak berubah, prima facie. Bagaimana saya tahu itu? Karena stringobjeknya tidak berubah. Namun, implementasinya tidak ideal. Karena resulttidak dapat diubah, objek string baru harus dibuat setiap kali melalui loop, menggantikan objek asli yang resultmenunjuk. Ini dapat secara negatif mempengaruhi kecepatan dan memberi tekanan pada pengumpul sampah, karena harus membersihkan semua string ekstra.

Sekarang, katakanlah saya melakukan ini:

public string ConcatenateWithCommas(ImmutableList<string> list)
{
    var result = new StringBuilder();
    bool isFirst = false;

    foreach (string s in list)
    {
        if (isFirst)
            result.Append(s);
        else
            result.Append(", " + s);
    }
    return result.ToString();
} 

Perhatikan bahwa saya telah diganti string resultdengan objek yang bisa berubah StringBuilder,. Ini jauh lebih cepat daripada contoh pertama, karena string baru tidak dibuat setiap kali melalui loop. Sebagai gantinya, objek StringBuilder hanya menambahkan karakter dari setiap string ke kumpulan karakter, dan menampilkan semuanya di akhir.

Apakah fungsi ini tidak berubah, meskipun StringBuilder bisa berubah?

Ya itu. Mengapa? Karena setiap kali fungsi ini dipanggil, StringBuilder baru dibuat, hanya untuk panggilan itu. Jadi sekarang kita memiliki fungsi murni yang aman-utas, tetapi mengandung komponen yang dapat berubah.

Tetapi bagaimana jika saya melakukan ini?

public class Concatenate
{
    private StringBuilder result = new StringBuilder();
    bool isFirst = false;

    public string ConcatenateWithCommas(ImmutableList<string> list)
    {
        foreach (string s in list)
        {
            if (isFirst)
                result.Append(s);
            else
                result.Append(", " + s);
        }
        return result.ToString();
    } 
}

Apakah metode ini aman untuk digunakan? Tidak. Mengapa? Karena kelas sekarang memegang keadaan di mana metode saya tergantung. Suatu kondisi lomba sekarang hadir dalam metode: satu utas dapat memodifikasi IsFirst, tetapi utas lain dapat melakukan yang pertama Append(), dalam hal ini saya sekarang memiliki koma di awal string saya yang tidak seharusnya ada di sana.

Mengapa saya ingin melakukannya seperti ini? Yah, saya mungkin ingin utas menumpuk string ke saya resulttanpa memperhatikan urutan, atau dalam urutan bahwa utas masuk. Mungkin itu adalah penebang, siapa tahu?

Pokoknya, untuk memperbaikinya, saya menaruh lockpernyataan di sekitar jeroan metode ini.

public class Concatenate
{
    private StringBuilder result = new StringBuilder();
    bool isFirst = false;
    private static object locker = new object();

    public string AppendWithCommas(ImmutableList<string> list)
    {
        lock (locker)
        {
            foreach (string s in list)
            {
                if (isFirst)
                    result.Append(s);
                else
                    result.Append(", " + s);
            }
            return result.ToString();
        }
    } 
}

Sekarang aman-utas lagi.

Satu-satunya cara metode abadi saya mungkin gagal menjadi aman-thread adalah jika metode entah bagaimana bocor bagian dari implementasinya. Bisakah ini terjadi? Tidak jika kompilernya benar dan programnya benar. Akankah saya membutuhkan kunci pada metode seperti itu? Tidak.

Untuk contoh bagaimana implementasi dapat dibocorkan dalam skenario konkurensi, lihat di sini .

Saya tidak yakin apakah saya mengerti pertanyaan Anda.

IMHO jawabannya adalah ya. Jika semua objek Anda tidak berubah, maka Anda tidak perlu kunci apa pun. Tetapi jika Anda perlu mempertahankan keadaan (mis. Anda menerapkan basis data atau Anda perlu mengagregasi hasil dari banyak utas) maka Anda perlu menggunakan kemampuan berubah-ubah dan karenanya juga terkunci. Kekekalan menghilangkan kebutuhan akan kunci, tetapi biasanya Anda tidak mampu memiliki aplikasi yang sepenuhnya tidak dapat diubah.

Jawab ke bagian 2 - kunci harus selalu lebih lambat daripada tidak ada kunci.

Mengenkapsulasi sekelompok keadaan terkait dalam referensi tunggal yang dapat berubah ke objek yang tidak berubah dapat memungkinkan banyak jenis modifikasi negara dilakukan tanpa kunci menggunakan pola:

do
{
   oldState = someObject.State;
   newState = oldState.WithSomeChanges();
} while (Interlocked.CompareExchange(ref someObject.State, newState, oldState) != oldState;

Jika dua utas keduanya mencoba memperbarui someObject.statesecara bersamaan, kedua objek akan membaca status lama dan menentukan status baru tanpa perubahan satu sama lain. Utas pertama yang menjalankan CompareExchange akan menyimpan apa yang menurutnya seharusnya keadaan selanjutnya. Utas kedua akan menemukan bahwa keadaan tidak lagi sesuai dengan yang telah dibaca sebelumnya, dan dengan demikian akan menghitung ulang keadaan sistem berikutnya yang tepat dengan perubahan utas pertama diberlakukan.

Pola ini memiliki keuntungan bahwa utas yang mendapatkan waylaid tidak dapat memblokir kemajuan utas lainnya. Ini memiliki keuntungan lebih lanjut bahwa bahkan ketika ada pertikaian berat, beberapa utas akan selalu membuat kemajuan. Namun memiliki kelemahan, di hadapan pertengkaran banyak thread mungkin menghabiskan banyak waktu melakukan pekerjaan yang akhirnya akan dibuang. Misalnya, jika 30 utas pada CPU terpisah semuanya mencoba mengubah objek secara bersamaan, satu akan berhasil pada upaya pertama, satu pada kedua, satu pada ketiga, dll. Sehingga setiap utas berakhir pada rata-rata membuat sekitar 15 upaya untuk memperbarui datanya. Menggunakan kunci "penasehat" dapat meningkatkan banyak hal secara signifikan: sebelum utas mencoba pembaruan, ia harus memeriksa apakah indikator "pertikaian" diatur. Jika begitu, itu harus mendapatkan kunci sebelum melakukan pembaruan. Jika utas membuat beberapa upaya yang gagal pada pembaruan, itu harus menetapkan bendera pertikaian. Jika utas yang mencoba mendapatkan kunci menemukan tidak ada orang lain yang menunggu, itu akan menghapus bendera pertentangan. Perhatikan bahwa kunci di sini tidak diperlukan untuk "kebenaran"; kode akan berfungsi dengan benar bahkan tanpa itu. Tujuan kunci adalah untuk meminimalkan jumlah kode waktu yang dihabiskan untuk operasi yang tidak mungkin berhasil.

Anda mulai dengan

Jelasnya Ketidakmampuan meminimalkan kebutuhan untuk mengunci dalam pemrograman multi-prosesor

Salah. Anda perlu membaca dokumentasi dengan cermat untuk setiap kelas yang Anda gunakan. Sebagai contoh, const std :: string dalam C ++ tidak aman untuk thread. Objek yang tidak dapat berubah dapat memiliki status internal yang berubah saat mengaksesnya.

Tetapi Anda melihat ini dari sudut pandang yang benar-benar salah. Tidak masalah apakah suatu benda tidak dapat diubah atau tidak, yang penting adalah apakah Anda mengubahnya. Apa yang Anda katakan seperti mengatakan "jika Anda tidak pernah mengikuti tes mengemudi, Anda tidak akan pernah kehilangan SIM untuk mengemudi dalam keadaan mabuk". Benar, tapi agak kehilangan intinya.

Sekarang dalam kode contoh seseorang menulis dengan fungsi bernama "ConcatenateWithCommas": Jika input dapat diubah dan Anda menggunakan kunci, apa yang akan Anda peroleh? Jika orang lain mencoba mengubah daftar saat Anda mencoba menyatukan senar, kunci dapat mencegah Anda menabrak. Tetapi Anda masih tidak tahu apakah Anda menyatukan senar sebelum atau setelah utas lainnya mengubahnya. Jadi hasil Anda agak tidak berguna. Anda memiliki masalah yang tidak terkait dengan penguncian dan tidak dapat diperbaiki dengan penguncian. Tetapi kemudian jika Anda menggunakan objek yang tidak dapat diubah, dan utas lainnya mengganti seluruh objek dengan yang baru, Anda menggunakan objek lama dan bukan objek baru, sehingga hasil Anda tidak berguna. Anda harus memikirkan masalah-masalah ini pada tingkat fungsional yang sebenarnya.