Penggantian Antrian dalam RTOS

12

Untuk komunikasi Antar-tugas atau untuk berbagi data antara dua tugas RTOS, Kami menggunakan Antrian. Tetapi Masalah dengan Antrian adalah bahwa mereka lambat .... Mereka menyalin data dalam Buffer kemudian Penanganan Mutex dan kemudian Transfer Data. Sangat menjengkelkan lambat jika Anda harus mentransfer data besar. Masalah lain adalah jika antrian yang sama diakses oleh Banyak tugas. Kemudian Gambar menjadi seperti ini: - Pertama Tunggu untuk mendapatkan akses ke Antrian lalu Antrian Penanganan Mutex internal kemudian Transfer Data.

Ini meningkatkan overhead pada sistem. Apa yang bisa menjadi pengganti Antrian yang Efisien ?

(Saya kira pertanyaan ini Independen dari RTOS yang kami gunakan. Sebagian besar RTOS menangani Antrian dengan cara ini saja)

Swanand
sumber
Apa yang Anda maksud dengan antrian yang diakses oleh banyak tugas? Apakah maksud Anda memposting ke antrian atau membaca dari antrian? Beberapa tugas harus dapat dikirim ke antrian dengan overhead yang minimal. RTOS harus menangani mutexing sehingga pos adalah operasi atom. Untuk 99% tugas, Anda harus memiliki perulangan yang menunggu antrian dan memproses pesan. Antrian harus (biasanya) hanya dibaca oleh satu tugas. Anda mungkin perlu melihat desain Anda dan bagaimana Anda menggunakan antrian alih-alih menggantinya.
Erik
@Erik: Maaf! Saya menggunakan mekanisme yang Anda sebutkan .... Saya ingin mengatakan sesuatu yang lain dan saya menulis yang berbeda .... Saya akan mengeditnya !! Terima kasih telah menunjukkan kesalahannya! Saya menunggu akses antrian dalam kode saya!
Swanand

Jawaban:

7

Antrian beroperasi seperti itu karena itu adalah model transaksi yang aman untuk komunikasi antar-tugas. Anda berisiko mengalami korupsi data dan / atau masalah kepemilikan dalam skema yang tidak terlalu ketat.

Apakah Anda menyalin data ke buffer di memori kemudian meneruskan pointer dengan elemen antrian, atau mencoba meneruskan semua data dalam elemen antrian sendiri? Jika Anda tidak melewati pointer maka Anda akan mendapatkan peningkatan kinerja melakukan itu daripada melewati satu byte pada suatu waktu melalui elemen antrian.

