Swapping, Partitioning, dan Paging

Swaping

Sebuah proses, sebagaimana telah diterangkan di atas, harus berada di memori sebelum dieksekusi. Proses swapping menukarkan sebuah proses keluar dari memori untuk sementara waktu ke sebuah penyimpanan sementara dengan sebuah proses lain yang sedang membutuhkan sejumlah alokasi memori untuk dieksekusi. Tempat penyimpanan sementara ini biasanya berupa sebuah fast disk dengan kapasitas yang dapat menampung semua salinan dari semua gambaran memori serta menyediakan akses langsung ke gambaran tersebut. Jika eksekusi proses yang dikeluarkan tadi akan dilanjutkan beberapa saat kemudian, maka ia akan dibawa kembali ke memori dari tempat penyimpanan sementara tadi. Bagaimana sistem mengetahui proses mana saja yang akan dieksekusi? Hal ini dapat dilakukan dengan ready queue. Ready queue berisikan semua proses yang terletak baik di penyimpanan sementara maupun memori yang siap untuk dieksekusi. Ketika penjadwal CPU akan mengeksekusi sebuah proses, ia lalu memeriksa apakah proses bersangkutan sudah ada di memori ataukah masih berada dalam penyimpanan sementara. Jika proses tersebut belum berada di memori maka proses swapping akan dilakukan seperti yang telah dijelaskan di atas.

Gambar 2.1. Proses Swapping

Sebuah contoh untuk menggambarkan teknik swapping ini adalah sebagai berikut: Algoritma Round-Robin yang digunakan pada multiprogramming environment menggunakan waktu kuantum (satuan waktu CPU) dalam pengeksekusian proses-prosesnya. Ketika waktu kuantum berakhir, memory manager akan mengeluarkan (swap out) proses yang telah selesai menjalani waktu kuantumnya pada suatu saat serta memasukkan (swap in) proses lain ke dalam memori yang telah bebas tersebut. Pada saat yang bersamaan penjadwal CPU akan mengalokasikan waktu untuk proses lain dalam memori. Hal yang menjadi perhatian adalah, waktu kuantum harus cukup lama sehingga waktu penggunaan CPU dapat lebih optimal jika dibandingkan dengan proses penukaran yang terjadi antara memori dan disk.

Teknik swapping roll out, roll in menggunakan algoritma berbasis prioritas dimana ketika proses dengan prioritas lebih tinggi tiba maka memory manager akan mengeluarkan proses dengan prioritas yang lebih rendah serta me-load proses dengan prioritas yang lebih tinggi tersebut. Saat proses dengan prioritas yang lebih tinggi telah selesai dieksekusi maka proses yang memiliki prioritas lebih rendah dapat dimasukkan kembali ke dalam memori dan kembali dieksekusi.

Sebagian besar waktu swapping adalah waktu transfer. Sebagai contoh kita lihat ilustrasi berikut ini: sebuah proses pengguna memiliki ukuran 5 MB, sedangkan tempat penyimpanan sementara yang berupa harddiskmemiliki kecepatan transfer data sebesar 20 MB per detiknya. Maka waktu yang dibutuhkan untuk mentransfer proses sebesar 5 MB tersebut dari atau ke dalam memori adalah sebesar 5000 KB / 20000 KBps = 250 ms

Perhitungan di atas belum termasuk waktu latensi, sehingga jika kita asumsikan waktu latensi sebesar 2 ms maka waktu swap adalah sebesar 252 ms. Oleh karena terdapat dua kejadian dimana satu adalah proses pengeluaran sebuah proses dan satu lagi adalah proses pemasukan proses ke dalam memori, maka total waktu swap menjadi 252 + 252 = 504 ms.

Agar teknik swapping dapat lebih efisien, sebaiknya proses-proses yang di- swap hanyalah proses-proses yang benar-benar dibutuhkan sehingga dapat mengurangi waktu swap. Oleh karena itulah, sistem harus selalu mengetahui perubahan apapun yang terjadi pada pemenuhan kebutuhan terhadap memori. Disinilah sebuah proses memerlukan fungsi system call, yaitu untuk memberitahukan sistem operasi kapan ia meminta memori dan kapan membebaskan ruang memori tersebut.

