iSIOMAS
Vina's daddy

Soal 3.34

Misal satu set yang terdiri dari empat buah task dengan parameter seperti pada tabel di bawah. Dengan menggunakan algoritma IRIS1, tentukan parameter-parameter dan gambarkan diagramnya.

Task number mi oi ri Di
1 2* 4 0 10
2 1 2 0* 12
3 2* 3 1 15
4 6 3* 2 18*

* = berubah dari soal

Jawab:

Mengacu kepada algoritma IRIS1 1), maka pertanyaan pertama (langkah 1) adalah apakah task-task dalam schedule ini dapat dikerjakan atau tidak (feasible atau not feasible). Sesuai dengan ketentuan algoritma EDF, apabila Utilitas > 1 maka dikatakan not feasible 2). Untuk itu ditinjau dari waktu eksekusi:

e1 = 2 + 4 = 6
e2 = 1 + 2 = 3
e3 = 2 + 3 = 5
e4 = 6 + 3 = 9

Totalnya adalah 23 satuan waktu, sementara deadline adalah 18. Dari sini dapat diambil kesimpulan bahwa schedule ini tidak feasible, karena waktu eksekusi melebihi deadline dan utilitasnya > 1. Diagram St0 dapat dilihat pada gambar.

Selanjutnya masuk ke langkah ke-2, mencari task M untuk mencari schedule Sm, yaitu M1, M2, M3, M4 dan M5. Diagram Sm dapat dilihat pada gambar.

Setelah itu masuk langkah ke-3, diperoleh:

a0 = 0
a1 = 2
a2 = 3
a3 = 5
a4 = 11
dan k = 4

Pada loop pertama (yaitu pada j = k-1 = 3), T4 pada St0 adalah 4 satuan waktu sedangkan T4 pada Sm adalah 6 satuan waktu, berarti Lmj > Ltj dan harus dimodifikasi. Yaitu porsi T4 sebesar 6 – 4 = 2 dipindah pada interval [a3, a4]. Hasilnya adalah seperti terlihat pada gambar St1. Kemudian pada loop ke-2, yaitu pada interval [a2, a3], T3pada Sm adalah 2 sedangkan pada St0 adalah 5 (lebih kecil), maka tidak diperlukan modifikasi. Selanjutnya pada loop ke-3, yaitu pada interval [a1, a2], T2 pada Sm adalah 1 sedangkan pada St0 adalah 2 (lebih kecil), maka tidak diperlukan modifikasi. Terakhir yaitu pada loop ke-4, yaitu pada interval [a0, a1], T1 pada Sm adalah 2 sedangkan pada St0 adalah 6 (lebih kecil), maka tidak diperlukan modifikasi.

Berikut adalah gambar diagram lengkapnya:

Catatan tambahan: ri adalah release time dari task Ti , yaitu merupakan waktu dimana semua data yang diperlukan untuk memulaitask tersedia 3). Jadi dalam hal ini release time dari masing-masing task seperti pada tabel adalah semuanya terpenuhi.

Notes berikut adalah mengacu kepada buku “REAL-TIME SYSTEMS”, C.M. Krishna & Kang G. Shin, McGraw-Hill, 1997.

1) Halaman 99
2) Halaman 74
3) Halaman 41

Written by iQ on Thursday March 23, 2006
Permalink -

« Bridge, Switch dan Virtual LAN - Soal 3.20 »