Solaris CPU Scheduler

Penjadwalan merupakan kumpulan kebijaksanaan dan mekanisme di sistem operasi yang berkaitan dengan urutan kerja yang dilakukan sistem komputer. Proses penjadwalan yang akan dibahas disini adalah proses penjadwalan sistem operasi SOLARIS.

Sasaran atau tujuan utama penjadwalan proses optimasi kinerja menurut kriteria tertentu. dimana kriteria untuk mengukur dan optimasi kerja penjadwalan antara lain :

• Agar semua pekerjaan memperoleh pelayanan yang adil (firness).
•  Agar pemakaian prosesor dapat dimaksimumkan.
•  Agar waktu tanggap dapat diminimumkan.
•  Agar pemakaian sumber daya seimbang.
• Turn arround time, waktu sejak program masuk ke system sampai proses selesai.
• Efesien, proses tetap dalam keadaan sibuk tidak menganggur.
• Agar terobosan (thoughput) dapat dimaksimumkan.

Terdapat 3 tipe penjadwal berada secara bersama-sama pada sistem operasi yang kompleks, yaitu:

1. Penjadwal jangka pendek (short term scheduller), Bertugas menjadwalkan alokasi pemroses di antara proses-proses ready di memori utama Penjadwalan dijalankan setiap terjadi pengalihan proses untuk memilih proses berikutnya yang harus dijalankan.
2. Penjadwal jangka menengah (medium term scheduller), Setelah eksekusi selama suatu waktu, proses mungkin menunda sebuah eksekusi karena membuat permintaan layanan masukan/keluaran atau memanggil suatu system call. Proses-proses tertunda tidak dapat membuat suatu kemajuan menuju selesai sampai kondisi-kondisi yang menyebabkan tertunda dihilangkan. Agar ruang memori dapat bermanfaat, maka proses dipindah dari memori utama ke memori sekunder agar tersedia ruang untuk proses-proses lain. Kapasitas memori utama terbatas untuk sejumlah proses aktif. Aktivitas pemindahan proses yang tertunda dari memori utama ke memori sekunder disebut swapping. Proses-proses mempunyai kepentingan kecil saat itu sebagai proses yang tertunda. Tetapi, begitu kondisi yang membuatnya tertunda hilang dan dimasukkan kembali ke memori utama dan ready.
3. Penjadwal jangka panjang (long term scheduller), Penjadwal ini bekerja terhadap antrian batch dan memilih batch berikutnya yang harus dieksekusi. Batch biasanya adalah proses-proses dengan penggunaan sumber daya yang intensif (yaitu waktu pemroses, memori, masukan/keluaran), program-program ini berprioritas rendah, digunakan sebagai pengisi (agar pemroses sibuk) selama periode aktivitas job-job interaktif rendah.

Penjadwalan pada SIstem Operasi Solaris

Solaris menggunakan penjadwalan berdasarkan prioritas dimana yang mempunyai prioritas yang lebih tinggi dijalankan terlebih dahulu. Informasi tentang penjadwalan kernel thread dapat dilihat dengan ps -elcL. Kernel Solaris adalah fully preemtible, artinya semua thread, termasuk thread yang mendukung aktifitas kernel itu sendiri dapat ditunda untuk menjalankan thread dengan prioritas yang lebih tinggi.

Kernel Solaris adalah fully preemtible, artinya semua thread, termasuk thread yang mendukung aktifitas kernel itu sendiri dapat ditunda untuk menjalankan thread dengan prioritas yang lebih tinggi.

Solaris mengenal 170 prioritas yang berbeda, 0-169. Terbagi dalam 4 kelas penjadwalan yang berbeda:

1. Real time (RT).  Thread di kelas RT memiliki prioritas yang tetap dengan waktu kuantum yang tetap juga. Thread ini memiliki prioritas yang tinggi berkisar antara 100-159. Hal inilah yang membuat proses waktu nyata memiliki response time yang cepat. Proses waktu nyata akan dijalankan sebelum proses-proses dari kelas yang lain dijalankan sehingga dapat menghentikan proses di system class. Pada umumnya, hanya sedikit proses yang merupakan real time class.
2. System (SYS). Solaris menggunakan system class untuk menjalankan kernel proses, seperti penjadwalan dan paging daemon. Threads di kelas ini adalah "bound" threads, berarti bahwa mereka akan dijalankan sampai mereka di blok atau prosesnya sudah selesai. Prioritas untuk SYS threads berkisar 60-99. Sekali dibangun, prioritas dari sistem proses tidak dapat dirubah. System class dialokasikan untuk kernel use( user proses berjalan di kernel mode bukan di system class).
3. Time Sharing (TS).  Time sharing class merupakan default class untuk proses dan kernel thread yang bersesuaian. Time slices masing-masing proses dibagi berdasarkan prioritasnya. Dalam hal ini, prioritas berbanding terbalik dengan time slices-nya. Untuk proses yang prioritasnya tinggi mempunyai time-slices yang pendek, dan sebaliknya proses dengan prioritas yang rendah mempunyai time slices yang lebih panjang. Besar prioritasnya berada antara 0-59. Proses yang interaktif berada di prioritas yang tinggi sedangkan proses CPU-bound mempunyai prioritas yang rendah. Aturan penjadwalan seperti ini memberikan response time yang baik untuk proses yang interaktif, dan troughput yang baik untuk proses CPU-bound.
4. Interactive (IA). Kelas Interaktif menggunakan aturan yang sama dengan aturan dengan kelas kelas time sharing, tetapi kelas ini memberikan prioritas yang tinggi untuk aplikasi jendela ( windowing application) sehingga menghasilkan performance yang lebih baik. Seperti TS, range IA berkisar 0-59.

Tabel 16.2. Solaris dispatch table for interactive and time sharing threads

Priority	Time quantum	Time quantum expired	return from sleep
0	200	0	50
5	200	0	50
10	160	0	51
15	160	5	51
20	120	10	52
25	120	15	52
30	80	20	53
35	80	25	54
40	40	30	55
45	40	35	56
50	40	40	58
55	40	45	58
59	20	49	59

Keterangan:

• Priority: prioritas berdasarkan kelas untuk time sharing dan interactive class. Nomor yang lebih tinggi menunjukkan prioritas yang lebih tinggi.
• Time quantum: waktu kuantum untuk setiap prioritas. Dapat diketahui bahwa fungsi waktu kuantum berbanding terbalik dengan prioritasnya.
• Time quantum expired: Prioritas terbaru untuk thread yang telah habis time slices-nya tanpa diblok. Dapat dilihat dari tabel bahwa thread yang CPU-bound tetap mempunyai prioritas yang rendah.
• Return from sleep: Prioritas thread yang kembali dari sleeping(misalnya menunggu dari M/K). Seperti yang terlihat dari tabel ketika M/K berada di waiting thread, prioritasnya berada antara 50-59, hal ini menyebabkan response time yang baik untuk proses yang interaktif.
• Fixed Priority (FX).  Thread di kelas fixed priority memiliki range prioritas (0-59) yang sama seperti di time-sharing class; tetapi, prioritas mereka tidak akan berubah.
• Fair Share Scheduler (FSS). Thread yang diatur oleh FSS dijadwalkan berdasar pembagian sumber daya dari CPU yang tersedia dan dialokasikan untuk himpunan proses-proses (yang dikenal sebagai project). FS juga berkisar 0-59. FSS and FX baru mulai diimplementasikan di Solaris 9.

Seperti yang telah diketahui, setiap kelas penjadwalan mempunyai himpunan dari prioritas-prioritas. Tetapi, penjadwal mengubah class-specific priorities menjadi global priorities kemudian memilih thread dengan prioritas paling tinggi untuk dijalankan. Thread yang dipilih tersebut jalan di CPU sampai thread tersebut (1) di- block, (2) habis time slices-nya, atau (3) dihentikan oleh thread dengan prioritas yang lebih tinggi. Jika ada beberapa thread dengan prioritas yang sama, penjadwal akan menggunakan Round-Robin queue. Seperti yang pernah dijelaskan sebelumnya, Solaris terdahulu menggunakan many-to-many model tetapi solaris 9 berubah menggunakan one-to-one model.

Multi Level Feedback Queue Scheduler

