Bahasa Assembly, Stack & Queue (3) - 1 [PDF]

Citation preview

A.Bahasa Assembly Bahasa Assembly adalah bahasa pemrograman tingkat rendah yang digunakan pada berbagai perangkat elektronika dan robotika. Bahasa Assembly bekerja dengan cara diterjemahkan ke dalam bahasa mesin yang hanya bisa dimengerti oleh komputer. Tiap-tiap mesin memiliki bahasa Assemby yang berbeda-beda instruksinya. Ada tiga jenis bahasa Assembly yang terkenal. Yaitu, Assembly x86 yang hanya digunakan untuk CPU berbasis intel, ARM yang digunakan pada ponsel dan sistem embedded, dan MIPS yang digunakan pada beberapa konsol game. Bahasa Assembly yang digunakan untuk membuat OS disini adalah Assembly x86. Bahasa Assembly adalah bahasa komputer yang kedudukannya di antara bahasa mesin dan bahasa level tinggi misalnya bahasa C, C++, Pascal, Turbo Basic, Java, dan sebagainya. Bahasa C atau Pascal dikatakan sebagai bahasa level tinggi karena memakai kata-kata dan pernyataan yang mudah dimengerti manusia, meskipun masih jauh berbeda dengan bahasa manusia sesungguhnya. Assembler adalah program yang bekerja membantu penulisan instruksi dalam format bahasa inggris sehingga mudah dibaca dan dipahami. MOV R0, #02h MOV A, #03h ADD A, R0



Perintah baris pertama bekerja menjalankan proses pengisian register R0 dengan data 02h. Perintah baris kedua bekerja menjalankan proses pengisian register A dengan data 03h. Kemudian proses penjumlahan data pada register A dengan data pada register R0 dijalankan menggunakan perintah ADD A,R0 dan menghasilkan data 05h tersimpan di register A. Perintah MOV dan ADD adalah mnemonik atau singkatan dari perintah MOVE dan ADD. Mnemonik dari perintah lainnya dapat dirangkum dalam tabel 8 berikut. Tabel Mnemonik Perintah Assembly AT89S51 No



PERINTAH



MNEMONIK



1.



ADD



ADD



2.



ADD WITH CARRY



ADC



3.



SUB WITH BORROW



SBB



4.



INCREMENT



INC



5.



DECREMENT



DEC



6.



MULTIPLY



MUL



7.



DEVIDE



DIV



8.



AND LOGIC



ANL



9.



OR LOGIC



ORL



10.



EXLUSIVE OR LOGIK



XRL



11.



DECIMAL ADJUST ACCUMULATOR



DAA



12.



CLEAR ACCUMULATOR



CLR A



13.



COMPLEMENT ACCUMULATOR



CPL A



14.



ROTATE ACCUMULATOR LEFT



RLA



15.



ROTATE ACCUMULATOR LEFT THROUGH CARRY



16.



ROTATE ACCUMULATOR RIGHT



17.



ROTATE ACCUMULATOR RIGHT THROUGH



RLCA RRA RRCA



CARRY 18.



SWAPP NIBBLE WITHIN ACCUMULATOR



SWAP



19.



PUSH DIRECT BYTE KE STACK



PUSH



20.



POP DIRECT BYTE DARI STACK



POP



21.



JUMP IF CARRY SET C=1



22.



JUMP IF CARRY NOT SET C = 0



23.



JUMP IF DIRECT BIT SET



24.



JUMP IF DIRECT BIT NOT SET



JNB



25.



JUMP IF DIRECT BIT SET & CLEAR BIT



JBC



26.



ABSOLUTE CALL



ACALL



27.



LONG CALL



LCALL



28.



RETURN



RET



29.



RETURN FROM INTERRUPT



RETI



30.



ABSOLUTE JUMP



AJMP



31.



LONG JUMP



LJMP



32.



SHORT JUMP



SJMP



33.



JUMP INDIRECT



JMP



34.



JUMP IF ACCUMULATOR ZERRO



35.



JUMP IF ACCUMULATOT NOT ZERRO



JNZ



36.



COMPARE AND JUMP IF NOT EQUAL



CJNE



37.



DECREAMENT AND JUMP IF NOT ZERO



DJNZ



38.



NO OPERATION



NOP



Beberapa penjelasan fungsi Mnemonik Perintah Assembly : 



mov - MOVE, untuk memindah value.







add - ADD, untuk menambah bilangan.







sub - SUBSTRACT, untuk mengurangi bilangan.







mul - MULTIPLY, untuk mengalikan bilangan.







div - DIVIDE, untuk membagi bilangan.







and - AND, untuk operasi logika dan (^).



JC JNC JB



JZ







or - OR, untuk operasi bilangan atau (v).







call - CALL, untuk memanggil suatu fungsi tertentu.







cmp - COMPARE, untuk membandingkan dua value.







jmp - JUMP, untuk pergi ke sebuah fungsi (bukan memanggil) je - JUMP IF.







EQUAL, untuk pergi ke fungsi tertentu jika perbandingan antara kedua value sama.







jne - JUMP ID NOT EQUAL, untuk pergi ke fungsi tertentu jika perbandingan antara kedua value tidak sama.







jg - JUMP IF GREATER, untuk pergi ke fungsi tertentu jika value pertama lebih besar daripada value kedua.







jng - JUMP IF NOT GREATER, untuk pergi ke fungsi tertentu jika value pertama lebih kecil daripada value kedua.







int - INTERRUPT, untuk menjalankan instruksi milik mesin.







push - PUSH, untuk memasukkan value yang ada di suatu register ke posisi teratas stack.







pop - POP, untuk mengeluarkan value terluar di stack ke dalam sebuah register.







ret - RETURN, untuk kembali ke posisi kode dimana fungsi dipanggil.



Bahasa mesin adalah kumpulan kode biner yang merupakan instruksi yang bisa dijalankan oleh komputer. Di dalam mikrokontroler instruksi disimpan dalam kode heksa sehingga sulit dibaca dan dipahami maknanya. Sedangkan bahasa assembly memakai kode mnemonik untuk menggantikan kode biner, agar lebih mudah diingat sehingga lebih memudahkan dalam penulisan program.



No



OPERATION



ASSEMBLY



CODE



1.



78 02



MOV R0, #02h



2.



74 03



MOV A, #03h



3.



28



ADD A, R0



Kode bahasa mesin atau sering disebut dengan operation code dari perintah MOV R0,#02h adalah 78 02. Untuk MOV A,#03h kode operasinya dalah 74 03 dan 28 adalah kode operasi dari perintah ADD A, R0. Kode operasi untuk setiap perintah dapat dibaca pada lembar instruction set. Program yang ditulis dengan bahasa assembly terdiri dari label; kode mnemonik, operand 1, operand 2, keterangan, dan lain sebagainya. Program ini disebut



sebagai program sumber (Source Code). Source code belum bisa diterapkan langsung pada prosesor untuk dijalankan sebagai program. Source code harus diterjemahkan dulu menjadi bahasa mesin dalam bentuk kode biner atau operasi.



Source code ditulis dengan program editor biasa, misalnya Note Pad pada Windows atau SideKick pada DOS, TV demo, lalu source code diterjemahkan ke bahasa mesin dengan menggunakan program Assembler. Proses menterjemahkan source code menjadi bahasa mesin disebut dengan proses assembled. Hasil kerja program Assembler adalah “program objek” dan juga “assemly listing”. Program Objek berisikan kode kode operasi bahasa mesin. Biasanya file program objek menguanakan ekstensi .HEX. Kode-kode operasi bahasa mesin inilah yang dituliskan ke memori-program prosesor. Dalam dunia mikrokontroler biasanya program objek ini diisikan ke UV EPROMatau EEPROM dan khusus untuk mikrokontroler buatan Atmel, program ini diisikan ke dalam Flash PEROM yang ada di dalam chip mikrokontroler AT89S51 atau AT89C2051.



Assembly Listing merupakan naskah yang berasal dari program sumber, dalam naskah tersebut pada bagian sebelah setiap baris dari program sumber diberi tambahan hasil terjemahan program Assembler. Tambahan tersebut berupa nomor memori-program berikut dengan kode yang akan diisikan pada memori-program bersangkutan. Naskah ini sangat berguna untuk dokumentasi dan sarana untuk menelusuri program yang ditulis. Gambar 22 menunjukkan model editor program assembly dan bagan kerja proses assembly.



