Bab 22. Sinkronisasi Linux Pendahuluan Concurrent access dapat terjadi dalam sebuah kernel, termasuk kernel linux. Concurrent access adalah beberapa thread yang sedang berjalan mengakses resources yang sama dalam waktu yang sama. Jika hal ini terjadi, thread-thread tersebut akan saling mengoverwrite perubahan yang dilakukan thread sesamanya, sebelum perubahan tersebut mencapai state yang konsisten. Sehingga hasil dari proses menjadi tidak seperti yang diharapkan. Oleh karena itu, diperlukan proteksi dalam kernel yang bersangkutan. Proteksi yang dapat dilakukan adalah dengan sinkronisasi. Proteksi resources dari concurrent access bukanlah merupakan hal yang mudah. Beberapa tahun yang lalu sebelum Linux mendukung adanya symmetrical multiprocessing, proteksi masih mudah dilakukan karena hanya ada satu processor yang didukung. Satu-satunya cara bagi resources dapat diakses secara concurrent (bersamasama) oleh thread adalah ketika ada interrupt atau memang ada jadwal dari kernel bahwa thread lain diperbolehkan untuk mengakses resources tersebut. Namun dengan berkembangnya zaman, Linux akhirnya mendukung adanya symmetrical multiprocessing dalam versi 2.0 kernelnya. Multiprocessing artinya kernel code dapat dijalankan dalam dua atau lebih processor. Jika tanpa proteksi, code yang dijalankan dalam dua processor yang berbeda dapat mengakses resources yang sama dalam waktu yang sama. Dengan adanya kernel Linux 2.6 yang mendukung adanya konsep preemptive, scheduler dalam kernel dapat meng-interrupt kernel code yang sedang berjalan untuk memberi kesempatan bagi kernel code lain untuk dijalankan. Dengan demikian pengaksesan resources yang sama dalam waktu yang sama dapat dihindari. Dalam bab ini akan dijelaskan bagaimana implementasi sinkronisasi dalam Linux. Metode-metode sinkronisasi yang dibahas meliputi integer atomik yang merupakan salah satu jenis dari operasi atomik, locking yang terdiri dari spin lock dan semafor, dan dijelaskan hal-hal lain yang terkait dengan pembahasan ini.
Critical Section Sebuah proses memiliki bagian dimana bagian ini akan melakukan akses dan manipulasi data. Bagian ini disebut dengan Critical section. Ketika sebuah proses sedang dijalankan dalam critical sectionnya, tidak ada proses lain yang boleh dijalankan dalam critical sectionnya karena hal ini dapat memungkinkan terjadinya akses ke resources yang sama dan dalam waktu yang sama. Keadaan seperti ini disebut sebagai proses mutually exclusive. Oleh karena itu, diperlukan suatu mekanisme atau aturan agar proses bersifat mutually exclusive dapat terpenuhi. Dengan cara mengontrol variabel mana yang berubah baik di dalam maupun di luar critical section, concurrent access dapat dicegah. Critical section biasanya digunakan
saat program multithreading, dimana program yang terdiri dari banyak thread dapat mengubah nilai dari variabel. Dalam hal ini critical section diperlukan untuk melindungi variabel dari concurrent access yang dapat membuat nilai dari variabel tersebut menjadi tidak konsisten. Lalu bagaimana critical section tersebut diimplementasikan di dalam sistem operasi ? Metode yang paling sederhana adalah dengan mencegah adanya thread lain yang mengubah variabel yang sedang digunakan dalam critical section. Selain itu, system call yang dapat menyebabkan context switch juga dihindari. Jika scheduler meng-interrupt proses yang sedang mengakses critical sectionnya, maka scheduler akan membiarkan proses tersebut menyelesaikan critical sectionnya atau menghentikannya sementara untuk memberi kesempatan bagi proses lain untuk menjalankan critical sectionnya. Proses yang sedang berada dalam critical sectionnya dijalankan secara mutually exclusive. Contoh 22.1. Critical section do{ critical section }while(1)
Penyebab Konkurensi Kernel Sinkronisasi diperlukan karena adanya program yang dijadwalkan secara preemptive. Karena proses dapat di interrupt maka proses yang lain dapat masuk ke processor menggantikannya untuk dijalankan. Hal ini memungkinkan proses awal di interrupt di critical regionnya. Jika ada proses baru yang dijadwalkan untuk dijalankan selanjutnya masuk ke critical region yang sama, maka race condition akan terjadi. Ada dua jenis concurrency yaitu pseudo-concurrency dan true-concurrency. Pseudo-concurrency terjadi ketika dua proses tidak benar-benar berjalan dalam waktu yang tepat sama namun ada waktu jeda diantara keduanya. Sedangkan true-concurrency terjadi ketika dua proses berjalan secara bersama-sama yang waktu yang sama. True-concurrency biasanya terjadi pada komputer yang berbasis symmetrical multiprocessing. Ada beberapa penyebab konkurensi kernel, diantaranya: • •
Interrupt. Interrupt dapat terjadi sewaktu-waktu, menghentikan sementara proses yang sedang berjalan. Softirqs dan Tasklets. Kernel dapat menjadwalkan Softirqs dan Tasklets sewaktu-waktu untuk menghentikan sementara proses yang sedang berjalan. Softirqs dan Tasklets adalah pengatur interrupt untuk interrupt-interrupt yang tidak dapat dilakukan interrupt-handler yang biasa. Softirqs dapat berjalan secara bersama-sama dalam beberapa processor bahkan dua Softirqs yang sama dapat berjalan bersama-sama. Sifat tasklets hampir sama dengan Softirqs, hanya saja dua tasklets yang sama tidak dapat berjalan secara bersama-sama.
• • •
Kernel Preemption. Karena kernel bersifat preemptive, sebuah proses yang sedang berjalan dapat dihentikan sementara oleh proses yang lain. Sleeping dan Syncronization with user-space. Sebuah proses dalam kernel dapat sleep dan meminta kernel untuk menjalankan proses yang lain. Symmetrical Multiprocessing. Dua atau lebih processor dapat menjalankan kernel code dalam waktu yang sama.
Integer Atomik Salah satu metode dalam kernel Linux untuk sinkronisasi adalah atomic operations. Integer atomik adalah salah satu jenis dari atomic operations. Atomic operations menyediakan instruksi yang dijalankan secara atomik ( tanpa interrupt ). Contohnya sebuah atomic increment dapat membaca dan meng-increment sebuah variabel dalam sebuah step yang tidak dapat dibagi-bagi. Misalnya i diinisialisasi sama dengan 7 Gambar 22.1. Atomic Operation Thread 1 Thread 2 -----------------------------------------------------------------Atomic increment i (7 -> 8) Atomic increment i (8->9)
Atomic increment pada thread 1 akan dijalankan sampai selesai tanpa interrupt sehingga hasil dari thread pertama adalah 8. Setelah itu barulah thread 2 dijalankan. Mula-mula nilai i yang dibaca adalah 8 kemudian di iincrement sehingga hasil akhirnya 9. Methods integer atomik hanya berjalan untuk tipe data atomic_t. Fungsi atomik akan menggunakan tipe data ini dan tidak akan mengirim tipe data ini ke fungsi nonatomik. Dalam penggunaannya, compiler tidak mengakses langsung nilai dari data ini namun yang diakses adalah alamat memorinya. Integer atomik ( atomic_t ) memiliki 32 bits dalam representasinya. Namun yang dipakai untuk menyimpan suatu nilai hanya 24 bits karena 8 bits sisanya dipakai untuk lock yang berfungsi untuk memproteksi concurrent access ke data atomic yang bersangkutan. Hal ini diimplementasikan dalam SPARC port pada Linux.
Gambar 22.2. 32-bit atomic_t
Untuk menggunakan atomic integer operations perlu dideklarasikan terlebih dahulu
. Berikut ini contoh penggunaan atomic integer : atomic_t v; atomic_t v = ATOMIC_INIT(0); atomic_set(&v,4); atomic_add(2,&v); atomic_inc(&v); printk("%d\n",atomic_read(&v));
Fungsi atomic_t v akan mendefinisikan variabel v sebagai sebuah integer atomik. Kemudian variabel v akan diinisialisasi menjadi 0 oleh fungsi ATOMIC_INIT(0). Untuk menset nilai v, misalnya menjadi 4 secara atomik dapat digunakan fungsi atomic_set(&v,4). Menambah nilai v secara atomik dengan menggunakan fungsi atomic_add(2,&v). Variabel v dapat juga dikenakan atomic increment dengan menggunakan fungsi atomic_inc(&v). Fungsi printk("%d\n",atomic_read(&v)) akan mencetak nilai v. Berikut ini beberapa Atomic Integer Operations : Tabel 22.1. Tabel Atomic Integer Operations Atomic Integer Operation
Description ATOMIC_INIT(int i) inisialisasi atomic_t menjadi i atomic_read(atomic_t *v) membaca nilai integer dari v void atomic_set(atomic_t *v,int i) set nilai v menjadi i void atomic_add(int i,atomic_t *v) menambah v sebesar i void atomic_sub(int i,atomic_t *v) mengurangi c sebesar i void atomic_inc(atomic_t *v) menambah v dengan 1 void atomic_dec(atomic_t *v) mengurangi v dengan 1
Spin Locks Metode Locking adalah salah satu metode dalam sinkronisasi yang diperlukan untuk menjaga agar tidak ada proses yang berjalan bersama-sama, yang dapat memungkinkan adanya concurrent access ke resources yang sama. Locking akan menutup proses yang sedang berjalan dalam critical region-nya dari proses yang lain sehingga hanya akan ada satu proses yang sedang berjalan dalam sebuah processor. Locking yang paling umum digunakan dalam Linux adalah spin lock. Spin lock adalah lock yang hanya dapat dilakukan oleh satu thread. Ketika sebuah thread yang akan dijalankan meminta spin lock yang sedang digunakan, maka thread ini akan loops menunggu sampai spin lock tersebut selesai digunakan oleh thread yang sedang berjalan. Jika spin lock sedang tidak digunakan maka thread yang akan dijalankan akan langsung mendapatkannya. Hal ini akan mencegah adanya dua thread yang dijalankan bersama-sama. Dalam spin lock tidak diperbolehkan kernel preemption. Berikut ini contoh penggunaan spin lock : Sebelum menggunakan spin lock, perlu dideklarasikan . spinlock-t mr_lock = SPIN_LOCK_UNLOCKED; unsigned long flags; spin_lock_irqsave(&mr_lock,flags); / * critical region … * / spin_unlock_irqrestore(&mr_lock,flags);
Fungsi SPIN_LOCK_UNLOCKED menyatakan bahwa variabel yang bersangkutan, dalam hal ini mr_lock, sedang tidak menjalankan spin lock. Fungsi spin_lock_irqsave(&mr_lock,flags) menyebabkan mr_lock mendapatkan spin lock dan menyimpan state terakhir dari thread yang di interrupt. Setelah itu, mr_lock akan masuk ke critical regionnya. Setelah selesai maka mr_lock melepaskan spin lock dengan menggunakan spin_unlock_irqrestore(&mr_lock,flags) dan thread yang di interrupt kembali ke state terakhirnya. Berikut ini beberapa spin lock methods : Tabel 22.2. Tabel Spin Lock Methods Method spin_lock() spin_lock_irq() spin_lock_irqsave() spin_unlock()
Description Mendapatkan lock Menginterrupt dan mendapatkan lock Menyimpan current state dari local interrupt dan mendapatkan lock Melepaskan lock
Method
Description spin_unlock_irq() Melepaskan lock dan enable local interrupt Melepaskan lock dan memberi local interrupt previous spin_unlock_irqrestore() statenya
Semafor Semafor dalam Linux adalah sleeping locks. Ketika sebuah thread meminta semafor yang sedang digunakan, maka semafor akan meletakkan thread tersebut dalam wait queue dan menyebabkan thread tersebut masuk status sleep. Kemudian processor menjalankan thread yang lain. Ketika thread yang memegang semafor melepaskan locknya, maka satu dari thread yang ada di wait queue akan dipanggil sehingga akan mendapatkan semafor. Beberapa konklusi yang dapat diambil berkaitan dengan sleeping yang terjadi dalam semafor diantaranya : •
•
•
•
Karena thread yang sedang menunggu giliran untuk dijalankan masuk dalam status sleep, maka semafor cocok untuk lock yang digunakan untuk waktu yang cukup lama. Sebaliknya, semafor tidak cocok untuk lock yang digunakan dalam waktu yang singkat karena waktu yang digunakan untuk sleeping, menjaga wait queue, dan membangunkan thread yang sedang sleep akan menambah waktu lock. Thread yang sedang memegang semafor dapat sleep dan tidak akan deadlock ketika ada thread yang lain yang mendapatkan semafor yang sama karena thread tersebut akan sleep dan membiarkan thread yang pertama untuk melanjutkan eksekusinya. Suatu thread tidak dapat memegang spin lock ketika menunggu untuk mendapatkan semafor karena thread tersebut harus sleep dan tidak dapat sleep dengan memegang spin lock.
Berbeda dengan spin lock, semafor memperbolehkan adanya kernel preemption. Dalam semafor juga diperbolehkan pemegang semafor lebih dari satu dalam suatu waktu yang sama. Banyaknya pemegang lock di sebut usage count. Nilai yang paling umum untuk usage count adalah satu yang artinya hanya ada satu thread yang berjalan dalam suatu waktu. Dalam hal ini jika usage count sama dengan 1 maka disebut binary semaphore atau mutex. Implementasi dari semafor didefinisikan dalam . Semafor dapat dibuat dengan cara sebagai berikut : static DECLARE_SEMAPHORE_GENERIC(name,count)
dimana name menyatakan nama variabel dan count adalah usage count dari semafor. static DECLARE_MUTEX(name)
dimana name adalah nama variabel dari semafor.
Berikut ini contoh implementasi semaphore : static DECLARE_MUTEX(mr_sem); if(down_interruptible(&mr_sem)){ /*critical region*/ up(&mr_sem); }
Fungsi down_interruptible() digunakan untuk meminta semafor. Jika gagal, maka variabel yang bersangkutan akan sleep dalam state TASK_INTERRUPTIBLE. Jika kemudian variabel menerima signal maka down_interruptible() akan mengembalikan -EINTR. Sehingga fungsi down() akan membuat variabel masuk dalam state TASK_UNINTERRUPTIBLE dan akan dijalankan dalam critical regionnya. Untuk melepaskan semafor, digunakan fungsi up().Mengetahui apakah akan menggunakan spin lock atau semafor adalah cara yang baik untuk mengoptimalkan code yang dibuat. Berikut ini tabel mengenai apa yang diperlukan untuk menentukan lock mana yang digunakan. Tabel 22.3. Tabel Spin Lock Versus Semaphore Requirement Overhead locking yang rendah Lock hold time yang singkat Lock hold time yang panjang Sleep ketika menunggu lock
Recommended Spin lock Spin lock Semaphore Semaphore
SMP Symmetrical Multiprocessing (SMP) mendukung adanya pengeksekusian secara paralel dua atau lebih thread oleh dua atau lebih processor. Kernel Linux 2.0 adalah kernel Linux pertama yang memperkenalkan konsep SMP. Untuk menjaga agar dua thread tidak mengakses resources yang sama dalam waktu yang sama, maka SMP menerapkan aturan dimana hanya ada satu processor yang dapat menjalankan thread dalam kernel mode dengan cara spin lock tunggal untuk menjalankan aturan ini. Spin lock ini tidak memunculkan permasalahan untuk proses yang banyak menghabiskan waktu untuk menunggu proses komputasi, tapi untuk proses yang banyak melibatkan banyak aktifitas kernel, spin lock menjadi sangat mengkhawatirkan. Sebuah proyek yang besar dalam pengembangan kernel Linux 2.1 adalah untuk menciptakan penerapan SMP yang lebih masuk akal, dengan membagi kernel spin lock tunggal menjadi banyak lock yang masingmasing melindungi terhadap masuknya kembali sebagian kecil data struktur kernel.
Dengan menggunakan teknik ini, pengembangan kernel yang terbaru mengizinkan banyak processor untuk dieksekusi oleh kernel mode secara bersamaan.
Rangkuman Pada suatu saat dalam sebuah kernel, tidak terkecuali kernel Linux, dapat terjadi concurrent access. Dalam hal ini diperlukan proteksi dalam kernel yang bersangkutan. Proteksi dapat dilakukan dengan sinkronisasi. Sebuah proses memiliki bagian dimana bagian ini akan melakukan akses dan manipulasi data. Bagian ini disebut dengan critical section. Ketika sebuah proses sedang dijalankan dalam critical sectionnya, tidak ada proses lain yang boleh dijalankan dalam critical sectionnya. Ada dua jenis concurrency yaitu pseudo-concurrency dan true-concurrency. Ada beberapa penyebab konkurensi kernel, diantaranya interrupt, softirqs dan tasklets, kernel preemption, sleeping dan synchronization with user-space, dan symmetrical multiprocessing. Salah satu metode dalam kernel Linux untuk sinkronisasi adalah atomic operations. Integer atomik adalah salah satu jenis dari atomic operations. Integer Atomik menyediakan instruksi yang dijalankan secara atomik ( tanpa interrupt). Locking yang paling umum digunakan dalam Linux adalah spin lock. Spin lock adalah lock yang hanya dapat dilakukan oleh satu thread. Ketika sebuah thread yang akan dijalankan meminta spin lock yang sedang digunakan, maka thread ini akan loops menunggu sampai spin lock tersebut selesai digunakan oleh thread yang sedang berjalan. Semafor dalam Linux adalah sleeping locks. Ketika sebuah thread meminta semafor yang sedang digunakan, maka semafor akan meletakkan thread tersebut dalam wait queue dan menyebabkan thread tersebut masuk status sleep. Symmetrical multiprocessing (SMP) mendukung adanya pengeksekusian secara paralel dua atau lebih thread oleh dua atau lebih processor. Kernel Linux 2.0 adalah kernel Linux pertama yang memperkenalkan konsep SMP.
Rujukan [RobertLove2005] Robert Love. 2005. Linux Kernel Development. Novell Press. [Silberschatz2005] Avi Silberschatz, Peter Galvin, dan Grag Gagne. 2005. Operating Systems Concepts. Seventh Edition. John Wiley & Sons. [Stallings2001] William Stallings. 2001. Operating Systems: Internal and Design Principles. Fourth Edition. Edisi Keempat. Prentice-Hall International. New Jersey.
[WEBDrake96] Donald G Drake. April 1996. Introduction to Java threads – A quick tutorial on how to implement threads in Java – http://www.javaworld.com/ javaworld/ jw-04-1996/ jw-04-threads.html . Diakses 29 Mei 2006. [WEBFasilkom2003] Fakultas Ilmu Komputer Universitas Indonesia . 2003. Sistem Terdistribusi – http://telaga.cs.ui.ac.id/ WebKuliah/ sisdis2003/ . Diakses 29 Mei 2006. [WEBHarris2003] Kenneth Harris. 2003. Cooperation: Interprocess Communication – Concurrent Processing – http://people.cs.uchicago.edu/ ~mark/ 51081/ LabFAQ/ lab5/ IPC.html . Diakses 2 Juni 2006. [WEBWalton1996] Sean Walton. 1996. Linux Threads Frequently Asked Questions (FAQ) – http://linas.org/ linux/ threads-faq.html . Diakses 29 Mei 2006. [WEBWiki2006a] From Wikipedia, the free encyclopedia. http://en.wikipedia.org/wiki/Zombie_process . Diakses 2 Juni 2006.
2006.
[WEBLINUX2002] Robert Love. 2002. Kernel Locking http://www.linuxjournal.com/article/5833/ . Diakses 3 Maret 2007.
Title
–
Techniques
[WEBwikipedia2007a] From Wikipedia, the free encyclopedia. 2007.. 2007. Symmetric Multiprocessing http://en.wikipedia.org/wiki/Symmetric_multiprocessing/ . Diakses 3 Maret 2007. [WEBwikipedia2007] From Wikipedia, the free encyclopedia. 2007.. 2007. Critical Section http://en.wikipedia.org/wiki/Critical_section.htm/ . Diakses 10 April 2007.
Appendix Perbandingan Sinkronisasi yang dilakukan pada Linux dan Windows Kernel code memanggil fungsi penjadwalan sendiri Setiap waktu banyak proses yang berjalan dalam kernel mode, akibatnya sangat mungkin untuk terjadi race condition, contoh, dalam kernel mode terdapat struktur data yang menyimpan list file yang terbuka, list tersebut termodofikasi bila ada data file yang baru dibuka atau ditutup,dengan menambah atau menghapus dari list, race condition timbul ketika ada dua file yang dibuka dan ditutup bersamaan, untuk mengatasi hal tersebut kernel mempunyai metode yaitu: a. Preemptive kernel. Pada mode ini proses yang sedang dieksekusi dalam kernel diizinkan untuk diinterupsi oleh proses lain yang memenuhi syarat, akibatnya mode ini juga rentan terkena race condition. Keuntungannya adalah mode ini amat efektif untuk digunakan dalam real time programming, namun mode ini lebih sulit diimplementasikan dari pada mode non preemptive kernel. Mode ini diimplementasikan oleh Linux versi 2.6 dan versi komersial linux lainnya. b. Non preemptive kernel. Mode yang tidak memperbolehkan suatu proses yang berjalan dalam kernel mode diinterupsi oleh proses lain, proses lain hanya bisa dijalankan setelah proses yang ada dalam kernel selesai dieksekusi, implementasinya memang lebih mudah dibandingkan dengan preemptive kernel, mode ini diimplementasikan lewat Windows XP dan Windows 2000.
