KAL
Menu

Multicore dan Model Memori

Arti sebenarnya dari memori bersama: visibilitas penulisan antarinti, cache koheren, dan sinkronisasi.

Daftar isi

Satu chip multicore memuat beberapa inti prosesor lengkap yang berbagi satu memori utama, sehingga istilah memori bersama terdengar seperti satu gudang tunggal yang dibaca bersama-sama. Kenyataannya setiap inti membawa cache pribadi, sehingga satu variabel dapat tersalin ke beberapa tempat sekaligus dan nilainya dapat berbeda antarsalinan. Topik ini membahas arti sesungguhnya dari memori bersama, yaitu masalah koherensi, cara protokol MESI menjaga kesatuan salinan, kapan penulisan satu inti terlihat oleh inti lain menurut model memori, dan alasan data bersama menuntut sinkronisasi. Setelah membacanya, keluaran program berserat yang tak terduga dapat diterjemahkan menjadi kejadian pada cache dan protokol koherensi.

Cache pribadi pada setiap inti#

Setiap inti pada prosesor multicore memiliki cache sendiri, biasanya L1 dan L2 yang bersifat pribadi, sedangkan cache L3 pada umumnya dibagi bersama. Cache yang pribadi bekerja dengan kebijakan write-back, yaitu hasil penulisan menetap di cache terlebih dahulu dan memori utama diperbarui belakangan. Akibatnya, satu variabel yang ditulis inti 0 berada pada tiga tempat sekaligus, yaitu cache inti 0, memori utama, dan bila inti 1 pernah membacanya, cache inti 1. Ketiganya dapat memuat nilai yang berbeda pada saat yang sama.

Modul Hierarki Memori membahas cache sebagai penangkal latensi memori utama, dan pada sistem satu inti salinan ganda itu tidak pernah menjadi masalah karena hanya ada satu pembaca. Pada sistem multicore, pertanyaan baru muncul dengan sendirinya, yaitu salinan mana yang terbaru dan apa yang dilihat inti lain ketika membaca variabel yang sama. Jawaban atas pertanyaan itu menentukan seluruh perilaku program berserat, dan perangkat keras menjawabnya melalui protokol koherensi yang diperkenalkan pada bagian berikutnya.

Koherensi cache dan protokol MESI#

Koherensi cache (cache coherence) adalah kesepakatan perangkat keras agar seluruh inti melihat urutan penulisan yang sama atas satu alamat, sehingga tidak ada inti yang membaca salinan lama dari cache miliknya. Protokol yang paling umum bertumpu pada empat keadaan per line yang membentuk singkatan MESI. Keempat keadaan itu adalah sebagai berikut.

  • Modified, yaitu satu-satunya salinan yang sah, dan isinya berbeda dari memori utama.
  • Exclusive, yaitu satu-satunya salinan yang sah, dan isinya sama dengan memori utama.
  • Shared, yaitu satu dari beberapa salinan yang semuanya sama dengan memori utama.
  • Invalid, yaitu salinan yang sudah usang dan tidak boleh dipakai.

Perangkat keras memelihara keempat keadaan itu melalui bus. Setiap inti mengintip (snoop) lalu lintas cache inti lain dan menanggapi dengan menulis balik salinannya atau menyatakannya Invalid. Perpindahan keadaan terjadi otomatis pada setiap baca dan tulis, sehingga salinan lama tidak pernah sampai dipakai oleh instruksi. Seluruh mekanisme ini bekerja di balik instruksi biasa, tanpa satu instruksi khusus pun yang perlu dipanggil oleh program.

Model memori dan visibilitas penulisan#

Model memori (memory model) adalah kontrak antara perangkat keras dan perangkat lunak yang menyatakan visibilitas (visibility) setiap penulisan, yaitu kapan efeknya dijamin terlihat oleh pembacaan pada inti lain. Tanpa sinkronisasi, yang terjamin hanyalah urutan program pada satu inti, sedangkan urutan kemunculannya antarinti tidak dijamin. Perangkat keras boleh menyusun ulang akses memori, dan compiler boleh menyimpan nilai dalam register, selama hasil eksekusi pada satu inti tetap sesuai urutan programnya.

Contoh konkret memperlihatkan bahayanya. Inti A menulis data = 42 terlebih dahulu, lalu menulis bendera = 1 sebagai tanda bahwa data siap. Inti B membaca bendera dan mendapati 1, tetapi pembacaan data sesudahnya dapat kembali memuat nilai lama, karena urutan visibilitas kedua penulisan tadi tidak dijamin tanpa aturan tambahan. Pola seperti ini sering tertulis tanpa disadari ketika program berserat mulai berbagi data.

