PENDAHULUAN

Dalam perkembangan dari teknologi sistem operasi, tentu saja kinerja dari penjadwalan pada suatu sistem operasi harus harus bekerja secara cepat, effisien dan akurat. Hal tersebut dilakukan dimana sistem penjadwalan (scheduler) harus dapat menentukan urutan proses yang akan di ekseskusi nantinya yang dimana pengurutan dari suatu proses harus dilihat dari beberapa aspek untuk menentukan proses yang mana harus diekseskusi terlebih dahulu dan proses yang mana akan di eksekusi belakangan.

Pada ruang lingkup system multiprogramming atau multiprocessing sebuah algoritma penjadwalan yang dapat bekerja secara cepat, akurat dan efisien sangatlah dibutuhkan pada sebuah sistem operasi untuk dapat memberikan pelayanan kepada user yang menggunakan sistem operasi tersebut. Dan hal ini juga untuk tetap mempertahankan utilisasi dari CPU yang dimana kinerja dari CPU bekerja secara maksimal dalam menjalankan suatu program.

Tujuan dari penjadwalan CPU adalah untuk memberikan sumber daya yang setara untuk semua proses (fairness), performa efisien pada prosesor dan waktu respond terhadap  proses yang sedang dieksekusi dan proses yang akan diproses.

Akan tetapi pada paper ini akan membahas tentang pengembangan algoritma penjadwalan dengan teknik Pipeline, algoritma µC/OS-II dan algoritma penjadwalan berbasis Fuzzy Logic.

ALGORITMA PENJADWALAN STANDAR

• First Come First Serve (FCFS)

Algoritma First Come, First Serve (FCFS) merupakan algoritma yang paling sederhana. Pada algortima penjadwalan tersebut proses yang akan dieksekusi merupakan proses yang pertama sampai dan proses tersebut akan langsung dieksekusi. Akan tetapi kelemahan dari algoritma tersebut adalah apabila yang pertama sampai adalah proses yang mempunyai service time yang lama dalam menenyelesaikan proses tersebut maka waktu tunggu terhadap proses yang mempunyai service time yang singkat harus terus menunggu sampai proses dengan service time yang lama tersebut telah selesai di eksekusi.

Tabel 1 – Data Proses [2]

Berikut merupakan data hasil dari pengujian dengan algoritma FCFS yang diambil dari jurnal “An Improved CPU Scheduling Algorithm”.

Tabel 2 – Hasil FCFS [2]

• Shortest Job First (SJF)

Algoritma penjadwalan SJF atau disebut juga Shortest Process Next (SPN) di buku “Operating System” karangan William Stallings merupakan algoritma penjadwalan yang memiliki karakteristik  dimana proses dengan waktu eksekusi terpendek akan dieksekusi duluan. Pengeksekusian proses terurut secara ascending berdasarkan service time proses. Algoritma ini menjadi solusi dari kelemahan algoritma FCFS.

Berikut adalah data hasil dari pengujian dengan algoritma SJF yang diambil dari jurnal “An Improved CPU Scheduling Algorithm”.

Tabel 3 – Hasil SJF [2]

• Penjadwalan Berprioritas (Pri)

Penjadwalan berprioritas merupakan teknik penjadwalan yang menggunakan prioritas sebagai patokan urutan eksekusi proses. Dalam buku “Operating System” karya William Stallings, algoritma penjadwalan berprioritas dibagi menjadi dua, yaitu prioritas stastis& prioritas statis.

Misal diambil data proses dengan spsifikasi sebagai berikut.

Tabel 4 – Data Proses (Pri) [2]

Dengan data tersebut, dilakukan pengetesan terhadap performa algoritma penjadwalan berprioritas sehingga mendapatkan hasil dibawah ini. (Berikut adalah data hasil dari pengujian dengan algoritma penjadwalan berprioritas yang diambil dari jurnal “An Improved CPU Scheduling Algorithm”.)

Tabel 5 – Hasil Pri [2]

• Round-Robin (RR)

Algoritma Round-Robin merupakan preemptive tanpa prioritas yang jatah waktu eksekusi proses didasarkan dengan waktu quantum. Algoritma ini menggilir proses yang ada di antrian. Jika time quantum-nya habis atau proses sudah selesai, CPU akan dialokasikan ke proses berikutnya. Jadi, semua proses mendapat jatah waktu yang sama dari CPU yaitu (1/n), dan tak akan menunggu lebih lama dari (n-1)q dengan q adalah lama 1 quantum.

