SISTEM I/O

Unit Input/Output (I/O) adalah bagian dari mikroprosesor yang digunakan oleh mikroprosesor itu untuk berhubungan dengan dunia luar. Unit input adalah unit luar yang digunakan untuk memasukan data dari luar kedalam mikroprosesor ini, contohnya data yang berasal dari keyboard dan mouse. sedangkan unit output biasanya untuk menampilkan data contohnya monitor, printer, dll.

Sistem I/O terdiri dari:
a. Perangkat Keras I/O
b. Aplikasi Antarmuka I/O
c. Kernel I/O
d. Mengubah I/O Request menjadi operasi perangkat keras
e. Streams
f. Performance

a. Perangkat Keras I/O
Konsep Umum :
> Port
> Bus (Daisy chain atau shared direct access)
> Controller (host adapter)
Perangkat kontrol instruksi I/O
Perangkat-perangkat tersebut memiliki alamat, digunakan untuk:
> Instruksi I/O langsung
> Memory-mapped I/O

Jenis Perangkat Keras
> Perangkat penyimpan data
> Perangkat penghubung
> Perangkat antarmuka dengan user

Suatu perangkat berhubungan dengan sistem komputer dengan cara mengirim sinyal melalui suatu kabel atau bahkan melalui udara Perangkat tersebut berkomunikasi dengan mesin melalui port, Struktur komputer yang umum dipakai adalah Daisy Chain.

DIAGRAM BLOK ARSITEKTUR KOMPUTER



POLLING
> Host terus membaca busy-bit secara berulang-ulang sampai bit tersebut clear
> Host set write-bit di command-register dan menulis satu byte di data-out register
> Host set bit command-ready
> Ketika controller mengetahui kalau bit command-ready di-set, dia men-set busy bit
> Controller membaca command-register dan melihat perintah tulis. Dia membaca
data-out register untuk mendapatkan bytenya, dan melakukan operasi I/O
> Controller menghapus bit command-ready, membersihkan bit error di status register
yang menandakan operasi I/O berhasil,dan menghapus busy-bit yang menandakan kalau
operasi sudah selesai.

Interrupt
> Jalur interrupt dihasilkan oleh perangkat I/O
> Interrupt Handler menerima interrupt tersebut
> Mekanisme interrupt juga digunakan untuk penanganan exception

Interrupt-Driven I/O Cycle



Direct Memory Access (DMA)
> Generasi komputer yang sangat tua
@ Controller membaca dari perangkat
@ Sistem Operasi meminta controller membaca data
> Generasi komputer yang tua
@ Controller membaca dari perangkat
@ Controller meng-interrupt OS
@ Sistem Operasi menyalin data ke memori
> Generasi DMA
@ Controller membaca dari perangkat
@ Controller menyalin data ke memori
@ Controller meng-interrupt OS

DMA Transfer



Aplikasi Antar-Muka I/O
> Sifat-sifat perangkat komputer diabstraksi oleh I/O system call berbentuk
kelas-kelas umum.
> Lapisan driver perangkat menyembunyikan perbedaanperbedaan I/O controller dari
kernel.
> Ragam device dari beberapa sisi:
> Character-stream atau block
> Sequential atau random-access
> Synchronous atau asynchronous
> Sharable atau dedicated
> Speed atau operation
> Read-write, read only, write only

Perangkat Block dan Character
> Perangkat block:
Ø Meliputi berbagai disk drive
Ø Perintah baca, tulis, pencarian data
Ø Dimungkinkan untuk mengakses berkas secara memorymapped
> Perangkat character:
Ø Contoh: keyboard, mouse
Ø Perintah menulis, mengambil
Ø Dapat dibuat library pengakses data per-baris

Perangkat Jaringan
> Interface berbeda dari baca, tulis disk, disebut interface socket.
> Socket: penghubung komputer dengan jaringan.
> Local socket dihubungkan dengan remote socket.
> Komunikasi antar komputer dilakukan melalui socket.

Clock dan Timer
> Fungsi clock dan timer pada hardware:
Ø Waktu saat ini
Ø Lama sebuah proses
ØTrigger proses pada suatu waktu
> Programmable interval timer : hardware pengukur waktu dan trigger.
> Sistem operasi mampu menangani time request lebih banyak dari jumlah hardware timer

Blocking dan Non-blocking I/O
> Blocking : proses dihentikan sementara
Ø Lebih mudah dimengerti
Ø Tidak cukup untuk beberapa hal
> Non-blocking : diimplementasikan lewat multi-threading
> Asynchronous : proses berjalan selama I/O dieksekusi

