A F G .docx

A. Penjadwalan proses Preemptive, Non Preemptive; FCFS, SJF, SRTF, RR, Prioritas, Multilevel Queue, Multilevel Feed- back Queue 

Algoritma Penjadwalan First Come First Served (FCFS)

Algoritma ini merupakan algoritma penjadwalan yang paling sederhana yang digunakan CPU. Dengan menggunakan algoritma ini setiap proses yang berada pada status ready dimasukkan kedalam FIFO queue atau antrian dengan prinsip first in first out, sesuai dengan waktu kedatangannya. Proses yang tiba terlebih dahulu yang akan dieksekusi. Proses yang pertama kali meminta jatah waktu untuk menggunakan CPU akan dilayani terlebih dahulu. Dan rata-rata waktu tunggu (Average waiting time) cukup tinggi.Algoritma penjadwalan FCFS merupakan salah satu strategi penjadwalan non-Preemptive karena sekali CPU dialokasikan pada suatu proses, maka proses tersebut akan tetap memakai CPU sampai proses tersebut melepaskannya, yaitu jika proses berhenti atau meminta I/O. Kelemahan dari Algoritma penjadwalan ini adalah adanya convoy effect. skema proses yang meminta CPU mendapat prioritas. Implementasi dari FCFS mudah diatasi dengan FIFO queue. Contoh: Terdapat 3 proses seperti pada tabel berikut:

Hitunglah AWT menggunakan algoritma FCFS Maka gantt chart kedatangan proses:

Sehingga waktu tunggu untuk tiap-tiap proses terlihat pada tabel berikut:

AWT = (0+23+29)/3 = 17,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 nonpreemptive, yaitu setiap proses yang sedang dieksekusi oleh CPU tidak dapat di-interrupt oleh proses yang lain.



Algoritma Shortest Job First Scheduler (SJF/SJFS)

Pada algoritma ini 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. Burst time : asumsi berapa lama sebuah proses membutuhkan CPU diantara proses menunggunya I/O. Hal ini tidak dapat diprediksi secara tepat sebelum dimulainya sebuah proses. Artinya jumlah waktu yang dibutuhkan sebuah proses dalam menggunakan CPU dalam sebuah satuan waktu.(Sebuah proses dapat menggunakan CPU selama beberapa kali selama task yang diberikan belum diselesaikan). Algoritma ini digunakan ketika CPU bebas proses yang mempunyai waktu terpendek untuk menyelesaikannya mendapat prioritas. Seandainya dua proses atau lebih mempunyai waktu yang sama maka FCFS algoritma digunakan untuk menyelsaikan masalah tersebut.Prinsip algoritma penjadwalan ini adalah, proses yang memiliki CPU burst paling kecil dilayani terlebih dahulu. Oleh karena itu, algoritma ini optimal jika digunakan, tetapi sulit untuk diimplementasikan karena sulit mengetahui CPU burst selanjutnya. CONTOH SHORTEST JOB FIRST (SJF) :

Contoh: Ada 4 buah proses yang datang berurutan yaitu :

   

1. 2.

P1 dengan arrival time pada 0.0 ms dan burst time 7 ms,. P2 dengan arrival time pada 2.0 ms dan burst time 4 ms. P3 dengan arrival time pada 4.0 ms dan burst time 1 ms. P4 dengan arrival time pada 5.0 ms dan burst time 4 ms.

Hitunglah waiting time rata-rata dan turnaround time dari keempat proses tersebut dengan mengunakan algoritma SJF. Average waiting time rata-rata untuk ketiga proses tersebut adalah sebesar (0 +6+3+7)/4=4 ms. Average waiting time rata-rata untuk ketiga prses tersebut adalah sebesar (9+1+0+2)/4=3 ms. Ada beberapa kekurangan dari algoritma ini yaitu: Susahnya untuk memprediksi burst time proses yang akan dieksekusi selanjutnya. 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.(SRTF) CONTOH SJF-PREEMPTIVE:

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 SJF-NON PREEMPTIVE :



Algoritma Priority Scheduling

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. 2. 3. 4. 5.

Time limit. Memory requirement. Akses file. Perbandingan antara burst M/K dengan CPU burst. 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: Terdapat 5 proses seperti pada tabel berikut:

Hitunglah AWT menggunakan algoritma PS.

Maka gantt chart kedatangan proses:

Sehingga waktu tunggu untuk tiap-tiap proses terlihat pada tabel berikut:

AWT = (12+22+19+2)/5 = 11 ms.