MLFQ pertamakali diperkenalkan oleh Corbato (1962) pada sistem yang dikenal dengan Compatible Time-Sharing System (CTSS) dan karyanya berikutnya pada Multics, menghantarkan ACM pada penghargaan “Turing Award”. MLFQ selalu dikembangkan setiap tahunnya untuk implementasinya pada sistem yang  modern. Permasalahan yang mendasar dari MLFQ  adalah untuk mencapai 2 hal. Pertama adalah mengoptimalisasi turn around-time, yang dilakukan dengan cara melakukan proses yang paling pendek, sayangnya OS tidak mengerti secara keseluruhan seberapa panjang suatu proses akan berjalan maka algoritma seperti SJF (atau STCF) diperlukan. Kedua, MLFQ ingin membuat sistem terasa lebih responsif dan interaktif oleh user dengan meminimalisasi response time, Sayangnya algoritma seperti round-robin memang akan meminimalisasi response time namun sangat buruk untuk menangani turn around-time. Bagaimana membangun suatu scheduler yang dapat mencapai kedua hal tersebut? Hal inilah yang ingin dicapai oleh Multi Level Feedback Queue Scheduler.

Pada bagian ini akan dibahas bagaimana dasar algoritma dibalik MLFQ. MLFQ membedakan prioritas dari proses berdasarkan observed behavior. Contohnya suatu proses berulang kali membebaskan CPU ketika menunggu input dari keyboard, MLFQ akan menetapkan proses tersebut pada prioritas tinggi untuk memperoleh interaktivitas, Contoh lain jika ada proses yang menggunakan CPU secara intensif untuk waktu yang lama maka MLFQ akan mengurangi prioritasnya. Dengan demikian MLFQ akan mencoba belajar tentang bagaimana suatu proses berjalan dan menggunakan history dari proses untuk memprediksi behavior dari setiap proses kedepannya.  Ada 2 basic rule untuk MLFQ:

• Rule 1: Jika prioritas (A) > Prioritas (B), A berjalan dan B tidak berjalan.
• Rule 2: Jika prioritas (A) = Prioritas (B), A dan B berjalan di RR.

Pada ilustrasi dibawah akan diperlihatkan bagaimana ada dua proses (A dan ) pada prioritas tertinggi dan proses C berada ditengah dan proses D pada prioritas terendah. Scheduler akan memanipulasi time-slice antara B dan A karena keduanya merupakan prioritas tertinggi pada system.

Dengan mempertimbangan proses yang membutuhkan interaktifitas (short running) dan secara periodik

membebaskan CPU dan proses yang bersifat CPU-Bound (long-running), berikut ini adalah algoritma untuk mengatur prioritas diantara kedua jenis proses tersebut:

Rule 3: Ketika proses masuk dalam sistem, ditempatkan pada prioritas paling tinggi (queue teratas)

Rule 4a: Jika pekerjaan menggunakan semua time slice ketika berjalan, prioritas diturunkan (bergerak turun 1 level pada antrian queue)

Rule 4b: Jika proses melepaskan CPU sebelum time slice, proses tersebut akan tetap pada level prioritas yang sama.

Rule 5: Setelah beberapa waktu, pindahkan semua process dalam sistem ke queue teratas.

                                          
Dengan cara demikian, MLFQ menawarkan solusi yang terbaik karena dapat mencapai performa yang optimal untuk proses yang bersifat short running interactive dan membagi secara adil untuk prose yang bersifat  long running CPU intensive. Untuk alasan inilah banyak sistem termasuk BSD UNIX derivatives , Solaris, dan Windows NT menggunakan model  MLFQ sebagai dasar schedulernya. 

Bresenham's Line Drawing Algorithm

Bresenham line algorithm merupakan algoritma yang menunjukkan pixel mana dalam sebuah gambar raster n-dimensi yang harus ditandai (diwarna) supaya membentuk mendekati garis lurus dari 2 titik. Algoritma ini digunakan untuk menggambar garis pada layar komputer dan hanya menggunakan operasi-operasi matematis bertipe data integer.  Algoritma ini dikembangkan oleh Jack E. B resenham, 1962 di IBM. Algoritma Bresenham juga dikembangkan untuk menampilkan lingkaran, biasa disebut dengan "Bresenham's circle algorithm" atau “midpoint circle algoritm”. Pada tulisan ini akan dijelaskan mengenai algoritma Bresenham untuk menggambar garis dan lingkaran beserta contoh implementasinya menggunakan bahasa pascal.

 Penjelasan Algoritma