Jika kita hendak melakukan swap, ada beberapa hal yang harus diperhatikan. Kita harus menghindari menukar proses dengan M/K yang ditunda (asumsinya operasi M/K tersebut juga sedang mengantri di antrian karena peralatan M/Knya sedang sibuk). Contohnya seperti ini, jika proses P1dikeluarkan dari memori dan kita hendak memasukkan proses P2, maka operasi M/K yang juga berada di antrian akan mengambil jatah ruang memori yang dibebaskan P1 tersebut. Masalah ini dapat diatasi jika kita tidak melakukan swap dengan operasi M/K yang ditunda. Selain itu, pengeksekusian operasi M/K hendaknya dilakukan pada buffer sistem operasi.

Tiap sistem operasi memiliki versi masing-masing pada teknik swapping yang digunakannya. Sebagai contoh pada UNIX, swapping pada dasarnya tidak diaktifkan, namun akan dimulai jika banyak proses yang membutuhkan alokasi memori yang banyak. Swapping akan dinonaktifkan kembali jika jumlah proses yang dimasukkan berkurang. Pada sistem operasi Microsoft Windows 3.1, jika sebuah proses baru dimasukkan dan ternyata tidak ada cukup ruang di memori untuk menampungnya, proses yang lebih dulu ada di memori akan dipindahkan ke disk. Sistem operasi ini pada dasarnya tidak menerapkan teknik swapping secara penuh, hal ini disebabkan pengguna lebih berperan dalam menentukan proses mana yang akan ditukar daripada penjadwal CPU. Dengan ketentuan seperti ini proses-proses yang telah dikeluarkan tidak akan kembali lagi ke memori hingga pengguna memilih proses tersebut untuk dijalankan.

Partitioning

Memori harus di diatur agar penempatan proses-proses tersebut dapat tersusun dengan baik. Hal tersebut berkaitan dengan banyaknya jumlah proses yang berada di memori pada suatu saat/waktu. Cara yang paling mudah adalah dengan membagi memori ke dalam beberapa partisi dengan ukuran yang tetap. Cara ini memungkinkan pembagian yang tidak sama rata. Tiap partisi dapat terdiri dari hanya satu buah proses. Sehingga derajat multiprogramming-nya dibatasi oleh jumlah partisi tersebut.

Gambar 2.3 mengilustrasikan multiprogramming dengan partisi memori yang tetap.

Gambar 2.3. Proses Partisi Memori Tetap

Ketika sebuah proses datang, ia akan diletakkan ke dalam input queue (antrian proses pada disk yang menunggu dibawa ke memori untuk dieksekusi) sesuai dengan ukuran terkecil partisi yang mampu menampungnya. Kerugian dari mengurutkan proses ke dalam antrian yang berbeda berdasarkan ukurannya muncul ketika partisi yang besar akan menjadi kosong karena tidak ada proses dengan ukuran sesuai yang diletakkan di partisi tersebut. Namun di lain sisi, antrian untuk partisi dengan ukuran kecil sangat padat karena banyaknya proses dengan ukuran yang sesuai. Cara alternatif yang dapat dilakukan adalah dengan membuat sebuah antrian tunggal seperti terlihat pada gambar diatas. Ketika sebuah partisi bebas, proses dengan ukuran sesuai partisi tersebut yang terletak di depan antrian dapat dimasukkan lalu dieksekusi. Namun metode ini memiliki kelemahan, yaitu bagaimana jika proses yang memasuki partisi yang cukup besar ternyata ukurannya jauh lebih kecil dari partisi itu sendiri? Masalah ini dapat diatasi dengan mencari proses terbesar ke dalam seluruh antrian yang dapat ditampung oleh sebuah partisi pada saat itu. Namun algoritma ini mendiskriminasikan proses yang kecil karena proses yang diambil adalah proses terbesar yang dapat dimuat ke dalam partisi yang sedang bebas saat itu.

