WEEK 05

1. First Come First Serve

   First Come First Serve adalah CPU scheduling algorithm termudah dan paling sederhana. Dalam jenis algoritme ini, proses yang meminta CPU mendapatkan alokasi CPU terlebih dahulu. Metode penjadwalan ini dapat diatur dengan antrian first in first out (FIFO). Saat proses memasuki antrean siap, PCB (Process Control Block) -nya dihubungkan dengan ujung antrean. Jadi, ketika CPU sudah bebas, C{U harus ditugaskan ke proses di awal antrian. Karakteristik dari First Come First Serve adalah menawarkan scheduling algorithm non-preemptive dan pre-emptivek, pekerjaan selalu dijalankan atas dasar siapa cepat dia dapat, mudah diimplementasikan dan digunakan, dan sayangnya metode ini memiliki kinerja yang buruk, dan waktu tunggu umumnya cukup tinggi.

2. Shortest Remaining Time

   Shortest Remaining Time juga dikenal sebagai preemptive scheduling SJF. Dalam metode ini, proses akan dialokasikan ke tugas yang paling dekat dengan penyelesaiannya. Metode ini mencegah proses status siap yang lebih baru menahan penyelesaian proses yang lebih lama. karakteristik dari shortest remaining time adalah metode ini sebagian besar diterapkan di lingkungan batch di mana pekerjaan singkat harus diberikan preferensi, bukan metode yang ideal untuk menerapkannya dalam sistem bersama di mana waktu CPU yang diperlukan tidak diketahui, dan mengasosiasikan dengan setiap proses sebagai panjang ledakan CPU berikutnya. Sehingga sistem operasi menggunakan panjang ini, yang membantu menjadwalkan proses dengan waktu sesingkat mungkin.

3. Priority Based Scheduling

   Priority Based Scheduling adalah metode proses scheduling berdasarkan prioritas. Dalam metode ini, penjadwal memilih tugas yang akan dikerjakan sesuai prioritas. Scheduling prioritas juga membantu OS untuk melibatkan penetapan prioritas. Proses dengan prioritas yang lebih tinggi harus dilakukan terlebih dahulu, sedangkan pekerjaan dengan prioritas yang sama dilakukan secara round-robin atau FCFS. Prioritas dapat ditentukan berdasarkan kebutuhan memori, persyaratan waktu, dll.

4. Round-Robin Scheduling

   Round robin adalah algoritma penjadwalan tertua dan paling sederhana. Nama algoritma ini berasal dari prinsip round-robin, di mana setiap orang mendapat bagian yang sama secara bergantian. Ini sebagian besar digunakan untuk menjadwalkan algoritma dalam multitasking. Metode algoritma ini membantu eksekusi proses tanpa kelaparan. Karakteristik dari Round-Robin Scheduling adalah Round robin adalah model hybrid yang digerakkan oleh jam, bagian waktu harus minimum, yang ditetapkan untuk tugas tertentu yang akan diproses. Namun, ini mungkin berbeda untuk proses yang berbeda, ini adalah sistem waktu nyata yang menanggapi acara dalam batas waktu tertentu.

5. Shortest Job First

   SJF adalah bentuk penuh (Shortest job first) adalah algoritma penjadwalan dimana proses dengan waktu eksekusi terpendek harus dipilih untuk eksekusi selanjutnya. Metode penjadwalan ini dapat bersifat preemptive atau non-preemptive. Ini secara signifikan mengurangi waktu tunggu rata-rata untuk proses lain yang menunggu eksekusi. Karakteristik dari SJF adalah metode ini berkaitan dengan setiap pekerjaan sebagai unit waktu untuk diselesaikan. Dalam metode ini, ketika CPU tersedia, proses atau pekerjaan berikutnya dengan waktu penyelesaian terpendek akan dijalankan terlebih dahulu. Metode ini diimplementasikan dengan kebijakan non-preemptive. Metode algoritme ini berguna untuk pemrosesan tipe batch, di mana menunggu pekerjaan selesai tidak penting. Metode ini ini meningkatkan hasil pekerjaan dengan menawarkan pekerjaan yang lebih pendek, yang harus dijalankan terlebih dahulu, yang sebagian besar memiliki waktu penyelesaian yang lebih pendek.

6. Multiple-Level Queues Scheduling

   Multiple-Level Queues Scheduling memisahkan antrian siap menjadi beberapa antrian terpisah. Dalam metode ini, proses ditetapkan ke antrian berdasarkan properti tertentu dari proses tersebut, seperti prioritas proses, ukuran memori, dll. Namun, ini bukan algoritma OS penjadwalan independen karena perlu menggunakan jenis algoritma lain untuk menjadwalkan pekerjaan. Multiple-level Queues Scheduling memiliki karakteristik beberapa antrian harus dipertahankan untuk proses dengan beberapa karakteristik. Setiap antrian mungkin memiliki algoritme penjadwalan terpisah. Prioritas diberikan untuk setiap antrian.

7. Local replacement

   Local replacemen adalah ketika suatu proses membutuhkan halaman yang tidak ada dalam memori, itu dapat membawa halaman baru dan mengalokasikannya sebuah bingkai dari kumpulan bingkai yang dialokasikan saja. Keunggulan dari local replacement adalah halaman-halaman dalam memori untuk proses tertentu dan rasio kesalahan halaman dipengaruhi oleh perilaku paging dari proses itu saja. Namun local replacement juga memiliki sebuah kekurangan, yaitu proses berprioritas rendah dapat menghalangi proses berprioritas tinggi dengan tidak membuat bingkai tersedia untuk proses prioritas tinggi.

8. Global replacement

   Global replacement adalah ketika suatu proses membutuhkan halaman yang tidak ada dalam memori, ia dapat membawa halaman baru dan mengalokasikannya sebuah bingkai dari himpunan semua bingkai, bahkan jika bingkai tersebut saat ini dialokasikan ke beberapa proses lain; artinya, satu proses dapat mengambil kerangka dari proses lainnya. Keunggulan dari global replacement adalah tidak menghalangi kinerja proses dan karenanya menghasilkan throughput sistem yang lebih besar. Kekurangan dari global replacement adalah rasio kesalahan halaman suatu proses tidak dapat sepenuhnya dikontrol oleh proses itu sendiri. Halaman-halaman dalam memori untuk suatu proses juga bergantung pada perilaku paging dari proses lain.

9. The Buddy Allocator

   Ide dasar pengalokasi teman cukup sederhana. Memori fisik dipecah menjadi beberapa bagian besar memori di mana setiap bagian adalah “urutan halaman” (yaitu, 2 ^ n * PAGE_SIZE). Kapanpun sebuah blok memori perlu dialokasikan dan ukurannya tidak tersedia, satu potongan besar dibelah dua secara terus menerus, sampai potongan dengan ukuran yang benar ditemukan. Pada titik ini, dari dua bagian, juga dikenal sebagai sobat, satu akan digunakan untuk memenuhi permintaan alokasi, dan yang lainnya akan tetap gratis. Pada tahap selanjutnya, jika dan saat memori itu bebas, kedua teman (jika keduanya kosong) akan bergabung membentuk bagian yang lebih besar dari memori bebas.

10. The Slab Allocator

    Pengalokasi slab di Linux berada di atas pengalokasi buddy dan ide dasar di baliknya adalah untuk menjaga cache dari objek yang umum digunakan tersedia untuk alokasi di kernel. Ini sangat berguna karena kernel Linux mengalokasikan dan membebaskan banyak struktur secara terus menerus (misalnya, struct task_struct yang merupakan struktur yang mewakili proses, inode, dentries, dll…). Dengan meng-cache objek yang dibebaskan, struktur dasar dapat dipertahankan di antara penggunaan sehingga memungkinkan alokasi cepat salinan baru dari struktur yang sama. Yaitu, Dengan menggunakan kembali objek yang dibebaskan, dalam beberapa kasus, kernel tidak perlu menginisialisasi ulang dari awal. Selama bertahun-tahun (dan banyak versi kernel…) pengalokasi slab Linux telah berkembang, dan berubah secara substansial. Ada tiga penerapan berbeda hingga hari ini, yaitu SLOB Allocator, SLAB Allocator, dan SLUB Allocator.