Materi Teori Operating Systems

1. Introduction to Operating Systems: Definisi, Struktur & System Calls

Operating System (OS) adalah perangkat lunak sistem tingkat rendah yang bertindak sebagai perantara (intermediary) antara pengguna komputer/program aplikasi dengan perangkat keras komputer (hardware).

Dua Peran Utama OS:

Resource Allocator: Mengelola dan mengalokasikan CPU time, ruang memori RAM, ruang disk penyimpanan file, serta perangkat I/O secara adil dan efisien di antara program-program yang bersaing.
Control Program: Mengontrol eksekusi program pengguna untuk mencegah terjadinya kesalahan (errors) dan penggunaan komputer yang tidak sah (security violation).

Dual-Mode Operation (Proteksi Hardware):

CPU modern mendukung minimal dua mode operasi yang dibedakan oleh bit status (Mode Bit):

User Mode (Mode Bit = 1): Tempat eksekusi aplikasi pengguna biasa. Instruksi sensitif (privileged instructions seperti akses I/O langsung atau memori fisik kernel) dilarang.
Kernel / Supervisor Mode (Mode Bit = 0): Tempat eksekusi kernel OS dengan akses tanpa batas ke seluruh instruksi CPU dan alamat fisik memori hardware.

Arsitektur Struktur Kernel

Struktur Kernel	Karakteristik & Desain	Kelebihan	Kelemahan	Contoh Nyata
Monolithic Kernel	Seluruh layanan OS (scheduler, virtual memory, file system, driver) berjalan bersama dalam satu address space di kernel mode.	Performa sangat tinggi karena pemanggilan fungsi antar-komponen dilakukan lewat panggilan langsung tanpa context switch IPC.	Jika satu device driver crash atau terkena buffer overflow, seluruh sistem operasi akan crash (Kernel Panic/BSOD).	Linux Kernel, FreeBSD, MS-DOS.
Microkernel	Hanya fungsi paling esensial (minimal memory management, primitive process scheduling, IPC) yang berada di kernel mode. Layanan lain (file system, network) dijalankan sebagai server proses di user mode.	Sangat modular, aman, dan stabil. Jika server file system crash, kernel utama tetap hidup dan server cukup di-restart.	Overhead performa tinggi akibat ribuan kali message passing dan context switch antara user space dan kernel.	Mach, QNX (sistem otomotif), Minix.
Hybrid Kernel	Kombinasi performa monolitik dengan modularitas microkernel; sebagian layanan penting tetap diletakkan di kernel mode demi performa cepat.	Menyeimbangkan kecepatan komputasi dengan kemudahan driver management.	Kompleksitas kode basis sangat besar.	Windows NT Kernel, macOS (XNU / Darwin).

Mekanisme System Call (Transisi User ke Kernel)

Ketika program aplikasi di User Mode ingin melakukan operasi I/O (seperti membaca berkas read() atau mencetak teks write()), program memicu instruksi khusus CPU berupa Software Interrupt (Trap) atau instruksi syscall / sysenter.
CPU akan beralih ke Mode Bit 0 (Kernel Mode), membaca tabel System Call Interface, mengeksekusi rutin handler kernel yang sesuai, lalu kembali mengembalikan nilai hasil ke User Mode (Mode Bit 1).

2. Processes: Siklus Hidup, State Diagram & Struktur PCB

Proses secara formal didefinisikan sebagai "program yang sedang dieksekusi" (program in execution). Berbeda dengan program yang berupa entitas pasif tersimpan di disk (file biner ELF/EXE), proses adalah entitas aktif yang memiliki Program Counter, register CPU, dan rentang alamat memori virtual.

Diagram 5 Status Proses (Process State Diagram)

              [ NEW ] ---> (admitted) ---> [ READY ] <-----> (scheduler dispatch / timeout) <-----> [ RUNNING ] ---> (exit) ---> [ TERMINATED ]
                                              ^                                                          |
                                              |------------ (I/O or event completed) <--- [ WAITING ] <-- (I/O or event wait)
            

Penjelasan 5 Status Proses:

New: Proses baru saja dibuat namun belum dimuat sepenuhnya ke memori utama untuk dijadwalkan.
Ready: Proses telah siap dieksekusi di RAM dan sedang menunggu giliran dialokasikan waktu CPU oleh Scheduler.
Running: Instruksi-instruksi proses sedang aktif dieksekusi oleh inti core CPU.
Waiting / Blocked: Proses tidak dapat berjalan karena sedang menunggu penyelesaian suatu peristiwa eksternal (misal: menunggu input keyboard, pembacaan blok disk, paket jaringan).
Terminated: Proses telah menyelesaikan eksekusinya dan sumber dayanya sedang dibersihkan oleh OS.

Komponen Process Control Block (PCB):

Struktur data kernel (seperti struct task_struct di Linux) yang mewakili setiap proses:

Process Identifier (PID): Nomor identifikasi unik integer proses.
Process State: Ready, running, waiting, dll.
Program Counter (PC): Alamat instruksi selanjutnya yang akan dieksekusi saat proses kembali dijadwalkan.
CPU Registers: Akumulator, index registers, stack pointer (ESP/RSP), general purpose registers saat terjadi context switch.
CPU Scheduling Information: Prioritas proses, pointer ke scheduling queues.
Memory Management Info: Base and limit registers, page tables atau segment tables.
Accounting Info: Waktu CPU yang telah digunakan, batas waktu eksekusi.
I/O Status Info: Daftar berkas yang sedang dibuka, perangkat I/O yang dialokasikan.

Manajemen Proses POSIX: fork(), exec(), wait()

fork(): Menduplikasi proses pemanggil menjadi proses anak (Child Process). Mengembalikan nilai 0 pada proses anak, mengembalikan nilai PID anak pada proses orang tua (Parent), atau -1 jika gagal.
execve() / execlp(): Menggantikan seluruh address space proses saat ini dengan binary program baru.
wait() / waitpid(): Memblokir proses parent hingga salah satu proses anaknya selesai, guna membaca status exit dan mencegah terjadinya Zombie Process.
Zombie Process: Proses yang sudah terminate tetapi parent-nya belum memanggil wait() sehingga entry PCB-nya masih tersisa di tabel proses.
Orphan Process: Proses anak yang parent-nya sudah mati lebih dahulu tanpa menunggu anak selesai; otomatis diadopsi oleh proses init / systemd (PID 1).

3. Threads: Konsep, Model Multithreading & POSIX Pthreads

Thread (sering disebut Lightweight Process atau LWP) adalah unit terkecil pemanfaatan CPU. Sebuah proses dapat memiliki banyak thread yang berjalan secara konkuren di dalam dirinya.

Shared vs Private Resources

Di dalam sebuah proses multithread:

Dibagi Bersama (Shared): Text/Code Segment, Data Segment (variabel global), BSS, Heap memory (alokasi malloc), dan File Descriptors (file terbuka, socket).
Privat per-Thread (Unique): Thread ID (TID), Nilai Register CPU (EAX, EBX, PC), dan Call Stack tersendiri (variabel lokal dan jejak pemanggilan fungsi).

Keunggulan Thread dibanding Fork:

Responsiveness: Aplikasi tetap dapat merespons UI meski thread worker sedang sibuk komputasi berat.
Resource Sharing: Tidak membutuhkan mekanisme IPC rumit karena thread berbagi memori yang sama.
Economy (Hemat): Membuat thread jauh lebih cepat dan hemat memori daripada menduplikasi seluruh address space proses (overhead context switch thread jauh lebih ringan).
Scalability: Mengoptimalkan multiprocessor core secara masif.

3 Model Relasi Thread (User vs Kernel Level)

