Bagikan melalui

Pertimbangan Pemrograman Tanpa Kunci untuk Xbox 360 dan Microsoft Windows

Pemrograman tanpa kunci adalah cara untuk berbagi data yang berubah dengan aman antara beberapa utas tanpa biaya memperoleh dan melepaskan kunci. Ini terdengar seperti obat mujarab, tetapi pemrograman tanpa penguncian itu kompleks dan halus, dan kadang-kadang tidak memberikan manfaat yang dijanjikannya. Pemrograman tanpa kunci sangat kompleks pada Xbox 360.

Pemrograman tanpa kunci adalah teknik yang valid untuk pemrograman multithreaded, tetapi tidak boleh digunakan dengan ringan. Sebelum menggunakannya, Anda harus memahami kompleksitas, dan Anda harus mengukur dengan hati-hati untuk memastikan bahwa itu benar-benar memberi Anda keuntungan yang Anda harapkan. Dalam banyak kasus, ada solusi yang lebih sederhana dan lebih cepat, seperti berbagi data lebih jarang, yang harus digunakan sebagai gantinya.

Menggunakan pemrograman tanpa kunci dengan benar dan aman membutuhkan pengetahuan yang signifikan tentang perangkat keras dan pengkompilasi Anda. Artikel ini memberikan gambaran umum tentang beberapa masalah yang perlu dipertimbangkan saat mencoba menggunakan teknik pemrograman tanpa kunci.

Pemrograman dengan Kunci

Saat menulis kode multi-utas, sering kali perlu berbagi data antar utas. Jika beberapa utas secara bersamaan membaca dan menulis struktur data bersama, kerusakan memori dapat terjadi. Cara paling sederhana untuk memecahkan masalah ini adalah dengan menggunakan kunci. Misalnya, jika ManipulateSharedData hanya boleh dijalankan oleh satu utas pada satu waktu, CRITICAL_SECTION dapat digunakan untuk menjamin ini, seperti dalam kode berikut:

// Initialize
CRITICAL_SECTION cs;
InitializeCriticalSection(&cs);

// Use
void ManipulateSharedData()
{
    EnterCriticalSection(&cs);
    // Manipulate stuff...
    LeaveCriticalSection(&cs);
}

// Destroy
DeleteCriticalSection(&cs);

Kode ini cukup sederhana dan mudah, dan mudah untuk mengetahui bahwa kode ini benar. Namun, pemrograman dengan kunci dilengkapi dengan beberapa potensi kerugian. Misalnya, jika dua utas mencoba memperoleh dua kunci yang sama tetapi memperolehnya dalam urutan yang berbeda, hal ini dapat menyebabkan kebuntuan. Jika sebuah program memegang kunci terlalu lama—baik karena desain yang buruk atau karena utas digantikan oleh utas yang memiliki prioritas lebih tinggi—utas lain dapat terblokir untuk waktu yang lama. Risiko ini sangat besar pada Xbox 360 karena utas perangkat lunak diberi utas perangkat keras oleh pengembang, dan sistem operasi tidak akan memindahkannya ke utas perangkat keras lain, bahkan jika ada yang menganggur. Xbox 360 juga tidak memiliki perlindungan terhadap inversi prioritas, di mana utas berprioritas tinggi berputar dalam perulangan sambil menunggu utas berprioritas rendah untuk melepaskan kunci. Akhirnya, jika panggilan prosedur yang ditangguhkan atau mengganggu rutinitas layanan mencoba memperoleh kunci, Anda mungkin mendapatkan kebuntuan.

Terlepas dari masalah ini, primitif sinkronisasi, seperti bagian penting, umumnya adalah cara terbaik untuk mengoordinasikan beberapa utas. Jika primitif sinkronisasi terlalu lambat, solusi terbaik biasanya adalah menggunakannya lebih jarang. Namun, bagi mereka yang mampu membayar kompleksitas ekstra, opsi lain adalah pemrograman tanpa kunci.

Pemrograman Tanpa Kunci

Pemrograman tanpa kunci, seperti namanya, adalah keluarga teknik untuk memanipulasi data bersama dengan aman tanpa menggunakan kunci. Ada algoritma tanpa kunci yang tersedia untuk meneruskan pesan, berbagi daftar dan antrean data, dan tugas lainnya.

Saat melakukan pemrograman tanpa kunci, ada dua tantangan yang harus Anda hadapi: operasi non-atomik dan menyusun ulang.

Operasi Non-Atomik

Operasi atom adalah operasi yang tak terbagi—di mana utas lain dijamin tidak akan pernah melihat operasi tersebut ketika belum sepenuhnya selesai. Operasi atomik penting untuk pemrograman tanpa kunci, karena tanpanya, thread lain mungkin melihat nilai yang belum sepenuhnya ditulis, atau melihat keadaan yang tidak konsisten.

Pada semua prosesor modern, Anda dapat berasumsi bahwa operasi baca dan tulis pada jenis data asli yang terselaraskan secara alami bersifat atomik. Selama bus memori setidaknya seluas jenis yang dibaca atau ditulis, CPU membaca dan menulis jenis ini dalam satu transaksi bus, sehingga tidak mungkin bagi utas lain untuk melihatnya dalam keadaan setengah selesai. Pada x86 dan x64, tidak ada jaminan bahwa pembacaan dan penulisan yang lebih besar dari delapan byte bersifat atomik. Ini berarti bahwa pembacaan dan penulisan 16 byte pada register ekstensi SIMD streaming (SSE), serta operasi string, mungkin tidak bersifat atomik.