Dalam partisi tetap ini, sistem operasi menggunakan sebuah tabel untuk mengindikasikan bagian memori mana yang kosong dan mana yang terisi. Pada awalnya semua partisi kosong dan dianggap sebagai sebuah blok besar yang tersedia (hole). Ketika sebuah proses datang dan membutuhkan memori, ia akan dicarikan lubang yang cukup besar yang mampu menampungnya. Setelah menemukannya, memori yang dialokasikan untuknya hanyalah sebesar memori yang dibutuhkannya sehingga menyisakan tempat untuk memenuhi kebutuhan proses lain. Sistem operasi mencatat kebutuhan memori masing-masing proses yang berada dalam antrian serta jumlah memori yang masih tersedia untuk menentukan proses mana yang harus dimasukkan. Sistem akan memiliki sebuah daftar yang berisi ukuran blok yang masih tersedia serta antrian masukan proses. Sistem operasi dapat mengurutkan antrian input tersebut berdasarkan algoritma penjadwalan. Memori dialokasikan pada proses yang ukurannya sesuai hingga akhirnya kebutuhan memori untuk proses berikutnya tidak dapat dipenuhi karena tidak ada lagi blok yang cukup untuknya. Sistem operasi akan menunggu hingga blok yang cukup besar untuk menampung proses tersebut tersedia atau sistem operasi dapat juga melewati proses tersebut dan mencari jikalau ada proses dengan kebutuhan memori yang dapat ditampung oleh blok memori yang tersedia. Pada kenyatannya, partisi tetap kurang mengoptimalkan memori sebagai sumber daya yang penting karena seringkali terjadi, partisi yang cukup besar dialokasikan untuk proses dengan ukuran yang lebih kecil sehingga sisa dari partisi tersebut tidak digunakan.

Pada alokasi penyimpanan dinamis, kumpulan lubang-lubang (ruang memori kosong) dalam berbagai ukuran tersebar di seluruh memori sepanjang waktu. Apabila ada proses yang datang, sistem operasi akan mencari lubang yang cukup besar untuk menampung memori tersebut. Apabila lubang yang tersedia terlalu besar, maka ia akan dipecah menjadi 2. Satu bagian digunakan untuk menampung proses tersebut sedangkan bagian lain akan digunakan untuk bersiap-siap menampung proses lain. Setelah proses tersebut selesai menggunakan alokasi memorinya, ia akan melepaskan ruang memori tersebut dan mengembalikannya sebagai lubang-lubang kembali. Apabila ada 2 lubang yang berdekatan, keduanya akan bergabung untuk membentuk lubang yang lebih besar. Pada saat itu, sistem harus memeriksa apakah ada proses dalam antrian yang dapat dimasukkan ke dalam ruang memori yang baru terbentuk tersebut. Isu utama dari alokasi penyimpanan dinamis adalah bagaimana memenuhi permintaan proses berukuran n dengan kumpulan lubang-lubang yang tersedia. Ada beberapa solusi untuk masalah ini:

1. First Fit.  Memory manager akan mencari sepanjang daftar yang berisi besarnya ukuran memori yang dibutuhkan oleh proses dalam antrian beserta ukuran memori yang tersedia pada saat itu. Setelah menemukan lubang yang cukup besar (ruang memori dengan ukuran lebih besar dari ukuran yang dibutuhkan oleh proses bersangkutan), lubang itu lalu dipecah menjadi 2 bagian. Satu bagian untuk proses tersebut dan bagian lain digunakan untuk memori yang tak terpakai, kecuali tentu saja jika memang ukuran ruang memori tersebut sama besar dengan yang dibutuhkan oleh proses. First fit ini merupakan algoritma yang bekerja dengan cepat karena proses pencariannya dilakukan sesedikit mungkin
2. Next Fit.  Algoritma ini hampir sama persis dengan first fit, kecuali next fit meneruskan proses pencarian terhadap lubang yang cukup besar untuk sebuah proses mulai dari lubang sebelumnya yang telah sesuai dengan proses sebelumnya. Pendek kata, algoritma ini tidak memulai pencarian dari awal. Gambar di bawah ini mengilustrasikan sebuah contoh yang membedakan antara first fit dan next fit. Jika blok berukuran 2 dibutuhkan maka first fit akan memilih lubang pada alamat 5, namun next fit akan memilih lubang pada 18.
   
   Gambar 2.4. Bagian Memori dengan 5 Proses dan 3 Lubang
   
   