Konstruksi Program Assembly Source program dalam bahasa Assembly menganut prinsip 1 baris untuk satu perintah tunggal. Setiap baris perintah tersebut bisa terdiri atas beberapa bagian (field), yakni bagian Label, bagian mnemonik, bagian operand yang bisa lebih dari satu dan terakhir bagian komentar. Untuk membedakan masing-masing bagian tersebut dibuat ketentuan sebagian berikut: 1. Masing-masing bagian dipisahkan dengan spasi atau TAB, khusus untuk operand yang lebih dari satu masing-masing operand dipisahkan dengan koma. 2. Bagian-bagian tersebut tidak harus semuanya ada dalam sebuah baris, jika ada satu bagian yang tidak ada maka spasi atau TAB sebagai pemisah bagian tetap harus ditulis. 3. Bagian Label ditulis mulai huruf pertama dari baris, jika baris bersangkutan tidak mengandung. Label mewakili nomor memori-program dari instruksi pada baris bersangkutan, pada saat menulis instruksi JUMP, Label ini ditulis dalam bagian operand untuk menyatakan nomor memori-program yang dituju. Dengan demikian Label selalu mewakili nomor memori-program dan harus ditulis dibagian awal baris instruksi.



Disamping Label dikenal pula Symbol, yakni satu nama untuk mewakili satu nilai tertentu dan nilai yang diwakili bisa apa saja tidak harus nomor memori-program. Cara penulisan Symbol sama dengan cara penulisan Label, harus dimulai di huruf pertama dari baris instruksi.



Mnemonik (artinya sesuatu yang memudahkan diingat) merupakan singkatan perintah, dikenal dua macam mnemonik, yakni manemonic yang dipakai sebagai instruksi mengendalikan prosesor, misalnya ADD, MOV, DJNZ dan lain sebagainya. Ada pula mnemonik yang dipakai untuk mengatur kerja dari program Assembler misalnya ORG, EQU atau DB, mnemonik untuk mengatur kerja dari program Assembler ini dinamakan sebagai ‘Assembler Directive’.



Operand adalah bagian yang letaknya di belakang bagian mnemonik, merupakan pelangkap bagi mnemonik. Kalau sebuah instruksi di-ibaratkan sebagai kalimat perintah, maka mnemonik merupakan subjek (kata kerja) dan operand merupakan objek (kata benda) dari kalimat perintah tersebut.



Tergantung pada jenis instruksinya, operand bisa berupa berbagai macam hal. Pada instruksi JUMP operand berupa Label yang mewakili nomor memori-program yang dituju misalnya LJMP Start, pada instruksi untuk pemindahan/pengolahan data, operand bisa berupa Symbol yang mewakili data tersebut, misalnya ADD A,#Offset. Banyak instruksi yang operandnya adalah register dari prosesor, misalnya MOV A,R1. Bahkan ada pula instruksi yang tidak mempunyai operand, misalnya RET.



Komentar merupakan bagian yang sekedar sebagai catatan, tidak berpengaruh pada prosesor juga tidak berpengaruh pada kerja program Assembler, tapi bagian ini sangat penting untuk keperluan dokumentasi.



Assembler Directive Sudah dibahas di atas, bagian Mnemonik dari sebuah baris perintah bisa merupakan instruksi untuk prosesor, maupun berupa Assembler Directive untuk mengatur kerja dari program Assembler. Mnemonik untuk instruksi prosesor, sangat tergantung pada prosesor yang dipakai, sedangkan mnemonik untuk Assembler Directive tergantung pada program Assembler yang dipakai. Meskipun demikian, terdapat beberapa Assembler Directive yang umum, yang sama untuk banyak macam program Assembler. Assembler Directive yang bersifat umum tersebut, antara lain adalah : ORG – singkatan dari ORIGIN, untuk menyatakan nomor memori yang dipakai setelah perintah itu, misalnya ORG 0000h maka memori berikutnya yang dipakai Assembler adalah 0000h. ORG berlaku untuk memori program maupun memori-data. Dalam hal penomoran memori, dikenal tanda sebagai awalan untuk menyatakan nomor memori dari baris bersangkutan. Misalnya : ORG 0H MOV A,#11111110B Mulai: MOV P0,A EQU – singkatan dari EQUATE, dipakai untuk menentukan nilai sebuah Symbol. Misalnya Angka88 EQU 88 memberi nilai 88 pada Symbol Angka88, atau CR EQU 0D mempunyai makna kode ASCII dari CR (Caarriage Return) adalah 08.



DB – singkatan dari DEFINE BYTE, dipakai untuk memberi nilai tertentu pada memori-program. Nilai tersebut merupakan nilai 1 byte, bisa berupa angka ataupun kode ASCII. DB merupakan Assembler Directive yang dipakai untuk membentuk teks maupun tabel. DW – singkatan dari DEFINE WORD, dipakai untuk memberi nilai 2 byte ke memori-program pada baris bersangkutan. Assembler Directive ini biasa dipakai untuk membentuk suatu tabel yang isinya adalah nomor-nomor memori-program. DS – singkatan dari Define Storage, Assembler Directive ini dipakai untuk membentuk variable. Sebagai variabel tentu saja memori yang dipakai adalah memori-data (RAM) bukan memori-program (ROM). Hal ini harus benar-benar dibedakan dengan Assembler Directive DB dan DW yang membentuk kode di memori-program. Dan karena DS bekerja di RAM, maka DS hanya sekedar menyediakan tempat di memori, tapi tidak mengisi nilai pada memori bersangkutan.



B. Stack Pengertian Stack pada Struktur Data adalah sebagai tumpukan dari benda, sekumpulan data yang seolah-olah diletakkan di atas data yang lain, koleksi dari objek-objek homogen, atau Suatu urutan elemen yang elemennya dapat diambil dan ditambah hanya pada posisi akhir (top) saja. Stack pada Struktur Data dapat diilustrasikan dengan dua buah kotak yang ditumpuk, kotak yang satu akan ditumpuk diatas kotak yan0kg lainnya. Jika kemudian stack 2 kotak tadi, ditambah kotak ketiga, keempat, kelima, dan seterusnya, maka akan diperoleh sebuah stack kotak yang terdiri dari N kotak.



Stack bersifat LIFO (Last In First Out) artinya Benda yang terakhir masuk ke dalam stack akan menjadi yang pertama keluar dari stack. Operasi-operasi yang biasanya terdapat pada Stack yaitu: 1. Push : digunakan untuk menambah item pada stack pada tumpukan paling atas 2. Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas 3. Clear : digunakan untuk mengosongkan stack 4. IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong



5. IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh



Cara mendefenisikan Stack dengan Array of Struct yaitu: 1. Definisikan Stack dengan menggunakan struct 2. Definisikan konstanta MAX_STACK untuk menyimpan maksimum isi stack 3. Buatlah variabel array data sebagai implementasi stack 4. Deklarasikan operasi-operasi/function di atas dan buat implemetasinya.



contoh : //Deklarasi MAX_STACK #define MAX_STACK 10 //Deklarasi STACK dengan struct dan array data typedef struct STACK{ int top; char data[10][10]; }; //Deklarasi/buat variabel dari struct STACK tumpuk;



Inisialisasi Stack, pada mulanya isi top dengan -1, karena array dalam C dimulai dari 0, yang berarti stack adalah kosong. Top adalah suatu variabel penanda dalam STACK yang menunjukkan elemen teratas Stack sekarang. Top Of Stack akan selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack penuh.



Ilustrasi Stack pada saat inisialisasi



IsFull berfungsi untuk memeriksa apakah stack sudah penuh atau tidak. Dengan cara, memeriksa top of stack, jika sudah sama dengan MAX_STACK-1 maka full, jika belum (masih lebih kecil dari MAX_STACK-1) maka belum full.



Ilustrasi Stack pada kondisi Full



IsEmpty berfungsi untuk memeriksa apakah stack masih kosong atau tidak. Dengan cara memeriksa top of stack, jika masih -1 maka berarti stack masih kosong.



Push berfungsi untuk memasukkan elemen ke stack, selalu menjadi elemen teratas stack (yang ditunjuk oleh TOS). Tambah satu (increment) nilai top of stack lebih dahulu setiap kali ada penambahan elemen stack. Asalkan stack masih belum penuh, isikan data baru ke stack berdasarkan indeks top of stack setelah diincrement sebelumnya.



Pop berfungsi untuk mengambil elemen teratas (data yang ditunjuk oleh TOS) dari stack. Ambil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan dipop, baru dilakukan decrement nilai top of stack sehingga jumlah elemen stack berkurang.