Membaca dan menulis tipe yang tidak diselaraskan secara alami—misalnya, menulis DWORD yang melewati batas-batas empat byte—tidak dijamin berlangsung secara atomik. CPU mungkin harus melakukan pembacaan dan penulisan ini sebagai beberapa transaksi bus, yang dapat memungkinkan utas lain untuk memodifikasi atau melihat data di tengah pembacaan atau penulisan.

Operasi komposit, seperti urutan baca-ubah-tulis yang terjadi ketika Anda menaikkan variabel bersama, bukan atomik. Pada Xbox 360, operasi ini diimplementasikan sebagai beberapa instruksi (lwz, addi, dan stw), dan proses/thread dapat beralih di tengah-tengah urutan. Pada x86 dan x64, ada satu instruksi (inc) yang dapat digunakan untuk menaikkan variabel dalam memori. Jika Anda menggunakan instruksi ini, menaikkan variabel adalah atomik pada sistem prosesor tunggal, tetapi masih belum atomik pada sistem multi-prosesor. Membuat inc atomik pada sistem multi-prosesor berbasis x86 dan x64 memerlukan penggunaan awalan kunci, yang mencegah prosesor lain melakukan urutan baca-ubah-tulisnya sendiri antara baca dan tulis perintah inc.

Kode berikut menunjukkan beberapa contoh:

// This write is not atomic because it is not natively aligned.
DWORD* pData = (DWORD*)(pChar + 1);
*pData = 0;

// This is not atomic because it is three separate operations.
++g_globalCounter;

// This write is atomic.
g_alignedGlobal = 0;

// This read is atomic.
DWORD local = g_alignedGlobal;

Menjamin Atomisitas

Anda dapat yakin Anda menggunakan operasi atom dengan mengombinasikan hal-hal berikut:

  • Operasi yang secara alami bersifat atomik
  • Kunci untuk membungkus operasi komposit
  • Fungsi sistem operasi yang mengimplementasikan versi atomik dari operasi komposit yang populer

Menaikkan variabel bukanlah operasi atomik, dan penambahan dapat menyebabkan kerusakan data jika dijalankan pada beberapa utas.

// This will be atomic.
g_globalCounter = 0;

// This is not atomic and gives undefined behavior
// if executed on multiple threads
++g_globalCounter;

Win32 dilengkapi dengan serangkaian fungsi yang menawarkan versi baca-modifikasi-tulis atomik untuk beberapa operasi umum. Ini adalah keluarga fungsi InterlockedXxx. Jika semua modifikasi variabel bersama menggunakan fungsi-fungsi ini, modifikasi akan aman utas.

// Incrementing our variable in a safe lockless way.
InterlockedIncrement(&g_globalCounter);

Menyusun ulang

Masalah yang lebih halus adalah menyusun ulang. Bacaan dan tulisan tidak selalu terjadi dalam urutan yang telah Anda tulis dalam kode Anda, dan ini dapat menyebabkan masalah yang sangat membingungkan. Dalam banyak algoritma multi-utas, sebuah utas menulis beberapa data dan kemudian menulis ke sebuah penanda yang memberi tahu utas lain bahwa data siap. Ini dikenal sebagai rilis tulis. Jika penulisan diurutkan ulang, utas lain bisa jadi melihat bahwa penanda diatur sebelum mereka dapat melihat data yang telah ditulis.

Demikian pula, dalam banyak kasus, utas membaca dari bendera dan kemudian membaca beberapa data bersama jika bendera mengatakan bahwa utas telah memperoleh akses ke data bersama. Ini dikenal sebagai read-acquire. Jika bacaan diurutkan ulang, maka data dapat dibaca dari penyimpanan bersama sebelum bendera, dan nilai yang terlihat mungkin tidak diperbarui.

Menyusun ulang pembacaan dan penulisan dapat dilakukan baik oleh pengkompilasi maupun oleh prosesor. Kompiler dan prosesor telah melakukan penyusunan ulang ini selama bertahun-tahun, tetapi pada mesin dengan satu prosesor, hal ini kurang menjadi masalah. Ini karena pengaturan ulang CPU baca dan tulis tidak terlihat pada mesin prosesor tunggal (untuk kode driver non-perangkat yang bukan bagian dari driver perangkat), dan pengaturan ulang pembacaan dan penulisan kompilator cenderung tidak menyebabkan masalah pada mesin prosesor tunggal.

Jika pengkompilasi atau CPU mengatur ulang tulisan yang ditampilkan dalam kode berikut, utas lain mungkin melihat bahwa bendera hidup diatur saat masih melihat nilai lama untuk x atau y. Penataan ulang serupa dapat terjadi saat membaca.

Dalam kode ini, satu thread menambahkan entri baru ke array sprite.

// Create a new sprite by writing its position into an empty
// entry and then setting the 'alive' flag. If 'alive' is
// written before x or y then errors may occur.
g_sprites[nextSprite].x = x;
g_sprites[nextSprite].y = y;
g_sprites[nextSprite].alive = true;

Pada blok kode berikutnya, utas lain membaca dari array sprite.

// Draw all sprites. If the reads of x and y are moved ahead of
// the read of 'alive' then errors may occur.
for( int i = 0; i < numSprites; ++i )
{
    if( g_sprites[nextSprite].alive )
    {
        DrawSprite( g_sprites[nextSprite].x,
                g_sprites[nextSprite].y );
    }
}

Untuk membuat sistem sprite ini aman, kita perlu mencegah kompilator dan CPU melakukan pengurutan ulang pembacaan dan penulisan.

Memahami Penataan Ulang Operasi Penulisan CPU

