Polinomial Linked List

Salah satu bentuk struktur data yang berisi kumpulan data yang tersusun secara sekuensial, saling bersambungan, dinamis dan terbatas adalah senarai berkait (linked list). Suatu senarai berkait (linked list) adalah suatu simpul (node) yang dikaitkan dengan simpul yang lain dalam suatu urutan tertentu. Suatu simpul dapat berbentuk suatu struktur atau class. Simpul harus mempunyai satu atau lebih elemen struktur atau class yang berisi data.

Secara teori, link list adalah sejumlah node yang dihubungkan secara linier dengan bantuan pointer. Dikatakan single linked apabila hanya ada satu pointer yang menghubungkan setiap node.

Perhitungan aritmetika polinomial dengan menggunakan komputer akan menjamin kecepatan dan ketepatan hasil yang diperoleh, dengan terlebih dahuhr-mendefinisikan suatu Tipe Data abstrak (TDA) Polinomial. Pemilihan struktur data yang tepat untuk menyajikan polinomial dimaksudkan agar diperoleh suatu program yang baik, yaitu dengan menggunakan linked list.

Dalam linked list setiap suku dari polinomial adalah suatu simpul yang berupa record yang terdiri atas field koefisien, pangkat dan pointer yang menunjuk ke simpul (suku) berikutnya. Implementasi TDA Polinomial dilakukan dengan cara menyajikan polinomial dengan linked list dan mengkodekan setiap operasi yang didefinisikan dalam TDA Polinomial ke dalam program dalam bentuk prosedur atau fungsi.

Header link list kerap kali dipergunakan untuk menyimpan polynomial dalam memory. Di sini simpul header selalu merupakan bagian penting dalam penyajian, Karena ia dibutuhkan untuk menyajikan polynomial nol.

Selain menggunakan linked list. Pertimbangkan dua polinomial f (x) dan g (x), yang dapat diwakili menggunakan linked list sebagai berikut pada Gambar. 5,22. Kedua polinomial dapat ditambahkan dengan h(x)= f(x)+ g(x)= mx 4+(a + n) x 3+ ox 2+(b + p)x +(c + q) yaitu; menambahkan konstanta dari polinomial yang sesuai dari eksponensial sama. h (x) dapat direpresentasikan sebagai pada gambar Berikut ini…..

f(x) = ax3 + bx + c

g(x) = mx4 + nx3 + ox2 + px + q

Kedua polynomial dapat ditambahkan dengan

H(x) = f(x) + g(x) = ax3 + bx + c + mx4 + nx3 + ox2 + px + q

= mx4 + (a + n) x3 + ox2 +(b + p)x + (c +q)

Yaitu menambahkan konstanta dari polynomial yang sesuai dari eksponensial sama.

Hasil dari H(x) dapat di jabarkan seperti gambar berikut:

Category › Algoritma Dan Struktur Data , Kuliah , Tugas

Algoritma Search Engine Google

A.           Search Engine

Mesin pencari adalah program komputer yang dirancang untuk melakukan pencarian atas berkas-berkas yang tersimpan dalam layanan www, ftp, publikasi milis, ataupun news group dalam sebuah ataupun sejumlah komputer peladen dalam suatu jaringan. Hasil pencarian umumnya ditampilkan dalam bentuk daftar yang seringkali diurutkan menurut tingkat akurasi ataupun rasio pengunjung atas suatu berkas yang disebut sebagai hits. Informasi yang menjadi target pencarian bisa terdapat dalam berbagai macam jenis berkas seperti halaman situs web, gambar, ataupun jenis-jenis berkas lainnya. Beberapa mesin pencari juga diketahui melakukan pengumpulan informasi atas data yang tersimpan dalam suatu basisdata ataupun direktori web (Wikipedia).

Sebagian besar mesin pencari dijalankan oleh perusahaan swasta yang menggunakan algoritma kepemilikan dan basisdata tertutup, di antaranya yang paling populer adalah Google (MSN Search dan Yahoo!). Telah ada beberapa upaya menciptakan mesin pencari dengan sumber terbuka (open source), contohnya adalah Htdig, Nutch, Egothor dan OpenFTS (Wikipedia).