Print berfungsi untuk menampilkan semua elemen-elemen stack dengan cara looping semua nilai array secara terbalik, karena kita harus mengakses dari indeks array tertinggi terlebih dahulu baru ke indeks yang kecil.



Operasi Push void Push (NOD **T, char item) { NOD *n; n=NodBaru (item); n->next=*T; *T=n;



}



Operasi Pop char Pop (NOD **T) { NOD *n; char item; if (!StackKosong(*T)) { P=*T; *T=(*T)->next; item=P->data; free(P); } return item; }



create berfungsi untuk membuat sebuah stack baru yang masih kosong. spesifikasi: tujuan : mendefinisikan stack yang kosong input : stack syarat awal : tidak ada output stack : - (kosong) syarat akhir : stack dalam keadaan kosong



C.Queue/Antrian Queue atau antrian, struktur data antrean atau queue adalah suatu bentuk khusus dari linear list, dengan operasi penyisipan (insertion) hanya diperbolehkan pada salah satu sisi, yang disebut sisi belakang (REAR), dan operasi penghapusan (deletion) hanya diperbolehkan pada sisi lainnya, yang disebut sisi depan (FRONT), dari list.



Sebagai contoh dapat kita lihat antrean (Q1, Q2,...,QN). Kita notasikan bagian depan dari antrean Q sebagai FRONT(Q) dan bagian belakang sebagai REAR(Q). Jadi untuk antrean Q = [Q1, Q2, …, QN] : FRONT(Q) = Q1 dan REAR(Q) = QN



Kita menggunakan notasi NOEL(Q) untuk menyatakan jumlah elemen di dalam antrean Q. NOEL(Q) mempunyai harga integer. Untuk antrean Q = [Q1,Q2,…, QN], maka NOEL(Q) = N. Operator penyisipan (insertion) disebut INSERT dan operator penghapusan (deletion) disebut REMOVE. Sebagai contoh untuk memperjelas bekerjanya antrean, kita perhatikan sederetan operasi berikut ini. Kita mulai dengan antrean hampa Q. Antrean hampa Q, atau Q[ ] dapat disajikan seperti terlihat pada Gambar 4-1 ------------------------------------



------------------------------------



Gambar 4.1. Antrean hampa Di sini : NOEL(Q) = 0 FRONT(Q) = tidak terdefinisi REAR(Q) = tidak terdefinisi



Lalu kita INSERT elemen A, diperoleh Q = [A], seperti terlihat di Gambar 4.2.



1.



---- -------------



A 2.



---- -------------



Gambar 4.2. Elemen A dimasukkan Di sini : NOEL(Q) = 1 FRONT(Q) = A REAR(Q) = A Dilanjutkan dengan INSERT elemen B, sehingga diperoleh Q = [A, B], seperti terlihat di Gambar 4-3. 4.



---- -------------



AB 5.



---- -------------



Gambar 4.3. Elemen B dimasukkan setelah elemen A



Di sini :



NOEL(Q) = 2 FRONT(Q) = A REAR(Q) = B



Dilanjutkan dengan INSERT elemen C, sehingga diperoleh Q = [A, B, C], seperti terlihat di Gambar 4.4. ------------ABC -------------



Gambar 4.4. Elemen C dimasukkan setelah elemen B



Di sini : NOEL(Q) = 3 FRONT(Q) = A REAR(Q) = C



Dilanjutkan dengan DELETE satu elemen dari Q, sehingga diperoleh Q = [B, C], seperti terlihat di Gambar 4.5. ------------BC -------------



Gambar 4.5. Satu elemen dihapus Di sini : NOEL(Q) = 2 FRONT(Q) = B REAR(Q) = C



Demikian seterusnya, kita dapat melakukan serangkaian INSERT dan DELETE yang lain. Suatu kesalahan underflow dapat terjadi, yakni apabila kita melakukan penghapusan pada antrean hampa. Antrean dikatakan beroperasi dalam cara FIRST-IN-FIRST-OUT (FIFO). Disebut demikian karena elemen yang pertama masuk merupakan elemen yang pertama ke luar. Model antrean, sangat sering ditemukan dalam kejadian sehari-hari, seperti mobil yang menunggu untuk pengisian bahan bakar, mobil pertama dari antrean merupakan mobil pertama yang akan keluar dari antrean. Sebagai contoh lain adalah orang yang menunggu dalam antrean di suatu bank. Orang pertama yang berada di dalam barisan tersebut akan merupakan orang pertama yang akan dilayani.



OPERASI DASAR PADA ANTREAN Ada 4 operasi dasar yang dapat dilakukan pada struktur data antrean, yakni : 1. CREATE (antrean) 2. ISEMPTY (antrean) 3. INSERT (elemen,antrean) 4. REMOVE (antrean) Pandang misalnya antrean Q = [Q1, Q2, …, QNOEL], maka :



CREATE (antrean) : CREATE(Q) adalah suatu operator untuk membentuk dan menunjukkan suatu antrean hampa Q. Berarti : NOEL(CREATE(Q)) = 0 FRONT(CREATE(Q)) = tidak terdefinisi REAR(CREATE(Q)) = tidak terdefinisi ISEMPTY(antrean) ISEMPTY(Q) adalah operator yang menentukan apakah antrean Q hampa atau tidak. Operand dari operator ini merupakan antrean, sedangkan hasilnya merupakan tipe data boolean.



Di sini : ISEMPTY(antrean) = true, jika Q hampa, yakni jika NOEL(Q)=0 = false, dalam hal lain. Maka, ISEMPTY(CREATE(Q)) = true.



INSERT(elemen, antrean) INSERT(E,Q) adalah operator yang memasukkan elemen E ke dalam antrean Q. Elemen E panjang.



REAR(INSERT(E,Q)) = E QNOEL adalah E ISEMPTY(INSERT(E,Q)) = false



REMOVE(antrean) REMOVE(Q) adalah operator yang menghapus elemen bagian depan dari Antrean Q. Hasilnya merupakan antrean yang lebih pendek. Pada setiap operasi ini, harga dari NOEL(Q)



berkurang satu, dan elemen kedua dari Q menjadi elemen terdepan. Jika NOEL(Q) = 0, maka REMOVE(Q) memberikan suatu kondisi error, yakni suatu underflow. Jelas bahwa REMOVE(CREATE(Q)) juga memberikan kondisi underflow error.



PENYAJIAN DARI ANTREAN Antrean dapat disajikan di dalam komputer dalam berbagai cara. Biasanya dengan menggunakan one-way-list (linear linked list) ataupun menggunakan array. Kalau tidak disebutkan lain, maka antrean kita sajikan dalam array QUEUE, dengan dilengkapi dua variabel penunjuk. FRONT, berisi lokasi dari elemen DEPAN antrean dan REAR, berisi lokasi dari elemen BELAKANG antrean. Nilai FRONT = NULL menunjukkan bahwa antrean adalah hampa.



Gambar 4.6 menunjukkan bagaimana menyajikan suatu antrean dalam sebuah array QUEUE dengan N elemen. Gambar itu juga menunjukkan bagaimana melakukan pemasukan dan penghapusan elemen antrean.



Pada Gambar 4.6(a) terlihat bahwa antrean mula-mula terdiri atas elemen AAA (sebagai DEPAN), BBB, CCC, dan DDD (sebagai BELAKANG) . Gambar 4.6.(b) menunjukkan keadaan setelah penghapusan elemen. Di sini elemen DEPAN yakni AAA dihapus. Gambar 4.6.(c) menggambarkan keadaan setelah penambahan berturut-turut elemen EEE dan FFF. Terakhir sekali, keadaan setelah penghapusan elemen DEPAN, BBB.



Gambar 4.6. Cara kerja antrean



Dapat kita lihat bahwa pada setiap kali penghapusan, nilai lokasi FRONT akan bertambah 1. Untuk setiap kali pemasukan elemen, nilai REAR akan bertambah 1. Hal ini berakibat bahwa setelah pemasukan elemen ke N (berawal dari antrean hampa), maka lokasi QUEUE(N) telah diduduki. Di sini mungkin saja tidak sebanyak N elemen ada dalam antrean (karena sudah dilakukan beberapa penghapusan).



Untuk melakukan pemasukan berikutnya, yakni memasukkan elemen ITEM, kita dapat menggunakan lokasi QUEUE(1). Demikian seterusnya. Dalam hal ini, kita menggunakan array sirkular, yakni bahwa QUEUE(1) datang sesudah QUEUE(N) di array dalam. Berdasarkan asumsi ini, maka REAR adalah 1. Secara yang sama, jika FRONT = N dan kita akan melakukan penghapusan, maka sekarang FRONT adalah 1, bukan N+l.