Kernel I/O Subsystem
> Scheduling :
* Permohonan I/O dilakukan berdasarkan antrian perangkat
* Beberapa sistem operasi berusaha untuk seadil mungkin
> Buffering : menyimpan data di memori selama proses transfer antar perangkat
* Solusi perbedaan kecepatan dari perangkat yang ada
* Solusi perbedaan ukuran transfer perangkat

Struktur Data Kernel
> Kernel menyimpan informasi penggunaan komponen I/O, termasuk tabel open-file
koneksi networking, informasi karakter device.
> Struktur data yang rumit dapat digunakan untuk memeriksa buffer, alokasi memori,
dan menentukan batasan sektor/blok.
> Beberapa sistem operasi menggunakan tehnik object oriented untuk mengkapsulasikan
perbedaan-perbedaan semantik yang ada.

Transformasi I/O Menjadi Operasi H/W
Proses:
> Blocking read system call diberikan pada pendeskripsi data dari data yang sudah
terbuka sebelumnya.
> Kode di kernel memeriksa parameter. Dalam proses input, jika data sudah ada di
buffer, data dikembalikan ke proses dan permintaan I/O selesai.

Contoh: membaca data dari disk untuk di proses.
> Menentukan device yang mengandung data,
> Menerjemahkan nama ke perwakilan device
> Secara fisik memindahkan data dari disk ke buffer
> Mempersiapkan data untuk proses permintaan I/O
> Mengembalikan kontrol ke proses

I/O Stream
> I/O stream adalah suatu mekanisme pengiriman data secara bertahap dan terus
menerus melalui suatu aliran data (dua arah)
> Biasa digunakan dalam network protocol
> Asynchronous
> Menggunakan message passing dalam men-transfer data
> Untuk memasukkan ke dalam stream digunakan ioctl system call
> Untuk menuliskan data ke device digunakan write / putmsg system call
> Untuk membaca data dari device digunakan read / getmsg system call
> User process: berhubungan langsung dengan stream head
> Ada beberapa modul dengan write dan read queue
> Device berhubungan langsung dengan driver

Kinerja I/O
> Pembuat CPU melaksanakan kode device-driver
> Memberitahukan ke-tidak efisien-an pada mekanisme penanganan interrupt dalam kernel
> Me-load memory bus sewaktu menyalin data yang dilakukan di controller dan physical
memory

Meningkatkan Kinerja I/O
> Memperkecil jumlah context switch
> Memperkecil jumlah penyalinan data yang dilakukan sewaktu pengoperan data antara
device dan aplikasi
> Memperkecil jumlah interrupt dengan menggunakan transfer secara besar-besaran,
smart controllers dan polling (jika busywaiting bisa diminimalisir)
> Menambah konkurensi dengan menggunakan DMA controllers atau channels yang telah
diketahui untuk meng-offload pennyalin sederhana dari CPU
> Memindahkan proses-proses primitif ke perangkat keras, untuk membuat operasinya
dalam device controllers konkuren dengan CPU dan operasi Bus
> Menyeimbangkan CPU, memory subsystem, bus, dan I/O performance, karena kelebihan
di salah satu area akan membuat keterlambatan pada yang lain.

Multiflexer dan Demultiflexer

A. Pengertian Multiplexer dan Demultiplexer
> Multiplexer adalah rangkaian logika yang menerima beberapa input data digital dan menyeleksi salah satu dari input tersebut pada saat tertentu untuk dikeluarkan pada sisi output.
> Demultiplexer adalah rangkain logika yang menerima satu input data digital dan mendistribusikan input tersebut ke beberapa output.



MULTIPLEXER : > Perangkat pemilih beberapa jalur data kedalam satu jalur data untuk dikirim ketitik lain.
> Mempunyai dua atau lebih signal digit sebagai input dan control sebagai pemilih (selector).
> Merupakan data selector (pemilih data)



Diagram Logika untuk 4 jalur multiplexer



IC 74151 Multiplexer 8 Jalur Input








DEMULTIPLEXER : > Kebalikan dari multiplexer.
> Mempunyai satu input data dan beberapa output data.
> Merupakan data distributor (distribusi data)





IC 74139 Demultiplexer 2-4 Jalur ( 2 Selector dan 4 jalur Output )



Diagram Logika IC 74139 Demultiplexer 2-4 jalur