Beberapa CPU mengatur ulang penulisan sehingga secara eksternal terlihat oleh prosesor atau perangkat lain dalam urutan non-program. Pengaturan ulang ini tidak pernah terlihat oleh kode non-driver berulir tunggal, tetapi dapat menyebabkan masalah dalam kode multi-utas.

Xbox 360

Meskipun CPU Xbox 360 tidak menyusun ulang instruksi, ia mengatur ulang operasi tulis, yang melengkapi setelah instruksi tersebut. Pengaturan ulang penulisan ini secara khusus diizinkan oleh model memori PowerPC.

Menulis di Xbox 360 tidak langsung masuk ke cache L2. Sebagai gantinya, untuk meningkatkan bandwidth tulis cache L2, mereka melalui antrean penyimpanan dan kemudian ke buffer pengumpulan penyimpanan. Buffer store-gather memungkinkan blok 64-byte ditulis ke cache L2 dalam satu operasi. Ada delapan buffer penyimpanan, yang memungkinkan penulisan yang efisien ke beberapa area memori.

Buffer kumpulan penyimpanan biasanya ditulis ke cache L2 dalam urutan pertama masuk-pertama keluar (FIFO). Namun, jika baris cache target penulisan tidak ada di cache L2, tulisan tersebut mungkin tertunda saat baris cache diambil dari memori.

Bahkan ketika buffer store-gather ditulis ke cache L2 dalam urutan FIFO yang ketat, ini tidak menjamin bahwa penulisan setiap data ditulis ke cache L2 dalam urutan yang sama. Misalnya, bayangkan bahwa CPU menulis ke lokasi 0x1000, lalu ke lokasi 0x2000, dan kemudian ke lokasi 0x1004. Penulisan pertama mengalokasikan buffer pengumpul dan meletakkannya di bagian depan antrean. Penulisan kedua mengalokasikan buffer pengumpulan store-gather lain dan menempatkannya dalam antrean berikutnya. Penulisan ketiga menambahkan datanya ke buffer store-gather pertama, yang tetap berada di bagian depan antrean. Dengan demikian, tulisan ketiga akhirnya masuk ke cache L2 sebelum penulisan kedua.

Penyusunan ulang yang diakibatkan oleh buffer store-gather pada dasarnya tidak dapat diprediksi, terutama karena kedua utas pada satu inti berbagi buffer store-gather, membuat alokasi dan pengosongan buffer store-gather tersebut sangat bervariasi.

Ini adalah salah satu contoh bagaimana penulisan dapat diurutkan ulang. Mungkin ada kemungkinan lain.

x86 dan x64

Meskipun CPU x86 dan x64 menyusun ulang instruksi, CPU x86 dan x64 umumnya tidak menyusun ulang operasi tulis relatif terhadap penulisan lain. Ada beberapa pengecualian untuk memori gabungan tulis. Selain itu, operasi string (MOVS dan STOS) dan penulisan SSE 16 byte dapat diurutkan ulang secara internal, tetapi jika tidak, penulisan tidak diurutkan ulang relatif satu sama lain.

Memahami Pengaturan Ulang Pembacaan CPU

Beberapa CPU mengatur ulang pembacaan sehingga secara efektif berasal dari penyimpanan bersama dalam urutan di luar program. Pengaturan ulang ini tidak pernah terlihat oleh kode non-driver yang berjalan dengan satu utas, tetapi dapat menyebabkan masalah dalam kode yang berjalan dengan banyak utas.

Xbox 360

Cache miss dapat menyebabkan beberapa pembacaan data tertunda, yang secara efektif menyebabkan pembacaan data dari memori bersama terjadi di luar urutan, dan waktu terjadinya kegagalan cache ini pada dasarnya tidak dapat diprediksi. Prefetching dan prediksi percabangan juga dapat menyebabkan data berasal dari memori bersama dalam urutan tidak teratur. Ini hanyalah beberapa contoh bagaimana bacaan dapat diurutkan ulang. Mungkin ada kemungkinan lain. Pengaturan ulang baca ini secara khusus diizinkan oleh model memori PowerPC.

x86 dan x64

Meskipun CPU x86 dan x64 menyusun ulang instruksi, CPU x86 dan x64 umumnya tidak menyusun ulang operasi baca relatif terhadap bacaan lain. Operasi string (MOVS dan STOS) dan pembacaan SSE 16 byte dapat diurutkan ulang secara internal, tetapi jika tidak, bacaan tidak diurutkan ulang relatif satu sama lain.

Penyusunan Ulang Lainnya

Meskipun CPU x86 dan x64 tidak mengatur ulang penulisan relatif terhadap penulisan lainnya, atau mengatur ulang pembacaan relatif terhadap pembacaan lainnya, mereka dapat mengatur ulang pembacaan relatif terhadap penulisan. Secara khusus, jika program menulis ke satu lokasi diikuti dengan membaca dari lokasi yang berbeda, data yang dibaca mungkin berasal dari memori bersama sebelum data tertulis sampai di sana. Penyusunan ulang ini dapat merusak beberapa algoritma, seperti algoritma eksklusi mutual Dekker. Dalam algoritma Dekker, setiap utas menetapkan bendera untuk menunjukkan bahwa ia ingin memasuki wilayah penting, lalu memeriksa bendera utas lainnya untuk melihat apakah utas lain berada di wilayah penting atau mencoba memasukkannya. Kode awal adalah sebagai berikut.

volatile bool f0 = false;
volatile bool f1 = false;

void P0Acquire()
{
    // Indicate intention to enter critical region
    f0 = true;
    // Check for other thread in or entering critical region
    while (f1)
    {
        // Handle contention.
    }
    // critical region
    ...
}


