faktor apa saja yang harus diperhatikan untuk melakukan schedulling pada sistem multiprocessors dan...

EDI SISWANTO 115090607111035 SISTEM OPERASI ‘A’TUGAS PERTEMUAN 10 DAN 11

faktor apa saja yang harus diperhatikan untuk melakukan schedulling pada sistem multiprocessors dan bagaimana melakukan schedulling pada sistem multiprocessors

Multiprocessor adalah kondisi sebuah sistem komputer memiliki lebih dari 1 prosesor. Multiprocessor juga membutuhkan Scheduling dan juga membutuhkan penjadwalan yang lebih rumit karena mempunyai banyak kemungkinan yang dicoba tidak seperti pada uniprocessor.

Dalam Multiprocessor Scheduling, tiap proses dapat mengakses memori dengan cara yang sama [uniform memory access]. Multiprocessor scheduling membutuhkan penjadualan yang lebih rumit karena mempunyai banyak kemungkinan yang akan terjadi bila dibandingkan dengan processor tunggal.

Pembatasan dalam Scheduling tersebut juga terjadi dalam multiprosesor. Hal ini disebabkan karena:

Kemungkinan adanya load sharing. Load sharing terjadi jika ada beberapa prosesor yang identik. Untuk mengatasi hal itu maka tiap prosesor memiliki kemampuan penjadwalan mandiri (self schedulling).

Kemungkinan terlewatinya sebuah proses dari antrian [ready queue] atau beberapa prosesor memilih untuk mengeksekusi proses yang sama. permasalahan seperti itu bisa dijawab dengan sebuah master-slave structure, yaitu suatu struktur dimana satu prosesor ditunjuk sebagai master. Master inilah yang akan bertanggung jawab dalam hal penjadwalan, memproses I/O, dan sebagainya. Sedangkan prosesor yang lain [slave] hanya bertugas untuk mengeksekusi user code. Hal ini disebut juga sebagai Asymmetric Multiprocessing karena hanya satu prosesor yang dapat mengakses struktur data dari sistem.

Macam-macam sistem multiprocessor : Loosely Coupled or distributed multiprocessor, or cluster : terdiri dari beberapa system

yang relatif otonom, setiap prosesor memiliki main memory sendiri dan I/O channels. Functionally specialized processor : terdapat master, general-purpose processor dan

specialozed processor dikendalikan oleh processor matster. Tightly couple multiprocessor : terdiri dari satu set processor yang membagi main

memory dan berada di bawah kendali integrasi pada sebuah sistem operasi.

Granularity adalah sebuah cara karakteristik multiprosesor dan menempatkanya dalam sebuah konteks dengan arsitektur lain demi mempertimbangkan granularitas sinkronisasi, atau frekuensi sinkronisasi, antara proses dalam suatu sistem.

Independent Parallelis dengan independent parallelism, tidak ada eksplisit sinkronisasi antara proses. Masing-masing mewakili aplikasi, terpisah atau berdiri sendiri. kebiasaan umum yang digunakan dari tipe parallelisme adalah sistem time-sharing.

Ada beberapa jenis dari sistem Multiprocessor Scheduling, Tapi disini hanya fokus pada processor yang homogen (sama) sesuai dengan fungsi masing-masing dari processor tersebut, serta dapat menggunakan processor yang tersedia untuk menjalankan proses didalam antrian, yaitu :

1. Asymmetric MultiProcessing Scheduling (AMP)Asymmetric Multiprocessing, atau AMP adalah pengganti sementara perangkat lunak untuk menangani beberapa,CPU sebelum Symmetric Multiprocessing atau SMP yang


tersedia. Pendekatan pertama untuk penjadwalan multiprosessor adalah penjadwalan asymmetric multiprocessing atau biasa disebut juga sebagai penjadwalan Master Slave MultiProcessor. Dimana pada metode ini satu prosesor bertindak sebagai master dan prosesor lainnya sebagai slave. Master Processor bertugas untuk menjadwalkan dan mengalokasikan proses yang akan dijalankan oleh Slave Processors.Master Processor melakukan pekerjaan yang berhubungan dengan System, Slave Processor melayani user requests dalam pengeksekusian program. Pemrosesan yang banyak tidak menyebabkan penurunan performance. Metode ini sederhana karena hanya satu prosesor yang mengakses struktur data sistem dan juga mengurangi data sharing. Sebagai contoh, prosesor master memilih proses yang akan dieksekusi, kemudian mencari prosesor yangavailable, dan memberikan instruksi start processor. Prosesor slavememulai eksekusi pada lokasi memori yang dituju. Saat slavemengalami sebuah kondisi tertentu, prosesor slave memberi interupsi kepada prosesor master dan berhenti untuk menunggu perintah selanjutnya. Perlu diketahui bahwa prosesor slave yang berbeda dapat ditujukan untuk suatu proses yang sama pada waktu yang berbeda. Master processor dapat mengeksekusi OS dan menangani I/O, sedangkan sisanya processor tidak punya kemampuan I/O dan disebut sebagai Attached Processor (Aps). APs mengeksekusi kodekode user dibawah pengawasan master processor.

