CHEATSHEET SISTEM OPERASI — BAB 4 (Threads), BAB 5 (Concurrency & Sync), BAB 6 (Deadlock)

BAB 4 — THREADS

1. Process vs Thread

Process = unit resource ownership & protection; punya virtual address space, akses ke processor, file, I/O, IPC.
Thread = unit dispatching (lightweight process); jalur eksekusi di dalam proses.
Multithreading = kemampuan OS mendukung banyak jalur eksekusi konkuren dalam satu proses.

2. Model Proses

Single-thread: 1 proses = 1 thread (cth: MS-DOS).
Multi-thread: 1 proses = banyak thread (cth: Java JVM, Windows, Solaris, Linux).
Setiap thread punya: execution state (Run/Ready/Blocked), thread context tersimpan, execution stack, storage statis lokal, akses memori & resource bersama dalam prosesnya.

3. Keuntungan Thread vs Process

Lebih cepat dibuat & di-terminate.
Context-switch antar thread lebih cepat dari antar proses.
Komunikasi antar thread lebih efisien (shared memory).

4. Penggunaan Thread (single-user)

Foreground & background work, asynchronous processing, speed of execution, modular structure.

5. Thread States

State utama: Running, Ready, Blocked.
Operasi: Spawn (buat), Block (tunggu event), Unblock, Finish.
Suspend proses ⇒ semua thread-nya suspend; terminate proses ⇒ semua thread terminate.

6. Thread Synchronization

Karena semua thread share address space, perubahan resource oleh 1 thread mempengaruhi yang lain ⇒ perlu sinkronisasi (dibahas Bab 5).

7. Jenis Thread

ULT (User-Level Thread): dikelola aplikasi via library; kernel tidak tahu thread.

+ Switch tanpa mode kernel, scheduling spesifik aplikasi, jalan di OS manapun.
− System call blocking memblok seluruh proses; tidak bisa multiprocessing.
Jacketing = ubah blocking call jadi non-blocking utk atasi kekurangan ULT.

KLT (Kernel-Level Thread): dikelola kernel via API (cth: Windows).

+ Beberapa thread satu proses bisa di banyak processor; thread blocked tidak blok proses; kernel routine bisa multi-thread.
− Switch thread butuh mode switch ke kernel (lebih lambat dari ULT).

Combined (cth: Solaris): pembuatan & sebagian besar scheduling di user space, eksekusi di KLT.

8. Hubungan Thread ↔ Process

T:P	Keterangan	Contoh
1:1	tiap thread = proses unik	UNIX tradisional
M:1	banyak thread dalam 1 proses	Windows NT, Solaris, Linux
1:M	thread bisa pindah proses	Ra (Clouds), Emerald
M:N	kombinasi M:1 & 1:M	TRIX

9. Multicore & Performance

Hukum Amdahl: porsi serial membatasi speedup; semakin besar porsi sekuensial, semakin kecil percepatan multicore.
Aplikasi yang untung: multithreaded native, multiprocess, Java (J2EE), multi-instance.

BAB 5 — MUTUAL EXCLUSION & SYNCHRONIZATION

1. Prinsip Concurrency

Konteks: multiprogramming (uniprocessor), multiprocessing (multi-CPU), distributed.
Masalah: race condition, sharing resource, alokasi waktu CPU, lokasi error sulit dilacak.
Race condition: hasil akhir tergantung urutan eksekusi proses/thread yang akses data bersama.

2. Perhatian OS

Track aktivitas proses, alokasi/dealokasi resource, lindungi data & resource, hasil proses harus independen terhadap kecepatan eksekusi.

3. Critical Section & Mutual Exclusion

Critical Section (CS): bagian kode yang mengakses resource bersama.
Mutual Exclusion: hanya 1 proses boleh di CS pada satu waktu.
Syarat solusi ME: hanya 1 di CS; tidak ada asumsi kecepatan/jumlah CPU; proses di luar CS tidak menahan yang lain; tidak deadlock/starvation; CS keluar cepat.

4. Dukungan Hardware

Disable Interrupt: hanya untuk uniprocessor; mengurangi efisiensi, tidak jalan di multiprocessor.
Atomic Instructions:
- Compare & Swap (Test & Set): cek lalu set nilai memori dalam satu instruksi atomik.
- Exchange: tukar isi register dengan memori secara atomik.
Kelebihan: berlaku di multiprocessor & multi-CS; sederhana. Kekurangan: busy waiting, mungkin starvation & deadlock.

5. Semaphore

Variabel integer dengan operasi atomik semWait/P() dan semSignal/V().
Binary semaphore: nilai 0/1. Counting semaphore: nilai bebas.
Strong: FIFO untuk proses blok; Weak: urutan tak ditentukan (bisa starvation).
Aturan: tidak boleh akses semaphore tanpa P/V; init >= 0; P decrement, blok jika <0; V increment, bangunkan 1 proses bila ada yang menunggu.

6. Producer / Consumer Problem

Producer hasilkan item ke buffer; consumer ambil. Buffer bisa infinite atau bounded.
Solusi pakai 3 semaphore (bounded buffer): s (mutex), n (item terisi), e (slot kosong).

7. Monitor

