Top 10 List of Week 07

1. What is a semaphore in C
   Mari kita mulai top 10 W07 kali ini dengan materi yang menurut saya paling menarik yaitu Semaphores. Kita pastinya sudah familiar dengan bendera semaphore yang biasa digunakan di suasana pramuka dengan guna berkomunikasi. Mirip sebenarnya semaphoring di OS akan tetapi tidak seribet semaphore pramuka yang ada 26 alfabet + 1 spasi gerakan. Semaphore yang sangat dasar di OS hanya ada 2 “bendera” yaitu 0 dan 1 dimana respon program itu ada 2 juga wait() dan signal() atau post() istilahnya. Dari kedua operasi itu intinya adalah kita harus wait() untuk melakukan CRITICAL SECTION yang menggunakan resource di shared memory lalu apabila sudah dapat giliran maka kita berhenti wait() dan “angkat bendera” kalau resource tsb sedang dipakai, apabila sudah selesai maka “turunkan bendera” dengan signal(). Pastinya penjelasan saya tadi masih belum terlalu terlihat dalam kode, oleh karena itu mohon anda coba lihat contoh di video dan juga di demo W07. Mengapa dipilih link ini: Kita sudah diperkenalkan dengan POSIX semaphores di kuliah sync dan juga syntaxnya di pop-quiz W07, dan kebetulan di video ini contohnya juga menggunakan POSIX semaphore dengan real-world cases. Ada juga quote di akhir yang cukup “bijak” kalau semaphore itu susah, apabila anda mulai merasakan penggunaan semaphore menjadi sering, maka kemungkinan besar aplikasi anda tidak reliable.

2. Dining Philosophers Problem
   Apabila anda sudah mengikuti mata kuliah SDA maka anda pasti familiar dengan “8 Queens Problem” untuk memvisualisasikan algoritma backtracking. Sama dengan OS kita memiliki sistem semaphore dan juga masalah-masalah di semaphore yang bisa di-ilustrasikan dengan baik oleh masalah “Makan Malam Para Filsuf”, secara pendek anggap ada meja bundar dengan 5 filsuf (threads) dan makanan ditengah (shared resource), di samping kanan dan kiri para filsuf ada 1 batang (bukan 1 pasang, hanya 1 batang) sumpit (semaphore). Setiap filsuf TIDAK BISA berbicara dengan filsuf lain dan filsuf hanya bisa makan jika ada sumpit di sebelah kanan dan kirinya lengkap. Sudah terbayang? kalau belum coba anda lihat gambar di link baru kembali kesini. Dari link pertama kita sudah mengenal wait(), CRITICAL SECTION, dan signal(), disini sebelum filsuf bisa makan dia akan wait() kedua sumpit di kanan dan kirinya, apabila ada keduanya maka dia makan atau melakukan CRITICAL SECTION, bila sudah maka dia kembalikan sumpitnya ke kanan dan kirinya atau bagian signal() dan filsuf di sebelahnya bisa makan apabila sumpit sebelahnya juga sudah tersedia. Namun kita belum sampai ke bagian yang menarik, sekarang anda bayangkan setiap filsuf secara berurutan mengambil sumpit di sebelah kanannya, akhirnya tidak ada filsuf yang bisa makan karena saling wait() akan sumpit sebelah kanannya yang diambil sebagai sumpit kiri filsuf lainnya. Kejadian tersebut dimana kita “mentok” adalah DEADLOCK, akan kita explore setelah ini. Mengapa dipilih link ini: Visualisasi untuk masalah yang cukup eye-opening ini sangat baik di video walaupun durasinya pendek. Belum lagi ditambah masalah-masalah yang bisa terjadi akibat semaphoring yang diabstrakkan dengan filsuf tadi.

3. Deadlock Characterization and one of the way its detected
   Kita sendiri telah mengenal deadlock di link sebelumnya, yaitu kondisi “nyangkut” karena tidak ada akses ke shared resource. Kita harus masuk dahulu ke 4 penyebab deadlock (harus terjadi semuanya untuk ada deadlock!) yaitu Mutual Exclusion (1 accessor only), Hold and Wait (anggap ada 2 resource, 1 resource di lock process tsb namun harus wait 1 resource lainnya), No Preemption (Resource yang di lock hanya bisa dilepas oleh pemasang lock), dan terakhir Circular Wait (process yang menunggu dalam pattern melingkar). Saya rasa dari ke-4 penyebab tersebut anda bisa menafsirkan masalah makan malam filsuf di link 2 saya. Selain 4 penyebab tersebut, kita juga diperkenalkan dengan System Resource Allocation Graph, intinya anggap resource dan process sebagai verteks, dan pemegang lock sebagai edge dari resource ke process, dan penunggu resource sebagai edge dari process ke resource. Intinya bila ada cycle di graph, maka terjadi deadlock. Gambar yang lebih detail anda bisa lihat sendiri di link yang sudah diberikan. Mengapa dipilih link ini: Saya rasa kurang ada artikel yang menekankan bahwa ke-4 kondisi harus dipenuhi untuk terjadi deadlock, dan juga ditambah fakta yang cukup baik tentang Resource Allocation Graph.

