Rabu, 01 Juli 2009

Rangkuman SISTEM OPERASI Sem.4

I. Konsep Dasar Perangkat Komputer

Komponen utama Sistem Komputer :

· Para penggunaà (users) merupakan pihak yang memanfaatkan sistem komputer tersebut. Para pengguna di sini bukan saja manusia, namun mungkin berbentuk program aplikasi lain, ataupun perangkat komputer lain.

· Perangkat kerasà(hardware) ini berbentuk benda konkret yang dapat dilihat dan disentuh. Perangkat keras ini merupakan inti dari sebuah sistem, serta penyedia sumber-daya (resources) untuk keperluan komputasi

· Perangkat lunakà membantu para pengguna untuk memanfaatkan sumber-daya komputasi yang disediakan perangkat keras. Perangkat lunak secara garis besar dibagi lagi menjadi dua yaitu :

ü Program aplikasi : perangkat lunak yang dijalankan oleh para pengguna untuk mencapat tujuan tertentu

ü Sistem Operasi : Sistem Operasi berada di antara perangkat keras komputer dan perangkat aplikasinya

Pengertian dari Sistem Operasi dapat dilihat dari berbagai sudut pandang, yaitu :

· Dari sudut pandang pengguna, Sistem Operasi merupakan sebagai alat untuk mempermudah penggunaan komputer.

· Dari sudut pandang sistem, Sistem Operasi dapat dianggap sebagai alat yang menempatkan sumber-daya secara efisien (Resource Allocator). Sistem Operasi ialah manager bagi sumber-daya, yang menangani konflik permintaan sumber-daya secara efisien. Sistem Operasi juga mengatur eksekusi aplikasi dan operasi dari alat M/K (Masukan/Keluaran). Fungsi ini dikenal juga sebagai program pengendali (Control Program). Lebih lagi, Sistem Operasi merupakan suatu bagian program yang berjalan setiap saat yang dikenal dengan istilah kernel.

· Dari sudut pandang tujuan Sistem Operasi, Sistem Operasi dapat dipandang sebagai alat yang membuat komputer lebih nyaman digunakan (convenient) untuk menjalankan aplikasi dan menyelesaikan masalah pengguna. Tujuan lain Sistem Operasi ialah membuat penggunaan sumber-daya komputer menjadi efisien.

Dapat disimpulkan, bahwa Sistem Operasi merupakan komponen penting dari setiap sistem komputer.

Sejarah Perkembangan

Arsitektur perangkat keras komputer tradisional terdiri dari empat komponen utama yaitu :

  • Prosesor
  • Memori Penyimpanan
  • Masukan (Input)
  • Keluaran (Output)
  • Model

tradisional tersebut sering dikenal dengan nama arsitektur von-Neumann

Pada saat awal, komputer berukuran sangat besar sehingga komponen-komponennya dapat memenuhi sebuah ruangan yang sangat besar. Sang pengguna -- menjadi programer yang sekali gus merangkap menjadi menjadi operator komputer -- juga bekerja di dalam ruang komputer tersebut. Walaupun berukuran besar, sistem tersebut dikategorikan sebagai "komputer pribadi" (PC). Siapa saja yang ingin melakukan komputasi harus memesan/antri untuk mendapatkan alokasi waktu (rata-rata 30-120 menit).


Perkembangan Sistem Operasi dimulai dari sini, dengan memanfaatkan sistem batch (Gambar 1.4, “Bagan Memori Untuk Sistem Monitor Batch Sederhana”). Para operator mengumpulkan job-job yang mirip yang kemudian dijalankan secara berkelompok. Umpama, job yang memerlukan kompilator Fortran akan dikumpulkan ke dalam sebuah batch bersama dengan job-job lainnya yang juga memerlukan kompilator Fortran. Setelah sebuah kelompok job rampung, maka kelompok job berikutnya akan dijalankan secara otomatis.


Pada perkembangan berikutnya, diperkenalkan konsep Multiprogrammed System. Dengan sistem ini job-job disimpan di memori utama di waktu yang sama dan CPU dipergunakan bergantian. Hal ini membutuhkan beberapa kemampuan tambahan yaitu: penyediaan I/O routine oleh sistem, pengaturan memori untuk mengalokasikan memori pada beberapa Job, penjadwalan CPU untuk memilih job mana yang akan dijalankan, serta pengalokasian perangkat keras lain (Gambar “Bagan Memori untuk Model Multiprogram System”).


Perangkat Keras Komputer

1. Prosesor

Secara umum, sistem komputer terdiri atas CPU dan sejumlah perangkat pengendali yang terhubung melalui sebuah bus yang menyediakan akses ke memori. Umumnya, setiap device controller bertanggung-jawab atas sebuah hardware spesifik. Setiap device dan CPU dapat beroperasi secara konkuren untuk mendapatkan akses ke memori. Adanya beberapa hardware ini dapat menyebabkan masalah sinkronisasi. Karena itu untuk mencegahnya sebuah memory controller ditambahkan untuk

sinkronisasi akses memori.

2. Media Penyimpanan Utama

a. Register

Tempat penyimpanan beberapa buah data volatile yang akan diolah langsung di prosesor yang berkecepatan sangat tinggi. Register ini berada di dalam prosesor dengan jumlah yang sangat terbatas karena fungsinya sebagai tempat perhitungan/komputasi data.

b. Cache Memory

Tempat penyimpanan sementara (volatile) sejumlah kecil data untuk meningkatkan kecepatan pengambilan atau penyimpanan data di memori oleh prosesor yang berkecepatan tinggi. Dahulu cache disimpan di luar prosesor dan dapat ditambahkan. Misalnya pipeline burst cache yang biasa ada di komputer awal tahun 90-an. Akan tetapi seiring menurunnya biaya produksi die atau wafer dan untuk meningkatkan kinerja, cache ditanamkan di prosesor. Memori ini biasanya dibuat berdasarkan desain memori statik.

c. Random Access Memory

Tempat penyimpanan sementara sejumlah data volatile yang dapat diakses langsung oleh prosesor. Pengertian langsung di sini berarti prosesor dapat mengetahui alamat data yang ada di memori secara langsung. Sekarang, RAM dapat diperoleh dengan harga yang cukup murah dangan kinerja yang bahkan dapat melewati cache pada komputer yang lebih lama.

d. Memori Ekstensi

Tambahan memori yang digunakan untuk membantu proses-proses dalam komputer, biasanya berupa buffer. Peranan tambahan memori ini sering dilupakan akan tetapi sangat penting artinya untuk efisiensi. Biasanya tambahan memori ini memberi gambaran kasar kemampuan dari perangkat tersebut, sebagai contoh misalnya jumlah memori VGA, memori soundcard.

e. Direct Memory Access

Perangkat DMA digunakan agar perangkat M/K (I/O device) yang dapat memindahkan data dengan kecepatan tinggi (mendekati frekuensi bus memori). Perangkat pengendali memindahkan data dalam blok-blok dari buffer langsung ke memory utama atau sebaliknya tanpa campur tangan prosesor. Interupsi hanya terjadi tiap blok bukan tiap word atau byte data. Seluruh proses DMA dikendalikan oleh sebuah controller bernama DMA Controller (DMAC). DMA Controller mengirimkan atau menerima signal dari memori dan I/O device. Prosesor hanya mengirimkan alamat awal data, tujuan data, panjang data ke pengendali DMA. Interupsi pada prosesor hanya terjadi saat proses transfer selesai. Hak terhadap penggunaan bus memory yang diperlukan pengendali DMA didapatkan dengan bantuan bus arbiter yang dalam PC sekarang berupa chipset Northbridge.

3. Penyimpanan Sekunder

Media penyimpanan data yang non-volatile yang dapat berupa Flash Drive, Optical Disc, Magnetic Disk, Magnetic Tape. Media ini biasanya daya tampungnya cukup besar dengan harga yang relatif murah. Portability-nya juga relatif lebih tinggi.

4. Memori Tersier

Pada standar arsitektur sequential komputer ada tiga tingkatan utama penyimpanan: primer, sekunder, and tersier. Memori tersier menyimpan data dalam jumlah yang besar (terabytes, atau 1012 bytes), tapi waktu yang dibutuhkan untuk mengakses data biasanya dalam hitungan menit sampai jam. Saat ini, memori tersiser membutuhkan instalasi yang besar berdasarkan/bergantung pada disk

atau tapes. Memori tersier tidak butuh banyak operasi menulis tapi memori tersier tipikal-nya write ones atau read many. Meskipun per-megabites-nya pada harga terendah, memory tersier umumnya yang paling mahal, elemen tunggal pada modern supercomputer installations. Ciri-ciri lain: non-volatile, penyimpanan off-line , umumnya dibangun pada removable media contoh optical disk, flash memory.

