Apakah alokasi memori di linux tidak memblokir?

menurut saya jika aplikasi interferensi Anda menggunakan baru/hapus (malloc/gratis), maka aplikasi interferensi akan lebih mengganggu pengujian non daur ulang. Tapi saya tidak tahu bagaimana tes interferensi Anda diterapkan.

Bergantung pada bagaimana Anda mendaur ulang (yaitu jika Anda menggunakan pthread mutex, amit-amit) kode daur ulang Anda bisa lambat (operasi atom gcc akan 40x lebih cepat dalam mengimplementasikan daur ulang).

Malloc, dalam beberapa variasi untuk waktu yang lama setidaknya pada beberapa platform, telah mengetahui utas. Gunakan sakelar kompiler di gcc untuk memastikan Anda mendapatkannya. Algoritme yang lebih baru mempertahankan kumpulan potongan memori kecil untuk masing-masing utas, jadi tidak ada atau sedikit pemblokiran jika utas Anda memiliki item kecil yang tersedia. Saya telah terlalu menyederhanakan ini dan itu tergantung pada malloc apa yang digunakan sistem Anda. Plus, jika Anda pergi dan mengalokasikan jutaan item untuk melakukan tes .... maka Anda tidak akan melihat efek itu, karena kumpulan item kecil ukurannya terbatas. Atau mungkin Anda akan melakukannya. Aku tidak tahu. Jika Anda membebaskan item tepat setelah mengalokasikan, kemungkinan besar Anda akan melihatnya. Item kecil yang dibebaskan kembali ke daftar item kecil daripada tumpukan bersama. Meskipun "apa yang terjadi ketika utas B membebaskan item yang dialokasikan oleh utas A" adalah masalah yang mungkin atau mungkin tidak ditangani pada versi malloc Anda dan mungkin tidak ditangani dengan cara non-pemblokiran. Yang pasti, jika Anda tidak segera membebaskan selama pengujian besar, maka utas harus mengisi ulang daftar item kecilnya berkali-kali. Itu dapat memblokir jika lebih dari satu utas mencoba. Terakhir, pada titik tertentu, heap proses Anda akan meminta memori heap pada sistem, yang jelas dapat diblokir.

Jadi, apakah Anda menggunakan item memori kecil? Untuk malloc Anda, saya tidak tahu apa itu kecil, tetapi jika Anda <1k itu pasti kecil. Apakah Anda mengalokasikan dan membebaskan satu per satu, atau mengalokasikan ribuan node dan kemudian membebaskan ribuan node? Apakah aplikasi interferensi Anda mengalokasikan? Semua hal ini akan mempengaruhi hasil.

Cara mendaur ulang dengan operasi atom (CAS =bandingkan dan tukar):

Pertama tambahkan pNextFreeNode ke objek node Anda. Saya menggunakan void*, Anda dapat menggunakan tipe Anda. Kode ini untuk pointer 32 bit, tetapi juga berfungsi untuk 64 bit. Kemudian buat tumpukan daur ulang global.

void *_pRecycleHead; // global head of recycle list. 

Tambahkan ke tumpukan daur ulang:

void *Old;
while (1) { // concurrency loop
  Old = _pRecycleHead;  // copy the state of the world. We operate on the copy
  pFreedNode->pNextFreeNode = Old; // chain the new node to the current head of recycled items
  if (CAS(&_pRecycleHead, Old, pFreedNode))  // switch head of recycled items to new node
    break; // success
}

hapus dari tumpukan:

void *Old;
while (Old = _pRecycleHead) { // concurrency loop, only look for recycled items if the head aint null
  if (CAS(&_pRecycleHead, Old, Old->pNextFreeNode))  // switch head to head->next.
    break; // success
}
pNodeYoucanUseNow = Old;

Menggunakan CAS berarti operasi akan berhasil hanya jika item yang Anda ubah adalah nilai Lama yang Anda berikan. Jika ada perlombaan dan utas lain sampai di sana lebih dulu, maka nilai lama akan berbeda. Dalam kehidupan nyata perlombaan ini sangat jarang terjadi. CAS hanya sedikit lebih lambat daripada benar-benar menetapkan nilai dibandingkan dengan mutex .... itu keren.

Hapus dari tumpukan, di atas, memiliki kondisi balapan jika Anda menambah dan menghapus item yang sama dengan cepat. Kami mengatasinya dengan menambahkan versi # ke data yang dapat CAS. Jika Anda melakukan versi # bersamaan dengan penunjuk ke kepala tumpukan daur ulang, Anda menang. Gunakan serikat pekerja. Tidak ada biaya tambahan untuk CAS 64 bit.

