Manajemen Proses: Sinkronisasi dan Penjadwalan

Sinkronisasi Sistem Operasi

Akses pada suatu data oleh beberapa proses secara bersamaan dapat mengakibatkan inkonsistensi nilai pada data (race condition). Konsistensi data dapat diperoleh dengan menerapkan mekanisme yang menjamin urutan eksekusi yang kooperatif.

Sinkronisasi bertujuan untuk menjaga konsistensi data dengan mengatur urutan eksekusi proses-proses yang mengakses atau memanipulasi data bersama (shared data).

Permasalahan Critical Section

Setiap proses memiliki segmen yang disebut critical section, yaitu bagian kode yang mengakses atau memanipulasi data bersama. Jika beberapa proses menjalankan critical section secara bersamaan, terjadi race condition dan inkonsistensi data. Solusi critical section harus memenuhi 3 syarat:

1. Mutual Exclusion: Jika satu proses sedang di critical section, tidak ada proses lain yang dapat masuk ke critical section mereka.
2. Progress: Jika tidak ada proses di critical section dan ada proses yang ingin masuk, pemilihan proses berikutnya tidak boleh tertunda tanpa batas.
3. Bounded Waiting: Ada batasan waktu tunggu bagi setiap proses untuk memasuki critical section.

Solusi Permasalahan Critical Section

Beberapa metode untuk mengatasi masalah critical section:

1. Solusi Peterson: Menggunakan variabel int turn dan Boolean flag[2] untuk dua proses. Algoritma ini memastikan mutual exclusion, progress, dan bounded waiting.
2. Penggunaan Kunci (Lock): Proses mendapatkan kunci sebelum masuk critical section dan melepaskannya setelah selesai.

   do {
   acquire lock
   critical section
   release lock
   remainder section
   } while (TRUE);

3. Sinkronisasi Perangkat Keras: Menggunakan instruksi mesin atomic non-interruptible seperti tsl (test and set lock), tas (test and set), atau cs (compare and set) yang mengunci bus selama eksekusi.
4. Solusi dengan instruksi TestAndSet: Fungsi TestAndSet atomic yang mengubah nilai boolean target menjadi TRUE dan mengembalikan nilai lama.

   boolean TestAndSet (boolean *target)
   {
   boolean rv = *target;
   *target = TRUE;
   return rv;
   }

Semaphore

Semaphore adalah metode sinkronisasi yang tidak memerlukan busy waiting. Konsep ini menggunakan variabel integer S (semaphore) dan dua operator atomic:

• wait(S): Mengurangi nilai S. Jika S menjadi non-positif, proses di-blok.

  wait (S) {
  while S <= 0
  ; // no-op
  S--;
  }

• signal(S): Menaikkan nilai S.

Semaphore dibagi menjadi:

• Counting semaphore: Nilai integer tak terbatas.
• Binary semaphore (mutex locks): Nilai hanya 0 atau 1, lebih sederhana.

Implementasi semaphore tanpa busy waiting menggunakan antrian tunggu (waiting queue) dan operasi block() serta wakeup().

Deadlock dan Starvation

• Deadlock: Situasi di mana dua atau lebih proses menunggu tanpa batas waktu karena saling memegang sumber daya yang dibutuhkan proses lain.
• Starvation: Situasi di mana satu proses tidak pernah mendapatkan sumber daya yang diminta atau tidak dapat menjalankan critical section-nya dalam waktu yang sangat lama.

Karakteristik Deadlock

Deadlock terjadi jika empat kondisi ini terpenuhi secara bersamaan:

1. Mutual exclusion: Hanya satu proses dapat menggunakan sumber daya pada satu waktu.
2. Hold and Wait: Proses memegang setidaknya satu sumber daya dan menunggu sumber daya tambahan yang dipegang proses lain.
3. No Preemption: Sumber daya hanya dapat dilepaskan oleh proses yang memegangnya setelah selesai tugas.
4. Circular Wait: Ada rantai melingkar proses di mana setiap proses menunggu sumber daya yang dipegang oleh proses berikutnya dalam rantai.

Penanganan Deadlock