5. Struktur Keluaran/Masukan (M/K)

Ada dua macam tindakan jika ada operasi M/K. Kedua macam tindakan itu adalah:

i. Setelah proses M/K dimulai, kendali akan kembali ke user program saat proses M/K selesai (Synchronous). Instruksi wait menyebabkan CPU idle sampai interupsi berikutnya. Akan terjadi Wait loop (untuk menunggu akses berikutnya). Paling banyak satu proses M/K yang berjalan dalam satu waktu.

ii. Setelah proses M/K dimulai, kendali akan kembali ke user program tanpa menunggu proses M/K selesai (Asynchronous). System call permintaan pada sistem operasi untuk mengizinkan user menunggu sampai M/K selesai. Device-status table mengandung data masukkan untuk tiap M/K device yang menjelaskan tipe, alamat, dan keadaannya. Sistem operasi memeriksa M/K device untuk mengetahui keadaan device dan mengubah tabel untuk memasukkan interupsi. Jika M/K device mengirim/mengambil data ke/dari memori hal ini dikenal dengan nama Direct Memory Access (DMA).

6. Bus

Untuk meningkatkan kinerja, digunakan beberapa buah bus. Tiap bus merupakan jalur data antara beberapa device yang berbeda. Dengan cara ini RAM, Prosesor, GPU (VGA AGP) dihubungkan oleh bus utama berkecepatan tinggi yang lebih dikenal dengan nama FSB (Front Side Bus). Sementara perangkat lain yang lebih lambat dihubungkan oleh bus yang berkecepatan lebih rendah yang terhubung dengan bus lain yang lebih cepat sampai ke bus utama. Untuk komunikasi antar bus ini digunakan sebuah bridge.

7. Interupsi

Kejadian ini pada komputer modern biasanya ditandai dengan munculnya interupsi dari software atau hardware, sehingga Sistem Operasi ini disebut Interrupt-driven. Interrupt dari hardware biasanya dikirimkan melalui suatu signal tertentu, sedangkan software mengirim interupsi dengan cara menjalankan system call atau juga dikenal dengan istilah monitor call. System/Monitor call ini akan menyebabkan trap yaitu interupsi khusus yang dihasilkan oleh software karena adanya masalah atau permintaan terhadap layanan sistem operasi. Trap ini juga sering disebut sebagai exception.

8. Local Area Network

Muncul untuk menggantikan komputer besar. Dirancang untuk melingkupi suatu daerah yang kecil.

Menggunakan peralatan berkecepatan lebih tinggi daripada WAN. Hanya terdiri atas sejumlah kecil

komputer.

9. Wide Area Network

Menghubungkan daerah yang lebih luas. Lebih lambat, dihubungkan oleh router melalui jaringan

data telekomunikasi.

Proteksi Perangkat Keras

Antaralain :

1. Proteksi Fisik

Proteksi fisik merupakan fungsi Sistem Operasi dalam menjaga, memproteksi fisik daripada sumberdaya (perangkat keras). Misal proteksi CUP dan proteksi hardisk. Contohnya adalah dalam kasus dual-mode operation (dibahas di sub-bab berikutnya).

2. Proteksi Media

Dalam keseharian kita ada beberapa jenis media yang digunakan untuk penyimpanan data, antara lain tape, disket, CD, USB flash disk, dan lainnya. Untuk menjamin keamanan data yang tersimpan dalam media-media tersebut, maka perlu sebuah mekanisme untuk menanganinya. Mekanisme proteksi antara satu media dengan media yang lain tidak sama. Umpamanya, media disket menggunakan katup yang dapat di geser. Jika katupnya dibuka maka disket bisa ditulis dan di baca, jika ditutup maka disket hanya bisa dibaca tetapi tidak bisa ditulis.

3. Konsep Mode Operasi Ganda

Membagi sumber daya sistem yang memerlukan Sistem Operasi untuk menjamin bahwa program yang salah tidak menyebabkan program lain berjalan salah juga. Menyediakan dukungan perangkat keras untuk membedakan minimal dua mode operasi yaitu: User Mode - Eksekusi dikendalikan oleh pengguna; Monitor/Kernel/System Mode - Eksekusi dikendalikan oleh Sistem Operasi. Instruksi tertentu hanya berjalan di mode ini (Privileged Instruction). Ditambahkan sebuah bit penanda operasi. Jika terjadi interrupt, maka perangkat keras berpindah ke monitor mode (Dual Mode Operation).

4. Proteksi Masukan/Keluaran

Semua instruksi masukan/keluaran umumnya Privileged Instruction (kecuali pada DOS, dan program tertentu). Harus menjamin pengguna program tidak dapat mengambil alih kontrol komputer di monitor mode.

5. Proteksi Memori

Harus menyediakan perlindungan terhadap memori minimal untuk interrupt vector dan interrupt service routine. Ditambahkan dua register yang menentukan di mana alamat legal sebuah program boleh mengakses, yaitu base register untuk menyimpan alamat awal yang legal dan limit register untuk menyimpan ukuran memori yang boleh diakses Memori di luar jangkauan dilindungi.

6. Proteksi CPU

Timer melakukan interrupt setelah perioda waktu tertentu untuk menjamin kendali Sistem Operasi. Timer diturunkan setiap clock. Ketika timer mencapai nol, sebuah Interrupt terjadi. Timer biasanya digunakan untuk mengimplementasikan pembagian waktu. Timer dapat juga digunakan untuk menghitung waktu sekarang walaupun fungsinya sekarang ini sudah digantikan Real Time Clock (RTC). System Clock Timer terpisah dari Pencacah Waktu. Timer sekarang secara perangkat keras lebih dikenal sebagai System Timer/CPU Timer. Load Timer juga Privileged Instruction.

II Konsep Dasar Sistem Operasi

Komponen Sistem Operasi

Sebuah sistem operasi dapat dibagi menjadi beberapa komponen. Secara umum, para pakar sepakat bahwa terdapat sekurangnya empat komponen manajeman utama yaitu:

• Manajemen Proses,

• Manajemen Memori, dan

• Manajamen Sistem Berkas.

• Manajemen Masukan/Keluaran

Selain keempat komponen di atas, Avi Silberschatz, dan kawan-kawan menambahkan beberapa komponen seperti:

• Manajemen Penyimpanan Sekunder.

• Manajemen Sistem Proteksi.

• Manajemen Jaringan.

• Command-Interpreter System.

1. Manajemen Proses

Sistem operasi bertanggung-jawab atas aktivitas-aktivitas yang berkaitan dengan manajemen proses seperti:

• Membuat dan menghapus proses pengguna dan sistem proses.

• Menunda atau melanjutkan proses.

• Menyediakan mekanisme untuk sinkronisasi proses.

• Menyediakan mekanisme untuk komunikasi proses.

Menyediakan mekanisme untuk penanganan deadlock.

2. Manajemen Memori Utama

Sistem operasi bertanggung-jawab atas aktivitas-aktivitas yang berkaitan dengan manajemen memori seperti:

• Menjaga track dari memori yang sedang digunakan dan siapa yang menggunakannya.

• Memilih program yang akan di-load ke memori.

3. Manajemen Sistem Berkas

Sistem operasi bertanggung-jawab dalam aktivitas yang berhubungan dengan manajemen berkas:

• Pembuatan dan penghapusan berkas.

• Pembuatan dan penghapusan direktori.

• Mendukung manipulasi berkas dan direktori.

• Memetakan berkas ke secondary-storage.

• Mem-back-up berkas ke media penyimpanan yang permanen (non-volatile).

4. Manajemen Sistem Masukan/Keluaran

Komponen Sistem Operasi untuk sistem Masukan/Keluaran:

• Penyangga: menampung sementara data dari/ke perangkat Masukan/Keluaran.

• Spooling: melakukan penjadwalan pemakaian Masukan/Keluaran sistem supaya lebih efisien (antrian dsb.).

• Menyediakan driver: untuk dapat melakukan operasi rinci untuk perangkat keras Masukan/Keluaran tertentu.

5. Manajemen Penyimpanan Sekunder

Sistem operasi bertanggung-jawab atas aktivitas-aktivitas yang berkaitan dengan manajemen disk seperti:

• free space management.

• alokasi penyimpanan.

• penjadwalan disk.

6. Sistem Proteksi

Proteksi mengacu pada mekanisme untuk mengontrol akses yang dilakukan oleh program, prosesor, atau pengguna ke sistem sumber daya. Mekanisme proteksi harus:

• Membedakan antara penggunaan yang sudah diberi izin dan yang belum.

• Menspesifikasi kontrol untuk dibebankan/diberi tugas.

• Menyediakan alat untuk pemberlakuan sistem.

Struktur Sistem Operasi

