Prediksi CPU Burst Time untuk sebuah proses di SJF

Algoritma SJF adalah salah satu algoritma penjadwalan terbaik karena memberikan throughput maksimum dan waktu tunggu minimal tetapi masalah dengan algoritma ini adalah waktu ledakan CPU tidak dapat diketahui sebelumnya.

Kami dapat memperkirakan waktu ledakan CPU untuk suatu proses. Ada berbagai teknik yang dapat digunakan untuk mengasumsikan waktu Burst CPU untuk suatu proses. Asumsi kami harus akurat untuk memanfaatkan algoritme secara optimal.

Ada teknik berikut yang digunakan untuk asumsi waktu ledakan CPU untuk suatu proses.

1. Teknik Statis

Ukuran Proses

Kita dapat memprediksi Burst Time proses dari ukurannya. Jika kita memiliki dua proses T_OLD dan T_New dan waktu burst sebenarnya dari proses lama dikenal sebagai 20 detik dan ukuran prosesnya adalah 20 KB. Kita tahu ukuran P_NEW adalah 21 KB. Maka kemungkinan P_New memiliki waktu ledakan yang sama dengan 20 detik adalah maksimum.

If,     P_OLD → 20 KB   

P_New → 21 KB   

BT(P_OLD) → 20 Secs  

Then,   

BT(P_New) → 20 secs  

Oleh karena itu, dalam teknik ini, kami benar-benar memprediksi waktu ledakan dari proses baru sesuai dengan waktu ledakan dari proses lama dengan ukuran yang sama dengan proses baru.

Jenis Proses

Kita juga bisa memprediksi waktu burst dari proses tersebut sesuai dengan jenisnya. Suatu Proses dapat dari berbagai jenis yang didefinisikan sebagai berikut.

Proses OS

Suatu Proses dapat menjadi proses sistem Operasi seperti penjadwal, kompiler, manajer program, dan banyak lagi proses sistem. Burst time mereka umumnya lebih rendah misalnya 3 sampai 5 satuan waktu.

Proses Pengguna

Proses yang dimulai oleh pengguna disebut proses pengguna. Ada tiga jenis proses sebagai berikut.

Proses Interaktif

Proses Interaktif adalah proses yang berinteraksi dengan pengguna dari waktu ke waktu atau Eksekusi yang sepenuhnya bergantung pada input Pengguna, misalnya berbagai game adalah proses tersebut. Waktu burst harus lebih rendah karena mereka tidak membutuhkan CPU untuk waktu yang lama, mereka terutama bergantung pada interaktivitas pengguna dengan proses sehingga mereka terutama adalah proses yang terikat IO.

Proses latar depan

Proses latar depan adalah proses yang digunakan oleh pengguna untuk melakukan kebutuhan mereka seperti MS office, Editor, perangkat lunak utilitas, dll. Jenis proses ini memiliki waktu burst yang sedikit lebih tinggi karena merupakan perpaduan sempurna antara proses terikat CPU dan IO.

Proses latar belakang

Proses latar belakang mendukung pelaksanaan proses lainnya. Mereka bekerja dalam mode tersembunyi. Misalnya, key logger adalah proses yang merekam tombol yang ditekan oleh pengguna dan aktivitas pengguna pada sistem. Mereka sebagian besar adalah proses yang terikat CPU dan membutuhkan CPU untuk waktu yang lebih lama. 

2. Teknik Dinamis

Rata-rata Sederhana

Dalam rata-rata sederhana, diberikan daftar n proses P(i).......P(n). Misalkan T(i) menunjukkan waktu ledakan dari proses P(i). Biarkan τ(n) menunjukkan waktu ledakan yang diprediksi dari proses Pth. Kemudian menurut rata-rata sederhana, perkiraan waktu ledakan proses n+1 akan dihitung sebagai,

τ(n+1) = (1/n) ∑ T(i)

Di mana, 0<=i<=n dan ∑ T(i) adalah penjumlahan waktu burst sebenarnya dari semua proses yang tersedia hingga saat ini.

Rata-Rata Eksponensial atau Penuaan

Misalkan, Tn adalah waktu burst aktual dari proses ke-n.τ(n) adalah waktu burst yang diprediksi untuk proses ke-n, maka waktu burst CPU untuk proses berikutnya (n+1) akan dihitung sebagai, 

τ(n+1) = α. Tn + (1-α) . τ(n)  

Dimana, α adalah smoothing. Nilainya terletak antara 0 dan 1.

Algoritma Penjadwalan Shortest Remaining Time First (SRTF). 

Algoritma ini adalah versi preemptive dari penjadwalan SJF. Dalam SRTF, eksekusi proses dapat dihentikan setelah waktu tertentu. Pada kedatangan setiap proses, penjadwalan jangka pendek menjadwalkan proses dengan sisa waktu burst paling sedikit di antara daftar proses yang tersedia dan proses yang sedang berjalan.