void P1Acquire()
{
    // Indicate intention to enter critical region
    f1 = true;
    // Check for other thread in or entering critical region
    while (f0)
    {
        // Handle contention.
    }
    // critical region
    ...
}

Masalahnya adalah bahwa pembacaan f1 pada P0Acquire dapat membaca dari penyimpanan bersama sebelum penulisan ke f0 sampai ke penyimpanan bersama. Sementara itu, pembacaan f0 di P1Acquire dapat dilakukan dari penyimpanan bersama sebelum penulisan ke f1 selesai dan tersimpan di penyimpanan bersama. Efek bersihnya adalah kedua utas mengatur benderanya ke TRUE, dan kedua utas melihat bendera utas lainnya sebagai FALSE, sehingga keduanya memasuki wilayah penting. Oleh karena itu, meskipun masalah dengan menyusun ulang pada sistem berbasis x86 dan x64 kurang umum daripada pada Xbox 360, mereka pasti masih dapat terjadi. Algoritma Dekker tidak akan berfungsi tanpa hambatan memori perangkat keras pada salah satu platform ini.

CPU x86 dan x64 tidak akan mengurutkan ulang penulisan sebelum pembacaan sebelumnya. CPU x86 dan x64 hanya menyusun ulang bacaan sebelum penulisan sebelumnya jika mereka menargetkan lokasi yang berbeda.

CPU PowerPC dapat menyusun ulang operasi baca sebelum menulis, dan dapat menyusun ulang operasi tulis sebelum membaca, selama pengaksesan dilakukan pada alamat yang berbeda.

Menyusun ulang Ringkasan

CPU Xbox 360 menyusun ulang operasi memori jauh lebih agresif daripada CPU x86 dan x64, seperti yang ditunjukkan dalam tabel berikut. Untuk detail selengkapnya, lihat dokumentasi prosesor.

Menyusun ulang Aktivitas x86 dan x64 Xbox 360
Pembacaan yang bergerak lebih cepat dari bacaan lainnya Tidak Ya
Penulisan mendahului penulisan lainnya Tidak Ya
Penulisan bergerak di depan bacaan Tidak Ya
Pembacaan didahulukan daripada penulisan Ya Ya

 

Hambatan Read-Acquire dan Write-Release

Konstruksi utama yang digunakan untuk mencegah penyusunan ulang baca dan tulis disebut penghalang baca-akuisisi dan tulis-rilis. Read-acquire adalah pembacaan sebuah flag atau variabel lain untuk mendapatkan kepemilikan sumber daya, disertai dengan penghalang terhadap pengurutan ulang. Demikian pula, rilis tulis adalah penulisan bendera atau variabel lain untuk memberikan kepemilikan sumber daya, ditambah dengan hambatan terhadap penyortihan ulang.

Definisi formal, berkat kontribusi dari Herb Sutter, adalah:

  • Operasi akuisisi pembacaan dijalankan sebelum semua operasi baca dan tulis oleh utas yang sama setelahnya dalam urutan program.
  • Penulisan-rilis dilakukan setelah semua operasi baca dan tulis oleh utas yang sama yang mendahuluinya dalam urutan program yang sesuai.

Saat kode Anda memperoleh kepemilikan beberapa memori, baik dengan memperoleh kunci atau dengan menarik item dari daftar tertaut bersama (tanpa kunci), selalu ada proses pembacaan yang terlibat—menguji penanda atau penunjuk memori untuk melihat apakah kepemilikan memori telah diperoleh. Bacaan ini mungkin merupakan bagian dari operasi InterlockedXxx, yang dalam hal ini melibatkan membaca dan menulis, tetapi bacaan yang menunjukkan apakah kepemilikan telah diperoleh. Setelah kepemilikan memori didapatkan, nilai biasanya dibaca dari atau ditulis ke memori tersebut, dan sangat penting agar pembacaan dan penulisan ini dilakukan setelah memperoleh kepemilikan. Hambatan read-acquire menjamin hal ini.

Ketika kepemilikan atas beberapa memori dilepaskan, baik dengan melepaskan kunci atau dengan mendorong item ke daftar tertaut bersama, selalu ada tindakan penulisan yang memberi tahu utas lain bahwa memori sekarang tersedia untuk mereka. Meskipun kode Anda memiliki kepemilikan atas memori, mungkin kode tersebut telah membaca dari atau menulis ke dalamnya, dan sangat penting pembacaan dan penulisan ini dilakukan sebelum melepaskan kepemilikan. Penghalang rilis tulis menjamin hal ini.

Paling mudah untuk menganggap penghalang read-acquire dan write-release sebagai operasi tunggal. Namun, mereka kadang-kadang harus dibangun dari dua bagian: membaca atau menulis dan penghalang yang tidak memungkinkan operasi membaca atau menulis melintas. Dalam hal ini, penempatan hambatan sangat penting. Untuk penghalang baca-akuisisi, pembacaan penanda dilakukan terlebih dahulu, kemudian penghalang, dan setelah itu pembacaan serta penulisan data bersama. Untuk penghalang penulisan-rilis, pembacaan dan penulisan data bersama terjadi terlebih dahulu, diikuti dengan penghalang, lalu penulisan bendera.

// Read that acquires the data.
if( g_flag )
{
    // Guarantee that the read of the flag executes before
    // all reads and writes that follow in program order.
    BarrierOfSomeSort();

    // Now we can read and write the shared data.
    int localVariable = sharedData.y;
    sharedData.x = 0;

    // Guarantee that the write to the flag executes after all
    // reads and writes that precede it in program order.
    BarrierOfSomeSort();
    
    // Write that releases the data.
    g_flag = false;
}