Sebuah sistem yang besar dan kompleks seperti sistem operasi modern harus diatur dengan cara membagi task kedalam komponen-komponen kecil agar dapat berfungsi dengan baik dan mudah dimodifikasi. Menurut Silberschatz dan kawan-kawan, ada tiga cara untuk menghubungkan komponen-komponen yang satu dengan yang lain, yaitu:

• Struktur Sederhana.

• Pendekatan Berlapis.

• Kernel Mikro.

Sedangkan menurut Stallings, kita bisa memandang sistem sebagai seperangkat lapisan. Tiap lapisan menampilkan bagian fungsi yang dibutuhkan oleh sistem operasi. Bagian yang terletak pada lapisan yang lebih rendah akan menmpilkan fungsi yang lebih primitif dan menyimpan detail fungsi tersebut.

1. Struktur Sederhana

Banyak sistem yang tidak terstruktur dengan baik, sehingga sistem operasi seperti ini dimulai dengan sistem yang lebih kecil, sederhana, dan terbatas. Kemudian berkembang dengan cakupan yang original. Contoh sistem seperti ini adalah MS-DOS, yang disusun untuk mendukung fungsi yang banyak pada ruang yang sedikit karena keterbatasan perangkat keras untuk menjalankannya.

2. Pendekatan Berlapis

Sistem operasi dibagi menjadi sejumlah lapisan yang masing-masing dibangun di atas lapisan yang lebih rendah. Lapisan yang lebih rendah menyediakan layanan untuk lapisan yang lebih tinggi. Lapisan yang paling bawah adalah perangkat keras, dan yang paling tinggi adalah user-interface. Menurut Tanenbaum dan Woodhull, sistem terlapis terdiri dari enam lapisan, yaitu:

• Lapisan 0. Mengatur alokasi prosesor, pertukaran antar proses ketika interupsi terjadi atau waktu habis. Lapisan ini mendukung dasar multi-programming pada CPU.

• Lapisan 1. Mengalokasikan ruang untuk proses di memori utama dan pada 512 kilo word drum yang digunakan untuk menahan bagian proses ketika tidak ada ruang di memori utama.

• Lapisan 2. Menangani komunikasi antara masing-masing proses dan operator console. Pada lapis ini masing-masing proses secara efektif memiliki opertor console sendiri.

• Lapisan 3. Mengatur peranti M/K dan menampung informasi yang mengalir dari dan ke proses tersebut.

• Lapisan 4. Tempat program pengguna. Pengguna tidak perlu memikirkan tentang proses, memori, console, atau manajemen M/K.

• Lapisan 5. Merupakan operator sistem.

Menurut Stallings, model tingkatan sistem operasi yang mengaplikasikan prinsip ini dapat dilihat pada tabel berikut, yang terdiri dari level-level dibawah ini:

• Level 1. Terdiri dari sirkuit elektronik dimana obyek yang ditangani adalah register memory cell,dan gerbang logika. Operasi pada obyek ini seperti membersihkan register atau membaca lokasi memori.

• Level 2. Pada level ini adalah set instruksi pada prosesor. Operasinya adalah instruksi bahasa-mesin, seperti menambah, mengurangi, load dan store.

• Level 3. Tambahan konsep prosedur atau subrutin ditambah operasi call atau return.

• Level 4. Mengenalkan interupsi yang menyebabkan prosesor harus menyimpan perintah yang baru dijalankan dan memanggil rutin menanganan interupsi.

Empat level pertama bukan bagian sistem operasi tetapi bagian perangkat keras. Meski pun demikian beberapa elemen sistem operasi mulai tampil pada level-level ini, seperti rutin penanganan interupsi. Pada level 5, kita mulai masuk kebagian sistem operasi dan konsepnya berhubungan dengan multi-programming.

• Level 5. Level ini mengenalkan ide proses dalam mengeksekusi program. Kebutuhan-kebutuhan dasar pada sistem operasi untuk mendukung proses ganda termasuk kemampuan men-suspend dan me-resume proses. Hal ini membutuhkan register perangkat keras untuk menyimpan agar eksekusi bisa ditukar antara satu proses ke proses lainnya.

• Level 6. Mengatasi penyimpanan sekunder dari komputer. Level ini untuk menjadwalkan operasi dan menanggapi permintaan proses dalam melengkapi suatu proses.

• Level 7. Membuat alamat logik untuk proses. Level ini mengatur alamat virtual ke dalam blok yang bisa dipindahkan antara memori utama dan memori tambahan.

• Level 8. Mengatasi komunikasi informasi dan pesan-pesan antar proses.

• Level 9. Mendukung penyimpanan jangka panjang yang disebut dengan berkas.

• Level 10. Menyediakan akses ke peranti eksternal menggunakan antarmuka standar.

• Level 11. Bertanggung-jawab mempertahankan hubungan antara internal dan eksternal identifier dari sumber daya dan obyek sistem.

• Level 12. Menyediakan suatu fasilitator yang penuh tampilan untuk mendukung proses.

• Level 13. Menyediakan antarmuka dari sistem operasi dengan pengguna yang dianggap sebagai shell atau dinding karena memisahkan pengguna dengan sistem operasi dan menampilkan sistem operasi dengan sederhana sebagai kumpulan servis atau pelayanan.

Dapat disimpulkan bahwa lapisan sistem operasi secara umum terdiri atas empat bagian, yaitu:

1. Perangkat keras. Lebih berhubungan kepada perancang sistem. Lapisan ini mencakup lapisan 0 dan 1 menurut Tanenbaum, dan level 1 sampai dengan level 4 menurut Stallings.

2. Sistem operasi. Lebih berhubungan kepada programer. Lapisan ini mencakup lapisan 2 menurut Tanenbaum, dan level 5 sampai dengan level 7 menurut Stallings.

3. Kelengkapan. Lebih berhubungan kepada programer. Lapisan ini mencakup lapisan 3 menurut Tanenbaum, dan level 8 sampai dengan level 11 menurut Stallings.

4. Program aplikasi. Lebih berhubungan kepada pengguna aplikasi komputer. Lapisan ini mencakup lapisan 4 dan lapisan 5 menurut Tanebaum, dan level 12 dan level 13 menurut Stallings.

3. Kernel-mikro

Metode ini menyusun sistem operasi dengan mengeluarkan semua komponen yang tidak esensial dari kernel, dan mengimplementasikannya sebagai program sistem dan level pengguna. Hasilnya kernel yang lebih kecil. Fungsi utama mikrokernel adalah mendukung fasilitas komunikasi antara program klien dan bermacam-macam layanan yang juga berjalan di user space.

4. Boot

Saat awal komputer dihidupkan, disebut dengan booting. Komputer akan menjalankan bootstrap program yaitu sebuah program sederhana yang disimpan dalam ROM yang berbentuk chip CMOS.

5. Kompilasi Kernel

Kernel adalah program yang dimuat pada saat boot yang berfungsi sebagai interface antara user-level program dengan hardware.

Ada beberapa langkah yang umumnya dilakukan dalam mengkompilasi kernel, yaitu:

• Download Kernel.

• Kompilasi Kernel

• Konfigurasi Kernel.

• Patch Kernel.

6. Sistem Terdistribusi dan Terkluster

Melaksanakan komputasi secara terdistribusi diantara beberapa prosesor. Hanya saja komputasinya bersifat loosely coupled system yaitu setiap prosesor mempunyai memori lokal sendiri. Komunikasi terjadi melalui bus atau jalur telepon. Keuntungannya hampir sama dengan prosesor jamak (multi-processor), yaitu adanya pembagian sumber daya dan komputasi lebih cepat. Dalam hal jaringan, sistem kluster mirip dengan sistem terdistribusi (distributed system). Bedanya, jika jaringan pada sistem terdistribusi melingkupi komputer-komputer yang lokasinya tersebar maka jaringan pada sistem kluster menghubungkan banyak komputer yang dikumpulkan dalam satu tempat.

7. Sistem Waktu Nyata

Sistem waktu nyata (Real Time Systems) ialah suatu sistem yang mengharuskan suatu komputasi selesai dalam jangka waktu tertentu. Jika komputasi ternyata belum selesai maka sistem dianggap gagal dalam melakukan tugasnya. Sistem waktu nyata memiliki dua model dalam pelaksanaannya: hard real time system dan soft real time system.

àHard real time system menjamin suatu proses yang paling penting dalam sistem akan selesai dalam jangka waktu yang valid. Jaminan waktu yang ketat ini berdampak pada operasi dan perangkat keras (hardware) yang mendukung sistem.

àSoft real time system tidak memberlakukan aturan waktu seketat hard real time system. Namun, sistem ini menjamin bahwa suatu proses terpenting selalu mendapat prioritas tertinggi untuk diselesaikan diantara proses-proses lainnya. Sama halnya dengan hard real time system, berbagai operasi dalam sistem tetap harus ada batas waktu maksimum.