Setelah semua proses tersedia dalam ready queue, Tidak ada preemption yang akan dilakukan dan algoritma akan bekerja sebagai penjadwalan SJF. Konteks proses disimpan di Blok Kontrol Proses saat proses dihapus dari eksekusi dan proses selanjutnya dijadwalkan. PCB ini diakses pada eksekusi berikutnya dari proses ini.

Contoh

Dalam Contoh ini, ada lima pekerjaan P1, P2, P3, P4, P5 dan P6. Waktu kedatangan dan waktu burst mereka diberikan di bawah ini dalam tabel.

Bagan Gantt disiapkan sesuai dengan waktu kedatangan dan ledakan yang diberikan dalam tabel.

• Karena, pada waktu 0, satu-satunya proses yang tersedia adalah P1 dengan waktu ledakan CPU 8. Ini adalah satu-satunya proses yang tersedia dalam daftar sehingga dijadwalkan.
• Proses selanjutnya tiba pada unit waktu 1. Karena algoritma yang kita gunakan adalah SRTF yang merupakan preemptive, eksekusi saat ini dihentikan dan penjadwal memeriksa proses dengan waktu burst paling sedikit.
• Hingga saat ini, ada dua proses yang tersedia dalam ready queue. OS telah mengeksekusi P1 untuk satu unit waktu sampai sekarang; sisa waktu ledakan P1 adalah 7 unit. Waktu ledakan Proses P2 adalah 4 unit. Karenanya Proses P2 dijadwalkan pada CPU sesuai dengan algoritme.
• Proses selanjutnya P3 tiba pada unit waktu 2. Pada saat ini, eksekusi proses P3 dihentikan dan proses dengan sisa waktu burst paling sedikit dicari. Karena proses P3 memiliki 2 satuan burst time maka akan diprioritaskan dibanding yang lain.
• Proses Selanjutnya P4 tiba pada unit waktu 3. Pada kedatangan ini, penjadwal akan menghentikan eksekusi P4 dan memeriksa proses mana yang memiliki waktu burst paling sedikit di antara proses yang tersedia (P1, P2, P3 dan P4). P1 dan P2 memiliki sisa waktu ledakan masing-masing 7 unit dan 3 unit.
• P3 dan P4 memiliki sisa waktu ledakan masing-masing 1 unit. Karena keduanya sama maka penjadwalan akan dilakukan sesuai dengan waktu kedatangan mereka. P3 tiba lebih awal dari P4 dan karenanya akan dijadwalkan lagi.
• Proses Selanjutnya P5 tiba di unit waktu 4. Hingga saat ini, Proses P3 telah menyelesaikan eksekusinya dan tidak ada lagi dalam daftar. Penjadwal akan membandingkan waktu burst yang tersisa dari semua proses yang tersedia. Karena waktu ledakan proses P4 adalah 1 yang paling sedikit di antara semuanya maka ini akan dijadwalkan.
• Proses Selanjutnya P6 tiba pada unit waktu 5, sampai saat ini Proses P4 telah menyelesaikan eksekusinya. Kami memiliki 4 proses yang tersedia hingga saat ini, yaitu P1 (7), P2 (3), P5 (3) dan P6 (2). Burst time P6 adalah yang paling sedikit di antara semuanya sehingga P6 dijadwalkan. Karena sekarang semua proses tersedia maka algoritma sekarang akan bekerja sama seperti SJF. P6 akan dieksekusi sampai selesai dan kemudian proses dengan sisa waktu paling sedikit akan dijadwalkan.

Setelah semua proses tiba, Tidak ada preemption yang dilakukan dan algoritme akan berfungsi sebagai SJF.

GATE SRTF 2011 Contoh

Jika kita berbicara tentang algoritma penjadwalan dari sudut pandang GATE, mereka umumnya menanyakan pertanyaan numerik sederhana tentang menemukan waktu tunggu rata-rata dan Waktu Penyelesaian. Mari kita bahas pertanyaan yang diajukan di GATE 2011 tentang SRTF.

Q. Diketahui waktu kedatangan dan burst time dari 3 pekerjaan pada tabel di bawah ini. Hitung rata-rata waktu tunggu sistem.

Ada tiga pekerjaan P1, P2 dan P3. P1 tiba pada satuan waktu 0; itu akan dijadwalkan pertama untuk waktu sampai proses selanjutnya tiba. P2 tiba pada 1 satuan waktu. Waktu ledakannya adalah 4 unit yang paling sedikit di antara pekerjaan dalam antrean. Oleh karena itu akan dijadwalkan selanjutnya.

Pada saat 2, P3 akan tiba dengan waktu ledakan 9. Karena sisa waktu ledakan P2 adalah 3 unit yang paling sedikit di antara pekerjaan yang tersedia. Karenanya prosesor akan melanjutkan eksekusinya hingga selesai. Karena semua pekerjaan sudah sampai jadi tidak ada preemption yang dilakukan sekarang dan semua pekerjaan akan dilaksanakan sampai selesai menurut SJF.