Model	Pemetaan	Kelebihan	Kelemahan Kritis
Many-to-One	Banyak thread user-level dipetakan ke 1 thread kernel. Pengelolaan di user space via library.	Peralihan thread sangat cepat tanpa melibatkan kernel trap.	Jika 1 thread melakukan blocking system call (misal: I/O baca disk), SELURUH proses akan terblokir! Tidak dapat memanfaatkan multicore.
One-to-One (Standar Modern)	Setiap thread user-level dipetakan tepat ke 1 thread kernel OS.	Konkurensi sejati pada multicore. Jika 1 thread blocking, thread lain tetap berjalan bebas.	Membuat thread user berarti membuat thread kernel (konsumsi memori kernel). Diadopsi oleh Linux (NPTL) dan Windows.
Many-to-Many	Banyak user thread dimultiplex ke jumlah kernel thread yang sama atau lebih sedikit.	Sangat fleksibel; tidak terbatas alokasi kernel namun tetap konkuren.	Sangat rumit untuk diimplementasikan secara efisien di level OS scheduler.

4. CPU Scheduling: Algoritma & Analisis Gantt Chart Lengkap

CPU Scheduling adalah basis dari sistem multiprogramming. Scheduler memilih salah satu proses yang berstatus Ready di memori dan mengalokasikan CPU kepadanya.

Kriteria Optimasi Penjadwalan:

CPU Utilization (Maksimalkan): Persentase waktu CPU sibuk bekerja (ideal: 40% - 90%).
Throughput (Maksimalkan): Jumlah proses yang tuntas per satuan waktu.
Turnaround Time / TAT (Minimalkan): Total selang waktu sejak proses submit tiba hingga selesai tuntas (TAT = Completion Time - Arrival Time).
Waiting Time / WT (Minimalkan): Total waktu yang dihabiskan proses mengantre di Ready Queue (WT = Turnaround Time - Burst Time).
Response Time (Minimalkan): Waktu sejak submit hingga respon keluaran pertama kali muncul.

Preemptive vs Non-Preemptive:

Non-Preemptive (Kooperatif): Sekali CPU dialokasikan ke suatu proses, proses tersebut memegang CPU sampai sukarela melepaskannya (terminate atau masuk mode waiting I/O).

Preemptive: OS berhak memotong paksa eksekusi proses yang sedang berjalan di tengah jalan jika habis jatah waktu (Timer Interrupt) atau ada proses dengan prioritas lebih tinggi yang baru tiba.

Studi Kasus Perhitungan UTS: Gantt Chart & Average Waiting Time

Diberikan 4 proses yang tiba pada waktu $Arrival\ Time (AT) = 0$ dengan durasi $Burst\ Time (BT)$ masing-masing:

Proses	Burst Time (BT)	Prioritas (1 = Tertinggi)
P1	20 ms	3
P2	4 ms	1 (High)
P3	6 ms	2
P4	2 ms	4

1. FCFS (First-Come, First-Served)

Urutan kedatangan: P1 -> P2 -> P3 -> P4

                Gantt Chart:

                |------ P1 ------|--P2--|---P3---|P4|

                0               20     24       30  32

WT P1 = 0 ms
WT P2 = 20 ms
WT P3 = 24 ms
WT P4 = 30 ms
Average Waiting Time (AWT) = (0 + 20 + 24 + 30) / 4 = 18.5 ms
Kelemahan: Convoy Effect (proses pendek terhambat lama di belakang proses besar).

2. SJF (Shortest Job First - Non Preemptive)

Urutan durasi tercepat: P4 (2) -> P2 (4) -> P3 (6) -> P1 (20)

                Gantt Chart:

                |P4|--P2--|---P3---|------ P1 ------|

                0  2      6        12              32

WT P4 = 0 ms
WT P2 = 2 ms
WT P3 = 6 ms
WT P1 = 12 ms
Average Waiting Time (AWT) = (0 + 2 + 6 + 12) / 4 = 5.0 ms
Optimal secara matematis! Menghasilkan AWT terkecil.

3. Priority Scheduling (Non-Preemptive)

Urutan prioritas: P2 (1) -> P3 (2) -> P1 (3) -> P4 (4)

                Gantt Chart:

                |--P2--|---P3---|------ P1 ------|P4|

                0      4        10              30  32