AngryEE
sumber
2
Saya akan mengatakan hal yang sama. Jika Anda hanya meneruskan pointer ke data dalam antrian, Anda dapat meningkatkan kecepatan, tetapi pastikan Anda tidak berakhir dengan dua utas yang mencoba menggunakan dan mengubah data.
Kortuk
Seperti kata @Kortuk, saya perlu "pastikan Anda tidak berakhir dengan dua utas yang mencoba menggunakan dan mengubah data" ... Yang berarti peningkatan dalam overhead ... Saya tidak ingin banyak pemrosesan! :(
Swanand
Jadi Tidak Ada pengganti Antrian seperti itu ... Alih-alih Antrian Data, saya perlu menggunakan Antrian Pointer!
Swanand
1
@Sandailah jika rencanakan aplikasi Anda sedemikian rupa sehingga antrian hanya searah (mis., Anda tidak pernah membaca antrian yang sama dalam dua tugas) dan Anda memproses data yang disimpan di penunjuk segera kemudian membebaskannya, Anda seharusnya tidak memiliki masalah dengan berbagi data. Akan ada peningkatan overhead karena Anda mungkin harus membuat beberapa antrian untuk meneruskan data secara andal tetapi ini adalah biaya untuk melakukan bisnis di lingkungan multi-tasking.
AngryEE
7

Salah satu cara mudah adalah dengan meletakkan pointer ke data pada antrian dan mengkonsumsi data menggunakan pointer.

Perhatikan bahwa Anda memperdagangkan keamanan untuk kinerja dengan cara ini karena Anda harus memastikan bahwa:

  1. buffer tetap valid sampai konsumen mengkonsumsi data
  2. seseorang mendelokasi buffer

Jika Anda tidak menggunakan memori yang dialokasikan secara dinamis, Anda tidak harus membatalkan alokasi, tetapi Anda masih harus memastikan bahwa area memori tidak digunakan kembali sebelum data dikonsumsi.

Coba Laugstøl
sumber
6

Antrian bebas-kunci dapat diterapkan untuk kasus produsen tunggal / konsumen tunggal, dan seringkali Anda dapat merancang perangkat lunak Anda untuk meminimalkan jumlah antrian banyak produsen atau banyak konsumen.

Antrian bebas-penguncian dapat dibuat seperti ini: Mengalokasikan array elemen yang akan dikomunikasikan, dan juga dua bilangan bulat, menyebutnya Head and Tail. Head adalah indeks ke dalam array, di mana item berikutnya akan ditambahkan. Ekor adalah indeks ke dalam array, di mana item berikutnya tersedia untuk dihapus. Tugas produsen membaca H dan T untuk menentukan apakah ada ruang untuk menambahkan item; menulis item pada indeks H, kemudian memperbarui H. Tugas konsumen membaca H dan T untuk menentukan apakah ada data yang tersedia, membaca data dari indeks T, lalu memperbarui T. Pada dasarnya itu adalah buffer cincin yang diakses oleh dua tugas, dan urutan operasi (masukkan, lalu perbarui H; hapus, lalu perbarui T) memastikan bahwa korupsi data tidak terjadi.

Jika Anda memiliki situasi dengan beberapa produsen dan satu konsumen, atau satu produsen dan beberapa konsumen, Anda secara efektif memiliki keterbatasan sumber daya, dan tidak ada yang lain selain menggunakan sinkronisasi, karena pembatas kinerja lebih mungkin untuk jadilah produsen / konsumen tunggal daripada overhead OS dengan mekanisme penguncian.

Tetapi jika Anda memiliki banyak produsen DAN konsumen, ada baiknya menghabiskan waktu (dalam desain-ruang) untuk melihat apakah Anda tidak bisa mendapatkan mekanisme komunikasi yang lebih terkoordinasi; dalam kasus seperti ini, membuat serialisasi segala sesuatu melalui satu antrian pasti menjadikan efisiensi antrian sebagai penentu utama kinerja.

JustJeff
sumber
1
Saya akan memberi ini +1, tetapi Anda salah: antrean bebas kunci mungkin diterapkan untuk banyak pembaca dan penulis, mereka hanya lebih rumit. (lihat makalah Michael + Scott tentang Antrian Tanpa Kunci google.com/search?q=michael%20scott%20queue )
Jason S
1
@Jason S - apakah kertas Scott secara khusus mengklaim re-entrancy untuk memasukkan dan menghapus operasi bebas-kunci? Jika demikian, jika Anda dapat mengekstraknya dan mempostingnya, silakan lakukan, itu akan menjadi aset yang sangat berharga bagi banyak orang. Pembaca harus mencatat bahwa kertas yang dikutip menggunakan instruksi mesin khusus, sedangkan posisi saya di posting di atas tidak mengasumsikan instruksi tersebut.
JustJeff
1
Ya, biaya dari algoritma bebas kunci biasanya bergantung pada CAS atau instruksi yang setara. Tapi bagaimana re-entrancy berperan di sini? Masuk akal untuk mutex + struktur penguncian, tetapi tidak untuk operasi struktur data.
Jason S
2

Seseorang bisa mendapatkan operasi yang efisien dalam antrian konsumen tunggal multi-produsen bebas-kunci jika antrian itu sendiri menyimpan barang-barang yang cukup kecil untuk bekerja dengan beban-toko-eksklusif, perbandingan-pertukaran, atau primitif serupa, dan satu dapat menggunakan nilai yang dipesan atau nilai yang dipesan untuk slot antrian kosong. Saat menulis ke antrian, penulis melakukan pertukaran-perbandingan untuk mencoba menyimpan datanya ke slot kosong berikutnya; jika gagal, penulis mencoba slot berikut. Meskipun antrian mempertahankan pointer ke slot kosong berikutnya, nilai pointer adalah "advisory". Perhatikan bahwa jika suatu sistem menggunakan pertukaran-pertukaran dan bukan-toko-eksklusif, mungkin perlu memiliki 'keluarga' dengan nilai 'slot kosong' yang berbeda. Kalau tidak, jika antara waktu penulis menemukan slot antrian kosong dan mencoba untuk menulis kepadanya, penulis lain menulis slot dan pembaca membacanya, penulis pertama tanpa sadar akan meletakkan datanya di tempat di mana pembaca tidak akan melihatnya. Masalah ini tidak terjadi dalam sistem yang menggunakan load-store-eksklusif, karena toko-eksklusif akan mendeteksi bahwa data telah ditulis meskipun itu ditulis kembali ke nilai lama.

supercat
sumber
1

Anda dapat mengakses antrian dengan lebih efisien dengan menulis di atas antrian. Biasanya sebagian besar RTOS memang memberikan dukungan untuk menambahkan ke depan antrian yang tidak memerlukan perolehan mutex. Tetapi pastikan Anda menggunakan menambahkan ke depan antrian seminimal mungkin di mana Anda hanya ingin mengeksekusi data lebih cepat. Biasanya struktur antrian memiliki batas ukuran maksimal sehingga Anda tidak boleh memasukkan semua data ke dalam antrian, sehingga melewati penunjuk selalu mudah.

Bersulang!!

Sai
sumber
1

Antrian pada dasarnya tidak lambat. The pelaksanaan dari mereka mungkin.

Jika Anda menyalin data secara membabi buta dan menggunakan antrian yang sinkron, Anda akan melihat peningkatan kinerja.

Seperti yang ditunjukkan poster lainnya, ada alternatif bebas kunci. Kasus produsen tunggal / konsumen tunggal sangat mudah; untuk banyak produsen dan konsumen, algoritma antrian kunci-bebas oleh Michael dan Scott (itu adalah nama belakang mereka) adalah standar, dan digunakan sebagai dasar untuk Java ConcurrentLinkedQueue Java .

Mungkin untuk mengoptimalkan kebutuhan antrian dalam kasus-kasus tertentu, tetapi mereka memberikan jaminan konkurensi yang biasanya memberikan manfaat penyederhanaan yang sangat besar pada sistem dengan memungkinkan Anda untuk memisahkan tugas.

Jason S
sumber
Dari makalah Michael & Scott: "itu adalah algoritme pilihan yang jelas untuk mesin yang menyediakan primitif atom universal (misalnya membandingkan dan menukar atau memuat tautan / penyimpanan bersyarat)". Meskipun ini mungkin tidak benar-benar mengunci utas, ada bentuk sinkronisasi yang terjadi di sini.
JustJeff
Anda ada benarnya; itu dapat mengurangi persyaratan konkurensi dari akses eksklusif ke penghalang memori.
Jason S