Setiap ISA modern menetapkan model memorinya secara tertulis, misalnya RVWMO (RISC-V Weak Memory Ordering) yang tercantum dalam manual ISA RISC-V. Satu hal yang konsisten di seluruh model, yaitu akses yang dilindungi sinkronisasi menikmati jaminan yang lebih kuat, dan koherensi memastikan inti yang mendapat giliran membaca memperoleh nilai terakhir yang ditulis.

Sinkronisasi lock dan operasi atomik#

Sinkronisasi adalah bagian dari kontrak yang wajib dipenuhi program, dan dua alat utamanya adalah lock serta operasi atomik. Lock menyediakan bagian kritis (critical section), yaitu rangkaian pernyataan yang hanya boleh dijalankan satu thread pada satu waktu. Operasi atomik (atomic) adalah operasi yang dikerjakan sebagai satu langkah yang tidak dapat terbagi, misalnya penambahan satu pada penghitung. Keduanya dibangun di atas instruksi prosesor khusus dan disediakan melalui library standar setiap bahasa.

Kaidahnya sederhana, yaitu setiap data bersama yang dibaca dan ditulis oleh lebih dari satu thread menuntut sinkronisasi. Biaya sinkronisasi nyata, sehingga alatnya tidak dipakai untuk setiap akses. Data yang hanya dibaca oleh banyak inti tidak memerlukan lock sama sekali, karena tidak ada penulisan yang perlu diurutkan, sedangkan data yang hanya disentuh satu thread juga bebas. Data bersama yang sering diperbarui biasanya dibungkus dengan struktur yang meminimalkan persaingan antarthread.

Tanpa sinkronisasi yang disiplin, penjadwal (scheduler) sistem operasi dapat memindahkan eksekusi antarthread kapan saja, sehingga urutan operasi yang teramati berbeda dari satu peluncuran ke peluncuran lainnya. Mekanisme pembuatan thread, lock, dan bahaya deadlock dibahas lebih lanjut pada jalur sistem operasi.

Simulasi MESI untuk satu variabel bersama#

Skrip berikut memainkan enam langkah akses dua inti atas satu variabel x, lengkap dengan cache per inti, memori utama, dan protokol MESI yang disediakan dalam kode. Kedua inti dieksekusi secara bergiliran dengan urutan tetap agar keluarannya deterministik. Perlu ditegaskan bahwa program berserat nyata tidak menjamin urutan seperti itu, karena penjadwal sistem operasi dapat menggantikan urutan eksekusi kedua thread kapan saja. Urutan tetap di sini adalah alat bantu pembelajaran, bukan gambaran urutan eksekusi yang dapat diandalkan.

python koherensi.py 
# Simulasi koherensi cache dua inti dengan protokol MESI.
# Kedua inti beroperasi secara bergiliran dengan urutan tetap,
# bukan sebagai thread nyata, sehingga keluarannya selalu sama.

NAMA_KEADAAN = {"M": "Modified", "E": "Exclusive", "S": "Shared", "I": "Invalid"}

memori = {"x": 10}          # memori utama yang bersama
cache = {0: {}, 1: {}}      # cache per inti: alamat -> [keadaan, nilai]

def snoop_baca(inti, alamat):
    """Bus mencari salinan terbaru satu alamat untuk inti yang membaca."""
    inti_lain = 1 - inti
    if alamat not in cache[inti_lain]:
        return memori[alamat]
    keadaan, nilai = cache[inti_lain][alamat]
    if keadaan == "M":
        memori[alamat] = nilai              # salinan Modified ditulis balik
    if keadaan in ("M", "E"):
        cache[inti_lain][alamat][0] = "S"   # inti lain turun ke Shared
    return nilai

def baca(inti, alamat):
    """Inti membaca satu alamat, cache miss digantikan melalui bus."""
    keadaan = cache[inti].get(alamat, ["I"])[0]
    if keadaan in ("M", "E", "S"):
        return                              # cache hit, tidak ada perubahan
    nilai = snoop_baca(inti, alamat)
    if cache[1 - inti].get(alamat, ["I"])[0] == "S":
        cache[inti][alamat] = ["S", nilai]  # berbagi dengan inti lain
    else:
        cache[inti][alamat] = ["E", nilai]  # satu-satunya salinan

def tulis(inti, alamat, nilai):
    """Inti menulis, salinan pada cache inti lain dinyatakan Invalid."""
    inti_lain = 1 - inti
    if alamat in cache[inti_lain]:
        keadaan, nilai_lama = cache[inti_lain][alamat]
        if keadaan == "M":
            memori[alamat] = nilai_lama     # ditulis balik terlebih dahulu
        cache[inti_lain][alamat][0] = "I"   # salinan lama tidak sah
    cache[inti][alamat] = ["M", nilai]