Algoritma 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 yaitu (1/n), dan tak akan menunggu lebih lama dari (n1)q dengan q adalah lama 1 quantum. 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 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. Contoh: Terdapat 3 proses seperti pada tabel berikut:

Hitunglah AWT menggunakan algoritma RR dengan Q=3.

Maka gantt chart kedatangan proses:

Sehingga waktu tunggu untuk tiap-tiap proses terlihat pada tabel berikut:

AWT = (12+9+12)/3 = 11 ms. PROSES KEJADIAN ALGORITMA ROUND ROBIN : Urutan Kejadian Algoritma Round Robin

Penggunaan Waktu Quantum

Ide dasar dari algoritma ini berdasarkan pada sistem prioritas proses. Prinsipnya, jika setiap proses dapat dikelompokkan berdasarkan prioritasnya, maka akan didapati queue seperti pada gambar berikut:Multilevel Queue Gambar Multilevel Queue

Dari gambar tersebut terlihat bahwa akan terjadi pengelompokan proses-proses berdasarkan prioritasnya. Kemudian muncul ide untuk menganggap kelompok-kelompok tersbut 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 yang memiliki banyak kelemahan. Oleh karena itu, dalam prakteknya, algoritma multilevel queue memungkinkan adanya penerapan algoritma internal dalam masing-masing sub-antriannya yang bisa memiliki algoritma internal yang berbeda untuk meningkatkan kinerjanya. 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.

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. Hal 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 M/K dapat terus sibuk. Semakin rendah tingkatannya, panjang CPU burst proses juga semakin besar.

Gambar Multilevel Feedback Queue

Algoritma ini didefinisikan melalui beberapa parameter, antara lain: a. b. c. d. e.

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 multilevel queue. 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. 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. 2. 3. 4. 5.

Jumlah antrian. Algoritma internal tiap queue. Aturan sebuah proses naik ke antrian yang lebih tinggi. Aturan sebuah proses turun ke antrian yang lebih rendah. Antrian yang akan dimasuki tiap proses yang baru datang.

Contoh: Terdapat tiga antrian; Q1=10 ms, FCFS Q2=40 ms, FCFS Q3=FCFS proses yang masuk, masuk ke antrian Q1. Jika dalam 10 ms tidak selesai, maka proses tersebut dipindahkan ke Q2. Jika dalam 40 ms tidak selesai, maka dipindahkan lagi ke Q3. 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.

F. Virtual Memory

DEMAND PAGING Demand Paging atau permintaan pemberian halaman adalah salah satu implementasi dari memori virtual yang paling umum digunakan. Demand paging pada prinsipnya hampir sama dengan permintaan halaman ( paging ) hanya saja halaman ( page ) tidak akan dibawa ke dalam memori fisik sampai ia benar-benar diperlukan. Untuk itu diperlukan bantuan perangkat keras untuk mengetahui lokasi dari page saat ia diperlukan. Page diletakkan di memori hanya jika diperlukan. Hal ini menyebabkan kebutuhan I/O lebih rendah, kebutuhan memori lebih rendah, respon lebih cepat dan lebih banyak user yang menggunakan.

Proses disimpan di memori sekunder (disk). Jika proses akan dieksekusi, maka dipindah (swap) ke memori. Menggunakan lazy swapper untuk melakukan swapping bila page tersebut akan digunakan yang berarti sebuah page tidak pernah ditukar ke memori kecuali page diperlukan. Jika page diperlukan, dilakukan acuan ke page tersebut, tetapi jika acuan invalid maka dilakukan penghentian. Untuk membedakan antara page pada memori dengan page pada disk digunakan valid-invalid bit. Tabel page untuk page yang berada di memori diset “valid’, sedangkan tabel page untuk page yang tidak sedang di memori (ada pada disk) diset “invalid”. Akses ke page yang diset “invalid” menyebabkan page fault, yang menyebabkan trap ke sistem operasi. Karena status (register, kode kondisi, counter instruksi) dari proses ter-interrupt disimpan bila terjadi page fault, proses dapat dimulai lagi pada tempat dan status yang sama, kecuali page yang cocok sedang di memori dan sedang diakses. Prosedur untuk menangani page fault.      

Sistem operasi melihat tabel untuk menentukan jika acuan invalid maka proses dihentikan dan page sedang tidak berada di memori. Jika acuan invalid dilakukan trap ke sistem operasi. Sistem mencari frame kosong Sistem melakukan proses swapping ke frame bebas. Tabel page di-reset, bit valid-invalid diset 1 atau valid instruksi di-restart.