Menurut [Morgan1992], terdapat sekurangnya lima karakteristik dari sebuah sistem waktu nyata

• Deterministik. Dapat ditebak berapa waktu yang dipergunakan untuk mengeksekusi operasi.

• Responsif. Kapan secara pasti eksekusi dimulai serta diakhiri.

• Kendali Pengguna. Dengan menyediakan pilihan lebih banyak daripada sistem operasi biasa.

• Kehandalan. Sehingga dapat menanggulangi masalah-masalah pengecualian dengan derajat tertentu.

• Penanganan Kegagalan. Agar sistem tidak langsung crash.

III. Proses dan Penjadwalan

1. Konsep Proses

Proses didefinisikan sebagai program yang sedang dieksekusi. Menurut Silberschatz proses tidak hanya sekedar suatu kode program (text section), melainkan meliputi beberapa aktivitas yang bersangkutan seperti program counter dan stack. Sebuah proses juga melibatkan stack yang berisi data sementara (parameter fungsi/metode, return address, dan variabel lokal) dan data section yang menyimpan variabel-variabel global.

2. Pembentukan Proses

Saat komputer berjalan, terdapat banyak proses yang berjalan secara bersamaan. Sebuah proses dibuat melalui system call create-process membentuk proses turunan (child process) yang dilakukan oleh proses induk parent process. Proses turunan tersebut juga mampu membuat proses baru sehingga kesemua proses-proses ini pada akhirnya membentuk pohon proses. Ketika sebuah proses dibuat maka proses tersebut dapat memperoleh sumber-daya seperti ''waktu CPU'', ''memori'', ''berkas'' atau perangkat ''M/K''. Sumber daya ini dapat diperoleh langsung dari Sistem Operasi, dari Proses Induk yang membagi-bagikan sumber daya kepada setiap proses turunannnya, atau proses turunan dan proses induk berbagi sumber-daya yang diberikan Sistem Operasi.

3. Terminasi Proses

Suatu proses diterminasi ketika proses tersebut telah selesai mengeksekusi perintah terakhir serta meminta sistem operasi untuk menghapus perintah tersebut dengan menggunakan system call exit.

Pada saat itu, proses dapat mengembalikan data keluaran kepada proses induk-nya melalui system call wait. Semua sumber-daya yang digunakan oleh proses akan dialokasikan kembali oleh sistem operasi agar dapat dimanfaatkan oleh proses lain. Suatu proses juga dapat diterminasi dengan sengaja oleh proses lain melalui system call abort. Biasanya proses induk melakukan hal ini pada turunannya. Alasan terminasi tersebut seperti:

• Turunan melampaui penggunaan sumber-daya yang telah dialokasikan. Dalam keadaan ini, proses

induk perlu mempunyai mekanisme untuk memeriksa status turunannya-nya.

• Task yang ditugaskan kepada turunan tidak lagi diperlukan.

• Proses induk selesai, dan sistem operasi tidak mengizinkan proses turunan untuk tetap berjalan.

Jadi, semua proses turunan akan berakhir pula. Hal ini yang disebut cascading termination.

4. Status Proses

Sebuah proses dapat memiliki tiga status utama yaitu:

• Running: status yang dimiliki pada saat instruksi-instruksi dari sebuah proses dieksekusi.

• Waiting: status yang dimiliki pada saat proses menunggu suatu sebuah event seperti proses M/K.

• Ready: status yang dimiliki pada saat proses siap untuk dieksekusi oleh prosesor.

Terdapat dua status tambahan, yaitu saat pembentukan dan terminasi:

• New: status yang dimiliki pada saat proses baru saja dibuat.

• Terminated: status yang dimiliki pada saat proses telah selesai dieksekusi.

RDY (Ready), RUN (Running), W (Wait).

Hanya satu proses yang dapat berjalan pada prosesor mana pun pada satu waktu. Namun, banyak

proses yang dapat berstatus Ready atau Waiting. Ada tiga kemungkinan bila sebuah proses memiliki

status Running:

• Jika program telah selesai dieksekusi maka status dari proses tersebut akan berubah menjadi

Terminated.

• Jika waktu yang disediakan oleh OS untuk proses tersebut sudah habis maka akan terjadi

interrupt dan proses tersebut kini berstatus Ready.

• Jika suatu event terjadi pada saat proses dieksekusi (seperti ada permintaan M/K) maka proses

tersebut akan menunggu event tersebut selesai dan proses berstatus Waiting.


Process Control Block

Setiap proses digambarkan dalam sistem operasi oleh sebuah process control block (PCB) - juga

disebut sebuah control block. Sebuah PCB ditunjukkan dalam Gambar 10.2, “Process Control

Block”. PCB berisikan banyak bagian dari informasi yang berhubungan dengan sebuah proses yang

spesifik, termasuk hal-hal di bawah ini:

• Status proses: status mungkin, new, ready, running, waiting, halted, dan juga banyak lagi.

• Program counter: suatu stack yang berisi alamat dari instruksi selanjutnya untuk dieksekusi untuk

proses ini.

• CPU register: Register bervariasi dalam jumlah dan jenis, tergantung pada rancangan komputer.

Register tersebut termasuk accumulator, register indeks, stack pointer, general-purposes register,

ditambah code information pada kondisi apa pun. Beserta dengan program counter,

keadaan/status informasi harus disimpan ketika gangguan terjadi, untuk memungkinkan proses

tersebut berjalan/bekerja dengan benar setelahnya (lihat Gambar 10.3, “Status Proses”).

• Informasi manajemen memori: Informasi ini dapat termasuk suatu informasi sebagai nilai dari

dasar dan batas register, tabel page/halaman, atau tabel segmen tergantung pada sistem memori

yang digunakan oleh sistem operasi (lihat Bagian V, “Memori”).

• Informasi pencatatan: Informasi ini termasuk jumlah dari CPU dan waktu riil yang digunakan,

batas waktu, jumlah akun jumlah job atau proses, dan banyak lagi.

• Informasi status M/K: Informasi termasuk daftar dari perangkat M/K yang di gunakan pada

proses ini, suatu daftar berkas-berkas yang sedang diakses dan banyak lagi.

• PCB hanya berfungsi sebagai tempat penyimpanan informasi yang dapat bervariasi dari proses

yang satu dengan yang lain.


Konsep Thread

Thread merupakan unit dasar dari penggunaan CPU, yang terdiri dari Thread_ID, program counter, register set, dan stack. Sebuah thread berbagi code section, data section, dan sumber daya sistem operasi dengan Thread lain yang dimiliki oleh proses yang sama. Thread juga sering disebut lightweight process. Sebuah proses tradisional atau heavyweight process mempunyai thread tunggal yang berfungsi sebagai pengendali. Perbedaannya ialah proses dengan thread yang banyak – mengerjakan lebih dari satu tugas pada satu satuan waktu.

Keuntungan Thread

Keuntungan dari program yang multithreading terbagi menjadi empat kategori:

1. Responsif. Aplikasi interaktif menjadi tetap responsif meski pun sebagian dari program sedang

diblok atau melakukan operasi yang panjang kepada pengguna

2. Berbagi sumber daya. thread berbagi memori dan sumber daya dengan thread lain yang

dimiliki oleh proses yang sama. Keuntungan dari berbagi kode adalah mengizinkan sebuah

aplikasi untuk mempunyai beberapa thread yang berbeda dalam lokasi memori yang sama.

3. Ekonomis. Pembuatan sebuah proses memerlukan dibutuhkan pengalokasian memori dan

sumber daya. Alternatifnya adalah dengan penggunaan thread, karena thread berbagi memori

dan sumber daya proses yang memilikinya maka akan lebih ekonomis untuk membuat dan

context switch thread.

4. Utilisasi arsitektur multiprocessor. Keuntungan dari multithreading dapat sangat meningkat

pada arsitektur multiprocessor, dimana setiap thread dapat berjalan secara pararel di atas

processor yang berbeda.

Thread Pools

Pada web server yang multithreading ada dua masalah yang timbul:

1. Ukuran waktu yang diperlukan untuk menciptakan thread untuk melayani permintaan yang

diajukan terlebih pada kenyataannya thread dibuang ketika ia seketika sesudah ia menyelesaikan

tugasnya.

2. Pembuatan thread yang tidak terbatas jumlahnya dapat menurunkan performa dari sistem.

Solusinya adalah dengan penggunaan Thread Pools, cara kerjanya adalah dengan membuat beberapa

thread pada proses startup dan menempatkan mereka ke pools, dimana mereka duduk diam dan

menunggu untuk bekerja. Jadi ketika server menerima permintaan maka maka ia akan

membangunkan thread dari pool dan jika thread tersedia maka permintaan tersebut akan dilayani.

Ketika thread sudah selesai mengerjakan tugasnya maka ia kembali ke pool dan menunggu