Asumsikan y= mx + b merepresentasikan penjumlahan variabel real dari garis yang di plotkan menggunakan pixel dimana dua buah titik (x1, y1) dan (x2, y2) memiliki koordinat integer yang akan dihubungkan dengan garis. Pada gambar dibawah ini, kedua titik tersebut berada di bagian kiri bawah dan kanan atas dari grid pixel (0,0) dan (35,9).

Kita asumsikan bahwa koordinat x-pixel bertambah ke arah kanan dan koordinat y-pixel bertambah ke atas. Pada contoh ini, kita asumsikan bahwa x1<x2 dan y1<y2. Ini merupakan batasan yang diperlukan untuk mendiskripsikan pengaturan umum untuk contoh dibawah ini. Asumsi berikutnya adalah kemiringan m adalah 0 ≤ m ≤ 1. Asumsi ini menjamin bahwa kita bergerak poin demi poin dari kiri ke kanan pada grafik. Y tidak akan pernah bergerak lebih dari 1  pixel dan nilai y bertambah sebagaimana nilai x juga bertambah. Asumsi ini juga penting untuk menjelaskan gagasan dibalik algoritma bresenham ini. Kita akan menggunakan pembagian untuk Δy / Δx untuk menyatakan nilai m.

Untuk membuat alur garis yang akurat, kita melacak akumulasi kesalahan dalam variabel y. Sejak titik pertama (x1, y1), variabel Accumulated y-Error harus di inisialisasi dengan nilai 0. Bersamaan dengan pergerakan garis dari kiri ke kanan, kita akan menentukan increment y dengan 1 hanya ketika nilai akumulasi pada variabel y-error   menjadi lebih besar dari 1/2. Pada kondisi ini, kita hanya akan menghitung point pada alur dimana y-koordinat berbeda dari nilai TrueY banyak 1 pixel.

CurrentY + AccumulatedY Error = TrueY

Atau

AccumulatedY Error = trueY - CurrentY

Diketahui operasi  y = mx + c, jika nilai x bertambah 1, maka nilai y harus naik sebanyak m. Jika nilai y tidak bertambah sama sekali ketika nilai x bertambah 1, maka accumulated error pada y harus ditambahkan sebanyak m. Begitu pula jika y hanya bertambah 1 nilai tanpa menambah nilai x sama sekali, maka nilai accumulated error pada y harus berkurang sebanyak 1.

procedure Bresenham( x1, y1, x2, y2 : integer);

var       AccumulatedYError : real;

Δy, Δx : real;

CurrentX, CurrentY : integer;

FinalX : integer;

begin

AccumulatedYError := 0.0;

CurrentX := x1;

CurrentY := y1;

FinalX := x2;

Δx := ÐrealÑ x2 - x1;

Δy := ÐrealÑ y2 - y1;

repeat

Plot(CurrentX, CurrentY);

CurrentX := CurrentX + 1;

AccumulatedYError := AccumulatedYError + Δx  / Δy ;

if AccumulatedYError > 1 then

begin

CurrentY := CurrentY + 1;

AccumulatedYError := AccumulatedYError - 1.0

end

until CurrentX > FinalX

end;  

Algoritma diatas mengasumsikan bahwa variabel AccumulatedY  Error  dan Δy  dan  Δx semuanya merupakan variabel real floating point. Kita harus menghindari semua nilai decimal dan pembagian supaya algoritma berjalan dengan cepat. Jadi, gunakan variabel dan nilai integer saja.

Menuliskan operasi: AccumulatedY Error = AccumulatedY Error + Δy / Δx

Ekuivalen dengan : Δx . AccumulatedY Error = Δx . AccumulatedY Error + Δy dimana nilai pecahan dihilangkan.

Selanjutnya, kita menghindari perkalian dengan bilangan 2 dan dengan Δx setiap saat melalui perulangan dengan menulis ulang operasi diatas dengan test kondisional:

(2 . Δx . AccumulatedY Error) = (2 . Δx . AccumulatedY Error) + (2 . Δy)

Jika (2 . Δx . AccumulatedY Error) > Δx

Perlu diingat bahwa m dapat ditulis dengan m = Δy / Δx = (y2 – y1) / (x2 – x1).