Gambar 4.7 memperlihatkan antrean yang disimpan dalam array dengan 5 lokasi memori, sebagai array sirkular.



Gambar 4.7. Circular Array



Sekarang kita akan menampilkan algoritma QINSERT, yang dimaksudkan untuk memasukkan data ke dalam suatu antrean. Yang mula-mula kita laksanakan dalam algoritma adalah, memeriksa kemungkinan terjadi overflow error, yakni dengan melihat apakah antrean tersebut terisi penuh. Algoritma kedua adalah algoritina QDELETE yang dimaksudkan untuk menghapus elemen DEPAN dari antrean.Yang mula-mula kita laksanakan ialah memeriksa kemungkinan terjadi underflow error, yakni dengan melihat apakah antrean tersebut kosong.



Algoritma QINSERT QINSERT(QUEUE, N, FRONT, DATA) 1. [Apakah antrean penuh] Jika FRONT := 1 dan REAR := N, atau jika FRONT := REAR + 1, maka write OVERFLOW, return. 2. Jika FRONT := NULL, maka FRONT := 1 REAR := 1 dalam hal lain jika REAR := N, maka REAR := 1 dalam hal lain REAR := REAR + 1 3. QUEUE(REAR) := DATA (masukkan elemen baru) 4. Return



Algoritma QDELETE QDELETE (QUEUE, N, FRONT, REAR, DATA) 1. [Apakah antrean kosong] Jika FRONT := NULL, maka Write : UNDERFLOW, return 2. DATA := QUEUE(FRONT) 3. FRONT mendapat nilai baru). Jika FRONT := REAR, maka (antrean memuat hanya 1 elemen) FRONT := NULL. REAR := NULL, dalam hal lain Jika FRONT := N, maka FRONT := 1, dalam hal lain : FRONT := FRONT+1 4. Return



DEQUE Kali ini akan kita bicarakan beberapa struktur data yang merupakan bentuk variasi dari struktur data antrean atau queue, yang telah kita bicarakan terdahulu. Struktur data tersebut adalah deque (atau deck atau dequeue) dan Antrean berprioritas (atau priority queue). DEQUE adalah suatu linear list atau daftar linear, yang penambahan dan penghapusan elemennya dapat dilakukan pada kedua sisi ujung list, tetapi tidak dapat dilakukan di tengah-tengah list. Dari sini, kita boleh mengatakan bahwa deque adalah suatu queue ganda atau double queue. Ada banyak cara penyajian suatu deque di dalam komputer. Namun yang biasa digunakan adalah penyajian dengan cara penempatan di dalam sebuah array sirkular atau array putar DEQUE. Di sini kita menggunakan dua pointer atau penunjuk, LEFT dan RIGHT, yang berturut-turut menunjuk pada sisi kiri dan sisi kanan dari deque. Kita senantiasa mengasumsikan bahwa elemen deque berurut dari kiri ke kanan. Pengertian sirkular di atas timbul karena elemen DEQUE(l) berada sesudah elemen DEQUE(N) dari array.



Gambar 4.8 menggambarkan 2 buah deque, masing-masing berisi 4 elemen, yang ditempatkan di dalam sebuah array dengan 8 lokasi memori. Kondisi LEFT = NULL dipergunakan untuk menyatakan bahwa suatu deque adalah hampa. Selain deque dengan sifat yang telah kita sebutkan di atas, masih ada 2 model variasi deque. Kedua variasi tersebut adalah deque input terbatas, dan deque output terbatas, yang merupakan tengah-tengah antara deque dan antrean. Deque input terbatas adalah suatu deque yang membatasi pemasukan elemen hanya pada satu ujung dari list, sementara penghapusan elemen boleh dilakukan pada kedua ujung list. Deque output terbatas adalah suatu deque yang hanya memperbolehkan penghapusan elemen pada salah satu ujung, tetapi memperbolehkan pemasukan elemen pada kedua ujung list. DEQUE



LEFT : 4 RIGHT : 6 1



2



AAA



BBB



CCC



DDD



4



5



6



7



3



(a)



8



DEQUE LEFT : 7 RIGHT : 2



YYY



ZZZ



1



2



3



4



5



6



WWW



XXX



7



8



Gambar 4.8. Deque



Sama halnya dengan antrean, komplikasi dapat timbul dalam pemrosesan deque, yakni apabila (a) terjadi overflow, yakni pada saat suatu elemen dimasukkan ke dalam deque yang sudah berisi penuh, dan (b) terjadi underflow, yakni bila suatu elemen harus dihapus dari deque yang sudah hampa.



ANTREAN BERPRIORITAS Sekarang kita bahas mengenai antrean berprioritas antrean berprioritas adalah himpunan elemen, yang setiap elemennya telah diberikan sebuah prioritas, dan urutan proses penghapusan elemen adalah berdasarkan aturan berikut : 1. Elemen yang prioritasnya lebih tinggi, diproses lebih dahulu dibandingkan dengan elemen yang prioritasnya lebih rendah. 2. Dua elemen dengan prioritas yang sama, diproses sesuai dengan urutan mereka sewaktu dimasukkan ke dalam priority queue.



Suatu prototipe dari antrean berprioritas adalah sistem time sharing. Di sini pro-gram dengan prioritas yang lebih tinggi diproses terlebih dahulu, dan sejumlah program dengan prioritas yang sama akan membentuk queue yang standar. Ada bermacam-macam cara penyimpanan antrean berprioritas di dalam memori. Kita akan membahas dua di antaranya, yakni yang pertama kita pergunakan cara penyimpanan dalam one-way list, dan yang kedua dengan cara penyimpanan dalam multiple queue. Kemudahan dan kesulitan di dalam operasi penambahan ataupun penghapusan elemen, pada antrean berprioritas, akan tergantung pada penyajian mana yang akan dipilih.



PENYAJIAN ONE-WAY LIST DARI ANTREAN BERPRIO-RITAS Satu cara untuk menyimpan antrean berprioritas dalam memori adalah dengan menggunakan one-way list, dengan ketentuan seperti berikut ini : 1. Setiap simpul dalam list akan berisi 3 buah data atau field, yakni field informasi yang biasa disebut INFO, Nomor prioritas (priority number) disebut PRN, dan nomor link, disebut LINK. 2. Simpul X mendahului simpul Y di dalam list :



1) bila X mempunyai prioritas yang lebih tinggi dari pada Y 2) bila keduanya mempunyai prioritas yang sama, tetapi X dimasukkan ke dalam queue terlebih dahulu sebelum Y.



Ini berarti bahwa urutan pada one-way list adalah berkorespondensi dengan urutan pada antrean berprioritas. Priority number akan beroperasi seperti cara yang biasa dipakai, yakni simpul dengan priority number terendah, akan mendapat prioritas yang tertinggi. Sebagai contoh, perhatikan Gambar 4.9 yang memperlihatkan diagram skematik dari antrean berprioritas dengan 7 elemen. Diagram tidak dapat menceritakan kepada kita apakah BBB dimasukkan ke dalam list sebelum atau sesudah DDD. Di lain pihak, diagram dapat memperlihatkan kepada kita, bahwa BBB dimasukkan sebelum CCC, karena BBB dan CCC mempunyai priority number yang sama dan BBB berada sebelum CCC di dalam list. Pada Gambar 4.10 diperlihatkan bagaimana cara antrean berprioritas muncul dalam memori, dengan menggunakan array INFO, PRN, dan LINK. Sifat utama dari penyajian one-way list dari sebuah antrean berprioritas adalah bahwa elemen dalam antrean yang seharusnya diproses pertama kali selalu muncul pada bagian permulaan one-way list . Oleh karena itu, adalah sangat sederhana untuk menghilangkan dan memproses sebuah elemen antrean prioritas kita tersebut. ST A R T



IN F O



PRN



AAA



1



L IN K



BBB



DDD



4



2



CCC



EEE



4



2



X



Gambar 4.9. Antrean berprioritas



Algoritmanya adalah sebagai berikut : Algoritma 1 Algoritma ini bekerja untuk menghapus dan memproses elemen pertama dalam sebuah antrean berprioritas yang muncul dalam memori sebagai sebuah one-way list. 1. Pasang ITEM := INFO(START). (Langkah ini dimaksudkan untuk menyimpan data dalam simpul pertama) 2. Hapus simpul pertama dari list. 3. Proses ITEM



4. Keluar



1



START



INFO



PRN



LINK



BBB



2



6



2



10



5



AVAI



3



DDD



4



4