Satu-satunya perbedaan antara read-acquire dan write-release adalah lokasi penghalang memori. Read-acquire memiliki barier setelah operasi penguncian, dan write-release memiliki barier sebelumnya. Dalam kedua kasus, hambatan berada di antara referensi ke memori yang dikunci dan referensi ke kunci.

Untuk memahami mengapa hambatan diperlukan baik ketika memperoleh dan saat merilis data, yang terbaik (dan paling akurat) menganggap hambatan ini sebagai menjamin sinkronisasi dengan memori bersama, bukan dengan prosesor lain. Jika satu prosesor menggunakan rilis tulis untuk merilis struktur data ke memori bersama, dan prosesor lain menggunakan read-acquire untuk mendapatkan akses ke struktur data tersebut dari memori bersama, kode kemudian akan berfungsi dengan baik. Jika salah satu prosesor tidak menggunakan hambatan yang sesuai, berbagi data mungkin gagal.

Menggunakan penghalang yang tepat untuk mencegah kompilator dan penyusuran ulang CPU untuk platform Anda sangat penting.

Salah satu keuntungan menggunakan primitif sinkronisasi yang disediakan oleh sistem operasi adalah bahwa semuanya termasuk hambatan memori yang sesuai.

Mencegah Penyusuran Ulang Pengkompilasi

Tugas kompilator adalah mengoptimalkan kode Anda secara agresif untuk meningkatkan performa. Ini termasuk mengatur ulang instruksi di mana pun itu berguna dan di mana pun itu tidak akan mengubah perilaku. Karena C++ Standard tidak pernah menyebutkan multithreading, dan karena pengkompilasi tidak tahu kode apa yang perlu aman untuk utas, pengkompilasi mengasumsikan bahwa kode Anda adalah utas tunggal saat memutuskan pengaturan ulang apa yang dapat dilakukannya dengan aman. Oleh karena itu, Anda perlu memberi tahu pengkompilasi saat tidak boleh melakukan penataan ulang operasi membaca dan menulis.

Dengan Visual C++ Anda dapat mencegah penyusunan ulang oleh pengompiler dengan menggunakan intrinsic _ReadWriteBarrier. Ketika Anda menyisipkan _ReadWriteBarrier ke dalam kode Anda, pengkompilasi tidak akan memindahkan baca dan tulis melewati batas tersebut.

#if _MSC_VER < 1400
    // With VC++ 2003 you need to declare _ReadWriteBarrier
    extern "C" void _ReadWriteBarrier();
#else
    // With VC++ 2005 you can get the declaration from intrin.h
#include <intrin.h>
#endif
// Tell the compiler that this is an intrinsic, not a function.
#pragma intrinsic(_ReadWriteBarrier)

// Create a new sprite by filling in a previously empty entry.
g_sprites[nextSprite].x = x;
g_sprites[nextSprite].y = y;
// Write-release, barrier followed by write.
// Guarantee that the compiler leaves the write to the flag
// after all reads and writes that precede it in program order.
_ReadWriteBarrier();
g_sprites[nextSprite].alive = true;

Dalam kode berikut ini, thread lain membaca dari array sprite:

// Draw all sprites.
for( int i = 0; i < numSprites; ++i )
{

    // Read-acquire, read followed by barrier.
    if( g_sprites[nextSprite].alive )
    {
    
        // Guarantee that the compiler leaves the read of the flag
        // before all reads and writes that follow in program order.
        _ReadWriteBarrier();
        DrawSprite( g_sprites[nextSprite].x,
                g_sprites[nextSprite].y );
    }
}

Penting untuk dipahami bahwa _ReadWriteBarrier tidak menyisipkan instruksi tambahan apa pun, dan itu tidak mencegah CPU mengatur ulang baca dan tulis—itu hanya mencegah pengkompilasi mengatur ulang. Dengan demikian, _ReadWriteBarrier cukup ketika Anda menerapkan penghalang rilis tulis pada x86 dan x64 (karena x86 dan x64 tidak menyusun ulang penulisan, dan penulisan normal cukup untuk melepaskan kunci), tetapi dalam kebanyakan kasus lain, perlu juga untuk mencegah CPU menyusun ulang bacaan dan tulis.

Anda juga dapat menggunakan _ReadWriteBarrier saat menulis ke memori gabungan tulis yang tidak dapat di-cache untuk mencegah penyortiban ulang penulisan. Dalam hal ini _ReadWriteBarrier membantu meningkatkan performa, dengan menjamin bahwa penulisan terjadi dalam urutan linier pilihan prosesor.

Dimungkinkan juga untuk menggunakan _ReadBarrier dan _WriteBarrier intrinsik untuk kontrol yang lebih tepat untuk menyusun ulang kompilator. Pengkompilasi tidak akan memindahkan bacaan di seluruh _ReadBarrier, dan tidak akan memindahkan penulisan di seluruh _WriteBarrier.

Mencegah Penyusuran Ulang CPU

Menyusun ulang CPU lebih halus daripada menyusun ulang pengkompilasi. Anda tidak pernah dapat melihatnya terjadi secara langsung, Anda hanya melihat bug yang tidak dapat dijelaskan. Untuk mencegah pengurutan ulang CPU baca dan tulis, Anda perlu menggunakan instruksi penghalang memori, pada beberapa prosesor. Nama serba guna untuk instruksi penghalang memori, pada Xbox 360 dan di Windows, adalah MemoryBarrier. Makro ini diimplementasikan dengan tepat untuk setiap platform.