pekerjaan lainnya. Bila tidak thread yang tersedia pada saat dibutuhkan maka server menunggu

sampai ada satu thread yang bebas.

Keuntungan thread pool:

1. Biasanya lebih cepat untuk melayani permintaan dengan thread yang ada dibanding dengan

menunggu thread baru dibuat.

2. Thread pool membatasi jumlah thread yang ada pada suatu waktu. Hal ini pentingpada sistem

yang tidak dapat mendukung banyak thread yang berjalan secara concurrent.

Jumlah thread dalam pool dapat tergantung dari jumlah CPU dalam sistem, jumlah memori fisik,

dan jumlah permintaan klien yang concurrent.

Solusi Multi-Threading

Seperti yang sudah diketahui, thread tidak selalu berada pada proses running. Ini akan

mengakibatkan kekosongan pada proses yang berjalan sehingga penggunaannya menjadi tidak

efektif. Karena itu, ketika thread sedang tidak berada pada proses running dapat dibuat thread lain

yang bisa mengisi kekosongan ini. Proses berjalannya thread-thread ini dinamakan MultiThreading.

Untuk menentukan proses mana yang harus berjalan pada multithreading, maka dibuatlah

scheduling yanga akan membuat thread berjalan sesuai dengan proses yang diinginkan

Konsep Penjadwalan

Ketika sebuah proses memasuki sistem, proses itu diletakkan di dalam job queue. Pada antrian ini terdapat seluruh proses yang berada dalam sistem. Sedangkan proses yang berada pada memori utama, siap dan menunggu untuk mengeksekusi disimpan dalam sebuah daftar yang bernama ready queue. Antrian ini biasanya disimpan sebagai linked list. Header dari ready queue berisi pointer untuk PCB pertama dan PCB terakhir pada list. Setiap PCB memiliki pointer field yang menunjuk kepada PCB untuk proses selanjutnya dalam ready queue.

Penjadwalan proses dapat direpresentasikan secara umum dalam bentuk diagram antrian.

Umumnya proses-proses yang ada pada sistem akan ada dalam beberapa tahap antrian yaitu job queue, ready queue, dan device queue. Job queue, menyimpan seluruh proses yang berada pada sistem. Ketika sebuah proses memasuki sebuah sistem, proses tersebut akan diletakkan di dalam job queue. Ready queue merupakan sebuah daftar proses-proses yang berada pada memori utama (main memori), siap dan menunggu untuk dieksekusi dan dialokasikan ke CPU. Daftar dari proses-proses yang menunggu peralatan M/K tertentu disbut dengan device queue. Tiap peralatan mempunyai device queue-nya masing masing. Proses-proses yang ada menunggu di dalam ready queue sampai dia dipilih untuk eksekusi, atau di-dispatched. Begitu proses tersebut dipilih lalu dialokasikan ke CPU dan sedang berjalan, satu dari beberapa kemungkinan di bawah ini dapat terjadi.

1. Proses tersebut mengeluarkan permintaan M/K, lalu ditempatakan dalam sebuah M/K device queue.

2. Proses tersebut dapat membuat sub-proses baru dan menunggu untuk di-terminasi.

3. Proses tersebut dikeluarkan (di-remove) secara paksa dari CPU, sebagai hasil dari suatu interrupt dan diletakkan kembali ke dalam ready queue.

Pada dua kemungkinan pertama (1 dan 2) proses berganti status dari waiting state menjadi ready state, lalu diletakkan kembali ke dalam ready queue. Siklus ini akan terus terjadi pada proses sampai dia di-terminasi, yaitu dimana proses tersebut dikeluarkan dari seluruh antrian yang ada dan memiliki PCB-nya sendiri dan seluruh sumber daya yang dia gunakan dialokasikan kembali.


Sebuah proses berpindah-pindah di antara berbagai penjadwalan antrian seumur hidupnya. Sistem operasi harus memilih dan memproses antrian-antrian ini berdasarkan kategorinya dengan cara tertentu. Oleh karena itu, proses seleksi ini harus dilakukan oleh scheduler yang tepat. Terdapat dua jenis scheduler pada CPU yang umum dipakai, yaitu:

i. Long-Term Scheduler atau Job Scheduler yang bertugas memilih proses dari tempat ini dan mengisinya ke dalam memori.

ii. Short-Term Scheduler atau CPU scheduler yang bertugas memilih proses yang sudah siap untuk melakukan eksekusi,dan dialokasikan di CPU untuk proses tersebut.

Secara umum, proses pada Long-Term Scheduler dapat dibagi menjadi dua, yaitu:

i. M/K Bound yaitu proses yang lebih banyak mengerjakan permintaan M/K dibandingkan komputasi.

ii. CPU Bound yaitu proses yang lebih banyak mengerjakan komputasi dibandingkan permintaan M/K.

Penjadwal CPU

Keberhasilan dari penjadwalan CPU tergantung dari beberapa properti prosesor. Pengeksekusian dari proses tersebut terdiri atas siklus CPU ekskusi dan M/K Wait. Proses hanya akan bolak-balik dari dua state ini. Pengeksekusian proses dimulai dengan CPU Burst, setelah itu diikuti oleh M/K burst, kemudian CPU Burst lagi lalu M/K Burst lagi begitu seterusnya dan dilakukan secara bergiliran. Dan, CPU Burst terakhir, akan berakhir dengan permintaan sistem untuk mengakhiri pengeksekusian daripada melalui M/K Burst lagi.


Durasi dari CPU bust ini telah diukur secara ekstensif, walau pun mereka sangat berbeda dari proses ke proses. Mereka mempunyai frekeunsi kurva yang sama.


Kriteria Penjadwalan

Suatu Algoritma penjadwalan CPU yang berbeda dapat mempunyai nilai yang berbeda untuk sistem yang berbeda. Banyak kriteria yang bisa dipakai untuk menilai algoritma penjadwalan CPU. Kriteria yang digunakan dalam menilai adalah:

1. CPU Utilization. Kita ingin menjaga CPU sesibuk mungkin. CPU utilization akan mempunyai range dari 0 sampai 100 persen. Di sistem yang sebenarnya ia mempunyai range dari 40 sampai 100 persen.

2. Throughput. Salah satu ukuran kerja adalah banyaknya proses yang diselesaikan per satuan waktu.jika kita mempunyai beberapa proses yang sama dan memiliki beberapa algoritma penjadwalan yang berbeda, throughput bisa menjadi salah satu kriteria penilaian, dimana algoritma yang menyelesaikan proses terbanyak mungkin yang terbaik.

3. Turnaroud Time. Dari sudut pandang proses tertentu, kriteria yang penting adalah berapa lama untuk mengeksekusi proses tersebut.

4. Waiting Time. Algoritma penjadwalan CPU tidak mempengaruhi waktu untuk melaksankan proses tersebut atau M/K, itu hanya mempengaruhi jumlah waktu yang dibutuhkan proses di antrian raedy. Waiting time adalah jumlah waktu yang dbutuhkan proses di antrian ready.

5. Response time.

Algoritma Penjadwalan I

Proses yang belum mendapat jatah alokasi dari CPU akan mengantri di ready queue. Di sini algoritma diperlukan untuk mengatur giliran proses-proses tersebut. Algoritma penjadwalan berfungsi untuk menentukan proses manakah yang ada di ready queue yang akan dieksekusi oleh CPU

1. FCFS: First-Come, First-Served

Algoritma ini merupakan algoritma penjadwalan yang paling sederhana yang digunakan CPU. Dengan menggunakan algoritma ini seiap proses yang berada pada status ready dimasukkan ke dalam FIFO queue sesuai dengan waktu kedatangannya. Proses yang tiba terlebih dahulu yang akan dieksekusi.

Contoh: Ada tiga buah proses yang datang secara bersamaan yaitu pada 0 ms, P1 memiliki burst time 24 ms, P2 memiliki burst time 5 ms, P3 memiliki burst time 3 ms. Hitunglah wating time rata-rata dan turnaround time (burst time + waiting time) dari ketiga proses tersebut dengan menggunakan algoritma FCFS.

Waiting time untuk p1 adalah 0 ms (P1 tidak perlu menunggu), sedangkan untuk p2 adalah sebesar 24 ms (menunggu P1 selesai) dan untuk p3 sebesar 29 ms (menunggu P1 dan P2 selesai). Waiting time rata-ratanya adalah sebesar (0+24+29)/3 = 17,6 ms.

Turnaround time untuk P1 sebesar 24 ms, sedangkan untuk P2 sebesar 29 ms (dihitung dari awal kedatangan P2 hingga selesai dieksekusi), untuk p3 sebesar 32 ms. Turnaround time rata-rata untuk ketiga proses tersebut adalah (24+29+32)/3 = 28,3 ms.

