Session 9 & Session 10

Session 9 & Session 10 (Scheduling)

Scheduling

A)   Perilaku Proses

  • Process-bound
  • I/O bound

Scheduling1

 

B)   CPU Scheduler

  • Memilih di antara proses-proses dalam memori yang siap untuk mengeksekusi, dan mengalokasikan CPU ke salah satu dari proses tersebut.
  • Keputusan CPU scheduling dapat terjadi ketika sebuah proses :
    1. Berpindah dari running ke waiting state.
    2. Berpindah dari running ke ready state.
    3. Berpindah dari waiting ke ready.
    4. Berakhir.
  • Scheduling dibawah 1 dan 4 adalah nonpreemptive.
  • Semua scheduling lainnya adalah preemptive.

C)   Jenis-Jenis Scheduler

  1. Long-term scheduling
    Keputusan untuk menambah sekelompok proses untuk dieksekusi.
  2. Medium-term scheduling
    Keputusan untuk menambah jumlah proses yang sebagian atau seluruhnya di dalam memori utama.
  3. Short-term scheduling
    Keputusan untuk proses yang tersedia akan dieksekusi oleh processor.
  4. I/O scheduling
    Keputusan untuk permintaan proses I/O yang tertunda harus ditangani oleh perangkat I/O yang tersedia.

D)   Scheduling dan Transisi Proses State

Scheduling2.1.png

 

E)   Long Term Scheduler

  • Menentukan program mana yang dimasukkan ke sistem untuk pengolahan.
  • Mengontrol tingkat multiprogramming.
    – Semakin banyak proses yang dibuat, semakin kecil persentase waktu yang dapat dieksekusi oleh setiap proses.
    – Dapat membatasi untuk memberikan pelayanan yang memuaskan pada sekumpulan proses saat ini.

Scheduling3

F)   Medium Term Scheduler

  • Bagian dari fungsi swapping.
  • Swapping didasarkan pada kebutuhan untuk mengelola tingkat multiprogramming.
  • Mempertimbangkan persyaratan memori dari proses swapped-out.

G)   Short Term Scheduler

  • Dikenal sebagai dispatcher.
  • Paling sering mengeksekusi.
  • Membuat keputusan fine-grained untuk proses yang mana yang akan dieksekusi selanjutnya.
  • Dipanggil ketika sebuah peristiwa terjadi yang dapat menyebabkan pemblokiran proses saat ini atau yang dapat memberikan kesempatan untuk mendahului proses yang sedang berjalan dalam mendukung yang lain.

Scheduling4

 

H)   Kriteria Short Term Scheduling

  • Tujuan utamanya adalah untuk mengalokasikan waktu prosesor untuk mengoptimalkan aspek-aspek tertentu dari perilaku sistem.
  • Seperangkat kriteria yang dibutuhkan untuk mengevaluasi kebijakan scheduling.

Scheduling5

 

I)   Dispatcher

  • Modul Dispatcher memberikan kontrol CPU ke proses yang dipilih oleh short-term scheduler. Ini melibatkan :
    1. Peralihan konteks.
    2. Beralih ke mode pengguna
    3. melompat ke lokasi yang tepat dalam program user untuk me-restart program tersebut.
  • Dispatch latency – waktu yang diperlukan untuk operator untuk menghentikan satu proses dan mulai menjalankan yang lainnya.

J)   Kriteria Scheduling

  • Utilisasi CPU – Menjaga CPU sesibuk mungkin.
  • Throughput – # dari proses yang menyelesaikan eksekusi per satuan waktu.
  • Turnaround time – jumlah waktu untuk mengeksekusi proses tertentu.
  • Waiting time – jumlah waktu dimana proses telah menunggu dalam antrian siap.
  • Response time – jumlah waktu yang dibutuhkan dari saat permintaan disampaikan hingga tanggapan pertama diproduksi, bukan hasil (untuk lingkungan time-sharing).

K)   Kriteria Optimization

  • Max CPU utilization
  • Max throughput
  • Min turnaround time
  • Min waiting time
  • Min response time