4. SetUID, SetGID, and Sticky Bits
   Bayangkan sebuah kasus dimana anda memiliki file atau program yang menggunakan file lain yang aksesnya direstriksi ke owner file namun anda ingin orang lain menggunakan program tersebut tanpa memiliki akses ke akun owner tersebut. Bagaimana kita bisa melakukannya? jawabannya adalah dengan SetUID atau SetGID bila anda menggunakan grouping, intinya adalah kita menjalankan program dengan hak akses UID atau GID yang kita assign, syntaxnya adalah dengan chmod abcd dengan bcd itu representasi biner dalam desimal yang anda sudah ketahui untuk assignment permission user, group, dan others. Untuk yang baru adalah a dimana 4 menunjukkan boleh dieksekusi sebagai owner, 2 boleh dieksekusi sebagai group owner. Namun 1 apa? yaitu Sticky Bits yang berarti hanya owner directory yang bisa menghapus directory, sedangkan user lainnya boleh membuat dan memodifikasi file di dalamnya. Mengapa dipilih link ini: Contoh yang diberikan baik dengan menggunakan program-program yang ada di /bin seperti passwd dan juga penjelasan use case dari setiap fitur yang diberikan juga jelas.

5. Race condition and how was it first solved
   Race condition, saya rasa anda sudah familiar dengan term ini di mata kuliah Pemrograman Lanjut dan detail-detailnya. Intinya adalah masalah yang terjadi akibat ada 2 atau lebih program yang mengakses dan/atau memodifikasi data di waktu yang sama. Contoh yang cukup mudah adalah transfer bank di waktu yang sama pastinya kita ingin kedua transfer masuk ke rekening kita. Untuk mengatasi race condition, algoritma yang pertama kali ditemukan adalah Dekker’s Algorithm yang bisa dianalogikan dengan panah urutan dan juga lampu signal “ingin memakai”. Pendeknya apabila process ingin menggunakan data yang shared (critical section) maka harus menyalakan lampu signal, namun process hanya bisa masuk ke critical section hanya jika signal process lain itu mati. Apabila menyala maka kita akan gunakan panah urutan, kila keduanya menyala maka yang ditunjuk oleh panah urutan yang masuk duluan (process lain mematikan lampu signalnya). Terakhir kita juga diperkenalkan dengan konsep “Starvation” dimana program yang low priority seakan “ditunda” selamanya karena program high priority selalu dapat giliran di critical section. Mengapa link ini dipilih: Video ini animasinya sangat membantu dalam visualisasinya. Juga di akhir penjelasan juga diberikan hal-hal lain yang dipecahkan oleh Dekker’s Algorithm seperti starvation dengan panah gilirannya.

6. Deadlock handling methods and why ignorance is the best
   Kita sudah mengetahui 4 penyebab deadlock, sama seperti musibah ada langkah preventif dan mengatasinya, disini OS kita memiliki 4 cara mengatasi deadlock yaitu Prevention, Avoidance, Detection & Recovery, dan Ignorance. Prevention seperti katanya adalah preventif dengan mencegah salah 1 atau semua ke-4 penyebab tadi. Avoidance itu mirip dengan preventif namun dilakukan tepat sebelum deadlock bisa terjadi, yaitu kita tanyakan saat mau memberikan resource ke process, apakah akan terjadi deadlock? bila tidak maka berikan. Detection & Recovery sama seperti mengatasi, yaitu deadlock sudah terjadi maka bawakan process yang bisa mengatasi deadlock tsb. Terakhir adalah Ignorance sesuai namanya adalah cukup membiarkan deadlock itu terjadi saja. Di sisi lain Ignorance keliatan tidak bijak, namun ternyata OS yang UNIX based dan Windows ternyata menggunakan metode ini! Mengapa? karena deadlock jarang terjadi, dan juga algoritma untuk mendeteksi atau preventif terhadap deadlock itu menambah kompleksitas. Mengapa dipilih link ini: Walaupun video ini menggunakan TTS untuk narasinya, materi di video ini sangat jelas dengan analogi nyata (bensin dan motor) yang baik. Juga diberikan kesimpulan dari metode mana yang terbaik.

7. Scientists vs. Engineers: Deadlock Ignorance
   Ada juga link tambahan disini dan juga disini untuk mengetahui lebih lanjut tentang Deadlock Ignorance. Algoritma deadlock ignorance dinamakan “Ostrich Algorithm” yaitu dari istilah kalau burung unta akan mengubur kepalanya ke dalam pasir apabila ketakutan (entah ini benar atau tidak silahkan anda GSGS sendiri, hehe) jadi seakan tidak ada masalah yang dilihat. Deadlock ignorance ini cukup kontroversial diantara computer scientists (CS) yang melihat secara matematis dan computer / software engineers (SE). Para CS berpendapat kalau deadlock wajib ditanggapi dengan prevention method karena ya memang itu cara paling efisien, jadinya tidak ada deadlock yang bisa terjadi. Sedangkan para SE berpendapat kalau deadlock itu lebih baik menjadi perhatian prioritas sangat rendah, justru yang harus diperhatikan dulu itu bug, hardware crash, dll yang lebih sering terjadi daripada deadlock yang jarang sekali terjadi, belum lagi kalau deadlock prevention itu menambah complexity. Dan bila kita simpulkan seperti para SE menang dalam perlawanan ini, karena seperti di link sebelumnya OS-OS terkenal menggunakan deadlock ignorance.Intinya adalah: deadlock di-ignore karena tidak terlalu serius dalam merusak sistem dan juga dalam melakukan pencegahannya akan menambah kompleksitas di program walaupun jarang terjadi. Mengapa dipilih link ini: Topik yang cukup menarik dalam deadlock handling dijelaskan di dalam link-link yang saya berikan. Juga diberikan contoh di kasus nyata dengan files.