Kelemahan dari algoritma ini:

1. Waiting time rata-ratanya cukup lama.

2. Terjadinya convoy effect, yaitu proses-proses menunggu lama untuk menunggu 1 proses besar yang sedang dieksekusi oleh CPU.

Algoritma ini juga menerapkan konsep non-preemptive, yaitu setiap proses yang sedang dieksekusi oleh CPU tidak dapat di-interrupt oleh proses yang lain.

2. SJF: Shortest-Job First

Algoritma ini mempunyai cara penjadwalan yang berbeda dengan FCFS. Dengan algoritma ini maka setiap proses yang ada di ready queue akan dieksekusi berdasarkan burst time terkecil. Hal ini mengakibatkan waiting time yang pendek untuk setiap proses dan karena hal tersebut maka waiting time rata-ratanya juga menjadi pendek, sehingga dapat dikatakan bahwa algoritma ini adalah algoritma yang optimal.

Ada beberapa kekurangan dari algoritma ini yaitu:

1. Susahnya untuk memprediksi burst time proses yang akan dieksekusi selanjutnya.

2. Proses yang mempunyai burst time yang besar akan memiliki waiting time yang besar pula karena yang dieksekusi terlebih dahulu adalah proses dengan burst time yang lebih kecil.

Algoritma ini dapat dibagi menjadi dua bagian yaitu:

1. Preemptive. Jika ada proses yang sedang dieksekusi oleh CPU dan terdapat proses di ready queue dengan burst time yang lebih kecil daripada proses yang sedang dieksekusi tersebut, maka proses yang sedang dieksekusi oleh CPU akan digantikan oleh proses yang berada di ready queue tersebut. Preemptive SJF sering disebut juga Shortest-Remaining- Time-First scheduling.

2. Non-preemptive. CPU tidak memperbolehkan proses yang ada di ready queue untuk menggeser proses yang sedang dieksekusi oleh CPU meskipun proses yang baru tersebut mempunyai burst time yang lebih kecil.

Contoh: Ada 3 buah proses yang datang berurutan yaitu p1 dengan arrival time pada 0 ms dengan burst time 4 ms, p2 dengan arrival time pada 0 ms dengan burst time 5 ms, p3 dengan arrival time pada 1 ms dengan burst time 2 ms. Hitunglah waiting time rata-rata dan turnaround time dari ketiga proses tersebut dengan mengunakan algoritma SJF.

Waiting time rata-rata untuk ketiga proses tersebut adalah sebesar ((3-1)+(6-0)+(1-1))/3 = 2,6 ms.

Turnaround time dari ketiga proses tersebut adalah sebesar (6+11+(3-1))/3 = 6,3 ms.

Waiting time rata-rata untuk ketiga prses tersebut adalah sebesar (0+6+(4-1))/3 = 3 ms Turnaround time dari ketiga proses tersebut adalah sebesar (4+11+(6-1))/3 = 6,6 ms

3. Prioritas

Priority Scheduling merupakan algoritma penjadwalan yang mendahulukan proses yang memiliki prioritas tertinggi. Setiap proses memiliki prioritasnya masing-masing. Prioritas suatu proses dapat ditentukan melalui beberapa karakteristik antara lain:

1. Time limit.

2. Memory requirement.

3. Akses file.

4. Perbandingan antara M/K Burst dengan CPU Burst.

5. Tingkat kepentingan proses.

Priority Scheduling juga dapat dijalankan secara preemptive maupun non-preemptive. Pada preemptive, jika ada suatu proses yang baru datang memiliki prioritas yang lebih tinggi daripada proses yang sedang dijalankan, maka proses yang sedang berjalan tersebut dihentikan, lalu CPU dialihkan untuk proses yang baru datang tersebut.

Sementara itu, pada non-preemptive, proses yang baru datang tidak dapat menganggu proses yang sedang berjalan, tetapi hanya diletakkan di depan queue. Kelemahan pada priority scheduling adalah dapat terjadinya indefinite blocking (starvation). Suatu proses dengan prioritas yang rendah memiliki kemungkinan untuk tidak dieksekusi jika terdapat proses lain yang memiliki prioritas lebih tinggi darinya. Solusi dari permasalahan ini adalah aging, yaitu meningkatkan prioritas dari setiap proses yang menunggu dalam queue secara bertahap.

Contoh: Setiap 10 menit, prioritas dari masing-masing proses yang menunggu dalam queue dinaikkan satu tingkat. Maka, suatu proses yang memiliki prioritas 127, setidaknya dalam 21 jam 20 menit, proses tersebut akan memiliki prioritas 0, yaitu prioritas yang tertinggi. (semakin kecil angka menunjukkan bahwa prioritasnya semakin tinggi)

4. Round-Robin

Algoritma ini menggilir proses yang ada di antrian. Proses akan mendapat jatah sebesar time quantum. Jika time quantum-nya habis atau proses sudah selesai CPU akan dialokasikan ke proses berikutnya. Tentu proses ini cukup adil karena tak ada proses yang diprioritaskan, semua proses mendapat jatah waktu yang sama dari CPU (1/n), dan tak akan menunggu lebih lama dari (n-1)/q.

Algoritma ini sepenuhnya bergantung besarnya time quantum. Jika terlalu besar, algoritma ini akan sama saja dengan algoritma first-come first-served. Jika terlalu kecil, akan semakin banyak peralihan proses sehingga banyak waktu terbuang. Permasalahan utama pada Round Robin adalah menentukan besarnya time quantum. Jika time quantum yang ditentukan terlalu kecil, maka sebagian besar proses tidak akan selesai dalam 1 time quantum. Hal ini tidak baik karena akan terjadi banyak switch, padahal CPU memerlukan waktu untuk beralih dari suatu proses ke proses lain (disebut dengan context switches time). Sebaliknya, jika time quantum terlalu besar, algoritma Round Robin akan berjalan seperti algoritma First Come First Served. Time quantum yang ideal adalah jika 80% dari total proses memiliki CPU burst time yang lebih kecil dari 1 time quantum.

5. Multilevel Queue

Ide dasar dari algoritma ini adalah berdasarkan pada sistem prioritas proses. Prinsipnya adalah, jika setiap proses dapat dikelompokkan berdasarkan prioritasnya, maka akan didapati queue .

Pada saat itu akan terjadi pengelompokan- pengelompokan proses-proses berdasarkan prioritasnya. Kemudian muncul ide untuk menganggap kelompok-kelompok teresbut sebagai sebuah antrian-antrian kecil yang merupakan bagian dari antrian keseluruhan proses, yang sering disebut dengan algoritma multilevel queue. Dalam hal ini dapat dilihat bahwa seolah-olah algoritma dengan prioritas yang dasar adalah algoritma multilevel queue dimana setiap queue akan berjalan dengan algoritma FCFS dan dapat

diketahui bahwa algoritma FCFS memiliki banyak kelemahan, dan oleh karena itu maka dalam prakteknya, algoritma multilevel queue memungkinkan adanya penerapan algoritma internal dalam masing-masing sub- antriannya untuk meningkatkan kinerjanya, dimana setiap sub-antrian bisa memiliki algoritma internal yang berbeda.

Berawal dari priority scheduling, algoritma ini pun memiliki kelemahan yang sama dengan priority scheduling, yaitu sangat mungkin bahwa suatu proses pada queue dengan prioritas rendah bisa saja tidak mendapat jatah CPU. Untuk mengatasi hal tersebut, salah satu caranya adalah dengan memodifikasi algoritma ini dengan adanya jatah waktu maksimal untuk tiap antrian, sehingga jika suatu antrian memakan terlalu banyak waktu, maka prosesnya akan dihentikan dan digantikan oleh antrian dibawahnya, dan tentu saja batas waktu untuk tiap antrian bisa saja sangat berbeda tergantung pada prioritas masing-masing antrian.

6. Multilevel Feedback Queue

Algoritma ini mirip sekali dengan algoritma Multilevel Queue. Perbedaannya ialah algoritma ini mengizinkan proses untuk pindah antrian. Jika suatu proses menyita CPU terlalu lama, maka proses itu akan dipindahkan ke antrian yang lebih rendah. Ini menguntungkan proses interaksi, karena proses ini hanya memakai waktu CPU yang sedikit. Demikian pula dengan proses yang menunggu terlalu lama. Proses ini akan dinaikkan tingkatannya. Biasanya prioritas tertinggi diberikan kepada proses dengan CPU burst terkecil, dengan begitu CPU akan terutilisasi penuh dan I/O dapat terus sibuk. Semakin rendah tingkatannya, panjang CPU burst

proses juga semakin besar. Algoritma ini didefinisikan melalui beberapa parameter, antara lain:

• Jumlah antrian

• Algoritma penjadwalan tiap antrian