L)   Tujuan Scheduling

  1. All systems
    – Fairness – Memberikan setiap proses pembagian CPU yang adil.
    – Policy enforcement – Melihat bahwa kebijakan yang ditetapkan dilakukan.
    – Balance – Menjaga semua bagian dari sistem sibuk.
  2. Batch systems
    – Throughput – Memaksimalkan pekerjaan per jam.
    – Turnaround time – Meminimalkan waktu antara penyerahan dan penghentian.
    – CPU utilization – Menjaga CPU sibuk sepanjang waktu.
  3. Interactive systems
    – Response time – Menanggapi permintaan dengan cepat.
    – Proportionality – Memenuhi harapan pengguna.
  4. Real-time systems
    – Meeting deadlines –  Menghindari hilangnya data.
    – Predictability – Menghindari penurunan kualitas dalam sistem multimedia.

M)   Algoritma Batch Scheduling

  • First-Come First-Serve
    – Proses ditugaskan CPU dalam urutan sesuai dengan permintaan proses.
    * Keuntungan : Mudah dimengerti dan mudah diprogramkan.
    * Kerugian : Pekerjaan pendek mungkin akan menunggu terlalu lama jika pekerjaan panjang berada di depannya.
  • Contoh :
    Process  Burst Time
    P1              24
    P2              3
    P3              3

* Misalkan proses tiba dalam urutan: P1, P2, P3

Scheduling6

Gantt Chart untuk jadwal ini adalah:

* Waiting time untuk P1 = 0; P2 = 24; P3 = 27
* Rata-rata waiting time:  (0 + 24 + 27)/3 = 17

  • Shortest Job First
    – Penggabungan setiap proses, pecahan panjang CPU berikutnya. Gunakan panjang ini untuk menjadwalkan proses dengan waktu terpendek.- 2 skema :
    * Nonpreemptive – Sekali CPU diberikan ke proses, CPU tidak dapat didahului sampai pecahan CPU selesai.
    * Preemptive – Jika proses baru datang dengan panjang pecahan CPU lebih kecil dibandingkan waktu yang tersisa dari proses eksekusi saat ini, dahului. Skema ini dikenal sebagai Shortest-Remaining-Time-First (SRTF).- SJF adalah optimal – Memberikan minimum rata-rata waktu tunggu untuk sekelompok proses yang diberikan.
  • Shortest Job First –  Non Preemptive
    Process    Arrival Time   Burst Time
    P1                0.0                     7
    P2                 2.0                    4
    P3                  4.0                    1
    P4                  5.0                    4

    Scheduling7

*Average waiting time = (0 + 6 + 3 + 7)/4 = 4

  • Shortest Job First –  Preemptive
    Process    Arrival Time    Burst Time
    P1               0.0                      7
    P2                2.0                     4
    P3                4.0                     1
    P4                5.0                     4

Scheduling8
* Average waiting time = (9 + 1 + 0 +2)/4 = 3

 

 

*Session 10

Scheduling (2)

A)   Algoritma Interactive Scheduling

  • Round-robin scheduling
  • Virtual Round Robin scheduling
  • Shortest Process Next
  • Shortest Remaining Time Next
  • Highest Response Ratio Next
  • Feedback Scheduling
  • Guaranteed Scheduling
  • Fair Share Scheduling
  • Real Time Scheduling

B)   Round Robin Scheduling

  • Menggunakan preemption berdasarkan jam.
  • Juga dikenal sebagai time slicing karena setiap proses diberikan potongan waktu sebelum didahului.
  • Masalah desain utama adalah lamanya kuantum waktu, atau potongan waktu, untuk digunakan.
  • Sangat efektif dalam tujuan umum sistem time-sharing atau sistem pemrosesan transaksi.
  • Salah satu kelemahannya adalah perlakuan relatif dari processor-bound dan proses I/O bound.

Scheduling9.png

 

C)   Pengaruh Ukuran Preemption Kuantum Waktu

Scheduling10.1

 

D)   Virtual Round Robin

Scheduling11.1.png

 

E)   Shortest Process Next

  • Kebijakan nonpreemptive di mana proses dengan waktu pemrosesan terpendek yang diharapkan, dipilih berikutnya.
  • Sebuah proses singkat akan melompat ke bagian head antrian.
  • Kemungkinan terjadi starvation untuk proses yang lebih lama.
  • Salah satu kesulitannya adalah kebutuhan untuk tahu, atau setidaknya perkiraan, waktu proses yang dibutuhkan dari setiap proses.
  • Jika perkiraan programmer secara substansial di bawah waktu running yang sebenarnya, sistem dapat membatalkan pekerjaannya.