Dapat diasumsikan bahwa Δy dan Δx adalah integer dimana Δy = y2 – y1 dan Δx = x2 – x1. Kita buat variabel baru yang disebut TwoDxAccumulatedY Error.

- 1/2 ≤ AccumulatedY Error ≤ ½

Berikut adalah implementasi dari algoritma bresenham.

program TESTLINE(Input,Output);

uses dos, crt, bgidriv, bgifont, graph;

var       X1,Y1,X2,Y2 : integer;

grMode : integer;

grDriver : integer;

ErrorCode : integer;

procedure PlotLine(X1,Y1,X2,Y2 : integer);

var       CurrentX, CurrentY : integer;

Xinc, Yinc : integer;

Dx, Dy : integer;

TwoDx, TwoDy : integer;

TwoDxAccumulatedError : integer;

TwoDyAccumulatedError : integer;

begin

Dx := (X2-X1);

Dy := (Y2-Y1);

TwoDx := Dx + Dx;

TwoDy := Dy + Dy;

CurrentX := X1;

CurrentY := Y1;

Xinc := 1;

Yinc := 1;

if Dx<0 then

begin

Xinc := -1; { decrement X's }

Dx := -Dx;

T          woDx := -TwoDx

end;

if Dy<0 then

begin

Yinc := -1;

Dy := -Dy;

TwoDy := -TwoDy

end;

putpixel(X1,Y1,1);

if (Dx<>0) or (Dy<>0) then

begin

if Dy<=Dx then

begin

TwoDxAccumulatedError := 0;

repeat

inc(CurrentX, Xinc);

inc(TwoDxAccumulatedError, TwoDy);

if TwoDxAccumulatedError>Dx then

begin

inc(CurrentY, Yinc);

dec(TwoDxAccumulatedError, TwoDx)

end;

putpixel(CurrentX,CurrentY,1)

until CurrentX=X2

end

else

begin

TwoDyAccumulatedError := 0;

repeat

inc(CurrentY, Yinc);

inc(TwoDyAccumulatedError, TwoDx);

if TwoDyAccumulatedError>Dy then

begin

inc(CurrentX, Xinc);

dec(TwoDyAccumulatedError, TwoDy)

end;

putpixel(CurrentX,CurrentY,1)

until CurrentY=Y2

end

end

end; 

Midpoint Circle Algorithm 

Algoritma midpoint ini merupakan pengembangan dari algoritma bresenham untuk menggambar lingkaran. Ketika menggambar lingkaran dengan menggunakan algoritma ini, kita perlu mengkalkulasi floating point setiap koordinat dimana akan menjadi proses yang lambat apabila banyak objek sekaligus. Metode ini menyajikan cara yang sederhana dalam menggambar lingkaran dengan menggunakan perkiraan dari titik tengah (midpoint) lingkaran.

Untuk setiap titik p(x,y) kita dapat menentukan titik berikutnya (perkiraan) N(x, y+1), NW(x-1,y+1) berdasarkan titik tengah M(x-1/2, y+1). Jika titik M berada didalam lingkaran, Ttik N dekat dengan lingkaran, maka dari itu titik N harus dipilih sebagai titik berikutnya. Sebaliknya, titik NW yang harus dipilih. Untuk mengkalkulasi jarak dari M dapat dihitung dengan rumus Rd = r – Rm. Jika d < 0, maka M berada diluar lingkaran. Jika Rd > 0 maka M berada di dalam lingkaran. Dari rumus x ^ 2 + y ^ 2, dapat kita ketahui bahwa Xm ^ 2 + Ym + 2 – Rm ^ 2 = Xm ^ 2 + Ym ^ 2 – (r – Rd) ^ 2 = 0. Karena titik tengah dekat dengan lingkaran, maka dapat kita abaikan jika Rd > 2. Jadi, jika D(M) > o, Rd < 0, M berada diluar lingkaran, NW yang harus dipilih jika D(M) < 0, Rd > 0, M didalam lingkaran, N harus dipilih. Berikut algoritma dalam bahasa javascript.

var drawCircle = function(ctx , x , y , r){

  var cx = r;

  var cy = 0;

  //Inisialisasi 4 titik atas, bawah, kiri, kanan

  init(ctx,x,y,r);

   

  //Kita hanya perlu mengkalkulasi 1/8 dari lingkaran,

  //Yaitu ketika sudut= 45derajat, cx = xy

  while(cx > cy){

    if(cx*cx + cy*cy -r*r > 0){ // D(M) , if D(M) > 0, NW(x-1,y+1) dipilih

      cx--;

    }

    cy++;

  }

}

Algoritma ini dapat lebih di efektifkan dengan menyederhanakan kalkulasi D(M). Untuk setiap D(M) = D(x-1/2,y) = x^2 - x +1/4 + y^2 -r^2, berikutnya  D(Mnew) = D(x-1/2,y+1) = x^2 - x +1/4 + y^2 +2y +1 - r^2. Jadi kita mendapatkan perbedaan setiap tingkatan dari D(M), dy = 2y +1 dan nilai D(Mnew) = D(M) + 2y + 1. Ketika D(M) > 0, x harus digerakkan juga, jadi D(Mnew) = D(x-3/2,y+1) = x^2 - 3x +9/4 + y^2 +2y + 1 = D(M) -2x +2 +2y +1 . Kita mendapatkan perbedaan ketika x digerakkan : dx = -2x + 2. Untuk algoritma yang sudah di optimalisasi:

 var drawCircle = function(ctx, x, y, r){ 

 // d dimulai dari  D(M) = r^2 - r^2 + r-1/4 = r- 1/4 , tapi dapat di abaikan karena r>1/4

  var d = r;
  var dx = (-2) * r; //dx = -2x +2 , constant move to loop  var dy = 0; //dy = 2y + 1 , constant move to loop   var cx = r;
  var cy = 0;    
  init(ctx,x,y,r);   while(cx > cy){    if(d > 0){      cx--;      d += (-2)*cx + 2;    }    cy++;    d += 2*cy + 1;     mirrowing(ctx,x,y,cx,cy);  }}

Binary dan Sequential Search

Dalam ilmu komputer, sebuah algoritma pencarian dijelaskan secara luas adalah sebuah algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan solusi. Operasi pencarian adalah operasi untuk menemukan sebuah nilai (data) di dalam sekumpulan nilai yang bertipe sama. Untuk menemukan nilai yang dicari, instruksi yang paling penting yang harus dilakukan adalah memeriksa jika nilai yang dicari sama dengan salah satu nilai dalam kumpulan nilai yang dimaksud. Metode pencarian yang bisa dipergunakan tergantung dari Bagaimana urutan nilai-nilai di dalam kumpulan nilai dan bagaimana struktur data yang dipergunakan untuk menyusun nilai-nilai tersebut. 

Sequential Search

Algoritma sequential search adalah salah satu algoritma yang digunakan untuk memecahkan masalah pencarian data pada suatu data larik/array. Cara kerja dari algoritma ini adalah dengan menelusuri elemen-elemen array dari awal sampai akhir, dimana data tidak perlu diurutkan terlebih dahulu. Kemungkinan terbaik(best case) dari algoritma ini adalah jika data yang dicari berada pada elemen array yang terdepan sehingga waktu yang dibutuhkan untuk pencarian data semakin singkat. Sebaliknya, akan mencapai kondisi terburuk(wors case) apabila data yang dicari berada pada elemen akhir.

Metode pencarian beruntun atau linear (sequential search) dapat dipergunakan apabila:

1. Nilai-nilai tersebut belum berurutan.
2. Nilai-nilai tersebut sudah berurutan, tetapi struktur data yang dipergunakan untuk menyimpan nilai-nilai tersebut adalah linked list.

Contoh implementasi sequential search pada Pascal:

PROGRAM Pencarian_Sequential_Search;

USES CRT;

CONST

Max = 100;

TYPE

                ArrData = ARRAY[1..Max] OF INTEGER;

PROCEDURE INPUT_DATA(var D :ArrData; N:INTEGER);

VAR

                I : INTEGER;

BEGIN

                FOR I:=1 TO N DO

                BEGIN

                                WRITE('Tentukan Data ke - ',I,' : ');

                                READLN(D[I]);

                END;

END;

{--------------------Fungsi Sequential search----------------------}

FUNCTION SEQUENTIAL_SEARCH(var D :ArrData; N,Cari:INTEGER):BOOLEAN;

VAR

                I : INTEGER;

                Ketemu : BOOLEAN;

BEGIN

                I:=1;

                Ketemu := False;

                WHILE((I<=N) AND (Ketemu=False)) DO

                BEGIN

                                IF(D[I]=Cari) THEN Ketemu:=True;

                I:=I+1

                END;

                SEQUENTIAL_SEARCH:=Ketemu;

END;

{--------------------------Program Utama---------------------------}

VAR

                Data : ArrData;

                Jumlah, I, Cari : INTEGER;

BEGIN

                CLRSCR;

                WRITE('Tentukan Jumlah Data : ');READLN(Jumlah);

                INPUT_DATA(Data, Jumlah);

                WRITELN;

                WRITE('Tentukan data yang ingin dicari : ');

                READLN(Cari);

                IF (SEQUENTIAL_SEARCH(Data,Jumlah,Cari)) THEN

                                WRITELN('Data Ditemukan')

                ELSE

                WRITELN('Data Tidak Ditemukan');

                READLN;

END.

Binary Search

Binary search adalah algoritma pencarian untuk data yang terurut. Pencarian dilakukan dengan cara menebak apakah data yang dicari berada ditengah-tengah data, kemudian membandingkan data yang dicari dengan data yang ada ditengah. Bila data yang ditengah sama dengan data yang dicari, berarti data ditemukan. Namun, bila data yang ditengah lebih besar dari data yang dicari, maka dapat dipastikan bahwa data yang dicari kemungkinan berada disebelah kiri dari data tengah dan data disebelah kanan data tengah dapat diabai. Upper bound dari bagian data kiri yang baru adalah indeks dari data tengah itu sendiri. Sebaliknya, bila data yang ditengah lebih kecil dari data yang dicari, maka dapat dipastikan bahwa data yang dicari kemungkinan besar berada disebelah kanan dari data tengah. Lower bound dari data disebelah kanan dari data tengah adalah indeks dari data tengah itu sendiri ditambah 1. Demikian seterusnya.

Metode pencarian beruntun (sequential) maupun metode pencarian biner (binary search) dapat dipergunakan, jika:

1. Nilai-nilai tersebut sudah tersusun secara berurutan.
2. Nilai-nilai tersebut disusun ke dalam bentuk array atau struktur data sejenis yang masing-masing nilai tersimpan dalam bagian-bagian yang mempunyai indeks yang unik dan indeksnya berurutan dari yang paling kecil hingga yang paling besar (bersifat ordinal).

Ilustrasi Binary search: 

Berikut ini contoh implementasi binary search pada Pascal:

PROGRAM Pencarian_Binary_Search;

USES CRT;

CONST Max = 100;

TYPE

ArrData = ARRAY[1..Max] OF INTEGER;

PROCEDURE INPUT_DATA(var D :ArrData; N:INTEGER);

VAR

                I : INTEGER;

BEGIN

                FOR I:=1 TO N DO

                BEGIN

                                WRITE('Tentukan Data ke - ',I,' : ');

                                READLN(D[I]);

                END;

END;

{----------------------Fungsi Binary search------------------------}

FUNCTION BINARY_SEARCH(var D :ArrData; N,Cari:INTEGER):BOOLEAN;

VAR

                L,R,M : INTEGER;

                Ketemu : BOOLEAN;

BEGIN

                L:=1;

                R:=N;

                Ketemu := False;

                WHILE((L<=R) AND (Ketemu=False)) DO

                BEGIN

                                M:=ROUND((L+R) / 2);

                                IF(D[M]=Cari) THEN

                                                Ketemu:=True

                                ELSE IF(D[M]>Cari) THEN

                                                R:=M-1

                                ELSE

                                                L:=M+1;

                END;

                BINARY_SEARCH:=Ketemu;

END;

{--------------------------Program Utama---------------------------}

VAR

                Data : ArrData;

                Jumlah, I, Cari : INTEGER;

BEGIN

                CLRSCR;

                WRITE('Tentukan Jumlah Data : ');READLN(Jumlah);

                INPUT_DATA(Data, Jumlah);

                WRITELN;

                WRITE('Tentukan data yang ingin dicari : ');

                READLN(Cari);

                IF (BINARY_SEARCH(Data,Jumlah,Cari)) THEN

                                WRITELN('Data Ditemukan')

                ELSE

                                WRITELN('Data Tidak Ditemukan');

                READLN;

END.