WT P2 = 0 ms | WT P3 = 4 ms | WT P1 = 10 ms | WT P4 = 30 ms
Average Waiting Time (AWT) = (0 + 4 + 10 + 30) / 4 = 11.0 ms
Isu Starvation: Proses prioritas rendah bisa tak pernah jalan. Solusi: Aging (menaikkan prioritas seiring bertambahnya waktu tunggu).

4. Round Robin (Time Quantum = 4 ms)

Berputar bergiliran dengan kuantum q = 4 ms:

                Gantt Chart:

                |P1|P2|P3|P4|P1|P3|P1|P1|P1|

                0  4  8  12 14 18 20 24 28 32

P2 selesai di t=8; P4 selesai di t=14; P3 selesai di t=20; P1 selesai di t=32.
WT P1 = 32 - 20 = 12 ms | WT P2 = 4 ms | WT P3 = 14 ms | WT P4 = 12 ms
Average Waiting Time (AWT) = (12 + 4 + 14 + 12) / 4 = 10.5 ms
Sangat responsif untuk time-sharing interactive system!

5. Multiple Processor Systems: SMP, Multicore & NUMA

Sistem komputasi modern menggunakan multi-prosesor dan multi-core untuk mempercepat komputasi throughput secara paralel.

Symmetric Multiprocessing (SMP)

Setiap prosesor menjalankan salinan identik dari kernel sistem operasi.
Seluruh CPU berbagi bus sistem dan memori fisik RAM utama yang sama (Uniform Memory Access / UMA).
Proses dapat dieksekusi di prosesor mana pun tanpa memandang hierarki khusus.

Processor Affinity & Migration

Processor Affinity: Menjaga proses agar tetap dieksekusi di core CPU yang sama guna memanfaatkan data yang sudah berada di L1/L2 cache (menghindari cache invalidation).
Soft Affinity: OS berusaha mempertahankan proses di core yang sama tetapi tidak menjamin jika terjadi ketimpangan beban.
Hard Affinity: Proses secara eksplisit diikat ke core tertentu (misal: via sched_setaffinity() di Linux).

Non-Uniform Memory Access (NUMA)

Pada server berskala besar dengan ratusan core, bus memori tunggal menjadi bottleneck. Arsitektur NUMA membagi memori menjadi beberapa node lokal yang menempel langsung ke masing-masing socket CPU.
Prinsip Kinerja: Mengakses memori lokal (Local Memory) pada socket sendiri jauh lebih cepat daripada mengakses memori remote pada socket tetangga melalui interkoneksi QPI/UPI. Scheduler OS harus NUMA-aware dengan selalu mengalokasikan memori lokal untuk thread yang berjalan di CPU tersebut.

6. Synchronization & IPC: Race Condition, Mutex & Klasik Problem

Ketika beberapa thread atau proses mengakses dan memanipulasi data bersama secara serentak, hasil akhir eksekusi bergantung pada urutan akses instruksi yang terjadi. Fenomena ini disebut Race Condition.

            3 Syarat Wajib Solusi Critical Section Problem:
            Mutual Exclusion (Mutlak): Jika proses Pi sedang mengeksekusi Critical Section-nya, tidak ada proses lain yang diizinkan masuk ke Critical Section tersebut.
Progress: Jika tidak ada proses di Critical Section dan ada proses yang ingin masuk, hanya proses yang tidak sedang di Remainder Section yang berhak ikut menentukan siapa yang masuk berikutnya; seleksi tidak boleh ditunda tanpa batas waktu.
Bounded Waiting: Harus ada batas tertentu berapa kali proses lain diizinkan masuk setelah suatu proses mengajukan permintaan, guna mencegah kelaparan tak terbatas (starvation).

          

Mutex Lock (Mutual Exclusion Lock)

Mekanisme penguncian biner sederhana. Hanya thread yang berhasil melakukan acquire() yang berhak memasuki Critical Section, dan ia wajib melepaskan kunci dengan release() setelah selesai.
Jika menggunakan polling aktif saat menunggu kunci, disebut Spinlock (berguna untuk kunci berdurasi sangat singkat pada multicore).

Semaphore (Dijkstra)

