schedule

5/12/2018 Schedule - slidepdf.com

http://slidepdf.com/reader/full/schedule-55a35d3d5a014 1/11

5.6.6 Multilevel Feedback Queue Scheduling

Algoritma penjadwalan Multilevel Feedback Queue ini hampir sama dengan algoritma penjadwalan

multilevel queue, hanya saja suatu proses yang berada pada satu queue dapat berpindah ke queue lain.

Jika suatu proses akan menggunakan CPU dalam waktu yang cukup lama, maka proses tesebut dapat

berpindah ke queue dengan prioritasnya yang lebih rendah. Sebaliknya, jika suatu proses terlalu lama

menunggu pada prioritas yang lebih rendah, maka proses tersebut dapat berpindah ke queue dengan prioritas yang lebih tinggi.

Sebagai contoh, jika ada 3 queue (0, 1, dan 2) seperti terlihat pada Gambar 5.3. Scheduler pertama

kali akan mengeksekusi semua proses pada queue-0. Eksekusi akan berpindah ke queue-1 hanya jika

queue-0 dalam keadaan kosong. Demikian juga, eksekusi akan berpindah ke queue-2 hanya jika

queue-1 dalam keadaan kosong. Jika suatu proses ada di queue-0 dengan quantum time 8 ms. Proses

tersebut belum terselesaikan selama quantum time tersebut, maka proses akan berpindah ke ekor dari

queue-1. Pada saat queue-0 kosong, maka eksekusi akan berpindah ke queue-1 dengan quantum time

16. Demikian seterusnya.

Gambar 5.3 Multilevel Feedback Queue Scheduling

Parameter-parameter yang dibutuhkan oleh algoritma ini adalah sebagai berikut:

a. Jumlah queue;

b. Algoritma penjadwalan untuk tiap-tiap queue;

c. Metode yang diperlukan untuk menentukan kapan suatu proses akan diupgrade ke queue

dengan prioritas yang lebih tinggi;

d. Metode yang diperlukan untuk menentukan kapan suatu proses akan diturunkan ke queue

dengan prioritas yang lebih rendah; e. Metode yang diperlukan untuk menentukan letak queue, jika ada suatu proses yang akan

dilayani.

5.6.7 Guaranteed Scheduling

Algoritma penjadwalan harus menjamin bahwa algoritma tersebut mempunyai kinerja yang

cukup bagus dan menjanjikan kelangsungan hidup (masa depan) yang baik. Salah satu contoh

: misalkan ada n user yang sedang login, maka tiap-tiap user dijanjikan akan menerima 1/n

dari kemampuan CPU.



Untuk meyakinkan bahwa setiap user mendapatkan jatah waktu menggunakan CPU sesuai

dengan haknya, maka sistem harus tahu berapa CPU time yang diperlukan oleh setiap proses

dalam satu user , dan juga CPU time yang diperlukan oleh tiap-tiap user . Misalkan ada 5 user

(A, B, C, D, dan E) seperti terlihat pada tabel 5.1.

Tabel 5.1 CPU time untuk 5 user

User CPU Time (ms)

A 5

B 4

C 8

D 1

E 2

Total waktu yang dibutuhkan untuk mengakses kelima user tersebut adalah 20 ms. Sehingga

diharapkan tiap user mendaptkan 20/5 = 4 ms. Pada kenyataannya, mulai dari login hingga

saat ini, tiap-tiap user telah mendapatkan CPU seperti terlihat pada Tabel 5.2, dan rasio antara

CPU yang diperoleh sampai saat ini (aktual) dengan CPU yang seharusnya diperoleh (4 ms)dapat dicari.

Tabel 5.2 CPU yang telah diperoleh untuk 5 user

User CPU Aktual (ms) Rasio

A 3 3/4 = 0.75

B 6 6/4 = 1.5

C 2 2/4 = 0.5

D 1 1/4 = 0.25

E 1 1/4 = 0.25

Dari tabel 5.2 dapat dilihat bahwa user A memiliki rasio 0.75, artinya A baru mendaptkan ¾

dari jatah waktu yang harusnya diterima. User B memiliki rasio 1.5, artinya telah

mendapatkan 1.5 waktu dari yang seharusnya ia dapatkan. Algoritma ini kemudian akan

menjalankan proses dengan rasio yang paling rendah terlebih dahulu hingga proses tersebut

mendapatkan rasio melebihi rasio proses yang sebelumnya punya rasio satu tingkat lebih

tinggi darinya.

Dengan cara ini juga suatu proses yang butuh waktu 10 detik akan mendapatkan prioritas

yang lebih tinggi dibandingkan dengan proses yang butuh waktu 10 menit.

5.6.8 Policy ver su s Mechani sm

Adakalanya suatu proses akan melahirkan beberapa proses yang lainnya. Proses-proses yang

dilahirkan ini dibawah kontrol proses penciptanya. Sebagai contoh, suatu data base

management system proses akan memiliki beberapa anak (children). Tiap-tiap anak mungkin

akan bekerja atas permintaan yang berbeda (menjalankan fungsi-fungsi yang berbeda).