Referensi : 1. http://www.scribd.com/doc/19169115/Multiplexer
2. http://id.wikipedia.org/wiki/Multiplekser

Arsitektur Komputer

Arsitektur Komputer

Secara umum komputer dapat diartikan sebagai alat elektronika yang bekerja secara koordinasi dan integrasi berdasarkan program, dapat menerima masukan berupa data yang diproses didalam suatu sistem dan dikeluarkan dalam bentuk informasi.

Adapaun Arsitektur komputer tersebut adalah sebagai berikut :


1. Input Device (Alat Masukan)

Adalah perangkat keras komputer yang berfungsi sebagai alat untuk memasukan data atau perintah ke dalam komputer.

2. Output Device (Alat Keluaran)

Adalah perangkat keras komputer yang berfungsi untuk menampilkan keluaran sebagai hasil pengolahan data. Keluaran dapat berupa hard-copy (ke kertas), soft-copy (ke monitor), ataupun berupa suara.

3. I/O Ports

Bagian ini digunakan untuk menerima ataupun mengirim data ke luar sistem. Peralatan input dan output di atas terhubung melalui port ini.

4. CPU (Central Processing Unit)

CPU merupakan otak sistem komputer, dan memiliki dua bagian fungsi operasional, yaitu: ALU (Arithmetical Logical Unit) sebagai pusat pengolah data, dan CU (Control Unit) sebagai pengontrol kerja komputer.

5. Memori

Memori terbagi menjadi dua bagian yaitu memori internal dan memori eksternal. Memori internal berupa RAM (Random Access Memory) yang berfungsi untuk menyimpan program yang kita olah untuk sementara waktu, dan ROM (Read Only Memory) yaitu memori yang haya bisa dibaca dan berguna sebagai penyedia informasi pada saat komputer pertama kali dinyalakan.

6. Data Bus

Adalah jalur-jalur perpindahan data antar modul dalam sistem komputer. Karena pada suatu saat tertentu masing-masing saluran hanya dapat membawa 1 bit data, maka jumlah saluran menentukan jumlah bit yang dapat ditransfer pada suatu saat. Lebar data bus ini menentukan kinerja sistem secara keseluruhan. Sifatnya bidirectional, artinya CPU dapat membaca dan menirma data melalui data bus ini. Data bus biasanya terdiri atas 8, 16, 32, atau 64 jalur paralel.

7. Address Bus

Digunakan untuk menandakan lokasi sumber ataupun tujuan pada proses transfer data. Pada jalur ini, CPU akan mengirimkan alamat memori yang akan ditulis atau dibaca. Address bus biasanya terdiri atas 16, 20, 24, atau 32 jalur paralel.

8. Control Bus

Control Bus digunakan untuk mengontrol penggunaan serta akses ke Data Bus dan Address Bus. Terdiriatas 4 samapai 10 jalur paralel.

Referensi : http://www.scribd.com/doc/10916989/Organisasi-Dan-Arsitektur-Komputer

Algoritma Binary Search

A. Pengertian
Binary Search adalah algoritma pencarian yang lebih efisien daripada algorima Sequential Search. Hal ini dikarenakan algoritma ini tidak perlu menjelajahi setiap elemen dari tabel. Kerugiannya adalah algoritma ini hanya bisa digunakan pada tabel yang elemennya sudah terurut baik menaik maupun menurun.
Pada intinya, algoritma ini menggunakan prinsip divide and conquer, dimana sebuah masalah atau tujuan diselesaikan dengan cara mempartisi masalah menjadi bagian yang lebih kecil. Algoritma ini membagi sebuah tabel menjadi dua dan memproses satu bagian dari tabel itu saja.
Algoritma ini bekerja dengan cara memilih record dengan indeks tengah dari tabel dan membandingkannya dengan record yang hendak dicari. Jika record tersebut lebih rendah atau lebih tinggi, maka tabel tersebut dibagi dua dan bagian tabel yang bersesuaian akan diproses kembali secara rekursif.

B. Keunggulan
Keunggulan utama dari algoritma binary search adalah kompleksitas algoritmanya yang lebih kecil daripada kompleksitas algoritma sequential search. Hal ini menyebabkan waktu yang dibutuhkan algoritma binary search dalam mencari sebuah record dalam sebuah tabel lebih kecil daripada waktu yang dibutuhkan algoritma sequential search.

C. Fungsi
Pencarian Biner (Binary Search) dilakukan untuk :
1. memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.

2. Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).

3. Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.


ALGORITMA

Kamus
Const N : integer = 8 { misalkan jumlah elemen array maksimum = 8 }
Type A = array [ 1 ..... N ] of integer
Cari, BatasAtas, BatasBawah, Tengah : Integer
Ketemu : boolean
ALGORITMA
Input (cari) { meminta nilai data yang akan dicari}
BatasAtas  1 { indeks array dimulai dari 1 }
BatasBawah  N
Ketemu  False
While (BatasAtas < BatasBawah) and (not ketemu) do
Tengah  (BatasAtas + BatasBawah) div 2
If A [Tengah] = cari then
Ketemu  true
Else
If ( A [Tengah] < cari ) then { cari di bagian kanan }
BatasAtas  Tengah + 1
Else
BatasBawah  Tengah – 1 { cari di bagian kiri }
Endif
Endif
EndWhile
If (ketemu) then
Output ( ‘Data berada di index nomor’, Tengah )
Else Output ( ‘Data tidak ditemukan’ )
Endif


CONTOH

Contoh Nilai-Nilai data yang sudah terurut :

A 2 5 8 12 15 25 37 57
1 2 3 3 5 6 7 8

Kasus 1 : cari = 12
Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 8) div 2 = 4
A [Tengah] = A [4] = 12, berarti loop pertama data langsung ditemukan

Kasus 2 : cari = 15
Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 8) div 2 = 4
A [Tengah] = A [4] = 12 < cari = 15, berarti BatasAtas = Tengah + 1 = 4 + 1 = 5
Loop kedua : Tengah = (BatasAtas + BatasBawah) div 2 = (5 + 8) div 2 = 6
A [Tengah] = A [6] = 25 > cari = 15, berarti BatasBawah = Tengah - 1 = 6 - 1 = 5
Loop ketiga : Tengah = (BatasAtas + BatasBawah) div 2 = (5 + 5) div 2 = 5
A [Tengah] = A [5] = 15, berarti setelah loop ketiga, data ditemukan

Kasus 3 : cari = 10
Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 8) div 2 = 4
A [Tengah] = A [4] = 12 > cari = 10, berarti BatasBawah = Tengah - 1 = 4 - 1 = 3
Loop kedua : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 3) div 2 = 2
A [Tengah] = A [2] = 5 < cari = 10, berarti BatasAtas = Tengah + 1 = 2 + 1 = 3
Loop ketiga : Tengah = (BatasAtas + BatasBawah) div 2 = (3 + 3) div 2 = 3
A [Tengah] = A [3] = 8, berarti setelah loop ketiga, data tidak ditemukan

Untuk jumlah data sebanyak n, maka proses pembandingan maksimal sebanyak ( log n ) kali. Untuk contoh di atas, jumlah data 8, maka proses pembandingan maksimal sebanyak 3 kali.

Algoritma Divide dan Conquer

Divide and Conquer adalah metode pemecahan

masalah yang bekerja dengan membagi masalah menjadi

beberapa upa-masalah yang lebih kecil, kemudian

menyelesaikan masing-masing upa-masalah tersebut

secara independen, dan akhirnya menggabungkan solusi

masing-masing upamasalah sehingga menjadi solusi dari

masalah semula.

Pada algortima Divide and Conquer ini meiliki tiga proses

utama yaitu:

- Divide: membagi masalah menjadi beberapa upamasalah

yang memiliki kemiripan dengan masalah semula namun

berukuran lebih kecil (idealnya berukuran hampir sama),

- Conquer: memecahkan (menyelesaikan) masingmasing

upa-masalah (secara rekursif), dan

- Combine: mengabungkan solusi masing-masing upamasalah

sehingga membentuk solusi masalah semula.

Pada algoritma ini, tiap-tiap upa-masalah mempunyai

karakteristik yang sama (the same type) dengan

karakteristik masalah asal, sehingga metode Divide and

Conquer lebih natural diungkapkan dalam skema rekursif.

Secara umum, algoritma Divide and Conquer memiliki

sekema sbb:

procedure DIVIDE_and_CONQUER(input n :

integer)

{ Menyelesaikan masalah dengan

algoritma Dand-

C.

Masukan: masukan yang berukuran n

Keluaran: solusi dari masalah semula

}

Deklarasi

r, k : integer

Algoritma

if n ≤ n0 then {ukuran masalah sudah

cukup

kecil }

SOLVE upa-masalah yang berukuran n ini

else