Variabel integer yang hanya dapat diakses melalui dua operasi atomik:
wait(S) (atau P(S)): Mengurangi nilai S (S--). Jika $S < 0$, proses diblokir.
signal(S) (atau V(S)): Menambah nilai S (S++). Jika ada proses yang menunggu, salah satu proses dibangunkan.
Counting Semaphore: Nilai S mewakili jumlah unit sumber daya yang tersedia.

3 Masalah Klasik Sinkronisasi (Wajib Paham Alur)

1. Producer-Consumer (Bounded Buffer)

Producer memproduksi data ke buffer berukuran terbatas; Consumer mengambil data. Sinkronisasi harus menjamin:
- Producer tidak menimpa saat buffer penuh.
- Consumer tidak membaca saat buffer kosong.
- Solusi: 3 Semaphore (mutex=1, empty=N, full=0).

2. Readers-Writers Problem

Beberapa pembaca dapat membaca database bersamaan tanpa konflik. Namun jika seorang Penulis (Writer) ingin menulis, tidak boleh ada pembaca atau penulis lain yang sedang aktif.
- Solusi: Mutex penghitung pembaca read_count dan semaphore rw_mutex.

3. Dining Philosophers Problem

5 filsuf duduk melingkar dengan 5 sumpit di antara mereka. Untuk makan butuh 2 sumpit (kiri dan kanan). Jika semua filsuf serentak mengambil sumpit kiri, terjadi Deadlock!
- Solusi: Filsuf ganjil ambil kanan dulu; atau gunakan monitor dengan pembatasan maksimal 4 filsuf yang boleh mencoba makan bersamaan.

7. Deadlock: 4 Kondisi Coffman & Algoritma Banker (Avoidance)

Deadlock adalah situasi di mana sekumpulan proses terhenti permanen karena setiap proses menahan suatu sumber daya seraya menunggu sumber daya lain yang sedang ditahan oleh proses lain dalam kelompok tersebut.

4 Kondisi Coffman (Semua Harus Terpenuhi Agar Deadlock Terjadi):

Mutual Exclusion: Minimal 1 sumber daya harus bersifat non-shareable (hanya 1 proses dalam satu waktu).
Hold and Wait: Suatu proses harus sedang menahan minimal 1 sumber daya sambil menunggu untuk mendapatkan sumber daya tambahan.
No Preemption: Sumber daya tidak dapat disita paksa; hanya dapat dilepaskan secara sukarela oleh proses yang memegangnya.
Circular Wait: Terdapat himpunan proses $\{P_0, P_1, \dots, P_n\}$ sedemikian rupa sehingga $P_0$ menunggu sumber daya yang ditahan $P_1$, dan $P_n$ menunggu sumber daya yang ditahan $P_0$.

Algoritma Banker (Deadlock Avoidance)

Diciptakan oleh Edsger Dijkstra untuk sistem perbankan. Setiap kali proses meminta sumber daya, sistem menguji apakah pemenuhan permintaan tersebut akan mempertahankan sistem dalam Safe State (ada safe sequence di mana semua proses dijamin dapat tuntas).

Struktur Data Algoritma Banker:

Available[m]: Vektor jumlah instance sumber daya yang sedang bebas.
Max[n][m]: Matriks batas permintaan maksimum proses terhadap tiap sumber daya.
Allocation[n][m]: Matriks jumlah sumber daya yang saat ini sedang dipegang oleh masing-masing proses.
Need[n][m] = Max[n][m] - Allocation[n][m]: Matriks sisa kebutuhan sumber daya yang mungkin diminta lagi oleh proses hingga selesai.

              Kaidah Keselamatan (Safety Algorithm):

              Cari proses $P_i$ yang belum selesai (Finish[i] == false) dengan kebutuhan Need[i] <= Work.

              Jika ditemukan: asumsikan proses $P_i$ berjalan hingga selesai lalu mengembalikan seluruh alokasinya: Work = Work + Allocation[i] dan Finish[i] = true.

              Jika seluruh proses berhasil diselesaikan (semua Finish == true), maka urutan eksekusi tersebut disebut Safe Sequence dan alokasi disetujui tanpa resiko deadlock!