union TRecycle {
  struct {
    int iVersion;
    void *pRecycleHead;
  } ;  // we can set these.  Note, i didn't name this struct.  You may have to if you want ANSI
  unsigned long long n64;  // we cas this
}

Catatan, Anda harus membuka struct 128 bit untuk OS 64 bit. jadi tumpukan daur ulang global terlihat seperti ini sekarang:

TRecycle _RecycleHead;

Tambahkan ke tumpukan daur ulang:

while (1) { // concurrency loop
  TRecycle New,Old;
  Old.n64 = _RecycleHead.n64;  // copy state
  New.n64 = Old.n64;  // new state starts as a copy
  pFreedNode->pNextFreeNode = Old.pRecycleHead;  // link item to be recycled into recycle pile
  New.pRecycleHead = pFreedNode;  // make the new state
  New.iVersion++;  // adding item to list increments the version.
  if (CAS(&_RecycleHead.n64, Old.n64, New.n64))  // now if version changed...we fail
    break; // success
}

hapus dari tumpukan:

while (1) { // concurrency loop
  TRecycle New,Old;
  Old.n64 = _RecycleHead.n64;  // copy state
  New.n64 = Old.n64;  // new state starts as a copy
  New.pRecycleHead = New.pRecycledHead.pNextFreeNode;  // new will skip over first item in recycle list so we can have that item.
  New.iVersion++;  // taking an item off the list increments the version.
  if (CAS(&_RecycleHead.n64, Old.n64, New.n64))  // we fail if version is different.
    break; // success
}
pNodeYouCanUseNow = Old.pRecycledHead;

Saya yakin jika Anda mendaur ulang dengan cara ini, Anda akan melihat peningkatan kinerja.

Pertanyaan ini memiliki sejumlah tanggapan yang bagus:Dalam C/C++ multithreaded, apakah malloc/new mengunci heap saat mengalokasikan memori.

Konsensus ada bahwa ada penguncian. Jadi alokasi yang besar atau yang membutuhkan beberapa pertukaran dapat memblokir alokasi yang lebih kecil di utas lain, bahkan jika yang lebih kecil dapat selesai jika bukan karena alokasi yang lebih besar sedang berlangsung.

gcc baru adalah thread-safe, jika Anda mengkompilasi dengan dukungan pthreads, tapi bukan itu yang Anda tanyakan.

Saya tahu di windows Anda dapat membuat tumpukan Anda sendiri, yang dapat digunakan untuk mengatur memori di awal program Anda. Saya tidak mengetahui adanya panggilan linux/unix untuk melakukan hal serupa.

Ini sangat mirip dengan pertanyaan ini.

Pada dasarnya, malloc tidak didefinisikan aman untuk thread, tetapi pelaksana bebas menambahkan implementasi untuk membuatnya aman untuk thread. Dari uraian Anda, sepertinya versi khusus Anda.

Yang pasti, dalam kata-kata Obi-Wan, "Gunakan Sumbernya, Luke." malloc sumber akan ada dan umumnya cukup mudah dibaca.

@Mark, Anda bisa mendapatkan sumber libc GNU standar dengan

$ git clone git://sourceware.org/git/glibc.git
$ cd glibc
$ git checkout --track -b glibc-2_11-branch origin/release/2.11/master

Lihat juga di sini. Ingat bahwa malloc ada di manual bagian 3 -- ini adalah fungsi pustaka, jadi tidak akan ada di sumber kernel Anda. Namun, Anda mungkin perlu membaca brk ,sbrk , getrlimit dan setrlimit dan sejenisnya untuk mengetahui apa yang dilakukan kernel.

Satu tautan lagi:proyek GCC.

Oke, satu lagi (saya bisa berhenti kapan saja):inilah halaman tempat Anda dapat mengunduh sumbernya. Buka file tersebut dan Anda akan menemukannya di ./malloc/malloc.c .

Dalam sistem multithreaded, malloc() dan free() (dan new / delete ) biasanya menggunakan primitif sinkronisasi agar aman untuk dipanggil dari beberapa utas.

Sinkronisasi ini juga memengaruhi kinerja beberapa aplikasi, khususnya aplikasi yang melakukan banyak alokasi dan dealokasi di lingkungan yang sangat paralel. Pengalokasi memori multithread yang lebih efisien merupakan bidang penelitian yang aktif - lihat jemalloc dan tcmalloc untuk dua yang terkenal.