Penjadualan pada prosesor

Posted: 25 October 2010 in terbaik

Penjadualan Pada Prosesor Tunggal

sebelum kita membahas masalah penjadualan pada prosesor tunggal kita harus tau mengapa dalam prosesor tunggal harus ada penjadualannya?

– Supaya setiap proses dapat dilayani secara adil

– Agar tidak terjadi starvation

– Supaya efisien dalam penggunaan waktu prosesor

– Agar dapat meminimalkan terjadinya overhead

– Supaya response time dapat terpenuhi

– Supaya dapat memaksimalkan throughput .

• Jenis-jenis penjadualan

– Penjadualan jangka panjang (long-term)

✔     Adalah keputusan untuk menambah suatu proses ke kelompok proses yang akan dieksekusi

✔     Terjadi pada saat suatu proses baru diciptakan (lokasinya masih di dalam harddisk)

✔     Frekuensi dilakukannya lebih jarang daripada medium-term scheduling

✔     Membuat perkiraan kasar (coarse-grained) dalam menambahkan suatu proses

– Penjadualan jangka menengah (medium-term)

✔  Adalah keputusan untuk menambahkan sejumlah proses (sebagian atau seluruhnya) ke dalam main memory

✔  Terjadi pada saat swapping

✔  Keputusan untuk melakukan swapping menentukan derajat multiprogramming

✔  Freku dibahas pada materi tentang Proses, Manajemen memori, dan Memori virtual

– Penjadualan jangka pendek (short-term)

✔  Adalah keputusan untuk memilih proses mana yang akan dieksekusi diantara sejumlah proses yang sudah siap dieksekusi

✔  Sangat sering dilakukan Disebut juga dispatcher (yang bertugas untuk mengirimkan job)

✔  Membuat perkiraan halus (fine-grained) dalam memutuskan proses yang akan dieksekusi

– Short-term scheduling dilakukan bila terjadi event seperti

misalnya: Clock interrupts, I/O interrupts Signals (misal: semaphore), Pemanggilan ke sistem operasi (system call)

– Penjadualan I/O

✔  Keputusan untuk memilih proses mana yang akan diberi kesempatan untuk menggunakan I/O device diantara sejumlah proses yang sama-sama akan menggunakan I/O device tersebut

✔  Dibahas pada materi Manajemen I/O

– Letak penjadualan

✔              Letak penjadualan pada status proses

✔  tingkatan penjadualan

Penjadualan pada diagram antrian

• Algoritma penjadualan

– Kriteria penjadualan jangka pendek (short-term)

✔  Ada 4 macam kriteria penjadualan jangka pendek:

✗  User-oriented : Karakteristik sistem dilihat dari sudut pandang user atau proses

✗  System-oriented : Karakteristik sistem dilihat dari sisi efektifitas dan utilitas penggunaan prosesor

✗  Performance-related : Karakteristik sistem dinilai dengan menggunakan parameter yang kuantitatif (terukur)

✗  Not-performance-related : Karakteristik sistem dinilai dengan menggunakan parameter yang kualitatif (tidak dapat diukur dan dianalisis)

✔  Kombinasi kriteria penjadualan yang dapat terjadi:

✗  User-oriented, Performance-related.

✗  User-oriented, Not-performance-related.

✗  System-oriented, Performance-related.

✗  System-oriented, Not-performance-related.

✔  Parameter pada User oriented, Performance related .

✗  Turnaround time: Merupakan interval waktu sejak suatu proses masuk ke sistem hingga selesai dieksekusi.

✗  Response time: Adalah waktu yang diperlukan sejak suatu permintaan (request) dikirimkan oleh suatu proses hingga response terhadap request tersebut diperoleh Merupakan parameter yang lebih baik dibanding turnaround time dari sisi user

Contoh:

Suatu sistem interaktif dirancang dapat memberikan layanan yang baik bagi user bila response time-nya tidak lebih dari 2 detik. Maka tugas utama scheduling adalah memaksimalkan jumlah user yang menerima response time rata-rata 2 detik atau kurang