def tampilkan(langkah, keterangan):
    print(f"langkah {langkah}: {keterangan}")
    for inti in (0, 1):
        entri = cache[inti].get("x")
        if entri is None:
            print(f"  cache inti {inti}: tidak memuat x")
        else:
            keadaan, nilai = entri
            print(f"  cache inti {inti}: x = {nilai}  [{NAMA_KEADAAN[keadaan]}]")
    print(f"  memori: x = {memori['x']}")

baca(0, "x")
tampilkan(1, "inti 0 membaca x")
baca(1, "x")
tampilkan(2, "inti 1 membaca x")
tulis(0, "x", 11)
tampilkan(3, "inti 0 menulis 11 ke x")
baca(1, "x")
tampilkan(4, "inti 1 membaca x")
tulis(1, "x", 12)
tampilkan(5, "inti 1 menulis 12 ke x")
baca(0, "x")
tampilkan(6, "inti 0 membaca x")
text Keluaran 
langkah 1: inti 0 membaca x
  cache inti 0: x = 10  [Exclusive]
  cache inti 1: tidak memuat x
  memori: x = 10
langkah 2: inti 1 membaca x
  cache inti 0: x = 10  [Shared]
  cache inti 1: x = 10  [Shared]
  memori: x = 10
langkah 3: inti 0 menulis 11 ke x
  cache inti 0: x = 11  [Modified]
  cache inti 1: x = 10  [Invalid]
  memori: x = 10
langkah 4: inti 1 membaca x
  cache inti 0: x = 11  [Shared]
  cache inti 1: x = 11  [Shared]
  memori: x = 11
langkah 5: inti 1 menulis 12 ke x
  cache inti 0: x = 11  [Invalid]
  cache inti 1: x = 12  [Modified]
  memori: x = 11
langkah 6: inti 0 membaca x
  cache inti 0: x = 12  [Shared]
  cache inti 1: x = 12  [Shared]
  memori: x = 12

Langkah 1 menunjukkan inti 0 memuat x ke dalam cache dalam keadaan Exclusive, yaitu satu-satunya salinan yang isinya sama dengan memori utama. Langkah 2 menurunkan salinan inti 0 ke Shared karena inti 1 ikut membaca. Langkah 3 adalah langkah kuncinya, yaitu inti 0 menulis 11, salinan inti 1 dinyatakan Invalid, dan memori utama masih memuat 10. Pada langkah itulah tiga tempat penyimpanan x memuat dua nilai yang berbeda sekaligus, dan keadaan Invalid menahan inti 1 agar tidak memakai salinan lamanya.

Langkah 4 memperlihatkan tulis balik, yaitu salinan Modified pada inti 0 dituliskan ke memori utama ketika inti 1 meminta alamat yang sama, sehingga memori ikut berubah menjadi 11. Langkah 5 dan 6 mengulangi pola yang sama dengan peran yang ditukar, dan seluruh salinan kembali sepakat pada nilai 12. Protokol bekerja tanpa perintah apa pun dari program, persis seperti yang dijanjikan bagian koherensi.

Kesalahan umum#

Tiga kekeliruan berikut paling sering muncul ketika memori bersama baru dipelajari.

  1. Menganggap koherensi menggantikan sinkronisasi. Koherensi menjaga kesatuan salinan, bukan atomisitas operasi, sehingga dua baca-ubah-tulis yang berjalan serentak tetap dapat saling menyisip meskipun salinannya selalu mutakhir. Perbaikannya adalah melindungi data bersama dengan lock atau operasi atomik.
  2. Mengira setiap penulisan langsung sampai memori utama. Kebijakan write-back menahan nilai di cache sampai bus membutuhkannya, sehingga isi memori utama boleh berbeda dari salinan Modified. Alat inspeksi memori pun dapat menampilkan isi yang lebih tua daripada yang sedang dipakai inti, dan keanehan itu bukan tanda error. Perbaikannya adalah tidak menyimpulkan isi memori utama dari sisi program, melainkan membaca nilai melalui sinkronisasi.
  3. Berharap variabel bersama berubah tanpa aturan sinkronisasi. Compiler boleh menyimpan nilai dalam register, sehingga perulangan yang membaca ulang variabel bersama tidak pernah melihat perubahan dari thread lain. Perbaikannya adalah membaca dan menulis data lintas thread melalui lock atau operasi atomik.

Ringkasan#

  • Setiap inti membawa cache pribadi, sehingga satu variabel dapat memiliki beberapa salinan yang nilainya berbeda.
  • Protokol MESI menjaga koherensi melalui empat keadaan per line, yaitu Modified, Exclusive, Shared, dan Invalid.
  • Model memori menyatakan kapan penulisan satu inti dijamin terlihat oleh inti lain, dan urutannya tidak dijamin tanpa sinkronisasi.
  • Lock dan operasi atomik menyediakan sinkronisasi, sedangkan data bersama tanpa sinkronisasi menghasilkan keluaran yang tidak dapat diprediksi.

Referensi#