4



EEE



4



0



5



AAA



1



1



6



CCC



2



3



L



9 7



8



8



0



9



2



10



7



Gambar 4.10. Pemetaan antrean berprioritas di memori



Silakan anda merinci algoritma di atas, lengkap dengan kemungkinan terjadinya underflow. Menambah suatu elemen pada antrean berprioritas kita adalah jauh lebih rumit dibandingkan dengan proses menghapus sebuah elemen dari antrean, karena kita harus



menemukan tempat yang benar untuk menyisipkan elemen itu. Algoritma ini bekerja untuk menambahkan sebuah ITEM dengan nomor prioritas N, pada suatu antrean berprioritas yang disimpan dalam memori sebagai sebuah one-way list. a. Telusuri one-way list sampai ditemukan suatu simpul X yang nomor prioritasnya melebihi N. Sisipkan ITEM di depan simpul X b. Jika tidak ditemukan simpul semacam itu, sisipkan ITEM sebagai elemen terakhir list.



Kesulitan utama dalam algoritma muncul dari kenyataan bahwa ITEM disisipkan sebelum simpul X. Hal ini berarti bahwa ketika menelusuri list itu, seseorang harus tetap memperhatikan alamat simpul yang mendahului simpul yang sedang diakses.



STAR T



XXX



AAA 1



BBB



2



EEE



CCC 2



4



FFF



2



DDD 4



4



GGG 5 X



Gambar 4.11. Penyisipan pada antrean berprioritas



Sebagai contoh, perhatikan kembali antrean berprioritas pada Gambar 4.9. Misal-kan item XXX dengan nomor prioritas 2, akan dimasukkan ke dalam antrean. Kita telusuri list, sambil membandingkan nomor prioritas. Perhatikan bahwa elemen DDD merupakan elemen pertama di dalam list yang dijumpai mempunyai nomor prioritas lebih besar dari nomor prioritas XXX Karena itu, XXX dimasukkan ke dalam list di depan DDD, seperti terlihat pada Gambar 4-11. Dapat dilihat pula bahwa XXX datang sesudah BBB dan CCC, yang mempunyai nomor prioritas sama dengan XXX. Pandang sekarang kita akan menghapus elemen dari queue. Dalam hal ini AAA merupakan elemen pertama dari list akan terhapus. Pandang bahwa tidak ada lagi penyisipan elemen lain. Elemen berikutnya yang akan dihapus adalah BBB, lalu CCC, kemudian XXX dan seterusnya.



PENYAJIAN ARRAY DARI ANTREAN BERPRIORITAS



Cara lain untuk menyajikan suatu antrean berprioritas dalam memori adalah menggunakan suatu antrean terpisah untuk setiap tingkat prioritas (untuk setiap nomor prioritas). Setiap antrean semacam itu akan muncul dalam array sirkularnya sendiri dan harus mempunyai sepasang penunjuk sendiri, FRONT dan REAR. Kenyataannya, jika masingmasing antrean dialokasikan jumlah ruang yang sama, suatu array dua dimensi QUEUE dapat digunakan sebagai pengganti array. Gambar 4.12 menunjukkan repre-sentasi ini, untuk antrean berprioritas dalam Gambar 4.11, perhatikan bahwa FRONT(K) dan REAR(K) berisi masing-masing elemen depan dan belakang dari baris K array QUEUE, baris yang memuat antrean elemen yang bernomor prioritas K.



FRON T 1



REAR 2



2



1



2



3



4



5



6



1 AAA



2



1



3



2 BBB



3



0



0



3



4



5



1



4



CCC



XXX



FFF 5



4



4



DDD EEE



5 GGG



Gambar 4.12 Array dua dimensi QUEUE



Berikut ini garis besar algoritma untuk menghapus dan menyisipkan elemen pada suatu antrean berprioritas yang disimpan dalam memori oleh sebuah array dua dimensi QUEUE, seperti tersebut di atas.



Algoritma 3 Algoritma ini bekerja untuk menghapus dan memproses elemen pertama dalam sebuah antrean berprioritas yang disajikan oleh suatu array dua dimensi QUEUE. 1. (cari antrean tidak hampa yang pertama). Cari K terkecil, sedemikian sehingga FRONT(K) tidak sama dengan NULL. 2. Hapus dan proses elemen dari baris K QUEUE.



3. Keluar



Algoritma 4 Algoritma ini bekerja untuk menambah sebuah ITEM dengan nomor prioritas M pada suatu antrean berprioritas yang disajikan oleh sebuah array dua dimensi QUEUE.



1. Sisipkan ITEM sebagai elemen belakang dari baris M QUEUE. 2. Keluar



Jika kita ambil kesimpulan tentang baik buruknya masing-masing penyajian antrean berprioritas tersebut di atas, maka dapatlah dikatakan bahwa penyajian array adalah lebih efisien dari segi waktu dibandingkan dengan penyajian one-way list. Namun dari segi ruang yang dibutuhkan, penyajian one-way list adalah lebih efisien.



TAMBAHAN : MESIN ANTREAN Setelah kita bahas antrean dengan definisi dan teorinya, sekarang akan kita bahas suatu prosedur untuk pelaksanaan beberapa operasi terhadap antrean. Himpunan prosedur tersebut kita namakan “mesin antrean”.



Dalam pembahasan mesin antrean, kita menyediakan beberapa perintah dalam bentuk perintah huruf besar tunggal. Input dan output dari nilai yang akan dijalankan harus melalui suatu kode yang berupa perintah huruf besar tunggal. Petunjuk perintah dari mesin antrean adalah sebagai berikut : 



I adalah menyisipkan sebuah nilai ke dalam antrean.







D adalah menghapus nilai depan dari sebuah antrean.







F adalah menampilkan nilai depan dari sebuah antrean.







B adalah menentukan maksimum isi antrean.







C adalah mengosongkan antrean.







E adalah keluar.



Deklarasi untuk perintah mesin antrean TYPE TipeNilai = 0.. 99;



TipeAntrean = ARRAY [1..99] OF



INTEGER;



VAR nilaiMasuk



: TipeNilai;



Antrean



: TipeAntrean;



Batasan



: TipeNilai;



Depan



: TipeNilai;



Belakang



: TipeNilai;



Prosedur pemasukan sesuatu nilai :



PROCEDURE Sekarang (VAR Op:CHAR; VAR NilaiMasuk:TipeNilai); BEGIN NilaiMasuk :=0; Read(Op); WHILE NOT (Op IN [‘I’,’D’,’F’,’B’,’C’,’E’]) DO



Read(Op); IF (Op := ‘I’) THEN Readln(NilaiMasuk); IF (Op :=’B’) THEN Readln(NilaiMasuk)



PENYISIPAN SEBUAH NILAI KE DALAM ANTREAN Maksud dari operasi ini adalah untuk menyisipkan sebuah nilai ke dalam antrean. Sebelum menyisipkan sebuah nilai, maka harus diketahui dahulu batas maksimumnya dengan menggunakan perintah huruf besar tunggal B. Sebagai contoh dalam suatu antrean akan diisi nilai 1,2,3,4,5 dengan menggunakan perintah huruf besar tunggal I. Sebelum mengisi nilai harus diketahui dahulu batas maksimumnya, misal batas maksimum di sini adalah 5 dengan menggunakan perintah huruf besar tunggal B. Hasilnya akan terlihat dengan menggunakan perintah huruf tunggal F, maka hasilnya adalah 1,2,3,4,5. Jika nilai antrean yang disisipkan lebih besar dari batas maksimumnya, maka nilai yang ditentukan tadi tidak akan keluar, di situ akan terlihat bahwa “antrean telah penuh,” dengan demikian kita harus mencoba perintah yang lain. PROCEDURE Penyisipan(NilaiMasuk : TipeNilai); PROCEDURE



PerubahanQ(Antrean : TipeAntrean); VAR k : INTEGER; BEGIN IF (Depan > 0) THEN BEGIN FOR k := 1 TO (Belakang – Depan) DO Antrean[k] := Antrean[Depan+k]; Belakang := Belakang; Depan := 0 END



END (PerubahanQ); BEGIN IF (Belakang > Batasan) THEN BEGIN Perubahan(Antrean) END;



IF (Belakang >= Batasan) THEN