Scheduling12

 

F)   Shortest Remaining Time Next

  • Versi preemptive dari SPN.
  • Scheduler selalu memilih proses yang memiliki waktu proses tersisa terpendek yang diharapkan.
  • Risiko terjadi starvation dari proses yang lebih lama.
  • Harus memberikan kinerja turnaround time yang unggul ke SPN karena pekerjaan singkat diberikan preferensi langsung untuk pekerjaan running yang lebih lama.

Scheduling13

 

G)   Highest Response Ratio Next

  • Memilih proses berikutnya dengan rasio terbesar.
  • Menarik karena menghitung masa proses.
  • Saat pekerjaan yang lebih pendek diistimewakan, penuaan tanpa layanan meningkatkan rasio sehingga proses yang lebih lama akhirnya akan dapat melewati pekerjaan yang lebih pendek.

Scheduling14.png

 

Scheduling15.png

 

H)   Feedback Scheduling

Scheduling16.png

 

I)   Feedback Performance

Scheduling17.png

 

J)   Perbandingan Performance

  • Setiap disiplin penjadwalan yang memilih item berikutnya untuk dilayani independen dari waktu pelayanan, mematuhi hubungan:

Scheduling18

 

K)   Guaranteed Scheduling

  • Pada sistem user tunggal dengan n memproses running, masing-masing harus mendapatkan 1 / n dari siklus CPU.
  • Rasio 0,5 berarti bahwa proses hanya mempunyai setengah dari apa seharusnya dimiliki.
  • Rasio 2,0 berarti bahwa proses telah memiliki dua kali lebih banyak dari yang seharusnya.

L)   Fair Share Scheduling

  • Keputusan scheduling berdasarkan sekelompok proses.
  • Setiap user diberikan bagian dari prosesor.
  • Tujuannya adalah untuk memantau penggunaan untuk memberikan sumber daya yang lebih sedikit untuk user yang telah memiliki lebih dari fair share mereka dan lebih kepada mereka yang memiliki fair share yang lebih sedikit.
  • Memperhitungkan yang memiliki proses.
  • Setiap user dialokasikan beberapa pecahan dari CPU.
  • Jadi, jika 2 user telah dijanjikan 50% dari CPU, mereka masing-masing akan mendapatkannya, tidak peduli berapa banyak proses yang mereka miliki.
  • Contoh:
    Pengguna 1 memiliki 4 proses: A, B, C, DPengguna 2 memiliki 1 proses: EJika kedua user dijanjikan 50% dari waktu CPU, urutan scheduling yang mungkin akan menjadi :
    A E B E C E D E A E …jika user 1 berhak dua kali lebih banyak dari waktu CPU user 2, kita mungkin mendapatkan:
    A B E C D E A B E C D E …

M)   Real Time Scheduling

  • Sistem real-time yang schedulable.
  • Diberikan
    – m periodik event.
    – event i terjadi dalam periode Pi dan membutuhkan Ci detik.
  • Kemudian beban hanya dapat ditangani jika :
    Scheduling19
  • Contoh:
    Sebuah sistem real time yang soft dengan tiga periodik event, dengan periode 100, 200, dan 500 ms. Jika event ini membutuhkan 50, 30, dan 100 ms dari waktu CPU per event -> sistem ini schedulable karena :
    0.5 + 0.15 + 0.2 < 1

N)   Perbandingan Algoritma Scheduling

Scheduling20 Scheduling21 Scheduling22 Scheduling23
O)   Kebijakan vs Mekanisme

  • Pisahkan apa yang boleh dilakukan dengan bagaimana hal itu dilakukan.
    – sebuah proses tahu thread anak-anak mana yang penting dan membutuhkan prioritas.
  • Algoritma Scheduling diparameterkan.
    – mekanisme di kernel.
  • Parameter diisi oleh proses user.
    – kebijakan ditetapkan oleh proses user.

P)   Thread Scheduling

Scheduling24

(a) kemungkinan scheduling thread user-level dengan proses kuantum 50-msec dan thread yang berjalan 5 msec per pecahan CPU.

Scheduling25

(b) Kemungkinan scheduling thread kernel-level dengan karakteristik yang sama seperti (a).

 

 

 

 

Reference :

www.skyconnectiva.com
www.binus.ac.id

Leave a Reply

Your email address will not be published. Required fields are marked *