Pengujian: misal diambil data yang sama dengan sebelumnnya.

Time quantum = 2ms

Maka, sesuai dengan data yang diambil dari jurnal “An Improved CPU Scheduling Algorithm”, didapatkan hasil sebagai berikut.

Tabel 6 – Hasil RR [2]

PENGEMBANGAN ALGORITMA PENJADWALAN

Pengembangan dari algoritma penjadwalan terhadap penentuan urutan proses, dapat dikembangkan sebagai berikut:

• Algoritma Penjadwalan Standar yang Dikembangkan

Pada algoritma standar, dapat diterapkan konsep pipelining. Pipelining merupakan sekumpulan proses yang saling terhubung dimana urutan dari proses sudah ditentukan berdasarkan kriteria yang telah ditetapkan. Proses-proses tersebut dibagi menjadi sub proses yang kemudian sub proses-sub proses tersebut dieksekusi di segmen khusus secara konkuren dengan segmen-segmen lainnya [2]. Perbandingan antara penjadwalan proses yang menggunakan konsep pipelining dengan yang tidak menggunakan konsep pipelining dapat dilihat di bawah ini.

 

Keterangan: P1 memiliki prioritas tertinggi, dan P3 yang terendah

Tabel 7 – Pri w/o pipelining [2]

Tabel 8 – Pri w/ pipelining [2]

Dapat dilihat bahwa penggunaan algortima dengan menggunakan konsep pipelining, membutuhkan waktu yang lebih singkat daripada yang tidak menggunakan konsep pipelining, apabila diperjelas, penjadwalan tanpa menggunakan pipeling membutuhkan waktu sembilan clock sedangkan yang menggunakan pipelining membutuhkan hanya lima clock.

Mengapa bisa demikian?

Dengan teknik pipelining, waktu yang digunakan oleh CPU scheduler untuk menentukan proses mana yang selanjutnya akan dieksekusi dapat di by pass.

Jika terdapat k segmen pipeline dengan waktu siklus clock Tp yang digunakan untuk mengeksekusi n buah proses, maka proses pertama P1 akan membutuhkan waktu selama (k*Tp) untuk menyelesaikan operasinya. Sedangkan sisa proses yang berjumlah (n-1) akan ditangani setelah satu clock proses yang sedang dieksekusi seperti yang ditunjukkan pada Tabel 8. Maka dari itu, untuk menyelesaikan n buah proses, k segmen pipeline membutuhkan waktu sebanyak (k+(n-1)) clock. Sedangkan algoritma berprioritas standar (non-pipeline) membutuhkan waktu sebanyak (n*Tn) untuk mengeksekusi n buah proses, dimana Tn merupakan waktu yang dibutuhkan untuk mengeksekusi satu proses [2]. Dari situ didapatkan perbandingan rasio kecepatan antara teknik pipeline dengan non-pipeline, yaitu:

S = ((n)*(Tn)) / ((k+n-1)*Tp)                                                              [2]

Dimana Tn = k*Tp

 

• Algoritma Penjadwalan Fuzzy Logic

“Fuzzy logic merupakan generalisasi dari logic standar, dimana sebuah konsep memiliki derajat kebenaran yang bernilai antara 1 dan 0”[3]. Sistem fuzzy terdiri atas fuzzier, rules, mesin interference, dan defuzzier.

Langkah-langkah dari proses fuzzy yaitu:

• Fuzzifikasi, yaitu mengumpulkan set input asli lalu mengonversikannya menjadi set fuzzy menggunakan variabel fuzzy linguistic, istilah fuzzy linguistic, dan fungsi keanggotaan
• Interference dibuat atas dasar set rules
• Defuzzifikasi, yaitu hasil fuzzy output dipetakan ke output asli menggunakan fungsi keanggotaan

Variabel linguistik merupakan variabel input atau output dari sistem yang bertipe non-numerik.

Fungsi keanggotaan merupakan fungsi yang digunakan untuk memetakan input non-fuzzy ke fuzzy linguistic ataupun sebaliknya. Biasanya digunakan pada tahap fuzzifikasi dan defuzzifikasi.

Pada algoritma penjadwalan fuzzy logic, hal – hal yang harus dilakukan  pada penentuan penjadwalan proses adalah sebagai berikut:

• Pada setiap process yang berada dalam posisi ready pada queue, kumpulkan informasi dari burst time, nilai prioritas statis dan waktu sampai lalu berikan kepada FIS (Fuzzy Inference System). FIS merupakan proses pemetaan dari input yang telah diberikan menjadi output pada fuzzy logic.
• Pada setiap proses, evaluasi prioritas antar proses.
• Pada setiap proses, evaluasi burst time antar proses.
• Pada setiap proses yang berada pada kondisi ready pada antrian, bandingkan semua proses pada aspek prioritas untuk menemukan proses dengan nilai prioritas terendah.

 

Algoritma penjadwalan Fuzzy:

• Improved Fuzzy CPU Scheduling Algorithm (IFCS) – algoritma ini diusulkan oleh H.S. Behera. Algoritma IFCS menggunakan prioritas dinamis (dpi) dalam menjadwalkan CPU. IFCS meninjau fungsi keanggotaan dari prioritas, service time, dan response time dari proses untuk menentukan prioritas dinamisnya. Algoritma ini mampu mengurangi waiting time dan turnaround time (TAT) [3].
• Algoritma Fuzzy yang diajukan (PFCS) – algoritma PFCS ini  merupakan algoritma yang diusulkan oleh Prerna Ajmani dan Manoj Sethi (penulis jurnal “Proposed Fuzzy CPU Scheduling Algorithm (PFCS) for Real Time Operating Systems” yang menjadi referensi paper ini). Yang membedakan algoritma PFCS dengan IFCS adalah cara menentukan prioritas dinamisnya. PFCS meninjau fungsi keanggotaan dari prioritas dan service time [3].

Tahap:

1)      Menentukan prioritas dinamis (dpi) dari output FIS

2)      Menjadwalkan proses Pi dengan prioritas tertinggi untuk dieksekusi dimana 1<=i<=n

3)      Jika proses selesai dieksekusi & tidak ada proses baru, maka jalankan langkah-2. Jika ada proses baru, maka jalankan proses langkah-1

4)      Exit

Studi kasus:

Tabel 9 – Studi kasus fuzzy 1 [2]

Tabel 10 – Komparasi Hasil Fuzzy 1 [2]

Bagan 1 – Hasil Komparasi fuzzy 1 [2]

Tabel 11 – Studi kasus fuzzy 2 [3]

Tabel 12 – Komparasi Hasil fuzzy 2 [3]

Bagan 2 – Hasil Komparasi fuzzy 2 [3]

Dapat dilihat dari hasil studi kasus dia atas bahwa algoritma Fuzzy bisa meningkatkan performa dengan menurunkan waiting time dan turnaround time. Hasil juga memperlihatkan bahwa PFCS dan IFCS memiliki performa yang sama walaupun metode penentuan prioritas dinamis (dpi) keduanya berbeda.

• Algoritma Penjadwalan µC/OS-II

Pada algoritma penjadwalan µC/OS-II, pengembangan dilakukan dengan cara menambahkan bagian ready list pada algoritma tersebut. Hal ini dilakukan untuk membantu menyelesaikan masalah apabila ada proses yang mempunyai nilai prioritas yang sama dengan proses lain. Hal yang dilakukan pada masalah tersebut adalah dengan cara memilih prioritas yang paling lama menunggu pada ready list.

Hal tersebut mempunyai dampak dimana ready list berhubungan langsung dengan scheduler, sehingga menghemat waktu dalam membaca data pada memory.

Algoritma  µC/OS-II memiliki 5 status dalam menjadwalkan proses, yaitu Dormant, Ready, Running, dan Interrupt.

Bagan 3 – Status Penjadwalan µC/OS-II [1]

Dormant:

State dormant merupakan korespondensi terhadap proses yang berada dalam memori, tapi belum tersedia terhadap multitasking kernel.

Ready:

Suatu proses dikatakan ready, apabila proses sudah siap untuk di eksekusi tetapi prioritasnya lebih rendah dari proses yang sedang dijalankan.

Running:

Proses dikatakan running apabila proses tersebut sedang dijalankan oleh CPU.

Waiting:

Suatu proses berada state waiting apabila proses tersebut membutuhkan suatu event atau sedang menunggu suatu event untuk dapat di eksekusi.

Suatu proses berada dalam state interrupt apabila interrupt muncul pada proses tersebut dan CPU menangani interrupt yang telah muncul tersebut.

—

Pada TCB µC/OS-II, pada saat setiap pembuatan dari proses, maka TCB harus dibuat dengan tujuan untuk menangani dan menjadwalkan proses tersebut. Hal tersebut dilakukan untuk mempertahankan suatu state pada saat di preempted. µC/OS-II sesuai pada implementasi pada register yang didalamnya terdapat FPGA**. Pada penggunaan algoritma µC/OS-II, hal tersebut memudahkan dalam penentuan prioritas.