BEGIN Writeln('Antrean penuh, coba perintah yang lain.'); Writeln(‘Tekan B untuk batas maksimum isi



Antrean(0 ... 99)') END ELSE



BEGIN Belakang := Belakang + 1; Antrean[Belakang] := NilaiMasuk END



END [Penyisipan];



MENGHAPUS NILAI DEPAN DARI SEBUAH ANTREAN Selain menyisipkan sebuah nilai ke dalam antrean, antrean juga perlu dihapus. Untuk menghapus sebuah nilai antrean yakni dengan menggunakan perintah huruf besar tunggal D. Pada operasi ini akan ditentukan jika kita ingin menghapus sebuah nilai yang telah disisipkan. Dalam hal ini yang akan dihapus adalah nilai depan dari suatu antrean. Sebagai contoh dalam suatu antrean yang mempunyai nilai 1,2,3,4,5 dengan menggunakan perintah huruf besar tunggal I, maka nilai yang terhapus adalah nilai I dengan menggunakan perintah huruf besar tunggal D. Akan terlihat hasilnya dengan menggunakan perintah huruf besar tunggal F menjadi 2,3,4,5.



Perlu kita diketahui, jika dalam suatu antrean yang akan dihapus tidak ada nilainya, maka akan terlihat hasilnya ''Antrean kosong'', seperti terlihat pada procedure di bawah ini. PROCEDURE Penghapusan(Antrean : TipeAntrean); BEGIN IF Kosong(Antrean) THEN Writeln('Antrean kosong, coba perintah lain') ELSE BEGIN



Depan := Depan + 1; IF (Depan := Belakang)



THEN BEGIN Depan := 0; Belakang :=0 END



END [Penghapusan];



MENAMPILKAN NILAI DEPAN DARI SEBUAH ANTREAN Operasi ini merupakan suatu operasi yang khusus menampilkan sesuatu nilai. Pada dasarnya operasi ini hanya merupakan sebagai tampilan, khususnya menampilkan nilai depan dari sebuah antrean. Nilai -nilai yang telah dihasilkan merupakan nilai-nilai seperti terlihat pada contoh di atas yakni pada penggunaan perintah-perintah huruf besar tunggal I, D, B dan C. Perintah huruf besar tunggal C merupakan perintah yang fungsinya hanya untuk mengosongkan antrean. Jika antrean yang dijalankan tidak menghasilkan suatu nilai, maka hasilnya akan terlihat menjadi ''Antrean kosong''



PROCEDURE Tampilan(DepanTipeNilai); VAR k TipeNilai; BEGIN Writeln; IF Kosong(Antrean) THEN Writeln('Antrean kosong.') ELSE Writeln('Nilai depan adalah', Antrean[Depan+l]:3); Writeln END [Tampilan];



D.Sub Routine Subroutine adalah bagian dari kode dalam program yang lebih besar yang biasanya melakukan sesuatu yang sangat spesifik, dan yang dapat dipanggil dari mana saja dalam program. Subrutin yang diidentifikasi dengan nama yang mengikuti kata kunci Sub dan diakhiri oleh kata kunci EndSub. Misalnya, potongan berikut merupakan subrutin yang namanya PrintTime, dan melakukan pekerjaan mencetak waktu saat ini untuk TextWindow tersebut. sub PrintTime TextWindow.WriteLine (Clock.Time) EndSub Di bawah ini adalah program yang meliputi subroutine dan menyebutnya dari berbagai tempat. 1PrintTime () 2TextWindow.Write ("Masukkan nama Anda:") 3name = TextWindow.Read () 4TextWindow.Write (nama + ", waktu sekarang adalah:")



5PrintTime () 6 7sub PrintTime 8TextWindow.WriteLine (Clock.Time) 9EndSub Anda menjalankan subrutin dengan memanggil SubroutineName (). Seperti biasa, para punctuators “()” yang diperlukan untuk memberitahu komputer yang Anda ingin mengeksekusi sebuah sub rutin. Keuntungan menggunakan Subrutin. Seperti kita hanya melihat di atas, subrutin membantu mengurangi jumlah kode Anda harus mengetik masuk Setelah Anda memiliki subroutine PrintTime ditulis, Anda dapat menyebutnya dari mana saja dalam program Anda dan akan mencetak waktu saat ini. Catatan: Ingat, Anda hanya dapat memanggil subroutine SmallBasic dari dalam program yang sama. Anda tidak dapat memanggil subrutin dari dalam program lain. Selain itu, subrutin dapat membantu masalah yang kompleks terurai menjadi potongan-potongan sederhana. Katakanlah Anda memiliki persamaan yang kompleks untuk menyelesaikan, Anda dapat menulis beberapa subrutin yang memecahkan potongan-potongan kecil dari persamaan yang kompleks. Kemudian Anda dapat menempatkan hasil bersamasama untuk mendapatkan solusi untuk persamaan yang kompleks yang asli. Subrutin juga dapat membantu dalam meningkatkan pembacaan program. Dengan kata lain, jika Anda telah baik bernama subrutin untuk bagian umum menjalankan program Anda, program anda menjadi mudah untuk membaca dan memahami. Hal ini sangat penting jika Anda ingin memahami program orang lain atau jika Anda ingin membuat program untuk dimengerti oleh orang lain. Kadang-kadang, akan sangat membantu bahkan ketika Anda ingin membaca program Anda sendiri, katakanlah seminggu setelah anda menulisnya menggunakan variabel, anda dapat mengakses dan menggunakan variabel yang anda miliki dalam sebuah program dari dalam subrutin. Sebagai contoh, program berikut menerima dua angka dan mencetak lebih besar dari dua. Perhatikan bahwa max variabel yang digunakan baik di dalam maupun di luar subroutine. TextWindow.Write ("Masukkan angka pertama:") num1 = TextWindow.ReadNumber () TextWindow.Write ("Masukkan angka kedua:") num2 = TextWindow.ReadNumber ()



FindMax () TextWindow.WriteLine ("Jumlah maksimum adalah:" + max) sub FindMax Jika (num1> num2) Lalu max = num1 lain max = num2 Endif EndSub Mari kita lihat contoh lain yang akan menggambarkan penggunaan Subrutin. Kali ini kita akan menggunakan program grafis yang menghitung berbagai titik yang akan menyimpan dalam variabel x dan y. Kemudian panggilan DrawCircleUsingCenter subrutin yang bertanggung jawab untuk menggambar sebuah lingkaran menggunakan x dan y sebagai pusat. 1 GraphicsWindow.BackgroundColor = "Black" 2 GraphicsWindow.PenColor = "lightblue" 3 GraphicsWindow.Width = 480 4 Untuk i = 0 Langkah Untuk 6,4 0,17 5 x = Math.Sin (i) * 100 + 200 6 y = Math.Cos (i) * 100 + 200 7 8 DrawCircleUsingCenter () 9 Endfor 10 11Sub DrawCircleUsingCenter 12startx = x - 40 13startY = y - 40 14 15GraphicsWindow.DrawEllipse (startx, startY, 120, 120) 16EndSub



Memanggil subrutin dalam Loops. Kadang-kadang subrutin dipanggil dari dalam lingkaran, selama waktu mereka mengeksekusi set yang sama tetapi dengan pernyataan nilai yang berbeda dalam satu atau lebih variabel. Misalnya, mengatakan jika Anda memiliki



subrutin bernama PrimeCheck dan subrutin ini menentukan apakah nomor perdana atau tidak. Anda dapat menulis sebuah program yang memungkinkan pengguna untuk memasukkan nilai dan Anda kemudian dapat mengatakan jika Perdana atau tidak, menggunakan subrutin ini. Program di bawah ini menggambarkan bahwa. 1 TextWindow.Write ("Masukkan nomor:") 2 i = TextWindow.ReadNumber () 3 isPrime = "Benar" 4 PrimeCheck () 5 Jika (isPrime = "Benar") Lalu 6 TextWindow.WriteLine (i + "adalah bilangan prima") 7 Lain 8 TextWindow.WriteLine (i + "bukan merupakan bilangan prima") 9 Endif 10 11Sub PrimeCheck 12Untuk j = 2 Untuk Math.SquareRoot (i) 13Jika (Math.Remainder (i, j) = 0) Kemudian 14isPrime = "False" 15Goto EndLoop 16Endif 17Endfor 18EndLoop: 19EndSub Subrutin PrimeCheck mengambil nilai i dan mencoba untuk membagi dengan jumlah yang lebih kecil. Jika nomor membagi i dan meninggalkan sisanya tidak ada, maka saya bukanlah bilangan prima. Pada saat itu subrutin menetapkan nilai isPrime menjadi “False” dan keluar. Jika jumlah itu dibagi dengan angka yang lebih kecil maka nilai isPrime tetap sebagai “Benar.” Sekarang bahwa Anda memiliki subrutin yang dapat melakukan tes Perdana bagi kami, Anda mungkin ingin menggunakan ini untuk daftar semua bilangan prima di bawah ini, katakanlah, 100. Hal ini sangat mudah untuk memodifikasi program di atas dan membuat panggilan ke PrimeCheck dari dalam lingkaran. Ini memberikan subrutin nilai yang berbeda untuk menghitung setiap kali loop dijalankan. Mari kita lihat bagaimana hal ini dilakukan dengan contoh di bawah ini.



1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17



untuk i = 3 Untuk 100 isPrime = "Benar" PrimeCheck () Jika (isPrime = "Benar") Lalu TextWindow.WriteLine (i) Endif Endfor Sub PrimeCheck Untuk j = 2 Untuk Math.SquareRoot (i) Jika (Math.Remainder (i, j) = 0) Kemudian isPrime = "False" Goto EndLoop Endif Endfor EndLoop:EndSub



Dalam program di atas, nilai i diperbarui setiap kali loop dijalankan. Di dalam loop, panggilan ke PrimeCheck subroutine dibuat. The PrimeCheck subroutine kemudian mengambil nilai i dan menghitung apakah atau tidak saya adalah bilangan prima. Hasil ini disimpan dalam isPrime variabel yang kemudian diakses oleh lingkaran luar subrutin. Nilai i kemudian dicetak jika ternyata menjadi bilangan prima. Dan karena loop dimulai dari 3 dan naik ke 100, kita mendapatkan daftar semua bilangan prima yang antara 3 dan 100. Di bawah ini adalah hasil dari program.



E. Set Intruksi Set instruksi (instruction set) adalah sekumpulan lengkap instruksi yang dapat di mengerti oleh sebuah CPU, set instruksi sering juga disebut sebagai bahasa mesin (machine code), karna aslinya juga berbentuk biner kemudian dimengerti sebagai bahasa assembly, untuk konsumsi manusia (programmer), biasanya digunakan representasi yang lebih mudah dimengerti oleh manusia. Sebuah instruksi terdiri dari sebuah opcode, biasanya bersama dengan beberapa informasi tambahan seperti darimana asal operand-operand dan kemana hasil-hasil akan



ditempatkan. Subyek umum untuk menspesifikasikan di mana operand-operand berada (yaitu, alamat-alamatnya) disebut pengalamatan Pada beberapa mesin, semua instruksi memiliki panjang yang sama, pada mesinmesin yang lain mungkin terdapat banyak panjang berbeda. Instruksi-instruksi mungkin lebih pendek dari, memiliki panjang yang sama seperti, atau lebih panjang dari panjang word. Membuat semua instruksi memiliki panjang yang sama lebih muda dilakukan dan membuat pengkodean lebih mudah tetapi sering memboroskan ruang, karena semua instruksi dengan demikian harus sama panjang seperti instruksi yang paling panjang. Di dalam sebuah instruksi terdapat beberapa elemen-elemen instruksi: 1. Operation code (op code) 2. Source operand reference 3. Result operand reference 4. Next instruction preference



Format instruksi (biner): Missal instruksi dengan 2 alamat operand : ADD A,B A dan B adalah suatu alamat register. Beberapa simbolik instruksi: ADD



: Add (jumlahkan)



SUB



: Subtract (Kurangkan)



MPY/MUL



: Multiply (Kalikan)



DIV



: Divide (Bagi)



LOAD



: Load data dari register/memory



STOR



: Simpan data ke register/memory



MOVE



: pindahkan data dari satu tempat ke tempat lain



SHR



: shift kanan data



SHL



: shift kiri data .dan lain-lain



Cakupan jenis instruksi: Data processing dsb);