Dalam Algoritma divide dan conquer Pemrogram bertanggung jawab atas implementasi solusi. Pembuatan program akan menjadi lebih sederhana jika masalah dapat dipecah menjadi sub masalah - sub masalah yang dapat dikelola.

Penyelesaian masalah dengan komputer berhadapan dengan 4 hal, yaitu :

1. Pemahaman keterhubungan elemen-elemen data yang relevan terhadap solusi secara menyeluruh.

2. Pengambilan keputusan mengenai operasi-operasi yang dilakukan terhadap elemen-elemen data.

3. Perancangan representasi elemen-elemen data di memori sehingga memenuhi kriteria berikut:

a. Memenuhi keterhubungan logik antara elemen-elemen data.

b. Operasi-operasi terhadap elemen-elemen data dapat dilakukan secara mudah dan efisien.

4. Pengambilan keputusan mengenai mengenai bahasa pemrograman terbaik untuk menerjemahkan solusi persoalan menjadi program.

STRATEGI DIVIDE DAN CONQUER

Metode

Strategi Divide dan Conquer memecah masalah menjadi submasalah-submasalah independen yang lebih kecil sehingga solusi submasalah-submasalah dapat diperoleh secara mudah, solusi submasalah-submasalah digabung menjadi solusi seluruh masalah.

Skema umum algoritma divide dan conquer

Procedure DNC ( i,j : integer )

Var K : integer ;

If SMALL (i,j) then SOLVE (i,j)

Else begin

K : = DIVIDE (i,j)

COMBINE (DNC(i,k),DNC(k+1,j))

End if

Keterangan :

1. SMALL adalah fungsi yang mengirim BOOLEAN, menentukan apakah ukuran telah cukup kecil sehingga solusi dapat diperoleh. Ukuran dinyatakan sebagai telah berukuran kecil bergantung masalah.

2. DIVIDE adalah fungsi membagi menjadi 2 bagian pada posisi K. Biasanya bagian berukuran sama.

3. COMBINE adalah fungsi menggabungkan solusi X dan Y submasalah. Solusi diperoleh dengan memanggil prosedur rekursif DNC.

Jika ukuran kedua submasalah sama, waktu komputasi DNC dideskripsikan hubungan rekuren berikut :

T(n) = g (n), n kecil

2 T (n/2) + f (n), selainnya

dimana :

· T(n) adalah waktu untuk DNC dengan n masukan,

· g(n) adalah waktu komputasi jawaban secara langsung untuk masukan kecil dan

· f(n) adalah waktu COMBINE.

Untuk algoritma divide dan conquer yang menghasilkan submasalah-submasalah dengan tipe masalah yang sama dengan masalah awal, sangat alami untuk mendeskripsikan algoritma secara rekursi. Kemudian untuk meningkatkan efisiensi dilakukan penerjemahan menjadi bentuk iterasi.

Pemakaian teknik Divide dan Conquer banyak digunakan dalam menyelesaikan berbagai macam persoalan, antara lain :

1. Searching

2. Sorting

Sumber : http://pdflost.com/download/5991507/

Algoritma Kruskall

Contoh : Pandang sebuah graph sebagai berikut;

Algoritma Kruskall

Dasar pembentukan algoritma Kruskal berasal dari analogi growing forest. Growing forest maksudnya adalah untuk membentuk pohon merentang minimum T dari grafG adalah dengan cara mengambil satu per satu sisi dari graf G dan memasukkannya ke dalam pohon yang telah terbentuk sebelumnya. Seiring dengan berjalannya iterasi untuk setiap sisi, maka forest akan memiliki pohon yang semakin sedikit. Oleh sebab itu, maka analogi ini disebut dengan growing forest. Algoritma Kruskal akan terus menambahkan sisi – sisi ke dalam hutan yang sesuai hingga akhirnya tidak akan ada lagi forest dengan, melainkan hanyala

h sebuah pohon yang merentang minimum.Soal diatas dapat dijawab dengan menggunakan Algoritma Kruskall seperti ditunjukkan dibawah ini :.

-------Edge----- Cost

1. ( 1,2 )----- 10
   
2. ( 3,6 )----- 15
   
3. ( 4,6 )----- 20
   
4. ( 2,6 )----- 25
   
5. ( 1,4 )----- 30
6. ( 3,5 )----- 35

Maka Spanning Tree- nya adalah

Sehingga total costnya ialah 105

Tugas: (minimum spanning tree dan total cost nya)