Pada Xbox 360, MemoryBarrier didefinisikan sebagai lwsync (sinkronisasi ringan), juga tersedia melalui intrinsik __lwsync , yang didefinisikan dalam ppcintrinsics.h. __lwsync juga berfungsi sebagai penghalang memori kompilator, mencegah pengaturan ulang baca dan tulis oleh pengkompilasi.

Instruksi lwsync adalah hambatan memori pada Xbox 360 yang menyinkronkan satu inti prosesor dengan cache L2. Ini menjamin bahwa semua penulisan sebelum lwsync mencapai cache L2 sebelum penulisan yang mengikutinya. Ini juga menjamin bahwa setiap pembacaan yang mengikuti lwsync tidak mendapatkan data dari L2 yang lebih lama daripada pembacaan sebelumnya. Salah satu jenis pengubahan ulang yang tidak dicegah adalah pembacaan yang bergerak mendahului penulisan ke alamat yang berbeda. Dengan demikian, lwsync memberlakukan pengurutan memori yang cocok dengan urutan memori default pada prosesor x86 dan x64. Untuk mendapatkan urutan memori penuh memerlukan instruksi sinkronisasi yang lebih mahal (juga dikenal sebagai sinkronisasi kelas berat), tetapi dalam kebanyakan kasus, ini tidak diperlukan. Opsi susun ulang memori pada Xbox 360 diperlihatkan dalam tabel berikut.

Urutan Ulang Xbox 360 Tidak ada sinkronisasi lwsync sinkronisasi
Bacaan bergerak di depan pembacaan Ya Tidak Tidak
Penulisan mendahului penulisan lainnya Ya Tidak Tidak
Aktivitas penulisan dilakukan sebelum pembacaan Ya Tidak Tidak
Bacaan bergerak di depan penulisan Ya Ya Tidak

 

PowerPC juga memiliki instruksi sinkronisasi isync dan eieio (yang digunakan untuk mengontrol penyusunan ulang pada memori yang tidak mendukung penyimpanan sementara). Instruksi sinkronisasi ini tidak boleh diperlukan untuk tujuan sinkronisasi normal.

Pada Windows, MemoryBarrier didefinisikan dalam Winnt.h dan memberi Anda instruksi penghalang memori yang berbeda tergantung pada apakah Anda mengkompilasi untuk x86 atau x64. Instruksi batas memori berfungsi sebagai penghalang penuh, mencegah semua penyusunan ulang pembacaan dan penulisan di seberang batas tersebut. Dengan demikian, MemoryBarrier di Windows memberikan jaminan pengurutan ulang yang lebih kuat daripada pada Xbox 360.

Pada Xbox 360, dan di banyak CPU lainnya, ada satu cara tambahan yang dapat mencegah pengaturan ulang pembacaan oleh CPU. Jika Anda membaca pointer lalu menggunakan pointer tersebut untuk memuat data lain, CPU menjamin bahwa akses dari pointer tersebut tidak lebih lama daripada pembacaan pointer. Jika bendera kunci Anda adalah penunjuk dan jika semua pembacaan data bersama dilakukan melalui pointer, MemoryBarrier dapat dihilangkan, untuk penghematan kinerja yang sederhana.

Data* localPointer = g_sharedPointer;
if( localPointer )
{
    // No import barrier is needed--all reads off of localPointer
    // are guaranteed to not be reordered past the read of
    // localPointer.
    int localVariable = localPointer->y;
    // A memory barrier is needed to stop the read of g_global
    // from being speculatively moved ahead of the read of
    // g_sharedPointer.
    int localVariable2 = g_global;
}

Instruksi MemoryBarrier hanya mencegah pengurusan ulang pembacaan dan penulisan ke memori yang dapat di-cache. Jika Anda mengalokasikan memori sebagai PAGE_NOCACHE atau PAGE_WRITECOMBINE, teknik umum untuk penulis driver perangkat dan untuk pengembang game di Xbox 360, MemoryBarrier tidak berpengaruh pada akses ke memori ini. Sebagian besar pengembang tidak memerlukan sinkronisasi memori yang tidak dapat di-cache. Itu di luar cakupan artikel ini.

Fungsi yang Saling Terhubung dan Penataan Ulang CPU

Terkadang, pembacaan atau penulisan yang memperoleh atau melepaskan sumber daya dilakukan dengan menggunakan salah satu fungsi InterlockedXxx. Di Windows, ini mempermudah segalanya; karena pada Windows, fungsi InterlockedXxx semuanya berfungsi sebagai penghalang memori penuh. Mereka secara efektif memiliki hambatan memori CPU baik sebelum dan sesudahnya, yang berarti bahwa mereka adalah hambatan baca-memperoleh atau menulis-rilis semua dengan sendirinya.

Pada Xbox 360, fungsi InterlockedXxx tidak berisi hambatan memori CPU. Mereka mencegah penyusunan ulang operasi baca dan tulis oleh kompilator tetapi tidak penyusunan ulang oleh CPU. Oleh karena itu, dalam kebanyakan kasus saat menggunakan fungsi InterlockedXxx pada Xbox 360, Anda harus mendahului atau mengikutinya dengan __lwsync, untuk menjadikannya penghalang baca-akuisisi atau tulis-rilis. Untuk kenyamanan dan kemudahan membaca, ada versi Acquire dan Release dari banyak fungsi InterlockedXxx. Ini memiliki hambatan memori bawaan. Misalnya, InterlockedIncrementAcquire melakukan penambahan saling terkunci yang diikuti oleh batas memori __lwsync untuk memberikan fungsionalitas akuisisi baca penuh.