8. Mutex vs. Semaphores
   Di link pertama yang fokus terhadap semaphore juga dibahas sedikit tentang Mutex, keduanya juga merupakan mekanisme locking terhadap resource. Namun apa bedanya mutex dan semaphore? Mutex sebenarnya lebih sederhana dari semaphore, intinya adalah mutex hanya bisa didapatkan (semacam wait()) oleh hanya satu buah thread, apabila semaphore kita sudah tahu kalau beberapa semaphore bisa dilakukan wait() oleh beberapa thread semacam mengantri, sedangkan untuk mutex tidak bisa. Use case untuk mutex salah satunya adalah apabila ingin kode yang tidak dilaksanakan oleh beberapa thread di waktu yang sama. Referensi tambahan juga bisa dilihat disini dan juga contoh kode apabila anda ingin belajar lebih lanjut Mengapa dipilih link ini: Link berisi video cukup jelas dengan analogi toilet dan kunci. Intinya adalah hanya ada satu thread yang bisa mengakses critical resource di waktu tersebut.

9. Sleeping Barber problem and Starvation
   Mari kita dalami konsep Starvation, seperti di link-link sebelumnya, Starvation itu berarti sebuah process atau thread dkk. yang tidak bisa mendapat giliran untuk masuk ke critical section karena entah prioritasnya selalu lebih rendah, giliran yang random tidak pernah kebagian atau lainnya. Disini kita akan dalami dengan studi kasus Sleeping Barber problem, dimana ada penggunting rambut yang akan tidur di kursi potong rambut bila tidak ada pelanggan, bila ada pelanggan masukmaka pelanggan akan menunggu di kursi pelanggan bila ada yang sedang dicukur, bila tidak maka akan langsung dicukur. Secara singkat solusinya anda lebih baik lihat di link yang saya berikan karena visualisasinya sangat jelas. Inti dari permasalahannya adalah jangan sampai lupa untuk mengatur juga urutan akses dari pelanggan (thread atau process dkk) untuk mengakses critical section (kursi cukur) yang bisa diimplementasikan dengan entah queue atau sistem FIFO karena bila tidak, bisa terjadi potensi Starvation dimana pelanggan sangat lama menunggu untuk urutannya mendapat layanan penggunting rambut. Mengapa dipilih link ini: Sebuah studi kasus yang mengajak kita untuk berpikir kritis juga tentang Deadlock dengan memperhatikan juga masalah Starvation. Visualisasi dan cerita di link juga sangat jelas.

10. Limitation of semaphores with Cigarette Smokers problem
    Sebelum membaca link ini, saya berikan disclaimer bahwa merokok itu tidak sehat, dan saya tidak merekomendasikannya. Mari masuk ke masalahnya, rokok dibuat dari 3 bahan baku yaitu kertas, tembakau, dan juga korek api. Kita memiliki agen yang tidak merokok dan memberikan dua buah bahan baku secara acak (bahan baku pasti beda) kepada 3 perokok yang masing-masing memiliki tak hingga jumlah kertas atau tembakau atau korek api. Agen juga tidak akan memberikan bahan baku lagi sampai ada seseorang yang merokok (dengan membuat rokok dari 3 bahan baku). Sekarang lanjut ke masalahnya, apabila dua perokok mengambil 1 bahan baku saja, maka pasti akan terjadi deadlock ya karena setiap orang memiliki 2 bahan baku saja dan 1 orang lagi hanya 1 itu saja. Maka solusinya adalah kita harus memilih siapa yang mengambil 2 bahan baku berdasarkan siapa yang memiliki bahan baku yang bukan dari 2 bahan tersebut. Contohnya agen memberikan kertas dan tembakau, maka yang mengambil adalah perokok dengan korek api. Mungkin untuk lebih jelas mengapa masalah ini sedikit berbeda anda bisa melihat penjelasan yang lengkap di artikel. Intinya adalah operasi increment dan decrement tidak cukup untuk mengatasi deadlock. Mengapa dipilih link ini: Alur masalah yang cukup menarik, menyadarkan kita pandangan bahwa semaphore itu tidak selalu bisa mengatasi masalah deadlock. Namun kita juga harus atur struktur dari program kita agar bisa mengatasi deadlock sepenuhnya.