1. Mencegah deadlock (dengan memastikan salah satu dari 4 kondisi tidak terpenuhi).
2. Memungkinkan deadlock terjadi, lalu memulihkan (recovery).
3. Mengabaikan masalah (digunakan oleh sebagian besar OS seperti UNIX).

Penjadwalan

Penjadwalan CPU bertujuan untuk memaksimalkan utilitas CPU melalui multiprogramming, yaitu mengeksekusi beberapa proses secara bergantian dengan cepat. Penjadwal CPU memilih proses dari ready queue dan mengalokasikannya ke CPU.

Jenis Penjadwalan

1. Penjadwalan Non-Preemptive: Proses dieksekusi hingga selesai tanpa dapat disela. Terjadi pada peralihan status:
   • Berjalan (running) ke tunggu (waiting)
   • Selesai/berhenti (terminate)
2. Penjadwalan Preemptive: Proses yang sedang dieksekusi dapat disela oleh proses baru dengan ketentuan tertentu (misal: prioritas lebih tinggi). Terjadi pada peralihan status:
   • Berjalan (running) ke siap (ready)
   • Tunggu (waiting) ke siap (ready)

Kriteria Penjadwalan

1. CPU Utilization: Tingkat kesibukan CPU (dinyatakan dalam persen 0-100%). Penjadwalan optimal memaksimalkan nilai ini.
2. Throughput: Jumlah proses yang selesai per satuan waktu. Penjadwalan optimal memaksimalkan nilai ini.
3. Turnaround Time: Total waktu dari proses datang hingga selesai dieksekusi. Penjadwalan optimal meminimalkan nilai ini.
4. Waiting Time: Total waktu proses menunggu dalam ready queue. Penjadwalan optimal meminimalkan nilai ini.
5. Response Time: Waktu dari proses datang hingga respon pertama diterima/dihasilkan. Penjadwalan optimal meminimalkan nilai ini.

Algoritma Penjadwalan

1. First Come First Served (FCFS): Proses dieksekusi berdasarkan waktu kedatangan. Proses yang datang duluan dijalankan duluan.
2. Shortest Job First (SJF): CPU dialokasikan kepada proses dengan burst time (waktu eksekusi) terkecil berikutnya. Bisa Non-Preemptive atau Preemptive.
   • Preemptive SJF: Jika proses baru datang dengan burst time lebih pendek dari sisa waktu proses berjalan, proses berjalan disela.
3. Prioritas: CPU dialokasikan kepada proses dengan prioritas tertinggi. Bisa Non-Preemptive atau Preemptive.
   • Permasalahan: Starvation (proses prioritas rendah tidak pernah dieksekusi).
   • Solusi: Aging (prioritas proses ditingkatkan seiring waktu).
4. Round Robin (RR): Setiap proses mendapat jatah waktu CPU (time quantum), biasanya 10-100 milidetik. Setelah quantum habis, proses ditunda dan masuk kembali ke akhir ready queue.
   • Jika quantum terlalu besar, RR menyerupai FCFS.
   • Jika quantum terlalu kecil, terjadi overhead karena seringnya context switch.

Poin Penting

• Sinkronisasi diperlukan untuk mencegah inkonsistensi data akibat race condition dalam sistem operasi.
• Critical section adalah bagian kode yang mengakses data bersama, dan masuknya ke dalamnya harus diatur.
• Tiga syarat penyelesaian critical section adalah Mutual Exclusion, Progress, dan Bounded Waiting.
• Semaphore menggunakan nilai integer dan operasi wait() serta signal() untuk mengatur akses ke sumber daya, dengan implementasi waiting queue untuk menghindari busy waiting.
• Deadlock terjadi ketika empat kondisi (Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait) terpenuhi secara bersamaan.
• Starvation adalah kondisi di mana proses tidak pernah mendapatkan akses sumber daya. Aging dapat mengatasi ini dalam penjadwalan prioritas.
• Penjadwalan CPU bertujuan memaksimalkan CPU Utilization, Throughput, dan meminimalkan Turnaround Time, Waiting Time, Response Time.
• Algoritma penjadwalan utama meliputi FCFS, SJF, Prioritas, dan Round Robin, masing-masing memiliki karakteristik preemptive atau non-preemptive.

Tes Formatif 1 — Kegiatan Belajar 1

Tes Formatif 2 — Kegiatan Belajar 2