B.            Prinsip Umum Search Engine

Sistem kinerja mesin ini ada beberapa hal yang perlu di perhatikan terutama keterkaitannya dengan masalah arsitekrut dan mekanismenya (Wikipedia).

1.             Spider

Merupakan program yang men-download halaman-halaman yang mereka temukan, mirip dengan browser. Perbedannya adalah bahwa browser menapilkan secara langsung informasi yang ada (baik tekas, gambar, dll). Untuk kepentingan manusia yang menggunakannya pada saat itu, sedangkan spider tidak melakukan untuk menampulkan dalam bentuk yang terlihat seperti itu, karena kepentingannya adalah untuk mesin, bukan untuk manusia, spider pun dijalankan oleh mesin secara otomatis. Kepentingannya adalah untuk mengambil halaman-halaman yang dikunjunginya untuk disimpan kedalam database yang dimiliki oleh search engine.

2.             Crawler

Merupakan program yang dimiliki search engine untuk melacak dan menemukan link yang terdapat dari setiap halaman yang ditemuinya. Tugasnya adalah untuk menentukan spoder harus pergi kemana dan mengevaluasi link berdasarkan alamat yang ditentukan dari awal. Crawler mengikuti link dan mencoba menemukan dokumen yang belum dikenal oleh search engine.

3.             Indexer

Komponen ini melakukan aktifitas untuk menguraikan masing-masing halaman dan meneliti berbagai unsur, seperti teks, headers, struktur atau fitur dari gaya penulisan, tag HTML khusus, dll.

4.             Database

Merupakan tempat standar untuk menyimpan data-data dari halaman yang telah dikunjungi, di-download dan sudah dianalisis. kadang kala disebut juga dengan index dari suatu search engine.

5.             Result Engine

Mesin yang melakukan penggolongan dan penentuan peringkat dari hasil pencarian pada search engine. Mesin ini menentukan halaman mana yang menemui kriteria terbaik dari hasil pencarian berdasarkan permintaan penggunanya, dan bagaimana bentuk penampulan yang akan ditampilkan.

Proses ini dilaksanakan berdasarkan algoritma perangkingan yang dimiliki oleh search engine tersebut, mengikuti kaidah perangkingan hakaman yang dipergunakan oleh mereka adalah hak mereka, para peneliti mempelajari sifat-sifat yang mereka gunakan, terutama untuk meningkatkan pencarian yang dihasilkan oleh serach engine tersebut.

6.             Web Server