Konstruksi bahasa: kumpulan prosedur, variabel, struktur data dalam satu modul.
Variabel lokal hanya diakses prosedur monitor; proses masuk monitor dengan memanggil prosedurnya.
Mutual exclusion otomatis: hanya 1 proses aktif di monitor.
Sinkronisasi via condition variable dengan cwait(c) (suspend) & csignal(c) (bangunkan 1).

8. Message Passing

Primitif: send(destination, message) & receive(source, message).
Sinkronisasi:
- Blocking send & blocking receive (rendezvous).
- Non-blocking send, blocking receive (paling umum).
- Non-blocking send, non-blocking receive.
Addressing:
- Direct: send menyebut ID penerima; receive eksplisit/implisit.
- Indirect: pakai mailbox (queue); fleksibel (1:1, 1:N, N:1=port, N:N).
Format pesan: Header (type, dest ID, source ID, length, control) + Body (isi).
Bisa untuk mutual exclusion: gunakan mailbox sebagai token.

9. Readers / Writers Problem

Data dipakai banyak proses; reader hanya baca, writer hanya tulis.
Aturan: (1) banyak reader boleh baca bersamaan; (2) hanya 1 writer pada satu waktu; (3) saat writer menulis, tidak ada reader.
Solusi: Readers Priority (semaphore wsem + counter), Writers Priority (tambah rsem, y, z), atau pakai Message Passing (controller).
Beda dengan Producer/Consumer: tidak ada produksi/konsumsi data, hanya akses baca/tulis.

BAB 6 — DEADLOCK & STARVATION

1. Definisi

Deadlock: blocking permanen sekumpulan proses yang bersaing memperebutkan resource atau saling berkomunikasi.
Tiap proses dalam set menunggu event yang hanya bisa di-trigger proses lain di set itu ⇒ permanen, tidak ada solusi efisien umum.
Starvation: proses tertunda terus-menerus walau resource tersedia (beda dengan deadlock).

2. Kategori Resource

Reusable: dipakai 1 proses, tidak habis (CPU, I/O, memori, file, semaphore). Deadlock saat tiap proses pegang sebagian & minta milik proses lain.
Consumable: bisa dibuat & dihancurkan (interrupt, signal, pesan, isi buffer I/O). Deadlock contoh: 2 proses saling receive sebelum send.

3. Resource Allocation Graph

Node proses & resource; panah request (proses → resource) & held by (resource → proses).
Cycle di graph = indikasi deadlock (untuk resource single-instance: cycle ≡ deadlock).

4. Empat Syarat Deadlock

Mutual Exclusion: hanya 1 proses pakai resource pada satu waktu.
Hold & Wait: proses pegang resource sambil minta resource lain.
No Preemption: resource tidak bisa diambil paksa.
Circular Wait: ada rantai tertutup proses yang masing-masing menunggu resource milik proses berikutnya.

Tiga pertama = kebijakan (kondisi yang mungkin terjadi). Yang ke-4 = kejadian aktual. Semua harus ada agar deadlock terjadi.

5. Strategi Menangani Deadlock

Pendekatan	Kebijakan	Skema
Prevention	Konservatif (under-commit)	Minta semua sekaligus / Preemption / Resource ordering
Avoidance	Tengah	Banker's algo (cari minimal 1 safe path)
Detection	Liberal (grant sebisanya)	Cek periodik & recovery

6. Deadlock Prevention

Indirect: cegah salah satu 3 syarat pertama.
- Mutual Exclusion: tidak bisa di-cegah jika memang dibutuhkan OS.
- Hold & Wait: minta semua resource sekaligus di awal.
- No Preemption: jika ditolak, lepas resource yang dipegang & minta ulang; atau OS preempt proses kedua.
Direct: cegah circular wait ⇒ definisikan linear ordering tipe resource.

7. Deadlock Avoidance — Banker's Algorithm

Keputusan dinamis: grant request hanya jika sistem tetap safe.
Safe state: ada minimal 1 urutan alokasi yang membuat semua proses selesai tanpa deadlock.
Unsafe state: bukan deadlock, tapi bisa mengarah ke deadlock.
Dua pendekatan: Process Initiation Denial (tolak start proses) & Resource Allocation Denial (= banker's).
Struktur: matriks Claim (C), Allocation (A), Need = C−A; vektor Resource (R) & Available (V).
Batasan: max resource diketahui, proses independen, jumlah resource tetap, proses tidak exit sambil pegang resource.

8. Deadlock Detection & Recovery

Cek tiap request atau periodik. + deteksi dini, algoritma sederhana. − boros waktu CPU.
Recovery: (1) abort semua proses deadlocked; (2) rollback ke checkpoint; (3) abort proses satu per satu; (4) preempt resource satu per satu.

9. Dining Philosophers

5 filsuf, 5 garpu; tiap filsuf butuh 2 garpu (kiri & kanan) untuk makan.
Syarat: mutual exclusion (1 garpu = 1 filsuf) & bebas dari deadlock + starvation.
Solusi: semaphore garpu + semaphore room=4 (batasi 4 filsuf di meja), atau pakai monitor (get_forks/release_forks).

10. Mekanisme Concurrency UNIX

Pipes: circular buffer FIFO untuk producer-consumer; named & unnamed.
Messages: blok byte bertipe; msgsnd/msgrcv; tiap proses punya message queue (mailbox).
Shared memory: blok memori bersama antar proses (paling cepat).
Semaphores: generalisasi P/V.
Signals: notifikasi software ke proses akan kejadian asinkron.