Avg Waiting Time = (4+0+11)/3 = 5 units

Algoritma Penjadwalan Round Robin

Algoritma penjadwalan Round Robin adalah salah satu algoritma penjadwalan paling populer yang sebenarnya dapat diimplementasikan di sebagian besar sistem operasi. Ini adalah versi preemptive dari penjadwalan first come first serve. Algoritma berfokus pada Time Sharing. Dalam algoritma ini, setiap proses dieksekusi secara siklik. Irisan waktu tertentu ditentukan dalam sistem yang disebut kuantum waktu. Setiap proses yang ada dalam antrian siap diberi CPU untuk kuantum waktu itu, jika eksekusi proses selesai selama waktu itu maka proses akan berhenti jika tidak, proses akan kembali ke antrian siap dan menunggu giliran berikutnya selesai. eksekusi.

Keuntungan

Ini sebenarnya bisa diimplementasikan dalam sistem karena tidak tergantung pada waktu burst.

Itu tidak menderita masalah kelaparan atau efek konvoi.

Semua pekerjaan mendapatkan alokasi tarif CPU.

Kekurangan

Semakin tinggi kuantum waktu, semakin tinggi waktu respons dalam sistem.

Semakin rendah time quantum, semakin tinggi context switching overhead dalam sistem.

Memutuskan kuantum waktu yang sempurna benar-benar merupakan tugas yang sangat sulit dalam sistem.

Contoh Penjadwalan RR

Dalam contoh berikut, ada enam proses yang dinamai P1, P2, P3, P4, P5 dan P6. Waktu kedatangan dan waktu burst mereka diberikan di bawah ini dalam tabel. Kuantum waktu sistem adalah 4 satuan.

Menurut algoritme, kita harus mempertahankan ready queue dan Gantt chart. Struktur kedua struktur data tersebut akan diubah setelah setiap penjadwalan.

Antrean Siap:

Awalnya, pada waktu 0, proses P1 tiba yang akan dijadwalkan untuk pembagian waktu 4 unit. Oleh karena itu dalam ready queue, hanya akan ada satu proses P1 yang dimulai dengan CPU burst time 5 unit.

Grafik GANTT

P1 akan dieksekusi untuk 4 unit terlebih dahulu.

Antrian Siap

Sementara eksekusi P1, empat proses lagi P2, P3, P4 dan P5 tiba di ready queue. P1 belum selesai, perlu 1 unit waktu lagi maka akan ditambahkan kembali ke ready queue.

Antrian Siap

Selama eksekusi P2, satu lagi proses P6 tiba di ready queue. Karena P2 belum selesai maka P2 juga akan ditambahkan kembali ke ready queue dengan sisa burst time 2 unit.

Antrian Siap

Karena P3 sudah selesai, maka akan dihentikan dan tidak ditambahkan ke ready queue. Proses selanjutnya yang akan dijalankan adalah P4.

Antrian Siap

Proses selanjutnya dalam ready queue adalah P5 dengan 5 satuan burst time. Karena P4 selesai maka tidak akan ditambahkan kembali ke antrian.

Bagan GANTT

Proses P1 akan diberikan giliran berikutnya untuk menyelesaikan eksekusinya. Karena hanya membutuhkan 1 unit burst time maka akan selesai.

Antrian Siap

P1 selesai dan tidak akan ditambahkan kembali ke ready queue. Proses selanjutnya P6 hanya membutuhkan 4 unit burst time dan akan dieksekusi selanjutnya.

Antrian Siap

Karena P6 sudah selesai, maka tidak akan ditambahkan lagi ke antrian. Hanya ada dua proses yang ada dalam ready queue. Proses Selanjutnya P2 hanya membutuhkan 2 satuan waktu.

Antrian Siap

Sekarang, satu-satunya proses yang tersedia dalam antrian adalah P5 yang membutuhkan 1 unit waktu burst. Karena time slice adalah 4 unit maka akan selesai pada burst berikutnya.

Waktu penyelesaian, waktu penyelesaian dan waktu tunggu akan dihitung seperti yang ditunjukkan pada tabel di bawah ini.

Seperti yang kita tahu,

Waktu Berbalik = Waktu Penyelesaian - Waktu Kedatangan

Waktu Tunggu = Waktu Berputar - Burst Time

Jangan lupa untuk terus berkunjung dan mengikuti update terbarunya dari blog arahinfotech.com, Oh iya lupa, jika Sahabat memiliki tips-tips yang lebih bagus dari tips di atas, boleh dituliskan dimari caranya kelik menu bar lalu kelik kerja sama scrool kirim artikel. Selain itu juga, mohon dishare ketemen-temen atau keluarga jika memang artikel ini sangatlah bermanfaat untuk Sahabat.**

Berbagi :