**FPGA (Field Programmable Gate Array)

Merupakan sebuah Integrated Circuit (IC) yang dikonfigurasi dan disesuaikan berdasarkan spesifikasi dengan menggunakan Hardware Descriptin Language (HDL).

Berdasarkan kebutuhan tersebut struktur data dapat ditentukan sebagai berikut.

Bagan 4 – Struktur data µC/OS-II [1]

Penjelasan dari struktur data tersebut:

• OSTCBId.
  • Merupakan register dari identitas (ID) suatu proses dalam sistem operasi.
• OSTCBStat.
  • Merupakan register dari kondisi state proses yang sedang dijalankan.
  • Aktivitas reading dan writing dapat mengganti state dari proses tersebut dan dapat mengembalikan state proses tersebut.
• OSTCBPrio.
  • Merupakan penentu prioritas dari suatu proses.
• OSTCBDly.
  • Merupakan register untuk delay time, hal tersebut dibutuhkan untuk mendelay suatu proses pada waktu yang telah ditentukan.
• OSTCBStkSize.
  • Merupakan register variable yang menentukan kapasitas ukuran stack terhadap jumlah elemen atau proses.
• OSTCBStkButtom.
  • Merupakan pointer terhadap suatu proses yang terletak pada bagian paling bawah suatu stack.

Pengujian:

Bagan 5 – Simulasi µC/OS-II [1]

Penjelasan dari simulasi tersebut:

•  Awalnya membuat proses dengan nomor ID 6 dan nomor prioritas 6, pada saat ini tidak ada proses yang lain yang bekerja pada OS, lalu pada saat clock sedang berjalan maka nilai pada register Next_task_id adalah 6. Lalu dibuat proses dengan nomor ID adalah 3 dan level prioritastnya adalah 3. Pada hal ini proses dengan nomor ID 3 mempunyai level prioritas yang lebih tinggi daripada proses dengan nomor ID 6. Maka scheduler akan me-nyela proses dengan nomor ID 6 dan memberikan kendali pada proses dengan nomor ID 3.

• Pada saat proses dengan nomor ID 3 di suspend maka akan mengakibatkan penjadwalan ulang, pada waktu ini proses dengan nomor ID 6 mempunyai prioritas tertinggi dan proses dengan nomor ID 6 dieksekusi.

• Proses dengan nomor ID 3 dan 6 akan diberikan kepada penjadwalan proses, yang dimana akan mengembalikan state dari TCB proses 3 dan proses 6. Pengembalian tersebut akan dikirim kepada register current state.

• Proses dengan nomor ID 3 akan dilanjutkan kembali dan akan menyela proses dengan ID 6, yang dimana proses dengan nomor ID 6 akan dilanjutkan nanti.

• Buat dua proses dengan nomor ID 4 dan 5 yang dimana nomor prioritas ditentukan dberdasarkan nomor ID masing – masing proses.

Hapus proses 3, pada waktu ini terdapat dua proses yang berada dalam state waiting dan proses dengan nomor ID 5 menunggu paling lama, maka proses dengan nomor ID 5 memasuki kondisi ready-to-run.

Kita asumsikan bahwa apabila proses dengan nomor ID 8 dijalankan, lalu disimulasikan dengan menggunakan platform XC2VP30FF896C. Maka akan menghasilkan hasil sebagai berikut.

Bagan 6 – Hasil Simulasi µC/OS-II [1]

Dapat dilihat dari hasil simulasi di atas, bahwa dengan menggunakan algoritma dan implementasi dari µC/OS-II dapat diverifikasikan efisiensi dalam penjadwalan proses dengan memenuhi kondisi dari real-time operating system karena CPU Utilization yang minim.

REFERENSI

[1]     Li , Yue-hua. Xue Liu.Yun-feng Ding. Hao-xin Cui. Yong-bin Du. Yan Li, “An Improvement of Task Scheduling Algorithms and Hardware Scheduler of Real-time Operating System”, International Journal of Hybrid Information Technology, (2014)

[2]     Arora , Himanshi. Deepanshu Arora. Bagish Goel. Parita Jain, “An Improved CPU Scheduling Algorithm”, International Journal of Applied Information Systems, (2013)

[3]     Ajmani , Prerna. Manoj Sethi, “Proposed Fuzzy CPU Scheduling Algorithm (PFCS) for Real Time Operating Systems”, BIJIT – BVICAM’s International Journal of Information Technology, (2013)