2. Symmetric MultiProcessing Scheduling (SMP) Dalam system MultiProcessing ini, setiap prosesor menjadwalkan dirinya sendiri. Setiap prosesor memeriksa ready queue dan memilih proses yang akan dieksekusi. Penjadwalan terlaksana dengan menjadwalkan setiap prosesor untuk memeriksa antrian ready dan memilih suatu proses untuk dieksekusi. Jika suatu sistem Multiprocessor Scheduling mencoba untuk mengakses dan mengupdate suatu struktur data, penjadwal dari prosesor-prosesor tersebut harus diprogram dengan hati-hati, kita harus yakin bahwa dua prosesor tidak memilih proses yang sama dan proses tersebut tidak hilang dari antrian.

Penjadwalan Proses (CPU) Dalam Multiprogramming.

Penjadwalan CPU berhubungan dengan masalah penentuan proses dalam antrian yang akan diberikan CPU. Terdapat beberapa algoritma penjadwalan yang dapat digunakan, masing-masing dengan sifat-sifat khasnya sendiri. Dalam memilih algoritma yang akan dipakai dapat digunakan bermacam kriteria untuk membandingkan suatu algoritma dengan algoritma yang lain.

Kriteria yang digunakan dalam perbandingan dapat menyebabkan perbedaan dalam penentuan algoritma yang akan dipilih. Kriteria-kriteria tersebut meliputi:

Pemanfaatan CPU. Biaya CPU yang mahal menuntut pemakai untuk selalu memberikan pekerjaan kepada CPU sehingga kalau dimungkinkan maka dibuat kondisi yang sedemikian rupa dimana CPU tidak memiliki waktu luang. Dalam sistem susungguhnya, pemanfaatan CPU berkisar antara 40% sampai 90%.

Throughput. Untuk mengukur beban pekerjaan CPU, salah satu cara adalah dengan menghitung jumlah job yang diselesaikan setiap satuan waktu tertentu, yang disebut Throughput. Untuk job yang lama, kecepatannya mungkin satu job per jam, sedangkan untuk transaksi pendek dapat mencapai 10 job per detik.

Turnaround Time. Dari sudut pandang suatu job, mungkin yang paling penting adalah lamanya waktu penyelesaian job itu. Selang waktu dari saat penyerahan job sampai


waktu penyelesaian disebut Turnaround Time, yang meliputi juga waktu tunggu untuk memasuki memori, waktu tunggu di antrian, pengerjaan di CPU, dan pelaksanaan proses I/O.

Waiting Time (Waktu Tunggu). Sebagai alternatif Turnaround Time, dapat digunakan Waktu Tunggu di antrian untuk setiap job. Waktu Tunggu ini tidak termasuk waktu pelaksanaan tugas I/O.

Response Time (Waktu Tanggap). Seringkali suatu proses dapat mengeluarkan hasil yang relatif lebih cepat daripada waktu penyelesaian proses tersebut. Bersamaan dengan pengeluaran itu, proses tersebut dapat melanjutkan perhitungan hasil baru selanjutnya. Waktu yang dihitung sejak mulai dari penyerahan suatu permintaan sampai respons (tanggapan) pertama diperoleh pemakai tersebut Response Time.

Lima buah algoritma yang akan ditelaah untuk penjadwalan CPU, antara lain:1. First Come First Serve (FCFS).

Algoritma ini merupakan algoritma yang paling sederhana. Proses yang meminta CPU lebih dulu akan dilayani CPU lebih dahulu pula. Implementasi FCFS mudah diatur dengan antrian FIFO (First In First Out). Ketika proses memasuki antrian, proses ini disambungkan dengan ekor dari antrian dan menjadi ekor yang baru. Jika CPU sedang bebas tugas, maka CPU akan dialokasikan untuk proses yang berada di awal antrian. Proses tersebut lalu dikeluarkakn dari antrian.

2. Shortest Job First (SJF). Shortest Job First menelaah setiap job berdasarkan lamanya waktu CPU untuk