Apabila tidak ditemukan frame bebas maka dilakukan page replacement yaitu mencari beberapa page di memori yang tidak digunakan kemudian dilakukan swap out ke backing store. Terdapat beberapa algoritma page replacement dimana performansi algoritma diharapkan menghasilkan jumlah page fault minimum. Beberapa page kemungkinan dibawa ke memori beberapa kali Perangkat keras yang dibutuhkan untuk mendukung demand paging sama dengan perangkat keras untuk sistem paging dengan swapping yaitu Tabel page : table mempunyai kemampuan untuk memberi entry bit valid-invalid atau nilai khusus untuk bit proteksi Memori sekunder : digunakan untuk membawa page yang tidak di memori dan biasanya adalah disk kecepatan tinggi yang disebut swap device.

Algoritma page replacement Algoritma page replacement secara umum diinginkan mempunyai rata-rata page fault terendah. Algoritma dievaluasi dengan menjalankan pada string tertentu dari memori reference dan menghitung jumlah page fault. String yang mengacu ke memori disebut reference string (string acuan). String acuan dibangkitkan secara random atau dengan menelusuri sistem dan menyimpan alamat dari memori acuan.

Terdapat beberapa algoritma page replacement, setiap sistem operasi mempunyai skema yang unik. Algoritma page replacement secara umum diinginkan yang mempunyai rata-rata page fault terendah. Algoritma page replacement di antaranya adalah: 1. 2. 3. 4. 5. 6. 7.

Algoritma page replacement Acak Algoritma page replacement FIFO Algoritma page replacement Optimal Algoritma page replacement NRU Algoritma page replacement LRU Algoritma page replacement Second Chance Page Algoritma page replacement Clock

Mari kita bahas satu per-satu Algoritma Page Replacement di atas. 1. Algoritma Page Replacement Acak Dari segi mekanisme algoritma tersebut, setiap akan timbul page fault, page yang diganti dengan pilihan secara acak. Untuk segi tekniknya sendiri pun algoritma ini tidak perlu menggunakan informasi dalam menentukan page yang diganti, di dalam memory utama itu sendiri pun sudah mempunyai bobot yang sama untuk dipilih, karena teknik ini dapat dipakai untuk memilih page sembarang. Termasuk page yang sudah dipilih dengan benar-benar / page yang tidak seharusnya diganti.

Contoh gambar algoritma page replacement acak 2. Algoritma Page Replacement FIFO (First In - First Out) Inti dari algoritma ini adalah simple / paling sederhana karena prinsipnya sama seperti prinsip antrian tak berprioritas. Page yang masuk terlebih dahulu maka page tersebut akan keluar duluan juga. Untuk algoritma ini menggunakan structure data stack. Jadi cara kerjanya yaitu dimana ketika tidak ada frame yang kosong saat terjadi page fault maka korban yang dipilih adalah frame dengan stack paling bawah seperti hal nya halaman yang sudah lama tersimpan didalam memory maka dari itu algoritma ini juga bisa memindahkan page yang sering digunakan.

Contoh gambar page replacement FIFO Dulu algoritma ini di anggap cukup mengatasi pergantian page sampai pada tahun 70-an, pada saat itu juga Belady menemukan keganjalan pada algoritma ini dan dikenal dengan anomali Belady. Anomali Belady itu sendiri ialah keadaan dimana page fault rate meningkat seiring dengan pertambahannya jumlah frame.

Contoh gambar anomali Belady pada algoritma FIFO 3. Algoritma Page Replacement Optimal Pengertian dari algoritma ini sendiri yaitu algoritma yang page nya paling optimal. Untuk prinsip dari algoritma ini sangat efisien sekali karena hanya mengganti halaman yang sudah tidak terpakai lagi dalam jangka waktu lama sehingga page fault yang terjadi akan berkurang dan terbebas dari

anomali Belady Selain itu juga page fault dari algoritma ini memiliki rate paling tinggi dari algoritma lainnya dari semua kasus, akan tetapi belum bisa disebut sempurna karena sulit untuk dimengerti dan dari segi system pun belum tentu bisa mengetahui page untuk berikutnya tetapi dapat disimulasikan hanya untuk suatu program. Untuk intinya gunakanlah hingga mendekati page optimal agar bisa memanfaatkannya.