• Kapan menaikkan proses ke antrian yang lebih tinggi

• Kapan menurunkan proses ke antrian yang lebih rendah

• Antrian mana yang akan dimasuki proses yang membutuhkan

Dengan pendefinisian seperti tadi membuat algoritma ini sering dipakai. Karena algoritma ini mudah dikonfigurasi ulang supaya cocok dengan sistem. Tapi untuk mengatahui mana penjadwal terbaik, kita harus mengetahui nilai parameter tersebut.Multilevel feedback queue adalah salah satu algoritma yang berdasar pada algoritma mulilevelqueue. Perbedaan mendasar yang membedakan multilevel feedback queue dengan multilevel queue biasa adalah terletak pada adanya kemungkinan suatu proses berpindah dari satu antrian ke antrian lainnya, entah dengan prioritas yang lebih rendah ataupun lebih tinggi, misalnya pada contoh berikut.

1. Semua proses yang baru datang akan diletakkan pada queue 0 (quantum = 8 ms)

2. Jika suatu proses tidak dapat diselesaikan dalam 8 ms, maka proses tersebut akan dihentikan dan dipindahkan ke queue 1 (quantum = 16 ms)

3. Queue 1 hanya akan dikerjakan jika tidak ada lagi proses di queue 0, dan jika suatu proses di queue 1 tidak selesai dalam 16 ms, maka proses tersebut akan dipindahkan ke queue 2

4. Queue 2 akan dikerjakan bila queue 0 dan 1 kosong, dan akan berjalan dengan algoritma FCFS Gambar Multilevel Feedback Queue

Disini terlihat bahwa ada kemungkinan terjadinya perpindahan proses antar queue, dalam hal ini ditentukan oleh time quantum, namun dalam prakteknya penerapan algoritma multilevel feedback queue akan diterapkan dengan mendefinisikan terlebih dahulu parameter- parameternya, yaitu:

1. Jumlah antrian.

2. Algoritma internal tiap queue.

3. Aturan sebuah proses naik ke antrian yang lebih tinggi.

4. Aturan sebuah proses turun ke antrian yang lebih rendah.

5. Antrian yang akan dimasuki tiap proses yang baru datang.

Berdasarkan hal-hal di atas maka algoritma ini dapat digunakan secara fleksibel dan diterapkan sesuai dengan kebutuhan sistem. Pada zaman sekarang ini algoritma multilevel feedback queue adalah salah satu yang paling banyak digunakan.

Algoritma Penjadwalan II

Penjadwalan pada prosesor jamak jelas lebih kompleks, karena kemungkinan masalah yang timbul jauh lebih banyak daripada prosesor tunggal. Prioritas adalah suatu istilah yang digunakan untuk menentukan tingkat urutan atau hirarki suatu proses yang sedang masuk dalam ready queue. Konsep prioritas sangat penting dalam penjadwalan prosesor jamak. Prioritas adalah tingkat kepentingan suatu proses yang ada di ready queue. Penjadwalan pada prosesor jamak lebih rumit daripada prosesor tunggal. Hal ini sesuai dengan kemampuan prosesor jamak yang lebih baik daripada prosesor tunggal.

Prosesor Jamak