pengerjaan proses berikutnya. Ketika CPU siap dipakai, maka akan diberikan kepada job yang memiliki waktu pengerjaan paling sedikit. Jikaa dua job mempunyai waktu pengerjaan yang sama, FCFS digunakan, berarti yang datang lebih dulu akan dilayani. Shortest Job First telah terbukti optimal dalam hal perolehan waktu tunggu rata-rata yang paling minimum dari beberapa job. Keadaan ini dicapai dengan memindahkan job pendek dalam antrian sebelum job yang panjang sehingga mengurangi waktu tunggu job pendek lebih banyak daripada penambahan waktu tunggu dari job panjang.

Kesulitan dengan Shortest Job First adalah dalam hal yang berkaitan dengan penentuan lamanya pengerjaan job yang masuk berikutnya. Salah satu cara yaitu dengan mendorong pemilik job tertama untuk job panjang) agar memperkirakan lamanya waktu yang dibutuhkan untuk menyelesaikan jobnya.

3. Shortest Remaining Time First (SRTF). Algortima penjadwalan ini hampir serupa dengan Shortest Job First, tetapi

berbeda dalam hal penambahan metode penundaan job. Dalam SJF job yang sudah masuk ke dalam CPU jika ada job dalam antrian yang memiliki waktu penyelesaian yang lebih kecil. Algoritma SRTF adalah algoritma Preemptive, yaitu algoritma dimana job-job yang sedang dijalankan secara logik dapat ditunda untuk sementara waktu untuk memberikan kesempatan waktu CPU kepada job-job lainnya. Jadi, dari luar sistem job-job tersebut tampak seolah-seolah sedang dikerjakan bersama-sama.

4. Round Robin. Algoritma Penjadwalan Round Robin sebetulnya dirancang untuk sistem Time-

sharing, dimana job-job diberikan satuan waktu yang sama, disebut Time Quantum ini berkisar antara 10 sampai 100 milidetik. Queue (Antrian) dibuat secara sirkular kemudian skeduler akan mengelilingi antrian ini sambil mengalokasikan CPU kepada setiap


proses/job selama waktu quantum tadi. Implementasi penjadwalan Round Robin dilakukan dengan antrian FIFO. Job baru ditambahkan ke ekor antrian. Job di kepala antrian dikirim ke CPU, setelah itu ada dua kemungikinan, waktu proses job kurang dari waktu quantum, ataupun lebih dari waktu quantum. Dalam kemungkinan pertama, job sendiri yang meninggalkan CPU sebelum waktunya habis. Sedangkan kemungkinan kedua, job akan dikeluarkan oleh sistem operasi dari CPU dan diletakkan di akhir (ekor) antrian.

5. Preemptive Priority. Harus diperhatikan bahwa penjadwalan selalu dikelola dengan prioritas, baik

rendah ataupun tinggi. Job dengan prioritas yang sama ada dalam penjadwalan FCFS. Algoritma penjadwalan Shortest Job First adalah bentuk khusus dari penjadwalan Prioritas yang umum karena SJF dapat dijalankan dengan prioritas menurut nilai yang dihitung dari kebalikan (perkirakan) waktu penyelesaian job.

Prioritas-prioritas biasanya dalam bentuk bilangan yang telah ditetapkan sebelumnya. Walaupun demikian masih belum ada kesepakatan apakah suatu angka kecil memang menunjukkan prioritas yang rendah. Prioritas dapat dihitung baik secara ienternal maupun eksternal. Prioritas yang terdefinisi secara internal menggunakan ukuran kuantitas, seperti batas waktu, kebutuhan memori, jumlah file yang dibukanya, ataupun perbandingan antara waktu I/O dengan waktu CPU, dan lain-lain. Prioritas eksternal ditentukan oleh kriteria di luar sistem operasi, misalnya jumlah iuran yang dibayar untuk pemakaian komputer, bagian yang mensponsori kerja, bahkan mungkin saja faktor-faktor politis juga.

Masalah utama dengan algoritma preemtive priority adalah penahanan (blocking) takterbatas atau lebih dikenal starvation. Starvation muncul jika suatu job telah siap untuk dijalankan (sedang menunggu CPU) tetapi tidak pernah diberi kesempatan untuk menyelesaikan jobnya karena prioritasnya rendah. Pemecahan masalah ini adalah Aging (untuk selanjutnya disebut pemetaan). Pemetaan adalah teknik yang menaikkan secara berkala prioritas job yang sudah lama menunggu di dalam sistem. Misalnya untuk kisaran prioritas antara 0 (rendah) sampai 127 (tinggi), prioritas job yang menuggu dapat dinaikkan 1 setiap 15 menit . Sehingga walaupun prioritas job semula adalah 0, namun suatu saat mampu pula mencapai prioritas tertinggi dan akhirnya dijalankan oleh CPU. Walaupun sesungguhnya suatu sistem dapat memiliki beberapa buah CPU, dalam pembahasan selanjutnya untuk penyederhanaan hanya akan disediakan satu CPU untuk pengerjaan beberapa job.