Merupakan komponen yang melayani permintaan dan memberikan respon balik dari permintaan tersebut. Web Server ini biasanya menghasilkan informasi atau dokumen dalam format [[[HTML]]. Pada halaman tersebut tersedia layanan untuk mengisikan kata kunci pencarian yang diinginkan oleh usernya. Web Server ini juga bertanggung jawab dalam menyampaikan hasil pencarian yang dikirimkan kepada komputer yang meminta informasi.

C.           Algoritma Search Engine

1.             List Search

Algoritma ini bekerja dengan cara mencari secara berurutan. Bisa dibayangkan seperti saat ingin mencari seseorang dalam sebuah antrian. Maka mencarinya dengan cara memeriksa satu persatu, dari awal antrian hingga menemukan orang yang ingin dicari.

Cara atau algoritma seperti ini biasanya digunakan saat ingin mencari dengan menggunakan satu faktor atau satu kunci saja sebagai penentu. Untuk antrian yang pendek, cara ini mungkin cukup efektif dan efisien. Tapi untuk mencari sebuah kata dari milyaran web page yang ada di internet, maka akan membutuhkan waktu yang sangat lama.

2.             Tree Search

Bayangkan sebuah pohon! Bayangkan mulai dari akar, batang, cabang, kemudian ranting-rantingnya. Begitulah cara kerja dari algoritma ini. Algoritma ini akan bekerja dengan cara mencarinya dari yang paling mendekati hingga ke yang paling tidak mendekati. Atau bisa juga dikatakan dari yang paling umum hingga ke yang paling spesifik, atau sebaliknya.

Algoritma ini mirip dengan cara yang digunakan orang untuk mengatur internet. Seperti yang diketahui, setiap situs yang ada di internet itu mempunyai keterkaitan antara satu dengan yang lainnya. Bisa menelusuri keterkaitan ini dengan cara memulai dari tingkat yang paling kecil dulu, kemudian ke tingkat yang paling besar, atau sebaliknya.

Tree searches adalah cara yang ampuh digunakan untuk melakukan pencarian di internet, akan tetapi cara ini tidak selalu memberikan hasil yang memuaskan.

3.             SQL Search

Diambil dari kata sequel. Satu kelemahan saat melakukan pencarian menggunakan metode Tree Search yaitu pencarian dilakukan dengan cara dari point ke point, atau dari satu titik ke titik. Itu artinya data harus dicari secara hirarki, dari besar ke kecil atau sebaliknya. Dan kelemahan ini bisa teratasi dengan menggunakan SQL search.

4.             Informed Search

Algoritma informed search bekerja dengan cara mencari solusi yang spesifik atau khusus dari sebuah dataset yang bercabang-cabang (tree dataset). Sesuai dengan namanya, algoritma ini tidak selalu cocok digunakan untuk melakukan pencarian di internet. Karena algoritma ini cuma cocok digunakan untuk pemecahan masalah-masalah yang spesifik atau khusus saja. Sedangkan seringkali ingin mencari pemecahan untuk masalah-masalah yang bersifat umum atau luas.

5.             Adversarial Search

Adversarial search bekerja dengan cara mencari berbagai kemungkinan solusi atas sebuah masalah. Ini seperti saat melakukan permainan rolex atau gambling, dimana semua kemungkinan akan dicoba. Algoritma ini sulit digunakan untuk melakukan pencarian di internet, sebab berapa banyak kemungkinan yang akan di dapat untuk mencari sebuah kata di internet? Nyaris tak terhingga.

6.             Constraint Satisfaction Search

Saat mencari suatu kata/kalimat di internet, maka algoritma constraint satisfaction search ini sepertinya adalah metode yang paling mendekati atau sesuai dengan keinginan. Algoritma pencarian jenis ini, akan mencari solusi dengan cara memberikan berbagai alternatif pilihan. Algoritma ini akan mencari dengan berbagai cara, dan tidak harus dengan cara yang berurutan.

Itu tadi beberapa algoritma yang diperlukan saat sebuah search engine akan dibuat. Dan seringkali lebih dari satu algoritma yang digunakan oleh sebuah search engine. Dan seringkali juga, search engine tertentu akan membuat algoritma yang baru.

D.           Google

Google Inc. (NASDAQ: GOOG dan LSE: GGEA) merupakan sebuah perusahaan publik Amerika Serikat, berperan dalam pencarian Internet dan iklan online. Perusahaan ini berbasis di Mountain View, California, dan memiliki karyawan berjumlah 19.604 orang (30 Juni 2008) Filosofi Google meliputi slogan seperti "Don't be evil", dan "Kerja harusnya menantang dan tantangan itu harusnya menyenangkan", menggambarkan budaya perusahaan yang santai (Wikipedia).

Google didirikan oleh Larry Page dan Sergey Brin ketika mereka masih mahasiswa di Universitas Stanford dan perusahaan ini merupakan perusahaan saham pribadi pada 4 September 1998. Penawaran umum perdananya dimulai pada tanggal 19 Agustus 2004, mengumpulkan dana $1,67 miliar, menjadikannya bernilai $23 miliar. Melalui berbagai jenis pengembangan produk baru, pengambil alihan dan mitra, perusahaan ini telah memperluas bisnis pencarian dan iklan awalnya hingga ke area lainnya, termasuk email berbasis web, pemetaan online, produktivitas perusahaan, dan bertukar video (Wikipedia).

E.            Cara Kerja Dari Search Engine (Google).

Seperti yang diketahui bahwa cara kerja mesin pencari Google sangat tertutup tentang algoritma dan pusat data hasil pencarian google. Sejauh ini hanya bisa menebak garis besar kebijakan Google melalui halaman hasil mesin pencari (SERP’s) Google.

Dibalik teknologi pencarian adalah perangkat lunak. Perangkat lunak dengan serangkaian bahasa program untuk menghitung secara simultan dengan membutuhkan sepersekian detik. Mesin pencari tradisional lebih mengandalkan seberapa sering kata muncul pada halaman web. Google menggunakan lebih dari 200 sinyal, termasuk algoritma page rank yang merupakan hak paten Google. Sinyal ini berfungsi untuk memeriksa seluruh struktur link dari situs dan menentukan halaman yang paling penting.

Setelah itu Google menganalisis kesesuaian hipertext untuk menentukan halaman yang relevan dengan pencarian khusus yang dilakukan. Menggabungkan sinyal secara keseluruhan dan relevansi query spesifik, dan menempatkan hasil pertama yang paling relevan dan dapat diandalkan atas query pengguna.
Berikut ini secara garis besar langkah-langkah Cara Kerja Mesin Pencari Google secara urut menurut nomor:

1.             Anda menulis blog, menciak, memperbarui situs, atau menambahkan konten ke situs.

2.             Google bot merangkak pada situs untuk menemukan posting Anda.

·               Google bot mengikuti link. Jika tidak ada link ke situs Anda, biasanya hal ini tidak akan dijelajahi secara mendalam atau secara teratur.

·               Google bot tidak akan menjelajah situs Anda jika Anda tidak memberitahu mereka dengan sebuah robot.txt.

·               Jika link ke situs Anda memiliki tag nofollow, google bot tidak mengunjungi link tersebut.

·               Google juga dapat menemukan situs Anda dengan perangkat lunak ping untuk blog atau sitemap.xml.

·               Semakin banyak link yang Anda miliki dari halaman otoritas yang lebih tinggi dari situs anda, halaman otoritas Anda sendiri akan lebih besar juga. Selama mereka tidak menggunakan tag "nofollow".

3.             Setelah merangkak halaman akan diindeks dalam hitungan detik.

·               Konten halaman disimpan dalam sebuah indeks terbalik. --> Judul halaman dan link data disimpan dalam satu indeks yang digunakan untuk pencarian yang luas dan kompetitif. --> Pada konten halaman disimpan di lain indeks yang digunakan untuk pencarian isi halaman dan isi yang tidak jelas.

·               Jika Anda tidak mencari web yang aktif, tapi google cache hal itu, yang terus-menerus akan diperbarui.

4.             Google memperkirakan domain dan otoritas keseluruhan halaman berdasarkan link.

5.             Halaman diperiksa terhadap kebijakan editorial.

·               Pencarian berkualitas Google tim dan tim webspam meninjau dan memperbaiki algoritma (Baca : Dokumen Pedoman Penilaian Google Bocor : Cuplikan).

·               Lebih dari 10.000 penguji tersembunyi untuk tingkat kualitas pencarian mereka.

·               Google memohon laporan spam dari pengguna.

·               Google mendapatkan DMCA pemberitahuan untuk mencatat pekerjaan bajakan.

6.             Hukuman diterapkan dan setiap halaman, sekarang Google memiliki banyak daftar data terlampir untuk membantu kepentingan pengguna.

7.             Query Pengguna Google.

Pada query google terbanyak, sebenarnya anda masuk dalam beberapa kontrol atau kelompok eksperimental secara bersamaan. Pada dasarnya, semua query terlibat dalam beberapa tes.

8.             Google menyarankan kata kunci didasarkan pada apa yang telah diketik beberapa karakter.

9.             Google menggunakan sinonim untuk mencari kata-kata serupa untuk menyertakan dalam permintaan pencarian.

10.         Hasil set awal dibuat.

·               Google mengklaim mendapatkan jutaan hasil tetapi hanya 1.000 atau kurang yang pernah ditampilkan.

·               Hasil lokalisasi: situs lokal yang dipromosikan dalam hasil pencarian

11.         Hasil set diurutkan berdasarkan kewenangan dan pagerank, dan halaman duplikat dihapus.

·               Google menemukan iklan yang relevan berdasarkan kata kunci, iklan menyesuaikan lokasi jenis dan pengguna.

·               Iklan tunduk pada kebijakan editorial

§                Pengiklan beroperasi di luar pedoman mungkin memiliki akun iklan yang mereka dilarang.

§                Jika kata kunci memiliki volume pencarian yang rendah atau terlalun sedikit menghasilkan klik, iklan mungkin akan secara otomatis dinonaktifkan.

§                Bisnis disukai, mungkin seperti amazon.com, tokobagus.com mungkin akan diberikan diskon.

·               Iklan yang relevan yang diorder berdasarkan potensi laba (tawaran x skor kualitas iklan).

·               Untuk sebagian besar pengiklan konten sudah dibuat tapi kadang-kadang isi kata kunci dinamis digunakan untuk membuat iklan agar tampak lebih relevan.

§                Beberapa iklan juga memiliki ekstensi yang tersedia, seperti link situs, nomor telepon, produk, link, lokasi, dll.

·               Jika iklan menghasilkan tingkat melalui klik yang cukup tinggi, beberapa mungkin ditampilkan di atas hasil pencarian.

·               Sisanya pergi ke rel yang benar di mana mereka ditampilkan.

·               Hasil akan muncul dibawah satu detik, miliaran kali dalam sehari, menghasilkan lebih dari 20 miliar dolar setahun untuk google!

12.         Penyaring diterapkan

·               Dengan pencarian universal, jika google berpikir hasil berita, hasil belanja, hasil video, buku hasil, hasil lokal, atau bentuk lain dari pencarian vertikal yang relevan maka mereka mungkin mencampur secara langsung ke dalam hasil pencarian.

·               Personalisasi pengguna: situs yang pernah dikunjungi pengguna sering dipromosikan.

·               Manipulasi teks jangkar yang berlebihan dapat menyebabkan situs yang akan dihapus dari hasil.

·               Interkonektivitas lokal mempengaruhi hasil : jika halaman yang terhubung dengan baik antara situs lain dengan peringkat tinggi, maka peringkat mereka dapat meningkatkan.

·               Tren: jika istilah pencarian telah meledak besar dalam volume pencarian dan / atau banyak hasil berita terbaru, google mungkin menempatkan bobot tambahan pada hasil konten lebih segar.

·               Tren: Perolehan Google +1 dan situs jejaring sosial lainnya menempatkan bobot tambahan.

·               Beberapa halaman dari domain yang sama dapat dikelompokkan bersama-sama jika semua memiliki peringkat tinggi.

13.         Hasil organik ditampilkan

·               Hasil akan muncul dibawah satu detik, miliaran kali dalam sehari, menghasilkan lebih dari 20 miliar dolar setahun untuk google.

Daftar Rujukan

Google. http://id.wikipedia.org/google. Diakses tanggal 20 Februari 2012

Mesin Pencari. http://id.wikipedia.org/mesin_pencari. Diakses tanggal 20 Februari 2012

Cara Kerja Mesin Pencari Google. http://akharisyuli.blogspot.com/2011/12/cara-kerja-mesin-pencari-google.html. Diakses tanggal 20 Februari 2012

Search Engine Mesin Pencari. http://rendramm2.wordpress.com/2009/12/08/artikel-tentang-search-engine-mesin-pencari-online. Diakses tanggal 20 Februari 2012

Category › Algoritma Dan Struktur Data , Kuliah , Tugas

Penjadwalan / Antrian CPU

A.           Konsep Dasar

Dalam pemroses tunggal, hanya satu proses yang dapat dijalankan pada saat tertentu, sedangkan yang lain harus menunggu CPU bebas dan dijadwal ulang. Multiprogramming merupakan cara untuk menjalankan proses setiap waktu sehingga memaksimalkan penggunaan CPU.

Penjadwalan merupakan salah satu fungsi dasar dari sistem operasi. Hampir semua sumber daya komputer dijadwalkan sebelum digunakan.

B.            CPU-I/O Burst Cycle

Kesuksesan penjadwaln CPU tergantung dari observasi proses-proses. Pengeksekusian proses terdiri putaran ekseskusi CPU dan penungguan I/O. Eksekusi proses dimulai dari CPU burst, yaitu diikuti oleh I/O burst kemudian diikuti CPU burst lainnya lalu I/O burst lainnya dan begitu seterusnya.

Gambar 1 Urutan pergantian CPU Burst dengan I/O Burst

C.           Penjadwalan CPU

Ketika CPU mengalami waktu idle, sistem operasi harus memilih salah satu proses untuk masuk kedalam antrian yang akan untuk dieksekusi. Pemilihan tersebut dilakukan oleh penjadwal jangka pendek atau penjadwal CPU. [Bambang2002] Ada tiga tipe penjadwal yang berada bersama pada sistem operasi kompleks, yaitu :

1.             Penjadwal jangka pendek yang bertugas menjadwalkan alokasi pemroses di antara proses-proses yang telah siap di memori utama.

2.             Penjadwal jangka menengah akan menangani serta mengendalikan transisi dari suspended-toready dari proses-proses swapping.

3.             Penjadwal jangka panjang bekerja terhadap antrian batch dan memilih batch berikutnya yang harus dieksekusi.

Gambar 2 Tipe-tipe penjadwalan

Penjadwalan memilih proses yang ada di memori serta siap untuk dieksekusi, dan mengalokasikan CPU untuk mengeksekusinya. Penjadwalan CPU mungkin akan dijalankan ketika proses dalam keadaan:

1.             Berubah dari running ke waiting state.

2.             Berubah dari running ke ready state.

3.             Berubah dari waiting ke ready.

4.             Terminates.

Penjadwalan nomor 1 dan 4 bersifat non-preemptive atau cooperative sedangkan lainnya preemptive. Dalam penjadwalan non-preemptive sekali CPU telah dialokasikan untuk sebuah proses, maka tidak dapat di ganggu, penjadwalan model seperti ini digunakan oleh Windows 3.x; Windows 95 telah menggunakan penjadwalan preemptive yaitu saat suatu proses sedang dieksekusi, CPU dapat diambil alih oleh proses lain sehingga proses di tunda dan dilanjutkan kembali hingga proses selesai.

D.           Kriteria Penjadwalan

Setiap algoritma penjadwalan dapat berbeda dengan nilai yang berbeda dan sistem komputer yang berbeda. Dalam penjadwalan CPU diperlukan beberapa kriteria diantaranya adalah:

1.             CPU Utilization. Kita menginginkan kerja CPU sesibuk mungkin. Konsepnya pemanfaatan CPU mempunyai jangkauan dari 0 sampai 100 persen. Di sistem yang sebenarnya mungkin hanya mempunyai jangakuan dari 40 (untuk pemanggilan ringan sistem) sampai 90 persen (pemanggilan berat sistem).

2.             Throughput. Pengukuran kinerja CPU adalah banyaknya proses yang diselesaikan per satuan waktu. Jika kita mempunyai beberapa proses yang sama dan memiliki beberapa algoritma penjadwalan yang berbeda, hasil kinerja bisa menjadi salah satu kriteria penilaian, dimana algoritma yang menyelesaikan proses terbanyak mungkin yang terbaik.

3.             Turnaround Time. Dari sudut pandang proses tertentu, kriteria yang penting adalah berapa lama untuk mengeksekusi proses tersebut. Memang, lama pengeksekusian sebuah proses sangat tergantung dari hardware yang dipakai, namun kontribusi algoritma penjadwalan tetap ada dalam lama waktu yang dipakai untuk menyelesaikan sebuah proses. Misal, kita memilki sistem komputer yang identik dan proses-proses yang identik pula, namun kita memakai algoritma yang berbeda, algoritma yang mampu menyelesaikan proses yang sama dengan waktu yang lebih singkat mungkin lebih baik dari algoritma yang lain. Interval waktu yang diijinkan dengan waktu yang dibutuhkan untuk menyelesaikan sebuah proses disebut turnaround time.Turnaround time adalah jumlah periode tunggu untuk dapat ke memori, menunggu di ready queue, eksekusi CPU, dan melakukan operasi I/O atau waktu yang dihabiskan dari saat program atau job mulai masuk sistem sampai proses diselesaikan sistem. Turnaround = waktu eksekusi + waktu menunggu

4.             Waiting Time. Algoritma penjadwalan CPU tidak mempengaruhi waktu untuk melaksanakan proses tersebut atau I/O, karena hanya mempengaruhi jumlah waktu yang dibutuhkan proses diantrian ready. Waiting time adalah jumlah waktu yang dbutuhkan proses di antrian ready.

5.             Response time. Di sistem yang interaktif, turnaround time mungkin bukan waktu yang terbaik untuk kriteria. Sering sebuah proses dapat memproduksi output di awal, dan dapat meneruskan hasil yang baru sementara hasil yang sebelumnya telah diberikan ke pengguna. ukuran lain adalah waktu dari pengiriman permintaan sampai respon yang pertama diberikan. Hal ini disebut response time, yaitu waktu untuk memulai memberikan respon, tetapi bukan waktu yang dipakai output untuk respon tersebut. Turnround time umumnya dibatasi oleh kecepatan peralatan keluaran. Ada dua jenis response time berdasarkan penggunaannya pada sistem interaktif dan sistem waktu nyata (real time), yaitu:

a.             Terminal response time merupakan response time pada sistem interaktif sebagai waktu yang dihabiskan dari saat karakter terakhir dari perintah dimasukkan atau transaksi sampai hasil pertama muncul di layar.

b.             Event response time merupakan response time pada sistem waktu nyata sebagai waktu dan kejadian (internal/eksternal) sampai instruksi pertama rutin layanan yang dimaksud dieksekusi.

Sebaiknya ketika kita akan membuat algoritma penjadwalan yang dilakukan adalah memaksimalkan penggunaan CPU dan throughput, dan meminimalkan turnaround time, waiting time, dan response time.

E.            Algoritma Penjadwalan

Masalah penjadwaln CPU adalah memutuskan proses mana yang berada di dalam antrian ready akan dialokasikan ke CPU. Ada beberapa algoritma penjadwalan CPU beberapa diantaranya akan di jelaskan pada bagian berikut ini.

1.             First-Come First-Served (FCFS)

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 antrian FIFO sesuai dengan waktu kedatangannya. Proses yang tiba terlebih dahulu yang akan dieksekusi terlebih dahulu.

Misalnya 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.

Proses Burst time

P1 24 ms

P2 5 ms

P3 3 ms

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:

a.             Waiting time rata-ratanya cukup lama.

b.             Terjadinya convoy effect, yaitu proses-proses menunggu lama untuk menunggu satu 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.             Shortest-Job First (SJF)

Algoritma ini mempunyai cara penjadwalan yang berbeda dengan FCFS. Dengan algoritma ini maka setiap proses yang ada di antrian ready 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:

a.             Kesulitan untuk memprediksi burst time proses yang akan dieksekusi selanjutnya .

b.             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:

a.             Preemptive. Jika ada proses yang sedang dieksekusi oleh CPU dan terdapat proses di antrian ready 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 antrian ready tersebut. Preemptive SJF sering disebut juga Shortest-Remaining-Time-First scheduling.

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

Misalnya ada empat buah proses dengan masing-masing waktu kedatangan burst time di jelaskan pada tabel di bawah ini. Hitunglah waiting time rata-rata dan turnaround time dari keempat proses tersebut dengan mengunakan algoritma SJF.

Proses       Arrival time     Burst Time

P1             0 ms                 7 ms

P2             2 ms                 4 ms

P3             4 ms                 1 ms

P4             5 ms                 4 ms

Solusi Preemptive:

Rata-rata waiting time adalah (9 + 1 + 0 +2)/4 = 3, dimana :

P1: (0-0+11-2) = 9

P2: (2-2+5-4) = 1

P3: (4-4) = 0

P4: (7-5) = 2

Rata-rata turnaround time adalah ((9+7)+(1+4)+(0+1)+(4+2))/4 = 7

Solusi Non-Preemptive:

Rata-rata waiting time adalah (0 + 6 + 3 + 7)/4 = 4, dimana:

P1: (0-0) = 0

P2: (8-2) = 6

P3: (7-4) = 3

P4: (12-5) = 7

Rata-rata turnaround time adalah ((0+7)+(6+4)+(3+1)+(7+4))/4 = 8

3.             Penjadwalan dengan Prioritas

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

a.             Batas waktu

b.             Kebutuhan Memori

c.             Akses file

d.            Perbandingan antara I/O Burst dengan CPU Burst

e.             Tingkat kepentingan proses

Penjadwalan dengan prioritas 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 antrian.

Kelemahan pada penjadwalan prioritas adalah dapat terjadinya indefinite blocking (starvation) yaitu suatu proses dengan prioritas yang rendah memiliki kemungkinan untuk tidak dieksekusi jika terdapatproses lain yang memiliki prioritas lebih tinggi darinya. Solusi dari permasalahan ini adalah aging, yaitu meningkatkan prioritas dari setiap proses yang menunggu dalam antrian secara bertahap.

Misalnya:

Proses       Burst time       Prioritas

P1             10                    3

P2             1                      1

P3             2                      4

P4             1                      5

P5             5                      2

Diagram Gantt adalah sebagai berikut:

Rata-rata waiting time adalah (6+0+16+18+1)/5 = 8.2

Rata-rata turnaround time adalah ((6+10)+(0+1)+(16+2)+(18+1)+(1+5))/5 = 12

4.             Round Robin

Algoritma ini didesin untuk sistem time-sharing. Proses akan mendapat jatah sebesar time quantum dengan nilai quantum umumnya sebesar 10-100 ms. 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 6 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.

Misalnya ada tiga proses dengan masing-masing mendapatkan waktu quantum adalah 4 ms, maka P1 mendapatkan 4 ms pertama. Karena membutuhkan 20 ms lagi, sesudah quantum pertama P1 di preemptive dan CPU memberikan proses berikutnya ke proses P2 dan P2 tidak memerlukan 4 ms, P2 selesai sebelum jatah quantumnya habis, kemudian CPU memberikan ke proses berikutnya yaitu P3. Ketika setaiap proses meneriman satu quantum, CPU kembali ke proses P1 untuk tambahan waktu quantum.

Proses       Burst time

P1             24 ms

P2             3 ms

P3             3 ms

Rata-rata waiting time adalah (6+4+7)/3 = 5.66

Rata-rata turnaround time adalah ((6+24)+(4+3)+(7+3))/3 = 15.67

5.             Antrian Multilevel (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 seperti pada gambar berikut:

Gambar 3 Penjadwalan multilevel queue

Dari gambar tersebut terlihat bahwa akan terjadi pengelompokan-pengelompokan proses-proses berdasarkan prioritasnya. Kemudian muncul gagasan untuk menganggap kelompok-kelompok tersebut 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 antrian akan berjalan dengan algoritma FCFS dan dapat diketahui bahwa algoritma FCFS memiliki banyak kelemahan, oleh karena itu dalam prakteknya, algoritma multilevel queue memungkinkan adanya penerapan algoritma internal dalam masing-masing subantriannya 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 dimanfaatkan 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:

a.             Jumlah antrian

b.             Algoritma penjadwalan tiap antrian

c.             Kapan menaikkan proses ke antrian yang lebih tinggi

d.            Kapan menurunkan proses ke antrian yang lebih rendah

e.             Antrian mana yang akan dimasuki proses yang membutuhkan

Gambar 4 Antrian multilevel feedback

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 mulilevel 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.

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

b.             Jika suatu proses tidak dapat diselesaikan dalam 8 ms, maka proses tersebut akan dihentikan dan dipindahkan ke antrian pertama (quantum = 16 ms).

c.             Antrian pertama hanya akan dikerjakan jika tidak ada lagi proses di antrian 0, dan jika suatu proses di antrian pertama 1 tidak selesai dalam 16 ms, maka proses tersebut akan dipindahkan ke antrian kedua.

d.            Antrian kedua akan dikerjakan bila antrian 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:

a.             Jumlah antrian

b.             Algoritma internal tiap antrian

c.             Aturan sebuah proses naik ke antrian yang lebih tinggi

d.            Aturan sebuah proses turun ke antrian yang lebih rendah

e.             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 masa sekarang ini algoritma multilevel feedback queue adalah salah satu yang paling banyak digunakan.

Category › Algoritma Dan Struktur Data , Kuliah , Tugas