Contoh gambar page replacement optimal 4. Algoritma Page Replacement NRU (Not Recently Used) Untuk mekanisme dari algoritma ini diberi dua bit untuk mencatat status page, diantaranya bit M dan R yaitu : Bit M : Page yang telah dimodifikasi Bit M = 0 berarti tidak dimodif Bit M = 1 berarti sudah dimodif Bit R : Page yang sedang dipacu / referenced Bit R = 1 berarti sedang di acu Bit R = 0 berarti tidak sedang di acu Adanya dua bit di atas maka akan dapat dikelompokkan menjadi 4 kelas page, yaitu : Kelas 0 => Tidak sedang di acu / belum di modif (R=0, M=0) Kelas 1 => Tidak sedang di acu / telah di modif (R=0, M=1) Kelas 2 => Sedang di acu / belum di modif (R=1, M=0) Kelas 3 => Sedang di acu / telah di modif (R=1, M=1) Jadi, apabila algoritma ini diasumsikan kelas-kelas bernomor lebih rendah baru akan digunakan kembali dalam relatif jangka waktu lama. Intinya algoritma ini mudah dipahami dan dikembangkan karena sangat efisien walaupun tak banyak langkah dalam pemilihan page dan kelemahannya juga tidak optimal tapi dalam kondisi normal yang memadai.

5. Algoritma Page Replacement LRU (Least Recently Used) Dikarenakan algoritma optimal sangat sulit dalam pengimplementasiannya, maka dibuatlah algoritma lain yang performance-nya mendekati algoritma optimal dengan sedikit cost yang lebih besar. Sama seperti algoritma optimal, algoritma LRU tidak mengalami anomali Belady. Algoritma ini memakai linked list untuk mendata halaman mana yang paling lama tidak terpakai. Linked list inilah yang membuat cost membesar, karena harus meng-update linked list tiap saat ada halaman yang di akses.

Contoh gambar page replacement LRU 6. Algoritma Page Replacement Second Chance Page Algoritma second chance merupakan hasil modifikasi dari algoritma FIFO yang disempurnakan lagi. Algoritma ini menggunakan tambahan berupa reference bit yang nilainya 0 atau 1. Jika dalam FIFO menggunakan stack, maka second chance menggunakan circular queue. Halaman yang baru di-load atau baru digunakan akan diberikan nilai 1 pada reference bit-nya. Halaman yang reference bit-nya bernilai 1 tidak akan langsung diganti walaupun dia berada di antrian paling bawah (berbeda dengan FIFO). Urutan langkah kerja algoritma second chance adalah sebagai berikut: 



Apabila terjadi page fault dan tidak ada frame yang kosong, maka akan dilakukan razia (pencarian korban) halaman yang reference bit-nya bernilai 0 dimulai dari bawah antrian (seperti FIFO). Setiap halaman yang tidak di- swap (karena reference bit-nya bernilai 1), setiap dilewati saat razia reference bit-nya akan diset menjadi 0.

Contoh gambar algoritma page replacement SCP

7. Algoritma Page Replacement Clock Algoritma Clock merupakan hasil modifikasi dari algoritma FIFO yang kedua dan juga merupakan model lain dari algoritma page replacement second chance page, namun dalam implementasinya menggunakan 'circular queue' dengan page berbentuk lingkaran. Jika : Nilai bit = 0, ganti page Nilai bit = 1 - Ubah nilai bit = 0 - Pointer bergerak ke page berikutnya searah jarum jam.

G. Alokasi Berurut (Contiguous) Memori harus mengakomodasi kebutuhan SO dan proses user. Memori utama biasanya terbagi dalam dua bagian:  Resident operating system, biasanya tersimpan di alamat memori rendah.  User proces menggunakan memori beralamat tinggi/besar. Alokasi berurut terbagi menjadi tiga yakni: 1.

Partisi statis Ciri-ciri dari partisi statis sebagai berikut:

1. Memori dibagi menjadi partisi-partisi dengan ukuran yang tetap. 2. Satu proses hanya memakai satu partisi. Jika proses sudah selesai, partisi tersebut dapat digunakan proses yang lain. 3. Dibagi menjadi 2 bagian: a) Berukuran sama Banyak kelemahan, antara lain: Proses yang ukurannya lebih besar dari ukuran partisi tidak dapat dialokasikan. Sebaliknya bila ukuran proses lebih kecil daripada ukuran partisi, maka akan terjadi pemborosan ruang memori (Fragmentasi internal). b) Berukuran tidak sama Untuk mengatasi kelemahan dari Pengalokasian berurut dengan partisi statis dengan ukuran sama, yaitu proses ukuran kecil diletakkan ke partisi yang kecil dan sebaliknya. Ada 2 jenis strategi: 1) Satu antrian untuk setiap partisi Tiap proses diletakkan pada partisi dengan ukuran terkecil yang dapat dimuatnya. Kelemahan: ada partisi yang memiliki antrian panjang dan ada yang kosong. 2) Satu antrian untuk seluruh partisi Semua proses dimasukkan pada satu antrian yang sama, Algoritma penjadwalan melakukan pemilihan partisi Kelemahan: jika proses yang berukuran kecil terpaksa masuk ke partisi sisa yang besar, sehingga terjadi pemborosan ruang.

2. Partisi Dinamis Ciri-ciri: 1. Pada kondisi awal, memori tidak dibagi menjadi partisi-partisi 2. Pemartisian dilakukan pada saat image proses akan disalin ke memori utama. 3. Ukuran partisi yang dialokasikan akan disesuaikan dengan ukuran image proses. 4. Partisi akan dibebaskan jika program sudah selesai. 5. Keuntungan : tidak terjadi fragmentasi internal alokasi memori disesuaikan dengan besarnya image proses. Cara kerja: 1.

Pengalokasian dilakukan dengan mencari hole  suatu ruang memori utama yang kosong, yang cukup besar untuk menampung image proses.

2.

Hole sisa kadang kala terlalu kecil untuk dapat dialokasikan ke proses lainnya sehingga tidak bisa digunakan lagi  fragmentasi eksternal.

3. Salah satu cara untuk mengatasi masalah ini adalah melakukan memory compaction. Yaitu: menggeser image proses-proses yang ada di memori sehingga hole terkumpul di satu tempat saja Kelemahan:

 proses alokasi dan dealokasi menjadi lebih rumit  Perlu pengelolaan informasi area memori yang masih kosong.

Ada 2 metode pengelolaan memori kosong: 1. Peta bit (bitmap)  Menggunakan area memori khusus untuk mencatat seluruh area kosong pada memori utama.  Memakai nilai 0 dan 1  Nilai 0  alamat memori tersebut masih kosong  Nilai 1  alamat memori tersebut sudah terisi

2. Linked list  Informasi mengenai hole kosong berikutnya dicatat pada hole kosong sebelumnya.  Tidak diperlukan area memori khusus. Karena seluruh informasi tercatat di area memori kosong itu sendiri sehingga menghemat kapasitas memori utama.

Diperlukan algoritma untuk menentukan hole mana yang akan dialokasikan ke suatu proses. 1. Algoritma Best-fit  Mencari memori blok yang paling kecil yang dapat menampung image proses  Memerlukan waktu lama karena harus searching seluruh blok memori utama  Fragmentasi eksternal dapat ditekan sekecil mungkin

2. Algoritma First-fit  Mencari memori kosong dari alamat awal sampai menemukan blok yang dapat menampung image proses  Sederhana dan cepat.

3. Algoritma Next-fit  Hampir sama dengan First-fit.  Bedanya: proses searching dimulai dari alamat alokasi terakhir

4. Algoritma Worst-fit  Mencari hole yang paling besar di seluruh area memori utama.  Tujuannya: hole sisa yang tercipta setelah alokasi masih cukup besar untuk dialokasikan ke proses lainnya.

3.

Sistem Buddy

 Berupa pemartisian secara dinamis  Ciri khusus adalah partisi yang terbentuk senantiasa berukuran besar sebesar bilangan

2n

2,4,8,16…..256,512,1024(1Mb) Alokasi memori pada sistem buddy: 1) Menentukan ukuran partisi  Ditentukan ukuran partisi untuk menampung image proses yaitu ukuran bilangan pangkat 2 terkecil  Misal : ukuran image proses = 12kb, maka ukuran partisi yang bisa digunakan adalah 16kb.

2) Pengalokasian  Selanjutnya adalah mencari hole yang ukurannya sebesar perhitungan.  Jika tidak ada maka dicarikan hole yang berukuran sedikit lebih besar. Kemudian dipecah secara bertahap sesuai dengan aturan bilangan pangkat 2.  Misal : ukuran image proses = 12kb dan hole yang paling kecil adalah 64kb.  maka dipecah menjadi 2 partisi 32kb, selanjutnya dipecah lagi menjadi 2 partisi 16kb.  dan partisi 16kb pertama yang bisa dipakai untuk image proses 12kb.