Disarankan agar Anda menggunakan versi Acquire and Release dari fungsi InterlockedXxx (yang sebagian besar tersedia di Windows juga, tanpa penalti performa) untuk membuat niat Anda lebih jelas dan membuatnya lebih mudah untuk mendapatkan instruksi penghalang memori di tempat yang benar. Setiap penggunaan InterlockedXxx pada Xbox 360 tanpa hambatan memori harus diperiksa dengan sangat hati-hati, karena sering kali merupakan bug.

Sampel ini menunjukkan bagaimana satu utas dapat meneruskan tugas atau data lain ke utas lain menggunakan versi Acquire dan Release dari fungsi InterlockedXxxSList . Fungsi InterlockedXxxSList adalah keluarga fungsi untuk mempertahankan daftar yang ditautkan bersama tanpa kunci. Perhatikan bahwa varian Acquire dan Release dari fungsi-fungsi ini tidak tersedia di Windows, tetapi versi reguler dari fungsi-fungsi ini adalah penghalang memori penuh di Windows.

// Declarations for the Task class go here.

// Add a new task to the list using lockless programming.
void AddTask( DWORD ID, DWORD data )
{
    Task* newItem = new Task( ID, data );
    InterlockedPushEntrySListRelease( g_taskList, newItem );
}

// Remove a task from the list, using lockless programming.
// This will return NULL if there are no items in the list.
Task* GetTask()
{
    Task* result = (Task*)
        InterlockedPopEntrySListAcquire( g_taskList );
    return result;
}

Variabel volatil dan Penyortiran Ulang

Standar C++ mengatakan bahwa pembacaan variabel volatil tidak dapat di-cache, penulisan volatil tidak dapat ditunda, dan pembacaan dan penulisan volatil tidak dapat dipindahkan satu sama lain. Ini cukup untuk berkomunikasi dengan perangkat keras, yang merupakan tujuan kata kunci volatil di Standar C++.

Namun, jaminan standar tidak cukup untuk menggunakan volatile untuk pemrograman multi-threading. Standar C++ tidak menghentikan compiler untuk menyusun ulang pembacaan dan penulisan non-volatile relatif terhadap pembacaan dan penulisan volatile, dan tidak mengatakan apa pun tentang mencegah penyusunan ulang CPU.

Visual C++ 2005 lebih dari C++ standar dengan menentukan semantik yang mendukung multi-threading untuk akses variabel volatil. Dimulai dengan Visual C++ 2005, pembacaan dari variabel volatil didefinisikan untuk memiliki semantik akuisisi-baca, dan penulisan ke variabel volatil didefinisikan untuk memiliki semantik pelepasan-tulis. Ini berarti bahwa pengkompilasi tidak akan mengatur ulang pembacaan dan penulisan apa pun melewatinya, dan pada Windows akan memastikan bahwa CPU juga tidak melakukannya.

Penting untuk dipahami bahwa jaminan baru ini hanya berlaku untuk Visual C++ 2005 dan versi Visual C++di masa mendatang. Kompilator dari vendor lain umumnya akan menerapkan semantik yang berbeda, tanpa jaminan tambahan Visual C++ 2005. Selain itu, pada Xbox 360, pengkompilasi tidak menyisipkan instruksi apa pun untuk mencegah CPU menyusun ulang baca dan tulis.

Contoh Pipa Data Bebas Kunci

Pipa adalah konstruksi yang memungkinkan satu atau beberapa utas menulis data yang kemudian dibaca oleh utas lain. Versi pipa tanpa kunci dapat menjadi cara yang elegan dan efisien untuk meneruskan pekerjaan dari utas ke utas. DirectX SDK memasok LockFreePipe, sebuah pipa tanpa kunci dengan pembaca tunggal dan penulis tunggal yang tersedia di DXUTLockFreePipe.h. LockFreePipe yang sama tersedia di Xbox 360 SDK di AtgLockFreePipe.h.

LockFreePipe dapat digunakan ketika dua utas memiliki keterkaitan penghasil/pemakai. Utas produsen dapat menulis data ke pipa sehingga utas pemroses dapat memprosesnya di kemudian hari tanpa harus memblokir. Jika pipa terisi, penulisan gagal, dan utas produsen harus mencoba lagi nanti, tetapi ini hanya akan terjadi jika utas produsen berada di depan. Jika pipa kosong, pembacaan gagal, dan utas konsumen perlu mencoba lagi nanti, namun ini hanya terjadi jika tidak ada pekerjaan untuk utas konsumen. Jika kedua utas seimbang, dan pipa cukup besar, pipa memungkinkan kedua utas tersebut untuk meneruskan data dengan lancar tanpa penundaan atau hambatan.

Kinerja Xbox 360

Performa instruksi dan fungsi sinkronisasi pada Xbox 360 akan bervariasi tergantung pada kode lain apa yang berjalan. Mendapatkan kunci akan memakan waktu lebih lama jika saat ini kunci tersebut dimiliki oleh utas lain. InterlockedIncrement dan operasi bagian kritikal akan memakan waktu lebih lama jika utas lain menulis ke baris cache yang sama. Konten antrean toko juga dapat memengaruhi performa. Oleh karena itu, semua angka ini hanya perkiraan, dihasilkan dari tes yang sangat sederhana:

  • lwsync diukur sebagai mengambil 33-48 siklus.
  • InterlockedIncrement diukur sebagai mengambil 225-260 siklus.
  • Memperoleh atau merilis bagian penting diukur sebagai mengambil sekitar 345 siklus.
  • Memperoleh atau melepaskan mutex diukur memerlukan sekitar 2350 siklus.