✗  Deadline: Merupakan batas akhir suatu proses sudah harus selesai Proses yang sudah mendekati deadline lebih diutamakan, agar prosentase pemenuhan deadline dapat diperoleh secara maksimal .

✔  Parameter pada User oriented, Non- performance related

✗  Predictability: Layanan terhadap user dari waktu ke waktu tetap sama dan tidak terpengaruh dengan apa yang dilakukan oleh sistem Sebuah job akan dieksekusi dalam periode yang relatif sama dan dengan biaya yang sama tanpa dipengaruhi kondisi beban sistem Jika waktu eksekusi dan biaya yang diperlukan berubah-ubah akan membingungkan user, sehingga kestabilan sistem rendah

✔  Parameter pada System oriented, Performance related

✗  Throughput: Adalah jumlah proses yang dapat diselesaikan dalam periode waktu tertentu Semakin banyak semakin baik Nilainya bergantung pada panjang proses rata-rata  dan metode scheduling yang digunakan

✗  Processor utilization: Merupakan prosentase waktu dimana prosesor sibuk Nilainya sangat berarti pada shared system . Nilainya kurang penting pada sistem user tunggal (misal sistem real-time)

✔  System oriented, Non-performance related

✗  Fairness: Adalah nilai ‘keadilan’ (kesetaraan) perlakuan sistem scheduling terhadap setiap proses, agar tidak terjadi starvation

✗  Enforcing priorities: Scheduling harus lebih mengutamakan proses yang mempunyai prioritas lebih tinggi

✗  Balancing resources: Scheduling harus dapat menjaga keseimbangan dalam penggunaan resource .

– Penjadualan dengan prioritas

✔  Setiap proses diberi nomor prioritas yang nilainya dapat sama atau berbeda

✔  Scheduler selalu memilih proses yang mempunyai prioritas paling tinggi

✔  Digunakan beberapa antrian untuk menangani antrian proses dengan prioritas berbeda-beda

✔  Proses dalam antrian dengan prioritas lebih rendah baru akan dieksekusi jika semua proses dalam antrian yang lebih tinggi telah dieksekusi

✔  Nomor prioritas:

✗  Pada sistem Unix semakin tinggi angka prioritas, maka prioritasnya semakin rendah. Prioritas nomor 0 merupakan prioritas tertinggi

✗  Pada sistem Windows berlaku kebalikannya

✗  Dalam perkuliahan ini digunakan penomoran prioritas model Unix

✔  Kelemahan model prioritas:

✗    Proses dengan prioritas rendah dapat mengalami starvation

✗    Solusi: Prioritas suatu proses dapat berubah berdasarkan waktu atau history-nya .

Antrian prioritas:

✔  Pada gambar di atas hanya digambarkan sebuah blocked queue

– Penjadualan alternatif

Parameter-parameter pada penjadualan alternatif

✔  Selection function

✗  Decision mode: Nonpreemptive , Preemptive

✗  Service time

✗  Turnaround Time (TAT)

✗  Normalized Turnaround Time (NTAT)

✗  Selection function

✗  Decision mode

✔  First-Come-First-Served (FCFS)

✗  Algoritma

– Proses yang datang pertama yang dieksekusi

– Proses yang berada di antrian ready paling lama yang dieksekusi

✗  Disebut juga algoritma FIFO (First In First Out)

✗  Kelebihan:

(+) Merupakan metode scheduling paling sederhana

(+) Overhead kecil

(+) Dapat mencegah starvation

✗  Karakteristik FCFS

✗  w = waktu untuk menunggu

✗  Kekurangan:

(-) Proses yang pendek dapat dirugikan, bila urutan eksekusinya setelah proses yang panjang

(-) FCFS cenderung menguntungkan proses processor-bound dibanding proses I/O-bound

Solusi: gabungkan dengan model prioritas

✔  Round Robin (RR)

✗  Algoritma:

– Eksekusi proses diatur berdasarkan alokasi waktu tertentu (slot waktu) yang diatur dengan clock interrupt .

✗  Clock interrupt terjadi secara periodik

✗  Setiap satu slot waktu mempunyai ukuran yang sama (disebut teknik time slicing)

✗  Bila terjadi clock interrupt, maka:

– Proses yang sedang running dimasukkan ke dalam antrian ready

– Proses di antrian ready paling depan dieksekusi

✗  Karakteristik RR

✗  Kekurangan:

(-) Performansinya lebih buruk dibanding FCFS jika ukuran slot lebih besar daripada ukuran

proses terbesar.

(-) Dapat terjadi overhead berlebihan jika ukuran setiap slot (slice) terlalu kecil (lihat

halaman selanjutnya)

(-) Proses I/O bound mendapatkan waktu layanan lebih sedikit

Solusi:

Round robin dimodifikasi menjadi Virtual Round Robin (VRR) dengan menambahkan sebuah antrian yang  disebut antrian auxiliary

✗  Kelebihan Round Robin:

(+) Dapat menghindari ketidakadilan layanan terhadap proses kecil seperti yang terjadi pada

FCFS

(+) Response time lebih cepat untuk proses berukuran kecil

(+) Dapat mencegah starvation

(+) Overhead kecil, jika ukuran proses rata-rata lebih kecil dibanding ukuran quantum/slot

✔  Shortest Process Next (SPN)

✗  Algoritma:

Eksekusi proses diatur berdasarkan perkiraan ukuran proses terkecil

Proses yang datang belakangan langsung berada pada antrian proses terdepan bila ukurannya paling kecil

✗  Kelebihan:

(+) Dapat mencegah kerugian yang dialami proses kecil seperti pada FCFS

(+) Throughput tinggi

(+) Proses kecil mempunyai response time kecil

✗  Kekurangan:

(-) Scheduler harus mengetahui/memperkirakan ukuran setiap proses yang akan dieksekusi

(-) Proses besar dapat mengalami starvation

(-) Overhead bisa tinggi

✗  Karakteristik SPN

✔  Shortest Remaining Time (SRT)

Algoritma:

✗  Eksekusi proses diatur berdasarkan perkiraan sisa waktu terkecil

✗  Proses yang baru masuk dapat langsung  dieksekusi bila total waktu eksekusinya lebih kecil daripada sisa waktu proses yang  sedang running

✔  Merupakan model preemptive-nya SPN

✔  Kapan pemilihan proses yang akan ndieksekusi dilakukan ?

– Bila ada proses baru yang masuk, atau

– Bila proses yang sedang running telah selesai

✗  Kekurangan:

(-) Terjadi overhead akibat scheduler harus menghitung/memperkirakan sisa waktu eksekusi

setiap proses untuk menentukan sisa waktu yang terkecil

(-) Dapat terjadi starvation pada proses yang panjang

(-) Proses yang panjang dikalahkan oleh proses yang kecil

✗  Kelebihan:

(+) Kualitas layanan rata-rata yang diterima proses lebih baik (jumlah proses yang

memperoleh nilai NTAT = 1 lebih banyak)

(+) Throughput tinggi

(+) Response time cepat

✔  Highest Response Ratio Next (HRRN)

✔  Feedback (FB)

– Perbandingan performansi

✔  Analisis antrian

✔  Model Simulasi

– Penjadualan fair-share

✔  User’s application runs as a collection  of processes (threads)

✔  User is concerned about the  performance of the application

✔  Need to make scheduling decisions  based on process sets
Traditional UNIX Scheduling

✗  Multilevel feedback using round robin within each of the priority queues

✗  If a running process does not block or  complete within 1 second, it is  preempted

✗  Priorities are recomputed once per  second

✗  Base priority divides all processes into fixed bands of priority levels

✔  Bands

✗  Decreasing order of priority

– Swapper

– Block I/O device control

– File manipulation

– Character I/O device control

– User processes

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s