Terdapat 4 pendekatan bagaimana menjalankan program-program dalam komputer multiprosesor:

Load sharing : berbagi beban, semua program diantrikan dalam antrian, prosesor yang menganggur akan mengambil antrian terdepan dan menjalankannya.

Gang schedulling : sekumpulan thread yang saling terkait diantrikan pada sekumpulan prosesor pada saat yang sama, satu thread satu prosesor.

Dedicated prosesor assignment : pada sebuah program diberikan sejumlah rosesor sebanyak thread yang ada dalam program itu

Dynamic scheduling : jumlah thread yang diaktifkan dari suatu program dapat diubah-ubah.

Dalam pendekatan loadsharing terdapat pilihan berikut:


First come first served : thread-thread dari job yang datang diantrikan dalam antrian bersama. Prosesor menganggur akan memanggil thread terdepan.

Smallest number of thread first : ada antrian sesuai prioritas.prioritas tertinggi diberikan pada program dengan jumlah thread terkecil.

REAL-TIME SCHEDULING

Real time scheduling dapat diartikan sebagai penjadwalan proses dalam komputer yang mempunyai waktu deadline sehingga dapat lebih jelas kapan dia harus selesai memproses. Pada real-time setiap tugas di asosiasikan sejumlah batas waktu tertentu. Nah, tugas ini dibagi menjadi dua, yaitu:

Hard real-time systems Task kritis harus selesai dengan garansi waktu tertentu. OS akan melacak lamanya task tersebut dieksekusi (real time), yaitu untuk :

mengetahui lama waktu system call, fungsi dan response dari hardware; untuk melakukan prediksi apakah task tersebut dapat dijalankan.

Mudah dilakukan untuk OS khusus pada pemakaian khusus. Sulit untuk time-sharing sistem.

Soft real-time systems Membutuhkan penggunaan skema prioritas Multimedia, highly interactive graphics Prioritas tidak menurunkan over time.

Real Time Scheduling juga memiliki beberapa algoritma penjadwalan, adapun algoritmanya : Clock-driven

Pada clock-driven scheduling ini terdapat bagian yang menunjuk waktu penjadwalan yang disebut “scheduling desicion time” fungsingya untuk menentukan prioritas dalan suatu proses, penjadwalan dilakukan secara langsung dan pada waktu tertentu. Clock-driven biasanya digunakan pada hard real-time sistem.

Weighted round-robinMerupakan algoritma kelanjutan dari algoritma round robin ( RR ). Fungsinya untuk penjadwalan real – time traffic berkecepatan tinggi.

Priority drivenPriority-driven (algoritma yang mengutamakan prioritas untuk menyelesaikan suatu proses yang dieksekusi). Dalam sistem non real time, berbagai faktor dapat digunakan untuk menentukan prioritas. Dalam sistem real time , prioritas tugas terkait dengan kendala waktu terkait dengan tiap tugas.

Cara menjadwalkan program-program dalam sistem tersebut : Static table driven approaches : di jalankan analisis statis dari tugas-tugas yang sedang

antri, deadline mana yang terdekat, itu yang dijadwalkan dahulu. Program baru, jika datang pada saat jadwal dijalankan, akan diperhatikan untuk jadwal berikutnya.

Static priority driven preemptive approaches : tugas-tugas diprioritaskan berdasarkan batasan waktu. Pada saat dijalankan, jika ada tugas dengan prioritas lebih tinggi, tugas yang sedang dijalankan dapat dihentian.


Dynamic planning based approaches : tugas-tugas sudah direncanakan untuk dijalankan, hanya jika ada tugas baru datang dan memngkinkan untuk dijalankan, maka akan diterima untuk dijalankan.

Dynamic best effort scheduling, Penjadwalan yang sering digunakan oleh real time systems. Pada penjadwalan ini, ketika proses tiba maka akan dieksekusi tergantung dari prioritas masing-masing proses dan pengerjaannya terdapat batas waktu

faktor apa saja yang harus diperhatikan untuk melakukan schedulling pada sistem multiprocessors dan...

Documents