Performa Windows

Performa instruksi dan fungsi sinkronisasi pada Windows sangat bervariasi tergantung pada jenis prosesor dan konfigurasi, dan pada kode lain apa yang berjalan. Sistem multi-core dan multi-soket sering membutuhkan waktu lebih lama untuk menjalankan instruksi sinkronisasi, dan memperoleh kunci membutuhkan waktu lebih lama jika utas lain saat ini memiliki kunci.

Namun, bahkan beberapa pengukuran yang dihasilkan dari pengujian yang sangat sederhana sangat membantu:

  • MemoryBarrier diukur membutuhkan 20-90 siklus.
  • InterlockedIncrement diukur membutuhkan 36-90 siklus.
  • Memperoleh atau merilis bagian penting diukur memakan waktu 40-100 siklus.
  • Memperoleh atau melepaskan mutex diukur memakan waktu sekitar 750-2500 siklus.

Pengujian ini dilakukan pada Windows XP pada berbagai prosesor yang berbeda. Waktu singkat berada pada mesin prosesor tunggal, dan waktu yang lebih lama berada di mesin multi-prosesor.

Meskipun memperoleh dan melepaskan kunci lebih mahal daripada menggunakan pemrograman tanpa kunci, lebih baik berbagi data lebih jarang, sehingga menghindari biaya sama sekali.

Pemikiran Kinerja

Memperoleh atau melepaskan bagian penting terdiri dari penghalang memori, operasi InterlockedXxx , dan beberapa pemeriksaan tambahan untuk menangani rekursi dan untuk kembali ke mutex, jika perlu. Anda harus waspada terhadap penerapan bagian krusial Anda sendiri, karena berputar dalam lingkaran menunggu kunci tersedia, tanpa menggunakan kembali mutex, dapat mengurangi performa secara signifikan. Untuk bagian penting yang sangat diperebutkan tetapi tidak dikuasai untuk waktu yang lama, Anda harus mempertimbangkan untuk menggunakan InitializeCriticalSectionAndSpinCount sehingga sistem operasi akan berputar untuk sementara waktu menunggu bagian penting tersedia daripada segera beralih ke mutex jika bagian penting tersebut sedang dimiliki saat Anda mencoba mengaksesnya. Untuk mengidentifikasi bagian penting yang dapat memperoleh manfaat dari penghitung putaran, perlu untuk mengukur lama waktu tunggu rata-rata untuk kunci tertentu.

Jika tumpukan bersama digunakan untuk alokasi memori—perilaku default—setiap alokasi memori dan bebas melibatkan memperoleh kunci. Ketika jumlah utas dan jumlah alokasi meningkat, tingkat performa menjadi datar, dan akhirnya mulai berkurang. Menggunakan tumpukan per utas, atau mengurangi jumlah alokasi, dapat menghindari hambatan penguncian ini.

Jika satu utas menghasilkan data dan utas lain mengkonsumsi data, alur tersebut mungkin sering berbagi data. Ini dapat terjadi jika satu utas memuat sumber daya dan utas lain merender adegan. Jika utas rendering mereferensikan data bersama pada setiap panggilan gambar, overhead penguncian akan tinggi. Performa yang jauh lebih baik dapat dicapai jika setiap utas memiliki struktur data privat yang kemudian disinkronkan sekali setiap frame atau lebih jarang.

Algoritma tanpa kunci tidak dijamin lebih cepat daripada algoritma yang menggunakan kunci. Anda harus memeriksa apakah kunci benar-benar menyebabkan masalah sebelum mencoba menghindarinya, dan Anda harus mengukur untuk melihat apakah kode tanpa kunci Anda benar-benar meningkatkan performa.

Ringkasan Perbedaan Platform

  • Fungsi InterlockedXxx mencegah pengurutan ulang baca/tulis CPU pada Windows, tetapi tidak pada Xbox 360.
  • Membaca dan menulis variabel volatil menggunakan Visual Studio C++ 2005 mencegah penyusunan ulang baca/tulis CPU pada Windows, tetapi pada Xbox 360, itu hanya mencegah penyusunan ulang baca/tulis kompiler.
  • Penulisan diurutkan ulang pada Xbox 360, tetapi tidak pada x86 atau x64.
  • Pembacaan diatur ulang pada Xbox 360, tetapi pada x86 atau x64, pembacaan hanya diatur ulang sehubungan dengan penulisan, dan hanya jika pembacaan dan penulisan menargetkan lokasi yang berbeda.

Rekomendasi

  • Gunakan kunci jika memungkinkan karena lebih mudah digunakan dengan benar.
  • Hindari penguncian terlalu sering, sehingga biaya penguncian tidak menjadi signifikan.
  • Hindari memegang pengunci terlalu lama, untuk menghindari penundaan yang lama.
  • Gunakan pemrograman tanpa kunci jika sesuai, tetapi pastikan bahwa keuntungan membenarkan kompleksitas.
  • Gunakan pemrograman tanpa kunci atau kunci putar dalam situasi di mana kunci lain dilarang, seperti saat berbagi data antara panggilan prosedur yang ditangguhkan dan kode normal.
  • Hanya gunakan algoritma pemrograman tanpa kunci standar yang telah terbukti benar.
  • Saat melakukan pemrograman tanpa kunci, pastikan untuk menggunakan variabel bendera volatil dan instruksi penghalang memori sesuai kebutuhan.
  • Saat menggunakan InterlockedXxx pada Xbox 360, gunakan Akuisisi dan Rilis .

Referensi