3. Best Fit.  Best fit mencari dari keseluruhan daftar (kecuali jika daftar tersebut telah terurut berdasarkan ukuran), dan memilih lubang terkecil yang cukup untuk menampung proses yang bersangkutan. Daripada harus memecah sebuah lubang besar, yang mungkin saja dapat lebih bermanfaat nantinya, best fit mencari lubang dengan ukuran yang hampir sama dengan yang dibutuhkan oleh proses. Strategi ini menghasilkan sisa lubang terkecil. Kekurangan best fit jika dibandingkan dengan first fit adalah lebih lambat karena harus mencari ke seluruh tabel tiap kali dipanggil. Berdasarkan gambar diatas jika blok berukuran 2 dibutuhkan maka berdasarkan best fit akan memilih lubang pada alamat 18 yaitu lubang terkecil yang cukup menampung permintaan proses tersebut.
4. Worst Fit.  Worst fit akan mencari lubang terbesar. Sebagaimana best fit kita harus mencari dari keseluruhan daftar kecuali jika daftar tersebut telah terurut berdasarkan ukuran. Strategi ini menghasilkan sisa lubang terbesar. Berdasarkan gambar diatas jika blok berukuran 2 dibutuhkan maka berdasarkan worst fit akan memilih lubang pada alamat 28 yaitu lubang terbesar yang cukup menampung permintaan proses tersebut.
   
   Paging
   Sistem Paging Adalah sistem manajemen pada sistem operasi dalam mengatur program yang sedang berjalan. Program yang berjalan harus dimuat di memori utama. Kendala yang terjadi apabila suatu program lebih besar dibandingkan dengan memori utama yang tersedia.
   Untuk mengatasi hal tersebut Sistem Paging mempunyai 2 solusi, yaitu:
   ·         Konsep OverlayDimana program yang dijalankan dipecah menjadi beberapa bagian yang dapat dimuat memori (overlay).
   ·         Konsep Memori Maya (virtual Memory)Adalah kemampuan mengalamati ruang memori melebihi memori utama yang tersedia. Konsep ini pertama kali dikemukakan Fotheringham pada tahun 1961 untuk sistem komputer Atlas di Universitas Manchester, Inggris.
   
   
   Pengertian
   Paging adalah suatu metode yang mengizinkan alamat logika proses untuk dipetakan ke alamat fisik memori yang tidak berurutan, yaitu sebagai solusi dari masalah fragmentasi ekstern. Metode dasar dari paging adalah dengan memecah memori fisik menjadi blok-blok yang berukuran tertentu (frame) dan memecah memori logika menjadi blok-blok yang berukuran sama (page).
   Paging merupakan teknik menampilkan data dengan cara membaginya ke beberapa halaman. Teknik ini diberikan untuk mengurangi scrolling window apabila data yang disajikan terlalu banyak, sehingga akan menimbulkan kejemuan orang yang melihat dan juga akan menghasilkan page load time yang besar karena ukuran filenya besar (apabila data disajikan dalam satu halaman saja).
   
   
   v  Kekurangan dan Kelebihan Sistem Paging
   Sistem paging mempunyai keunggulan dan kelemahan masing-masing. Sistem paging transparan bagi pemrograman, mengeleminasi fragmentasi eksternal, penggunaan memori utama yang efisisen.Karena ptongan-potongan yang dipindahkan masuk dan keluar memori utama berukuran sama, maka dimungkinkan mengembangkan algoritma manajemen memori yang memanfaatkan kelakuan program.
   
   
    Segmentasi Secara Murni
   Segmen – segmen dapat berukuran berbeda dan dinamis. Pengacuan pengacuan memori berbentuk (nomor segmen, offset).Alamat maya adalah offset di segmen. Tiap proses mempunyai tabel segmen. Ketika proses Running, alamat awal tabel dimuatkan ke register dasar. Nomor segmen digunakan untuk mencari deskriptor segmen di tabel segmenyang menyediakan alamatfisik awal segmen, panjangnya dan bit – bit proteksi. Alamat fisik dihitung dengan menambahkan alamat dasar segmen ke alamat maya.
   
   
   Teknik Kombinasi
   Sistem paging mempunyai keunggulan dan kelemahan masing-masing. Sistem paging transparan bagi pemrograman, mengeleminasi fragmentasi eksternal, penggunaan memori utama yang efisisen. Karena ptongan-potongan yang dipindahkan masuk dan keluar memori utama berukuran sama, maka dimungkinkan mengembangkan algoritma manajemen memori yang memanfaatkan kelakuan program.Segmentasi tampak oleh pemrograman sehingga pemrograman harus memperhatikan. Segmentasi berkemampuan menangani pertumbuhan sturktur data, modularitas serta mendukung pemakaian bersama dan proteksi.
   
   
   Metode Dasar
   Sistem paging mempunyai keunggulan dan kelemahan masing-masing. Sistem paging transparan bagi pemrograman, mengeleminasi fragmentasi eksternal, penggunaan memori utama yang efisisen. Karena ptongan-potongan yang dipindahkan masuk dan keluar memori utama berukuran sama, maka dimungkinkan mengembangkan algoritma manajemen memori yang memanfaatkan kelakuan program.Segmentasi tampak oleh pemrograman sehingga pemrograman harus memperhatikan. Segmentasi berkemampuan menangani pertumbuhan sturktur data, modularitas serta mendukung pemakaian bersama dan proteksi.Contoh Translasi Alamat Pada Sistem Paging
   
   
   v  Tabel Halaman Bertingkat
   Hierarchical paging atau pemberian halaman secara bertingkat merupakan sebuah metode pemberian halaman dengan cara membagi sebuah page table menjadi beberapa page table yang berukuran lebih kecil. Metode ini merupakan solusi dari permasalahan alokasi page table berukuran sangat besar pada main memory yang umumnya dihadapi pada sistem komputer modern yang memiliki ruang alamat logika yang besar sekali (mencapai 2 pangkat 32 sampai 2 pangkat 64).
   Translasi Alamat pada Two-Level Paging
   
   v  Tabel Halaman Dengan HashMetode ini umumnya digunakan untuk menangani masalah ruang alamat logika yang besarnya mencapai 64 bit karena struktur page table pada metode ini bisa menghemat ruang memori dalam jumlah yang cukup besar.
   Hashed page table menggunakan tabel hash sebagai page table-nya dengan ukuran yang terbatas untuk menghemat ruang memori dan sebuah hash function untuk mengalokasikan alamat virtual pada page table tersebut.Setiap entri/blok pada page table berisi linked list yang menghubungkan elemen-elemen yang di- hash ke lokasi yang sama. page table berisi linked list yang menghubungkan elemen-elemen yang di- hash ke lokasi yang sama.
   
   PROTEKSIProteksi memori dapat diterapkan pada sistem paging dengan meletakkan bit proteksi pada setiap frame. Bit proteksi umumnya disimpan pada page table. Sebuah bit proteksi dapat mendefinisikan apakah page bersifat read-only atau read-write. Untuk memberikan proteksi yang lebih baik, dapat pula ditambahkan bit lainnya, misalnya untuk sifat execute-only.                       . Manajemen Memory Sistem PagingWalaupun sistem partisi dinamis sudah dapat menyelesaikan masalah menjemen memory banyak hal tetapi masih mempunyai keterbatasan acses sebatas address memory yang ada secara phisik. Kalau kita punya memory 32 MB maka address maksimum yang dapat di akses sebesar 32 MB itu saja. Agar kemampuan akses ke memory lebih luas maka dibentuklah memory maya (virtual memory).