: Aritmetik (ADD, SUB, dsb); Logic (AND, OR, NOT,



SHR,



konversidata



Data storage (memory) : Transfer data (STOR, LOAD, MOVE, dsb) Data movement



: Input dan Output ke modul I/O



Program flow control



: JUMP, HALT, dsb.



Bentuk instruksi: –



Format instruksi 3 alamat



Mempunyai bentuk umum seperti : [OPCODE][AH],[AO1],[AO2]. Terdiri dari satu alamt hasil, dan dua alamat operand, misal SUB Y,A,B Yang mempunyai arti dalam bentuk algoritmik : Y := A – B dan arti dalam bentuk penjelasan : kurangkan isi reg a dengan isi reg B, kemudian simpan hasilnya di reg Y. bentuk bentuk pada format ini tidak umum digunakan di dalam computer, tetapi tidak dimungkinkan ada pengunaanya, dalam peongoprasianya banyak register sekaligus dan program lebih pendek. Contoh: A, B, C, D, E, T, Y adalah register Program: Y = (A – B) / ( C + D × E) SUB Y, A, B



Y := A – B



MPY T, D, E



T := D × E



ADD T, T, C



T := T + C



DIV Y, Y, T



Y:= Y / T



Memerlukan 4 operasi



–



Format instruksi 2 alamat



Mempunyai bentuk umum : [OPCODE][AH],[AO]. Terdiri dari satu alamat hasil merangkap operand, satu alamat operand, missal : SUB Y,B yang mempunyai arti dalam algoritmik : Y:= Y – B dan arti dalam bentuk penjelasan : kurangkan isi reg Y dengan isi reg B, kemudian simpan hasillnya di reg Y. bentuk bentuk format ini masih digunakan di computer sekarang, untuk mengoprasikan lebih sedikit register, tapi panjang program tidak bertambah terlalu banyak. Contoh : A, B, C, D, E, T, Y adalah register Program: Y = (A – B) / ( C + D × E) MOVE Y, A



Y := A



SUB Y, B



Y := Y – B



MOVE T, D



T := D



MPY T, E



T := T × E



ADD T, C



T := T + C



DIV Y, T



Y:= Y / T



Memerlukan 6 operasi –



Format instruksi 1 alamat



Mempunyai bentuk umum : [OPCODE][AO]. Terdiri dari satu alamat operand, hasil disimpan di accumulator, missal : SUB B yang mempunyai arti dalam algoritmik : AC:= AC – B dan arti dalam bentuk penjelasan : kurangkan isi Acc dengan isi reg B, kemudian simpan hasillnya di reg Acc. bentuk bentuk format ini masih digunakan di computer jaman dahulu, untuk mengoprasikan di perlukan satu register, tapi panjang program semakin bertambah. Contoh : A, B, C, D, E, Y adalah register Program: Y = (A – B) / ( C + D × E) LOAD D



AC := D



MPY E



AC := AC × E



ADD C



AC := AC + C



STOR Y



Y := AC



LOAD A



AC := A



SUB B



AC := AC – B



DIV Y



AC := AC / Y



STOR Y



Y := AC



Memerlukan 8 operasi –



Format instruksi 0 alamat



Mempunyai bentuk umum : [OPCODE]. Terdiri dari semua alamat operand implicit, disimpan dalam bentuk stack. Operasi yang biasanya membutuhkan 2 operand, akan mengambil isi stack paling atas dan dibawahnya missal : SUB yang mempunyai arti dalam algoritmik : S[top]:=S[top-1]-S[top] dan arti dalam bentuk penjelasan : kurangkan isi stack no2 dari atas dengan isi stack paling atas, kemudian simpan hasilnya di stack paling atas, untuk mengoprasikan ada beberapa instruksi khusus stack PUSH dan POP. Contoh : A, B, C, D, E, Y adalah register Program: Y = (A – B) / ( C + D × E) PUSH A



S[top] := A



PUSH B



S[top] := B



SUB



S[top] := A – B



PUSH C



S[top] := C



PUSH D



S[top] := D



PUSH E



S[top] := E



MPY



S[top] := D × E



ADD



S[top] := C + S[top]



DIV



S[top] := (A – B) /S[top]



POP Y



Out := S[top]



Memerlukan 10 operasi Set instruksi pada CISC: Berikut ini merupakan karakteristik set instruksi yang digunakan pada beberapa computer yang memiliki arsitektur CISC Perbandingan set instruksi Beberapa computer CISC (Complex Instruction Set Computer) menggunakan cara implist dalam menentukan mode addressing pada setiap set instruksinya. Penentuan mode addressing dengan cara implicit memiliki arti bahwa pada set instruksi tidak di ada bagian yang menyatakan tipe dari mode addressing yang digunakan, deklarasi dari mode addressing itu



berada menyatu dengan opcode. Lain hal nya dengan cara imsplisit, cara eksplisit sengaja menyediakan tempat pada set instruksi untuk mendeklarasikan tipe mode addressing. Pada cara eksplisit deklarasi opcode dan mode addressing berada terpisah. Data pada tempat deklarasi mode addressing diperoleh dari logaritma basis dua jumlah mode addressing. Jika deklarasi mode addressing dilakukan secara implicit akan menghemat tempat dalam set instruksi paling tidak satu bit untuk IBM 3090 dan 6 bit untuk MC68040. Perubahan satu bit pada set instruksi akan memberikan jangkauan alamat memori lebih luas mengingat range memori dinyatakan oleh bilangan berpangkat dua. ELEMEN-ELEMEN DARI INSTRUKSI MESIN (SET INSTRUKSI) * Operation Code (opcode) : menentukan operasi yang akan dilaksanakan * Source Operand Reference : merupakan input bagi operasi yang akan dilaksanakan * Result Operand Reference : merupakan hasil dari operasi yang dilaksanakan * Next instruction Reference : memberitahu CPU untuk mengambil (fetch) instruksi berikutnya setelah instruksi yang dijalankan selesai. Source dan result operands dapat berupa salah satu diantara tiga jenis berikut ini: 



Main or Virtual Memory







CPU Register







I/O Device



DESAIN SET INSTRUKSI Desain set instruksi merupakan masalah yang sangat komplek yang melibatkan banyak aspek, diantaranya adalah: 1. Kelengkapan set instruksi 2. Ortogonalitas (sifat independensi instruksi) 3. Kompatibilitas : – Source code compatibility – Object code Compatibility Selain ketiga aspek tersebut juga melibatkan hal-hal sebagai berikut: 1. Operation Repertoire: Berapa banyak dan operasi apa saja yang disediakan, dan berapa sulit operasinya 2. Data Types: tipe/jenis data yang dapat olah Instruction Format: panjangnya, banyaknya alamat, dsb.



3. Register:



Banyaknya



register



yang



dapat



digunakan



4.Addressing:



Mode



pengalamatan untuk operand FORMAT INSTRUKSI * Suatu instruksi terdiri dari beberapa field yang sesuai dengan elemen dalam instruksi tersebut. Layout dari suatu instruksi sering disebut sebagai Format Instruksi (Instruction Format). OPCODE



OPERAND



REFERENCE



OPERAND



REFERENCE



JENIS-JENIS



OPERAND * Addresses (akan dibahas pada addressing modes) * Numbers : – Integer or fixed point – Floating point – Decimal (BCD) * Characters : – ASCII – EBCDIC * Logical Data : Bila data berbentuk binary: 0 dan 1 JENIS INSTRUKSI * Data processing: Arithmetic dan Logic Instructions * Data storage: Memory instructions * Data Movement: I/O instructions * Control: Test and branch instructions TRANSFER DATA * Menetapkan lokasi operand sumber dan operand tujuan. * Lokasi-lokasi tersebut dapat berupa memori, register atau bagian paling atas daripada stack. * Menetapkan panjang data yang dipindahkan. * Menetapkan mode pengalamatan. * Tindakan CPU untuk melakukan transfer data adalah : a. Memindahkan data dari satu lokasi ke lokasi lain. b. Apabila memori dilibatkan : 1. Menetapkan alamat memori. 2. Menjalankan transformasi alamat memori virtual ke alamat memori aktual. 3. Mengawali pembacaan / penulisan memori Operasi set instruksi untuk transfer data : * MOVE : memindahkan word atau blok dari sumber ke tujuan * STORE : memindahkan word dari prosesor ke memori.



* LOAD : memindahkan word dari memori ke prosesor. * EXCHANGE : menukar isi sumber ke tujuan. * CLEAR / RESET : memindahkan word 0 ke tujuan. * SET : memindahkan word 1 ke tujuan. * PUSH : memindahkan word dari sumber ke bagian paling atas stack. * POP : memindahkan word dari bagian paling atas sumber ARITHMETIC Tindakan CPU untuk melakukan operasi arithmetic : 1. Transfer data sebelum atau sesudah. 2. Melakukan fungsi dalam ALU. 3. Menset kode-kode kondisi dan flag. Operasi set instruksi untuk arithmetic : 1. ADD : penjumlahan 5. ABSOLUTE 2. SUBTRACT : pengurangan 6. NEGATIVE 3. MULTIPLY : perkalian 7. DECREMENT 4. DIVIDE : pembagian 8. INCREMENT Nomor 5 sampai 8 merupakan instruksi operand tunggal. LOGICAL * Tindakan CPU sama dengan arithmetic * Operasi set instruksi untuk operasi logical : 1. AND, OR, NOT, EXOR 2. COMPARE : melakukan perbandingan logika. 3. TEST : menguji kondisi tertentu. 4. SHIFT : operand menggeser ke kiri atau kanan menyebabkan konstanta pada ujung bit. 5. ROTATE : operand menggeser ke kiri atau ke kanan dengan ujung yang terjalin. CONVERSI Tindakan CPU sama dengan arithmetic dan logical. * Instruksi yang mengubah format instruksi yang beroperasi terhadap format data. * Misalnya pengubahan bilangan desimal menjadi bilangan biner. * Operasi set instruksi untuk conversi : 1. TRANSLATE : menterjemahkan nilai-nilai dalam suatu bagian memori berdasrkan tabel korespodensi. 2. CONVERT : mengkonversi isi suatu word dari suatu bentuk ke bentuk lainnya.



INPUT / OUPUT * Tindakan CPU untuk melakukan INPUT /OUTPUT : 1. Apabila memory mapped I/O maka menentukan alamat memory mapped. 2. Mengawali perintah ke modul I/O * Operasi set instruksi Input / Ouput : 1. INPUT : memindahkan data dari pernagkat I/O tertentu ke tujuan 2. OUTPUT : memindahkan data dari sumber tertentu ke perangkat I/O 3. START I/O : memindahkan instruksi ke prosesor I/O untuk mengawali operasi I/O 4. TEST I/O : memindahkan informasi dari sistem I/O ke tujuan TRANSFER CONTROL * Tindakan CPU untuk transfer control : Mengupdate program counter untuk subrutin , call / return. * Operasi set instruksi untuk transfer control : 1. JUMP (cabang) : pemindahan tidak bersyarat dan memuat PC dengan alamat tertentu. 2. JUMP BERSYARAT : menguji persyaratan tertentu dan memuat PC dengan alamat tertentu atau tidak melakukan apa tergantung dari persyaratan. 3. JUMP SUBRUTIN : melompat ke alamat tertentu. 4. RETURN : mengganti isi PC dan register lainnya yang berasal dari lokasi tertentu. 5. EXECUTE : mengambil operand dari lokasi tertentu dan mengeksekusi sebagai instruksi 6. SKIP : menambah PC sehingga melompati instruksi berikutnya. 7. SKIP BERSYARAT : melompat atau tidak melakukan apa-apa berdasarkan pada persyaratan 8. HALT : menghentikan eksekusi program. 9. WAIT (HOLD) : melanjutkan eksekusi pada saat persyaratan dipenuhi 10. NO OPERATION : tidak ada operasi yang dilakukan. CONTROL SYSTEM * Hanya dapat dieksekusi ketika prosesor berada dalam keadaan khusus tertentu atau sedang mengeksekusi suatu program yang berada dalam area khusus, biasanya digunakan dalam sistem op-].erasi. * Contoh : membaca atau mengubah register kontrol. JUMLAH ALAMAT (NUMBER OF ADDRESSES) * Salah satu cara tradisional untuk menggambarkan arsitektur prosessor adalah dengan melihat jumlah alamat yang terkandung dalam setiap instruksinya.



* Jumlah alamat maksimum yang mungkin diperlukan dalam sebuah instruksi : 1. Empat Alamat ( dua operand, satu hasil, satu untuk alamat instruksi berikutnya) 2. Tiga Alamat (dua operand, satu hasil) 3. Dua Alamat (satu operand merangkap hasil, satunya lagi operand) 4. Satu Alamat (menggunakan accumulator untuk menyimpan operand dan hasilnya) Macam-macam instruksi menurut jumlah operasi yang dispesifikasikan 1. O – Address Instruction 2. 1 – Addreess Instruction. 3. N – Address Instruction 4. M + N – Address Instruction Macam-macam instruksi menurut sifat akses terhadap memori atau register 1. Memori To Register Instruction 2. Memori To Memori Instruction 3. Register To Register Instruction



ADDRESSING MODES Jenis-jenis addressing modes (Teknik Pengalamatan) yang paling umum: * Immediate * Direct * Indirect * Register * Register Indirect * Displacement * Stack