Ada dua jenis susunan prosesor yang digunakan dalam sistem prosesor jamak, yaitu prosesor-prosesor yang fungsinya identik (homogen) dan prosesor-prosesor yang fungsinya berbeda (heterogen. Sistem prosesor jamak yang homogen memungkinkan terjadinya pembagian pekerjaan yang tidak merata antar prosesor. Pada waktu yang bersamaan, satu prosesor bisa sangat sibuk sementara prosesor lain tidak mengerjakan proses apapun. Hal ini mengakibatkan sistem tidak bekerja dengan optimal dan efisien. Untuk menghindari hal ini, sistem menggunakan ready queue yang berfungsi menampung semua proses yang masuk dan menjadwalkannya ke setiap prosesor yang tersedia. Ada dua pendekatan penjadwalan CPU pada sistem prosesor jamak:

1. Proses Jamak Asimetris. Proses ini mengalokasikan sebuah prosesor yang berfungsi mengatur proses M/K, menjadwal prosesor-prosesor lain dan melakukan pekerjaan-pekerjaan sistem lainnya. Prosesor-prosesor lain dialokasikan untuk menjalankan perintah-perintah dari pengguna.

2. Proses Jamak Simetris. Dalam proses jamak simetris, setiap prosessor menjadwalkan dirinya sendiri. Setiap proses dapat berada di ready queue yang dipakai bersama atau berada di queue yang ada di setiap prosesor.

IV. Sinkronisasi

Problem Critical Section

Solusi untuk memecahkan masalah critical section adalah dengan merancang sebuah protokol di mana proses-proses dapat menggunakannya secara bersama-sama. Setiap proses harus 'meminta izin' untuk memasuki critical section-nya. Bagian dari kode yang mengimplementasikan izin ini disebut entry section. Akhir dari critical section itu disebut exit section. Bagian kode selanjutnya

disebut remainder section.

Struktur umum dari proses Pi yang memiliki segmen critical section adalah:

Contoh 19.4. Critical Section (1)

do {

entry section

critical section

exit section

remainder section

} while (1);

Dari kode di atas, dapat kita lihat bahwa untuk bisa memasuki critical section sebuah proses harus melalui entry section.

Solusi dari masalah critical section harus memenuhi tiga syarat berikut [Silbeschatz 2004]:

1. Mutual Exclusion. Jika suatu proses sedang menjalankan critical section-nya, maka proses-proses lain tidak dapat menjalankan critical section mereka. Dengan kata lain, tidak ada dua proses yang berada di critical section pada saat yang bersamaan.

2. Terjadi kemajuan (progress). Jika tidak ada proses yang sedang menjalankan critical section-nya dan ada proses-proses lain yang ingin masuk ke critical section, maka hanya proses-proses yang yang sedang berada dalam entry section saja yang dapat berkompetisi untuk mengerjakan critical section.

3. Ada batas waktu tunggu (bounded waiting). Jika seandainya ada proses yang sedang menjalankan critical section, maka proses lain memiliki waktu tunggu yang ada batasnya untuk menjalankan critical section-nya, sehingga dapat dipastikan bahwa proses tersebut dapat mengakses critical section-nya (tidak mengalami starvation: proses seolah-olah berhenti, menunggu request akses ke critical section diperbolehkan).

Masalah Critical Section

Pemecahan masalah critical section digunakan untuk mengatasi Race Condition pada segmen code critical section. Race Condition adalah peristiwa ketidakvalidan data karena proses-proses menggunakan data secara bersamaan. Data yang didapat akhirnya adalah data yang terakhir kali dieksekusi. Untuk itu perlu dicegah terjadinya hal tersebut.

1. Mutual Exclusion. Pengertian Mutual Exclusion adalah ketika suatu proses (P0) sedang menggunakan critical section, maka tidak boleh ada proses lain (P1) yang menggunakan critical section di saat bersamaan.

2. Progress. Artinya ketika tidak ada proses yang menggunakan critical section dan ada proses-proses yang ingin menggunakan critical section tersebut, maka harus ada proses yang menggunakan critical section tersebut.

3. Bounded Waiting. Maksud dari Bounded Waiting adalah setiap proses yang menunggu menggunakan critical section, maka proses-proses yang menunggu tersebut dijamin suatu saat akan menggunakan critical section. Dijamin tidak ada thread yang mengalami starvation. Berikut akan di perlihatkan algoritma-algoritma untuk pemecahan masalah critical section. Setiap algoritma menggunakan dua proses dan dianggap berjalan secara concurrent/bersamaan. Ada dua jenis solusi masalah critical section, yaitu:

1. Solusi Perangkat Lunak. Dengan menggunakan algoritma-alogoritma yang nilai kebenarannya tidak tergantung pada asumsi-asumsi lain, selain bahwa setiap proses berjalan pada kecepatan yang bukan nol.

2. Solusi Perangkat Keras. Tergantung pada beberapa instruksi mesin tertentu, misalnya dengan me-non-aktifkan interupsi atau dengan mengunci suatu variabel tertentu (Lihat: Bab 25, Bounded Buffer).

Algoritma I

Ide Algoritma I ialah memberikan giliran kepada setiap proses untuk memasuki critical section-nya. Asumsi yang digunakan disini setiap proses secara bergantian memasuki critical section-nya. Sebenarnya kedua proses berjalan secara bersamaan, dan kita tidak dapat memprediksi proses manakah yang akan berjalan duluan. Misalkan, yang pertama kali dieksekusi adalah baris pertama pada proses P0, maka turn akan diset menjadi 0, artinya sekarang giliran P0 untuk menggunakan critical section. Lalu, seandainya proses P1 yang dieksekusi, maka ia akan merubah turn menjadi 1, artinya sekarang giliran P1 menggunakan critical section. Lalu P0 akan menunggu karena turn sudah berubah menjadi 1. Lalu P1 akan memasuki critical section karena turn=1. Setelah P1 selesai, maka ia akan merubah turn menjadi 0, artinya P1 memberikan giliran P0 untuk menggunakan critical section. Selanjutnya P1 akan menunggu di while turn!=1 jika ingin menggunakan critical section lagi. Lalu P0 keluar dari loop, karena turn sudah menjadi 0, saatnya giliran P0 memasuki critical section. Setelah P0 selesai, P0 akan merubah turn=1, artinya P0 memberikan giliran P1 untuk menggunakan critical section. Kejadian ini terus terjadi berulang-ulang.

Permasalahannya adalah, jika suatu proses, misalkan P0 mendapat giliran, artinya turn=0, setelah selesai menggunakan critical section, P0 akan merubah turn menjadi 1, nah seandainya P1 tidak membutuhkan critical section, turn akan tetap menjadi 1. Lalu pada saat P0 membutuhkan akses ke critical section lagi, ia harus menuggu P1 menggunakan critical section dan merubah turn menjadi 0. Akibatnya critical section dalam keadaan tidak dipakai oleh proses manapun, sedangkan ada proses (P0) yang membutuhkannya. Sampai kapanpun P1 tidak dapat mengakses critical section hingga P0 menggunakan critical section, lalu merubah turn menjadi 0. Kondisi kekosongan dari critical section ini tidak memenuhi syarat solusi critical section yang kedua yaitu progress. Analogi Algoritma I seperti kamar mandi dua pintu, ada dua orang yang bergiliran memakai kamar mandi yaitu A dan B. Kamar mandi adalah critical section. A tidak dapat menggunakan kamar mandi hingga B menggunakan kamar mandi lalu memberikan giliran kepada A. Begitu juga sebaliknya.

Algoritma 1 menggunakan yield() yang menjaga supaya thread di kondisi Runnable tetapi juga mengizinkan JVM untuk memilih thread Runnable lainnya.

Algoritma 2

Masalah yang terjadi pada algoritma 1 ialah ketika di entry section terdapat sebuah proses yang ingin masuk ke critical section, sementara di critical section sendiri tidak ada proses yang sedang berjalan, tetapi proses yang ada di entry section tadi tidak bisa masuk ke critical section. Hal ini terjadi karena giliran untuk memasuki critical section adalah giliran proses yg lain sementara proses

tersebut masih berada di remainder section.

Untuk mengatasi masalah ini maka dapat diatasi dengan merubah variabel trun pada algoritma pertama dengan variabel flag, seperti pada algoritma kedua. Pada Algoritma ini digunakan boolean flag untuk melihat proses mana yang boleh masuk critical section. Proses yang butuh mengakses critical section akan memberikan nilai flagnya true. Sedangkan proses yang tidak sedang membutuhkan critical section akan memberikan nilai flagnya bernilai false. Suatu proses akan menggunakan critical section, jika tidak ada proses lain yang sedang membutuhkan critical section, dengan kata lain flag proses lainnya sedang bernilai false.

Pada algoritma ini terlihat bahwa setiap proses melihat proses lain, apakah proses lain itu menginginkan critical section atau tidak. Jika ya, maka proses tersebut akan menunggu proses lain selesai memakai critical section.

Pertama-tama, masing-masing flag di set false. Kemudian flag0 diset true, menandakan bahwa proses P0 ingin menggunakan critical section, lalu P0 melihat apakah flag1 true atau false (proses P1 menginginkan critical section atau tidak). Jika ya, maka proses P0 akan mengijinkan proses P1 menggunakannya dahulu dan P0 menunggu. Setelah selesai, maka proses P0 gantian menggunakan critical section tersebut, ditandai dengan P1 mengeset flag1=false. Permasalahan muncul ketika, kedua proses secara bersamaan menginginkan critical section, maka kedua proses akan menset flag masing-masing menjadi true. P0 menset flag0=true, P1 menset

flag1=true. Lalu P0 akan menunggu P1 selesai menggunakan critical section dengan melihat flag1 apakah masih true. Sedangkan P1 juga akan menunggu P0 selesai menggunakan critical section dengan melihat apakah flag0 masih true. Akibatnya tidak ada yang mengakses critical section, sedangkan ada proses(P0 dan P1) yang ingin mengaksesnya. Sehingga syarat progress tidak terpenuhi. Kondisi ini akan terus bertahan.

Algoritma 3

Idenya berasal dari algoritma 1 dan 2. Algoritma 3 mengatasi kelemahan pada algoritma 1 dan 2 sehingga progres yang diperlukan untuk mengatasi critical section terpenuhi.

Pertama-tama masing flag diset false, menandakan bahwa proses tersebut tidak ingin menggunakan critical section. Kemudian ketika ada proses yang menginkan critical section, maka ia akan mengubah flag(memberikan tanda bahwa ia butuh critical section) lalu proses tersebut memberikan turn kepada lawannya. Jika lawannya menginginkan critical section dan turn adalah turn lawannya maka ia akan menunggu. Misalkan, proses-proses dieksekusi sesuai langkah-langkah berikut, Ketika proses P0 menginginkan critical section, maka ia menset flag0=true, lalu P1 juga menginginkan critical section, maka ia akan menset flag1=true. Selanjutnya P0 memberikan turn pada P1(turn=1), lalu P1 juga memberikan turn pada P0(turn=0). Sehingga P0 dapat memasuki critical section, sedangkan P1 menunggu P0 selesai mengakses critical section lalu P0 merubah flag0=false. P1 sekarang dapat memasuki critical section, setelah selesai P1 akan merubah flag1=false, sedangkan turn terakhir bernilai 0. Jika P0 atau P1 selesai mengakses remainder section dan menginginkan critical section maka proses ini akan mirip seperti diatas tentunya yang lebih dulu memasuki critical section adalah yang lebih dulu memberikan turn. Jika hanya ada satu proses yang ingin memasuki critical section,

maka ia dapat langsung masuk karena tidak perlu menunggu(karena flag lawannya bernilai false, tidak peduli berapapun nilai turnnya).

Apabila kedua proses P0 dan P1 berjalan secara bersamaan, maka proses yang akan memasuki critical section lebih dulu adalah proses yang lebih dulu mempersilahkan proses lainnya (yang lebih dulu mengubah turn menjadi turn untuk proses lawan). Karena turn akan diberikan oleh proses yang terakhir kali memberikan turn, artinya proses yang terakhir akan menentukan nilai turn (merubah

turn menjadi turn untuk lawannya).

Syarat progress terpenuhi karena ketika critical section tidak ada yang menggunakan dan ada proses-proses yang ingin menggunakannya maka dipastikan akan ada yang menggunakan critical section tersebut.

Algoritma Tukang Roti

Algoritma ini didasarkan pada algoritma penjadwalan yang biasanya digunakan oleh tukang roti, di mana urutan pelayanan ditentukan dalam situasi yang sangat sibuk.

Contoh 20.1. Algoritma Tukang Roti

do {

choosing[i] = true;

number[i] = max(number[0], number [1], ..., number [n+1])+1;

choosing[i] = false;

for (j=0; j <>

while (choosing[j]);

while ((number[j]!=0) && ((number[j],j) <>

}

critical section

number[i] = 0;

remainder section

} while (1);

Algoritma ini dapat digunakan untuk memecahkan masalah critical section untuk n buah proses, yang diilustrasikan dengan n buah pelanggan. Ketika memasuki toko, setiap pelanggan menerima sebuah nomor. Sayangnya, algoritma tukang roti ini tidak dapat menjamin bahwa dua proses (dua pelanggan) tidak akan menerima nomor yang sama. Dalam kasus di mana dua proses menerima

nomor yang sama, maka proses dengan nomor ID terkecil yang akan dilayani dahulu. Jadi, jika Pi dan Pj menerima nomor yang sama dan i <> proses adalah unik dan berurut, maka algoritma ini dapat digunakan untuk memecahkan masalah critical section untuk n buah proses.

Struktur data umum algoritma ini adalah

boolean choosing[n];

int number [n];

Awalnya, struktur data ini diinisialisasi masing-masing ke false dan 0, dan menggunakan notasi berikut:

- (a, b) < (c, d) jika a < c atau jika a= c dan b < d

- max(a0, ..., an-1) adalah sebuah bilangan k, sedemikian

sehingga k >= ai untuk setiap i= 0, ..., n – 1



Nama anggota kelompok :
1. Nico Andri P (07.52.1016)
2. Iwan Pramono (07.52.1021)
3. Irlan Candra W (07.52.1023)
4. Nur ndah P (07.52.1017)
5. Hari Sugianto (06.52.1017)


Tidak ada komentar:

Posting Komentar