Sayangnya, tak ada satupun algoritma penjadwalan di atas yang meminta pertimbangan dari



user , semuanya diputuskan oleh scheduler . Sehingga pada akhirnya scheduler -lah yang

memberikan pilihan terbaik.

Solusinya, pada policy vs mechanism disini diijinkan untuk memberikan kebijakan, kontrol

dan prioritas pada suatu child sedangkan mekanisme penjadwalan itu sendiri tetap diserahkan

pada kernel.

5.6.9 Two-level Scheduling

Sebelumnya telah diasumsikan bahwa semua proses yang siap dieksekusi diletakkan pada

memori utama. Jika memori utamanya tidak cukup, maka ada beberapa proses yang harus

ditempatkan di disk. Hal ini akan menyebabkan banyak waktu terbuang hanya untuk

switching . Salah satu cara untuk mengatasi hal ini adalah dengan menggunakan two-level

scheduling . Himpunan bagian dari proses-proses yang telah siap dieksekusi diload ke memori

utama (Gambar 5.4a.) Scheduler hanya memilih proses -proses pada himpunan bagian ini

untuk dieksekusi. Secara periodis, higher-level scheduler mengganti proses yang telah lama

tinggal di memori utama dengan proses-proses yang sudah cukup lama menuggu di disk.

Proses-proses di

memori utama

Proses-proses

di disk

(a) (b) (c)

Gambar 5.4 T wo-level scheduler

5.7 Implementasi Penjadwalan Prosesor

Andaikan diketahui 2 prosedur, yaitu Prosedur A dan Prosedur B. Kedua prosedur tersebut digarap

oleh satu prosesor.

Diketahui x dan y adalah variabel global ( atau shared variable). Bahwa, baik secara serial (2

prosedur dikerjakan oleh 1 prosesor), atau secara paralel (masing-masing prosedur dikerjakan oleh 2

A B

C D

E F

G H

B C

F G

E F

G H

A B

C D

A D

E H

??????????????????????????????????????????????????????????????????????????



prosesor), persoalannya adalah menetukan prosedur yang mana dulu yang harus dikerjakan. Salah

satu pendekatan yang bisa dikerjakan adalah memilih prosedur yang menulis suatu variabel harus

dikerjakan terlebih dahulu. Artinya, sebelum prosesor-1 menulis x, maka prosesor-2 tidak boleh

membaca x, dan juga sebaiknya.

Untuk itu perlu dibuat semacam ³ Procedure of Procce sse s´. Salah satu model yang dapat digunakan

dalam procedure of proccesses adaalah ³ Procedence Graph́ . Secara formal yang disebut dengan procedence graph didefinisikan sebagai :

P = {Pi | l i n} yang disebut himpunan proses.

< = {(pi, p j) | l i, j n} disebut pasangan berurutan pada p.

= (P, <.) disebut sebagai komputasi.

(pi, p j) berarti proses p j tidak akan dikerjakan sebelum proses pi selesaidikerjakan. Procedence graph

tidak dapat menggambarkan adanya looping. Bentuk procedence graph dari Prosedur A dan Prosedur

B terlihat pada Gambar 5.5

Dari procendence graph ini, maka yang dimaksud dengan komputasi adalah :

= [(p11, p12, p13, p14, p21, p22, p23, p24), {(p11, p12), (p12, p13), (p12, p21), (p21, p22), (p22, p23), (p23, p14),

(p13, p14), (p23, p24)}]



Untuk melakukan looping : (p1, p2), (p2, p3), (p3, p4) ..., (pn, pl) tidak dapat dilakukan dengan

menggunakan procedence graph. Contoh lain, suatu Prosedur C :

Procedure C ( )

{

x = 5; ---------------- p1

y = x+7; ---------------- p2

a = x=y; ---------------- p3

b = y=2; ---------------- p4

c = a-b; ---------------- p5

w = c-1; ---------------- p6

}

Bentuk procedence graphnya terlihat pada Gambar 5.6

Cara lain untuk menggambarkan procedure of proccesses adalah dengan mneggunakan ³ Petri Net ́ .

Petri Net adalah suatu graph yang berisi 2 himpunan simpul yang salah satunya meggambarkan

proses, dan yang lain menggambarkan transisi dari suatu proses ke proses berikutnya. Proses yang

sudah selesai ditandai dengan adanya token pada transisi.



Bentuk Petri Net Prosedur C terlihat pada Gambar 5.7.

Bentuk Petri Net dari prosedur A dan Prosedur B adalah

Untuk memprogram pada multiprosesor antara lain dapat dikerjakan dengan operasi : ³ FORK , JOIN ,

dan QUI T ́ .

FORK (LabelX), pernyataan untuk membangun proses yang baru (mengaktifkan prosesor lain) dan

mengerjakannya dimulai dari statemen yang diberi label LabelX

J OIN (Cacah), pernyataan untuk menggabungkan kembali beberapa proses menjadi sebuah proses

tunggal. Variabel cacah menunjukkan berapa kali perintah JOIN dikerjakan. Setiap kali JOIN

dieksekusi, secara otomatis nilai cacah akan berkurang satu.

QU IT ( ), pernyataan untuk keluar dari eksekusi (selesai).

Contoh penggunaan operasi FORK , JOIN , dan QUI T pada prosedur A dan prosedur B adalah :

Procedure A&B :

while true

{

cacah = 1;

<hitung p11>;

??????????????????????????????????????????????????????????/

??????????????????????????????????????????????????????????/



<hitung p12>;

FORK (L1);

<hitung p13>;

L2 : JOIN (cacah);

<hitung p14>;

QUI T ( );

L1: <hitung p21>;

<hitung p22>;

<hitung p23>;

FORK (L3);

GOTO (L2);

L3 : <hitung p24>;

QUI T ( );

}

Contoh lain, suatu Prosedur D :

Prosedur D ( )

{

while true

{

y = 5; -------------- p1

a = y*2; -------------- p2

r = y-20; -------------- p3

s = y-1; -------------- p4

b = r*s; -------------- p5

c = a-b; -------------- p6

w = c-1; -------------- p7

}



Bentuk procedence graphnya terlihat pada Gambar 5.9.

FORK hanya bisa menjadikan 1 kali proses baru, sehingga jika ingin lebih dari 1 proses baru, perlu

bantuan dummy node.

Dengan operasi FORK , JOIN, dan QUI T pada Prosedur A dan Prosedur B, adalah :

Procedure D :

while true

{

cacah = 2;

<hitung p1>;

FORK (L1);

<hitung p2>;

L3 : JOIN (Cacah);

<hitung p6>;

<hitung p7>;

QUI T ( );

L1 : FORK (L2);

<hitung p3>;

L4 : JOIN (Cacah);

<hitung p5>;

GOTO (L3);

L2 : <hitung p4>;

GOTO (L4);

}

??????????????????????????????????????????????????????????/



Selain itu ada operasi ³ ( PARBEGIN , PAREND)´ dan operasi ³ AND´. Statemen PARBEGIN dan

PAREND mengapit proses-proses yang dapat dikerjakan secara paralel. Statemen AND terletak di

antara 2 proses yang dapat diparalel.

Pada Prosedur D terlihat :

(1) Dengan (PARBEGIN, PAREND) :

while true

{

y = 5;

PARBEGIN

a = y*2;

PARBEGIN

r = y+20;

s = y-1;

PAREND;

b = r*s;

PAREND;

c = a-b;

w = c+1;

}

(2) Dengan AND :

while true

{

y = 5;

a = y*2;

AND

{

r = y+20;

AND

s = y-1;

b = r*s;

}

c = a-b;



w = c+1;

}

5.8 Implementasi Penjadwalan Multiprosesor

Diketahui suatu komputasi :

= (P, <.), { (pi) | pl ¼ P}

P = {pi | 1 | 7}

<. = {(p1, p3), (p2, p3), (p3, p4), (p5, p6), (p5, p7)}

= {(p1, 2), (p2, 1), (p3, 2), (p4,1), (p5, 2), (p6, 4), (p3, 1)}

Misalkan jumlah CPU sama dengan 2, maka gant chart -nya adalah :

Alternatif-1 :

CPU-1

CPU-2

Alternatif-2 :

Pada kedua gant chart dapat disimpulkan bahwa komputasi akan selesai setelah 7 satuan waktu.

Ada suatu algoritma yang mengasumsikan bahwa waktu yang diperlukan oleh setiap proses adalah

sama . Jika ada proses yang mempunyai waktu yang tidak sama, maka proses tersebut dapat dipecah

menjadi beberapa subproses yang masing-masing memiliki waktu yang sama. Algoritma tersebut

P1 P3 P4 P7

P2 P5 P6

??????????????????????????????????????????????????????????/



sering dikenal dengan nama ³ Tree Algorit ma´. Algoritma ini akan lebih jelas melalui contoh berikut

:

Misalkan terdapat komputasi :

P = { pi | 1 i 12}

<. = {(p1, p7), (p2, p7), (p3, p8), (p4, p8), (p5, p10), (p6, p10), (p7, p10), (p8, p11), (p9, p11), (p10, p12),

(p11, p12)}

= {(pi, 1) | 1 i 12}

Algoritma :

1. Tentukan semua proses yang dapat dikerjakan secara paralel.

2. Dari hasil pada langkah-1, tentukan proses yang mempunyai jarak maksimum ke proses yang

ada pada posisi akar.

3. Secara bebas, tentukan CPU untuk mengerjakan proses-proses dari hasil langkah-2.

4. Ulangi langkah-2 sampai semua proses selesai dikerjakan (jangan lupa memperhatikan

procedence graphnya).

Misalkan jumlah CPU sama dengan 3, maka gant chart -nya adlaah :

Sehingga waktu yang dibutuhkan untuk menjalankan keduabelas proses tersebut adalah sebesar 5

satuan waktu.

P1 P4 P7 P10 P12

P2 P5 P8 P11

P3 P6 P9

??????????????????????????????????????????????????????????/

schedule

Documents