AOK - CPU Structures and Functions
Showing posts with label Semester 3. Show all posts
Showing posts with label Semester 3. Show all posts
Tuesday, January 12, 2016
Monday, January 11, 2016
Aljabar Linier - Kisi-kisi UAS
- Basis untuk ruang baris dan ruang kolom dari suatu matriks A
- Cari basis ortogonal untuk ruang kolom matriks A dengan Gram-Schmidt
- Diagonalisasi Ortogonal
- Cari nilai eigen dan vektor eigen dari matriks A
- Transformasi linier dari Rn --> Rm seperti Example 10 halaman 451
- Perubahan basis : [w]B' = P(B-->B') [w]B
Happy Studying~
- Cari basis ortogonal untuk ruang kolom matriks A dengan Gram-Schmidt
- Diagonalisasi Ortogonal
- Cari nilai eigen dan vektor eigen dari matriks A
- Transformasi linier dari Rn --> Rm seperti Example 10 halaman 451
- Perubahan basis : [w]B' = P(B-->B') [w]B
Happy Studying~
Friday, January 08, 2016
Arsitektur dan Organisasi Komputer - Instruction Sets: Addressing Modes and Formats
Addressing Modes:
- Immediate
- Direct
- Indirect
- Register
- Register Indirect
- Displacement ( Indexed )
- Stack
1) Immediate Addressing
-> operand merupakan bagian dari instruksi
-> contoh: ADD 5 -> tambah 5 ke dalam isi akumulator
-> no memory reference to fetch data
-> fast
-> limited range
2) Direct Addressing
-> address field contains address of operand
-> EA (effective address) = address field (A)
-> cth: ADD A -> tambah isi dari A dgn akumulator
-> Single memory reference to access data
3) Indirect Addressing
-> address field mengandung alamat dari operand (pointer)
-> EA = (A)
-> contoh: ADD (A) -> lihat isi dari A, mencari alamat isi dari A utk mendapatkan operand
-> may be nested, cascaded, multilevel. cth: EA = (((A)))
Contoh Soal ! !
Tuliskan ADD 400 secara:
- Immediate
- Direct
- Indirect
4) Register Addressing -> paling cepet, krn udh ada di CPU
-> EA = R
5) Register Indirect Addressing
-> EA = (R)
-> operand is in memory cell pointed to by contents of register R
6) Displacement Addressing
-> EA = A + (R)
7) Relative Addressing
-> EA = A + (PC) *PC = Program Counter
-> cth: get operand from A cells from current location pointed to by PC
8) Base-Register Addressing
(gw gagitu ngerti, jd modal copas aja ya)
-> A holds displacement
-> R holds pointer to base address
-> R may be implicit or explicit
-> cth: segment registers in 80x86
9) Indexed addressing
-> A = Base
-> R = displacement
-> EA = A + R
-> Good for accessing arrays
EA = A + R
R++
10) Combinations
-> Postindex
EA = (A) + (R)
-> Preindex
EA = (A + (R))
11) Stack Addressing
-> operand is (implicitly) on top of stack
**Stack pointer: register yang menyimpan alamat paling atas dari stack
^^^keluar di kuis pak Tatang
JAWABAN LATIHAN SOAL
Immediate: A = 400
Direct: A = 420
Indirect: A = 470
- Immediate
- Direct
- Indirect
- Register
- Register Indirect
- Displacement ( Indexed )
- Stack
1) Immediate Addressing
-> operand merupakan bagian dari instruksi
-> contoh: ADD 5 -> tambah 5 ke dalam isi akumulator
-> no memory reference to fetch data
-> fast
-> limited range
2) Direct Addressing
-> address field contains address of operand
-> EA (effective address) = address field (A)
-> cth: ADD A -> tambah isi dari A dgn akumulator
-> Single memory reference to access data
3) Indirect Addressing
-> address field mengandung alamat dari operand (pointer)
-> EA = (A)
-> contoh: ADD (A) -> lihat isi dari A, mencari alamat isi dari A utk mendapatkan operand
-> may be nested, cascaded, multilevel. cth: EA = (((A)))
Contoh Soal ! !
- Immediate
- Direct
- Indirect
4) Register Addressing -> paling cepet, krn udh ada di CPU
-> EA = R
5) Register Indirect Addressing
-> EA = (R)
-> operand is in memory cell pointed to by contents of register R
6) Displacement Addressing
-> EA = A + (R)
7) Relative Addressing
-> EA = A + (PC) *PC = Program Counter
-> cth: get operand from A cells from current location pointed to by PC
8) Base-Register Addressing
(gw gagitu ngerti, jd modal copas aja ya)
-> A holds displacement
-> R holds pointer to base address
-> R may be implicit or explicit
-> cth: segment registers in 80x86
9) Indexed addressing
-> A = Base
-> R = displacement
-> EA = A + R
-> Good for accessing arrays
EA = A + R
R++
10) Combinations
-> Postindex
EA = (A) + (R)
-> Preindex
EA = (A + (R))
11) Stack Addressing
-> operand is (implicitly) on top of stack
**Stack pointer: register yang menyimpan alamat paling atas dari stack
^^^keluar di kuis pak Tatang
JAWABAN LATIHAN SOAL
Immediate: A = 400
Direct: A = 420
Indirect: A = 470
Arsitektur dan Organisasi Komputer - Instruction Sets: Characteristics and Functions
Instruction Sets: kumpulan instruksi yang dimengerti CPU
Elemen dari Instruksi:
- Operation Code (Op Code): do this
- Source Operand reference: to this
- Result Operand reference: put the answer here
- Next Instruction reference: when you have done that, do this...
Instruction Representation:
cth: ADD, SUB, LOAD
Simple Instruction Format:
Instruction Types:
- Data Processing
- Data Storage (main memory)
- Data Movement (I/O)
- Program flow control
Untuk mengambil operand, alamat dapat berjumlah 0, 1, 2, atau 3 alamat
3 Alamat
A = B + C
2 Alamat
A = A + B
1 Alamat
Accumulator, cth A++
0 Alamat
Menggunakan stack
cth:
PUSH A
PUSH B
ADD
POP C
sama saja seperti: C = A + B
Types of Operand:
- Addresses
- Numbers (integer/ floating point)
- Characters (ASCII dll)
- Logical Data (bits/ flags)
Types of Operation:
- Data transfer
Specify -> source, destination, amount of data
- Arithmetic
Add, subtract, multiply, divide
May include: increment (a++), decrement (a--), negate (-a)
- Logical
AND, OR, NOT
- Conversion
e.g binary to decimal
- I/O
May be specific instructions
May be done using data movement instructions (memory mapped)
May be done by separate controller (DMA)
- System Control
for OS use, CPU must be in specific state
- Transfer of Control
Branch, dibagi 2:
-> Branch Conditional, cth branch to x if result is zero
-> Branch Unconditional, cth call 1000
-> cth branch:
Skip
-> cth: increment and skip if zero
-> bersyarat
Subroutine Call
-> tanpa syarat
-> cth: interrupt call
Elemen dari Instruksi:
- Operation Code (Op Code): do this
- Source Operand reference: to this
- Result Operand reference: put the answer here
- Next Instruction reference: when you have done that, do this...
Instruction Representation:
cth: ADD, SUB, LOAD
Simple Instruction Format:
Instruction Types:
- Data Processing
- Data Storage (main memory)
- Data Movement (I/O)
- Program flow control
Untuk mengambil operand, alamat dapat berjumlah 0, 1, 2, atau 3 alamat
3 Alamat
A = B + C
2 Alamat
A = A + B
1 Alamat
Accumulator, cth A++
0 Alamat
Menggunakan stack
cth:
PUSH A
PUSH B
ADD
POP C
sama saja seperti: C = A + B
Types of Operand:
- Addresses
- Numbers (integer/ floating point)
- Characters (ASCII dll)
- Logical Data (bits/ flags)
More addresses
-> More complex (powerful?) instructions
-> More registers
-> Inter-register operations are quicker
-> Fewer instructions per program
Fewer addresses
-> Less complex (powerful?) instructions
-> More instructions per program
-> Faster fetch/execution of instructions
Types of Operation:
- Data transfer
Specify -> source, destination, amount of data
- Arithmetic
Add, subtract, multiply, divide
May include: increment (a++), decrement (a--), negate (-a)
- Logical
AND, OR, NOT
- Conversion
e.g binary to decimal
- I/O
May be specific instructions
May be done using data movement instructions (memory mapped)
May be done by separate controller (DMA)
- System Control
for OS use, CPU must be in specific state
- Transfer of Control
Branch, dibagi 2:
-> Branch Conditional, cth branch to x if result is zero
-> Branch Unconditional, cth call 1000
-> cth branch:
Skip
-> cth: increment and skip if zero
-> bersyarat
Subroutine Call
-> tanpa syarat
-> cth: interrupt call
Uses of Stack
Stack berguna utk menyimpan isi register kalau ada program yang loncat (bercabang) sehingga dia tau harus kembali ke mana
Stack hanya menyimpan operand yang di push dan alamat untuk kembali
Stack terdapat di RAM (memori bisa diambil secara acak)
Namun, stack tdk dapat diambil secara acak melainkan dengan LIFO
Contoh:
Arsitektur dan Organisasi Komputer - Computer Arithmetic
ALU -> melakukan kalkulasi dalam komputer.
-> Handles integers, may handle floating point (real) numbers
Integer Representation
- 0 and 1 merepresentasikan semuanya.
- Contoh: 41 = 00101001
- No minus sign
- Sign Magnitude (pd leftmost bit, 0 utk +, 1 utk - )
- Two's Complement
TWO'S COMPLEMENT
-> negating is fairly easy
cth:
3 = 00000011
boolean complement gives 11111100 (1 jd 0, 0 jd 1)
add 1 to LSB (Least Significant Digit -> digit plg blkg) gives 11111101 -> -3
-> range of numbers:
8 bit two's complement: 2^7 -1 to -2^7
16 bit two's complement: 2^15 -1 to -2^15
-> addition and subtraction
addition: normal binary addition
subtraction: e.g. a - b = a + (-b)
-> multiplication
a) Unsigned Binary Multiplication
Execution Example:
Keterangan:
C = Carry
A = tempat utk menampung perhitungan
Q = pengali (multiplier)
M = yang dikali (multiplicand)
Penjelasan:
Dari algoritma (flowchart) diatas, kita aplikasikan buat melakukan perkalian bilangan positif. Awalnya, nilai carry (C) dan A di set 0. Kita akan mengalikan 13 dengan 11 (1101 dan 1011). Count bernilai n, yaitu jumlah digit Q.
Next, kita lihat apakah Q0 nya bernilai 1? Q0 adalah LSD dari Q. Karena awalnya Q0 bernilai 1, kita menambahkan (add) A+M dan shift 1 digit ke kanan kanan. Jangan lupa count-1, nilai count sekarang adalah 3. nilai count != 0, maka diulang kembali.
Selanjutnya, nilai Q0 berubah menjadi 0, sehingga kita lakukan shift kembali dan count = 3-1 = 2. Nilai count != 0, maka perulangan kembali dilakukan.
Lalu, setelah di shift nilai Q0 menjadi 1, sehingga A+M menjadi 1101, dan shift kembali dilakukan. Count sekarang bernilai 1, dan belum sama dengan 0, sehingga perulangan lagi.
Akhirnya, kita lihat bahwa nilai Q0 adalah 1, sehingga A+M, Shift dan Count sekarang == 0, sehingga proses berakhir.
Hasil akhir dari perkalian adalah A, Q sehingga = 10001111 atau 143.
b) Signed Binary Multiplication -> menggunakan Booth's Algorithm
Contoh:
Penjelasan:
Rata" sama kyk unsigned binary sih, tapi bedanya yang ini ada Q-1 nya. Ikutin flowchart aja ya wkwk :p
-> division:
a) Unsigned Binary Division
- Cara pembagian biasa:
- Umumnya dibagi menjadi 2: restoring dan non-restoring
1) Restoring
cth: 8/3 -> 1000 / 11
2) Non-restoring
cth: 8/3 -> 1000 / 11
Semoga dgn membaca sendiri udah bisa ngerti ya :) kalo emang masih blm ngerti feel free to ask :)
REAL NUMBERS
-> numbers with fraction
-> floating point:
1) Single precision/format
2) Double Precision Format
Cara menghitung biased exponent
dan seterusnya.
Cara menghitung floating point:
contoh:
a. FP dari 102?
1) Cari biner dari 102 -> 1100110
2) Ubah bentuknya menjadi 1,...
1100110 -> 1,100110 x 2^6 (karena komanya geser 6 biner)
3) Cari biased exponentnya
Bias: 127
geser 6 biner -> E = 6
Bias + E = 133
Biner dari 133 = 10000101
4) Masukkan ke bentuk Floating point
0 10000101 10011000000000
(+) (Biased) (Dapet dari angka dibelakang koma)
b. konversi hexa ke desimal dalam bentuk floating point (gw gapunya term yg lebih bagus dr ini lol)
cth: 8 3 6 0 0 0 0 0
1) ubah ke bentuk biner
1000 0011 0110 0000 0000 0000 0000 0000
2) ubah ke bentuk floating point
1 | 000 0011 0 | 110 0000 0000 0000 0000 0000
Hope it helps!
-> Handles integers, may handle floating point (real) numbers
Integer Representation
- 0 and 1 merepresentasikan semuanya.
- Contoh: 41 = 00101001
- No minus sign
- Sign Magnitude (pd leftmost bit, 0 utk +, 1 utk - )
- Two's Complement
TWO'S COMPLEMENT
-> negating is fairly easy
cth:
3 = 00000011
boolean complement gives 11111100 (1 jd 0, 0 jd 1)
add 1 to LSB (Least Significant Digit -> digit plg blkg) gives 11111101 -> -3
-> range of numbers:
8 bit two's complement: 2^7 -1 to -2^7
16 bit two's complement: 2^15 -1 to -2^15
-> addition and subtraction
addition: normal binary addition
subtraction: e.g. a - b = a + (-b)
-> multiplication
a) Unsigned Binary Multiplication
Execution Example:
Keterangan:
C = Carry
A = tempat utk menampung perhitungan
Q = pengali (multiplier)
M = yang dikali (multiplicand)
Penjelasan:
Dari algoritma (flowchart) diatas, kita aplikasikan buat melakukan perkalian bilangan positif. Awalnya, nilai carry (C) dan A di set 0. Kita akan mengalikan 13 dengan 11 (1101 dan 1011). Count bernilai n, yaitu jumlah digit Q.
Next, kita lihat apakah Q0 nya bernilai 1? Q0 adalah LSD dari Q. Karena awalnya Q0 bernilai 1, kita menambahkan (add) A+M dan shift 1 digit ke kanan kanan. Jangan lupa count-1, nilai count sekarang adalah 3. nilai count != 0, maka diulang kembali.
Selanjutnya, nilai Q0 berubah menjadi 0, sehingga kita lakukan shift kembali dan count = 3-1 = 2. Nilai count != 0, maka perulangan kembali dilakukan.
Lalu, setelah di shift nilai Q0 menjadi 1, sehingga A+M menjadi 1101, dan shift kembali dilakukan. Count sekarang bernilai 1, dan belum sama dengan 0, sehingga perulangan lagi.
Akhirnya, kita lihat bahwa nilai Q0 adalah 1, sehingga A+M, Shift dan Count sekarang == 0, sehingga proses berakhir.
Hasil akhir dari perkalian adalah A, Q sehingga = 10001111 atau 143.
b) Signed Binary Multiplication -> menggunakan Booth's Algorithm
Contoh:
Rata" sama kyk unsigned binary sih, tapi bedanya yang ini ada Q-1 nya. Ikutin flowchart aja ya wkwk :p
-> division:
a) Unsigned Binary Division
- Cara pembagian biasa:
1) Restoring
cth: 8/3 -> 1000 / 11
2) Non-restoring
cth: 8/3 -> 1000 / 11
Semoga dgn membaca sendiri udah bisa ngerti ya :) kalo emang masih blm ngerti feel free to ask :)
REAL NUMBERS
-> numbers with fraction
-> floating point:
1) Single precision/format
2) Double Precision Format
Cara menghitung biased exponent
Cara menghitung floating point:
contoh:
a. FP dari 102?
1) Cari biner dari 102 -> 1100110
2) Ubah bentuknya menjadi 1,...
1100110 -> 1,100110 x 2^6 (karena komanya geser 6 biner)
3) Cari biased exponentnya
Bias: 127
geser 6 biner -> E = 6
Bias + E = 133
Biner dari 133 = 10000101
4) Masukkan ke bentuk Floating point
0 10000101 10011000000000
(+) (Biased) (Dapet dari angka dibelakang koma)
b. konversi hexa ke desimal dalam bentuk floating point (gw gapunya term yg lebih bagus dr ini lol)
cth: 8 3 6 0 0 0 0 0
1) ubah ke bentuk biner
1000 0011 0110 0000 0000 0000 0000 0000
2) ubah ke bentuk floating point
1 | 000 0011 0 | 110 0000 0000 0000 0000 0000
(sign) (biased) (fractions)
3) ubah ke desimal, caranya:
-> sign = 1 berarti minus (-)
-> biased = 6, utk mjd 127 berarti kurang 121 -> 2^(-121)
-> fractions = pake cara angka dibelakang koma, sehingga 0,5 + 0,25 = 0,75
-> lalu, gabungin semuanya~
- 1,75 x 2^(-121)
(jangan lupa didpn koma tambahin 1)
Thursday, January 07, 2016
Arsitektur dan Organisasi Komputer - Operating System
Software:
-> System: utk membantu, cth OS
-> Application: program yg dibuat utk menyelesaikan masalah
OS: kumpulan program utk membantu pemakai utk menggunakan komputer dengan lbh mudah.
Fungsi OS:
- Convenience -> membantu
cth: kalo mau bikin chart tinggal ambil
- Security (keamanan)
-> Aman thd ancaman (thread), cth: org yg ga punya hak gabisa buka
-> Data Availability, data integrity, lost data
-> Aman thd serangan
- Efficiency: utk mengatur sumber daya (CPU, Memory, I/O) di komputer utk dipakai se efisien mungkin.
Tipe" OS (Sesuai Algo):
1. Interactive
2. Batch
3. Single Program (uni-programming)
4. Multi Programming (multi-tasking)
Early systems -> No OS, program interact directly with hardware
Simple Batch Systems -> resident monitor program
Multi-programming Systems -> I/O Devices are very slow, so when one program is waiting for I/O, another can use the CPU
-> Time sharing systems: Allow users to interact directly with the computer. Multiprogramming allows a number oof users to interact with the computer
-> Scheduling: key of multiprogramming
-> Long Term: Determines which programs are submitted for processing. E.g. Program masih di hard disk tapi udah diatur nanti program dari HD mau diambil dan ditaro dimana
-> Medium Term: Part of the swapping function, usually based on the need to manage multiprogramming. Trjd di memori utama
-> Short Term: Dispatcher. Fine grained decisions of which job to execute next. Trjd di CPU
Process Control Block
- Identifier
- State
- Priority
- Program Counter
- Memory pointers
- Context data
- I/O Status
- Accounting Information
Diagram:
Key Element of OS:
Memory Management
- Uni Program: memori terbagi menjadi 2, satu utk OS (monitor), 1 utk program yg sdg berjalan
- Multi program: "user" part is sub-divided and shared among active processes
(Sisanya baca sendiri ya, ada juga di materi OS :))
-> System: utk membantu, cth OS
-> Application: program yg dibuat utk menyelesaikan masalah
OS: kumpulan program utk membantu pemakai utk menggunakan komputer dengan lbh mudah.
Fungsi OS:
- Convenience -> membantu
cth: kalo mau bikin chart tinggal ambil
- Security (keamanan)
-> Aman thd ancaman (thread), cth: org yg ga punya hak gabisa buka
-> Data Availability, data integrity, lost data
-> Aman thd serangan
- Efficiency: utk mengatur sumber daya (CPU, Memory, I/O) di komputer utk dipakai se efisien mungkin.
Tipe" OS (Sesuai Algo):
1. Interactive
2. Batch
3. Single Program (uni-programming)
4. Multi Programming (multi-tasking)
Early systems -> No OS, program interact directly with hardware
Simple Batch Systems -> resident monitor program
Multi-programming Systems -> I/O Devices are very slow, so when one program is waiting for I/O, another can use the CPU
-> Time sharing systems: Allow users to interact directly with the computer. Multiprogramming allows a number oof users to interact with the computer
-> Scheduling: key of multiprogramming
-> Long Term: Determines which programs are submitted for processing. E.g. Program masih di hard disk tapi udah diatur nanti program dari HD mau diambil dan ditaro dimana
-> Medium Term: Part of the swapping function, usually based on the need to manage multiprogramming. Trjd di memori utama
-> Short Term: Dispatcher. Fine grained decisions of which job to execute next. Trjd di CPU
Process Control Block
- Identifier
- State
- Priority
- Program Counter
- Memory pointers
- Context data
- I/O Status
- Accounting Information
Diagram:
Key Element of OS:
Memory Management
- Uni Program: memori terbagi menjadi 2, satu utk OS (monitor), 1 utk program yg sdg berjalan
- Multi program: "user" part is sub-divided and shared among active processes
(Sisanya baca sendiri ya, ada juga di materi OS :))
Sistem Operasi - Latihan Soal dan Kunci Jawaban
1. Diketahui 32 bit virtual address dibagi menjadi 4 segmen sbb:
Berapa memori yang dibutuhkan untuk page table jika ada 1 proses dengan ukuran 256 KB yang mulai dari alamat 0, dengan PTE (Page Table Entry) = 2 byte.
2. Diketahui 61 bit virtual address, page size 1 KB, RAM 64 KB, PTE 2 byte. Berapa memori yang diperlukan untuk page table jika digunakan:
a. Standard Page Table
b. Inverted page table
3. Diketahui:
Tentukan nomor segment dari alamat-alamat sbb:
a) 649
b) 2310
c) 1727
4. (Soal sama dengan no. 1), diketahui:
5. Apa dampaknya jika ukuran page besar?
KUNCI JAWABAN
1. (1024 + 256 + (64*16)) *2 = ... byte
2. a. ( 2^61/ 2^10 ) * 2^1 = 2^51 * 2^1 = 2^52
b. 64K/1K = 64 PTE = 128 byte
3. a) 0
b) 1
c) 3
5. - Jika dibuat bsr, jml pagenya berkurang, akan memperkecil jumlah page table, sehingga memori yg dipakai berkurang.
- Akan terjd fragmentasi internal
- Jika trjd pg fault maka proses utk swap out dan swap in mjd lebih lambat krn ukurannya bsr.
(Mau tau cara pengerjaannya? GO PREMIUM ! (?))
**LOL JK kerjain sendiri yaa. tanya" aja kalo gatau
JAWABAN DISK ARM SCHEDULING ALGORITHM
2. Diketahui 61 bit virtual address, page size 1 KB, RAM 64 KB, PTE 2 byte. Berapa memori yang diperlukan untuk page table jika digunakan:
a. Standard Page Table
b. Inverted page table
3. Diketahui:
a) 649
b) 2310
c) 1727
4. (Soal sama dengan no. 1), diketahui:
5. Apa dampaknya jika ukuran page besar?
KUNCI JAWABAN
1. (1024 + 256 + (64*16)) *2 = ... byte
2. a. ( 2^61/ 2^10 ) * 2^1 = 2^51 * 2^1 = 2^52
b. 64K/1K = 64 PTE = 128 byte
3. a) 0
b) 1
c) 3
5. - Jika dibuat bsr, jml pagenya berkurang, akan memperkecil jumlah page table, sehingga memori yg dipakai berkurang.
- Akan terjd fragmentasi internal
- Jika trjd pg fault maka proses utk swap out dan swap in mjd lebih lambat krn ukurannya bsr.
(Mau tau cara pengerjaannya? GO PREMIUM ! (?))
**LOL JK kerjain sendiri yaa. tanya" aja kalo gatau
JAWABAN DISK ARM SCHEDULING ALGORITHM
Tuesday, January 05, 2016
Sistem Operasi - Hard Disk
Teori yang lain coba pelajari sendiri ya, disini cuma bkl dibahas mengenai perhitungan:
DISK ARM SCHEDULING ALGORITHM
3 Faktor yang mendorong kecepatan:
- Seek Time: waktu yang dibutuhkan oleh head untuk berpindah dari satu track ke track lain
- Rotation Delay: semakin cepat rotation per meter (Rpm) semakin cepat transfer
- Actual transfer time
Algoritma dlm disk arm scheduling:
1. FCFS -> First Come First Served
2. SSF/SSTF -> Shortest Seek First / Shortest Seek Time First
3. Elevator (Scan)
Contoh soal:
Diketahui disk dengan 40 silinder (0-39). Pada saat sedang membaca silinder 11, ada permintaan untuk membaca silinder: 1, 36, 16, 34, 9, 12.
Hitung total silinder yang dilalui oleh head menggunakan algoritma:
a. FCFS
b. SSF
c. Elevator
Hint:
FCFS = sesuai urutan
SSF = mencari permintaan terdekat dgn posisi skrg
Elevator = meniru algoritma LIFT
Butuh dishare jawabannya? hehe
DISK ARM SCHEDULING ALGORITHM
3 Faktor yang mendorong kecepatan:
- Seek Time: waktu yang dibutuhkan oleh head untuk berpindah dari satu track ke track lain
- Rotation Delay: semakin cepat rotation per meter (Rpm) semakin cepat transfer
- Actual transfer time
Algoritma dlm disk arm scheduling:
1. FCFS -> First Come First Served
2. SSF/SSTF -> Shortest Seek First / Shortest Seek Time First
3. Elevator (Scan)
Contoh soal:
Diketahui disk dengan 40 silinder (0-39). Pada saat sedang membaca silinder 11, ada permintaan untuk membaca silinder: 1, 36, 16, 34, 9, 12.
Hitung total silinder yang dilalui oleh head menggunakan algoritma:
a. FCFS
b. SSF
c. Elevator
Hint:
FCFS = sesuai urutan
SSF = mencari permintaan terdekat dgn posisi skrg
Elevator = meniru algoritma LIFT
Butuh dishare jawabannya? hehe
Monday, January 04, 2016
Sistem Operasi - Modelling Page Replacement Algo.
Belady's Anomaly -> suatu gejala dimana dgn menambah memori (page frame), ada kemungkinan jumlah page faultnya bertambah.
Ditemukan di Algo. FIFO
Stack Algorithm
-> Memori dari M(m, r) akan menjadi subset dari M(m+1, r)
-> Suatu algoritma yang memiliki stack algorithm tidak akan mengalami Belady's Anomaly
Memprediksi Page Fault Rates
yah intinya gini aja sih. biasa di soal dikasih reference string dan ditanya page faultnya bakal ada berapa kalo page frame nya sekiansekian
nah dari contoh diatas page frame nya ada 4 (0-3)
awalnya kerjain aja kyk biasa, kl diatas sih pake cara FIFO
nah disini ada yg beda yaitu distance string.
Distance string adalah jarak dr angka yg ditemukan dari tempat awalnya (?)
contoh misalkan kolom 9, dia cari 3 dan 3 ada di page frame. nah si 3 ini naik berapa kotak keatas supaya bs jd plg atas (tapi kotak awal posisi dia diitung jg) jd hasilnya 4.
Setelah dapet distance string, kita bisa tau C vector nya. C vector adalah jumlah distance string nya.
C vector utk cth diatas:
C1 = 0
C2 = 1
C3 = 1
C4 = 2
C5 = 0
C6 = 0
C7 = 0
C8 = 0
C~ = 8
Dari C vector yg sudah diketahui kita bisa tau F vector. F vector adalah jumlah page fault yang akan terjadi bila memiliki page frame sebesar F.
F vector utk cth diatas adalah:
F1 = C2 + C3 + C4 + C5 + C6 + C7 + C8 + C~ = 12
F2 = C3 + C4 + C5 + C6 + C7 + C8 + C~ = 11
F3 = C4 + C5 + C6 + C7 + C8 + C~ = 10
F4 = C5 + C6 + C7 + C8 + C~ = 8
F5 = C6 + C7 + C8 + C~ = 8
F6 = C7 + C8 + C~ = 8
F7 = C8 + C~ = 8
Maksudnya adalah kalo misalkan jumlah page frame nya ada 1 (F1), maka akan terjadi 12 page fault. Dan seterusnya :)
Memory Management
-> Sistem Paging, tujuan: agar bs menjalankan program yang besar pada physical memory yg kecil
-> Segmentasi: pengalamatan 2 dimensi
Tujuan: untuk memudahkan pembuat program. Kenapa? karena biaya membuat software lebih besar dari biaya membuat hardware
Struktur file:
- Byte Sequence: file disimpan dan ditulis per byte
- Record sequence: isinya structure (1 record)
- Tree
Tipe file:
- Executable File: file yg berisi instruksi" yang dimengerti CPU
- Archive File: file yg digunakan utk menyimpan informasi (teks, gambar, video)
Pengaksesan File (pernah keluar di ujian!)
- Sequential Access: pengaksesan selalu dimulai dari awal dan pengakses berikutnya dilakukan secara berurutan. cth: linked list
- Random access: pengaksesan dilakukan secara acak. cth: array
- Direct Access, cth: hash table (array of linked list)
Ditemukan di Algo. FIFO
Stack Algorithm
-> Suatu algoritma yang memiliki stack algorithm tidak akan mengalami Belady's Anomaly
Memprediksi Page Fault Rates
nah dari contoh diatas page frame nya ada 4 (0-3)
awalnya kerjain aja kyk biasa, kl diatas sih pake cara FIFO
nah disini ada yg beda yaitu distance string.
Distance string adalah jarak dr angka yg ditemukan dari tempat awalnya (?)
contoh misalkan kolom 9, dia cari 3 dan 3 ada di page frame. nah si 3 ini naik berapa kotak keatas supaya bs jd plg atas (tapi kotak awal posisi dia diitung jg) jd hasilnya 4.
Setelah dapet distance string, kita bisa tau C vector nya. C vector adalah jumlah distance string nya.
C vector utk cth diatas:
C1 = 0
C2 = 1
C3 = 1
C4 = 2
C5 = 0
C6 = 0
C7 = 0
C8 = 0
C~ = 8
Dari C vector yg sudah diketahui kita bisa tau F vector. F vector adalah jumlah page fault yang akan terjadi bila memiliki page frame sebesar F.
F vector utk cth diatas adalah:
F1 = C2 + C3 + C4 + C5 + C6 + C7 + C8 + C~ = 12
F2 = C3 + C4 + C5 + C6 + C7 + C8 + C~ = 11
F3 = C4 + C5 + C6 + C7 + C8 + C~ = 10
F4 = C5 + C6 + C7 + C8 + C~ = 8
F5 = C6 + C7 + C8 + C~ = 8
F6 = C7 + C8 + C~ = 8
F7 = C8 + C~ = 8
Maksudnya adalah kalo misalkan jumlah page frame nya ada 1 (F1), maka akan terjadi 12 page fault. Dan seterusnya :)
Memory Management
-> Sistem Paging, tujuan: agar bs menjalankan program yang besar pada physical memory yg kecil
-> Segmentasi: pengalamatan 2 dimensi
Tujuan: untuk memudahkan pembuat program. Kenapa? karena biaya membuat software lebih besar dari biaya membuat hardware
Struktur file:
- Byte Sequence: file disimpan dan ditulis per byte
- Record sequence: isinya structure (1 record)
- Tree
Tipe file:
- Executable File: file yg berisi instruksi" yang dimengerti CPU
- Archive File: file yg digunakan utk menyimpan informasi (teks, gambar, video)
Pengaksesan File (pernah keluar di ujian!)
- Sequential Access: pengaksesan selalu dimulai dari awal dan pengakses berikutnya dilakukan secara berurutan. cth: linked list
- Random access: pengaksesan dilakukan secara acak. cth: array
- Direct Access, cth: hash table (array of linked list)
Sistem Operasi - Page Replacement Algorithm
Ada bbrp algo:
*) Optimal
*) FIFO
*) LRU
*) Second Chance
*) Clock
dll
Reference string: urutan sequence dr virtual page number pada saat program dieksekusi (biasa diket di soal)
cth soal:
diket ref. string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
dijalankan pada komputer dgn 3 page frame
berapa kali terjadi page fault jika digunakan algoritma:
a) Optimal
b) FIFO
c) LRU
d) clock
Kelemahan FIFO: kemungkinan program yang masin digunakan sdh dibuang karena pertama kali dikeluarkan
Diperbaiki menjadi second chance -> setiap page diberi R-bit, menggunakan linked list
Algoritma:
If R = 0 then Replace
If R = 1 then R = 0, cari page berikutnya sampe ketemu yg R = 0
Perbaikan FIFO dpt jg berupa clock.
Perbedaan clock dan second chance ?
(Comment dibawah kalo ada yg tau yaa wkwkwk)
*) Optimal
*) FIFO
*) LRU
*) Second Chance
*) Clock
dll
Reference string: urutan sequence dr virtual page number pada saat program dieksekusi (biasa diket di soal)
cth soal:
diket ref. string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
dijalankan pada komputer dgn 3 page frame
berapa kali terjadi page fault jika digunakan algoritma:
a) Optimal
b) FIFO
c) LRU
d) clock
Kelemahan FIFO: kemungkinan program yang masin digunakan sdh dibuang karena pertama kali dikeluarkan
Diperbaiki menjadi second chance -> setiap page diberi R-bit, menggunakan linked list
Algoritma:
If R = 0 then Replace
If R = 1 then R = 0, cari page berikutnya sampe ketemu yg R = 0
Perbaikan FIFO dpt jg berupa clock.
Perbedaan clock dan second chance ?
(Comment dibawah kalo ada yg tau yaa wkwkwk)
Sistem Operasi - Memory Management (Lanjutan)
Swapping (Harddisk -> Backing Store)
Program terdiri dari 3 bagian:
- Code -> tdk prnh berubah
- Data -> bs bertambah/kurang
- Stack -> bs bertambah/kurang
Pemantauan Memori -> agar dpt dgn cepat tau dimana memori dapat digunakan
Menggunakan bitmap dan linked list
Bitmap -> 1 blok memori dipantau dgn 1 bit. 0 = kosong, 1 = berisi
-> ukuran tetap
-> lambat
Linked List -> simpul" yang terkait
Dalam sebuah LL min. ada 2 field: data dan next.
Dari cth diatas, Linked List nya:
P 0 3 -> program dari 0 - 3 (offset 3)
H 3 2 -> Hole dari 3 offset 2
dst.
Contoh Soal!
Diket memori 1 GB
1 blok memori = 1KB
Besar memori yang dihabiskan utk pemantauan dgn bitmap?
Virtual Memory dan Physical Memory
Bila program memerlukan memori yang lebih besar dari besar physical memory yang tersedia, maka digunakan VIRTUAL MEMORY.
Virtual Memory -> menentukan seberapa bsr program yang dapat dieksekusi oleh CPU.
cth: program counter
bila PC hanya ada 2 bit maka hanya dapat mengeksekusi 2^2 program, yaitu dari 00 - 11.
Contoh soal:
Berdasarkan tabel diatas, Hitung physical address bila virtual address nya:
a) 2000
b) 5000
c) 10000
d) 35000
JAWABAN LATIHAN
a) First fit
90 417 212
100 500 200 300 600
10 83 88 (offset)
b) Next Fit
417 212 90
100500 200 300 600
83 88 510
c) Best Fit
90 417 212
100 500 200 300 600
10 83 88
d) Worst Fit
(gw blm tau jwbnnya, nnti diupdate yaa)
Pemantauan bitmap
1 GB/ 1KB = 2^20 blok memori
2^20 bit = 2^20/2^3 byte = 2^17 byte
2^17 byte = 128 KB :)
Menghitung physical address
a) 10192
b) 5000
c) 26384
d) Page Fault
Program terdiri dari 3 bagian:
- Code -> tdk prnh berubah
- Data -> bs bertambah/kurang
- Stack -> bs bertambah/kurang
Pemantauan Memori -> agar dpt dgn cepat tau dimana memori dapat digunakan
Menggunakan bitmap dan linked list
Bitmap -> 1 blok memori dipantau dgn 1 bit. 0 = kosong, 1 = berisi
-> ukuran tetap
-> lambat
Linked List -> simpul" yang terkait
Dalam sebuah LL min. ada 2 field: data dan next.
Dari cth diatas, Linked List nya:
P 0 3 -> program dari 0 - 3 (offset 3)
H 3 2 -> Hole dari 3 offset 2
dst.
Contoh Soal!
Diket memori 1 GB
1 blok memori = 1KB
Besar memori yang dihabiskan utk pemantauan dgn bitmap?
Virtual Memory dan Physical Memory
Bila program memerlukan memori yang lebih besar dari besar physical memory yang tersedia, maka digunakan VIRTUAL MEMORY.
Virtual Memory -> menentukan seberapa bsr program yang dapat dieksekusi oleh CPU.
cth: program counter
bila PC hanya ada 2 bit maka hanya dapat mengeksekusi 2^2 program, yaitu dari 00 - 11.
Contoh soal:
Berdasarkan tabel diatas, Hitung physical address bila virtual address nya:
a) 2000
b) 5000
c) 10000
d) 35000
JAWABAN LATIHAN
a) First fit
90 417 212
10 83 88 (offset)
b) Next Fit
417 212 90
100
83 88 510
c) Best Fit
90 417 212
10 83 88
d) Worst Fit
(gw blm tau jwbnnya, nnti diupdate yaa)
Pemantauan bitmap
1 GB/ 1KB = 2^20 blok memori
2^20 bit = 2^20/2^3 byte = 2^17 byte
2^17 byte = 128 KB :)
Menghitung physical address
a) 10192
b) 5000
c) 26384
d) Page Fault
Sistem Operasi - Memory Management
Memori dibagi menjadi 2:
*) No Memory Abstraction -> langsung mengakses ke physical memory
Umumnya digunakan pada:
- Komp. mainframe awal (sblm 2960)
- Minicomputer (sblm 1970)
- PC awal (sblm 1980)
*) Memory Abstraction
Contoh dlm gambar:
No memory abstraction dapat menjalankan bbrp program dalam waktu bersamaan. Proses di switch dengan swap.
RELOKASI: penyesuaian alamat program pada saat dipindah ke RAM
Relokasi ada 2:
- Jump Absolute
- Jump Relative -> tergantung posisinya
Analogi:
Fixed partition: kelas ada banyak, tapi jumlah bangku di masing" kelas 40.
Dynamic partition: seminar di FH, bangku yg dipake disesuaikan.
Multiple Input Queue:
+ Besarnya job" disesuaikan dengan besarnya partisi, menghemat memori
- Ada kemungkinan partisi yang kosong
Single Input Queue:
+ Tidak ada partisi yang kosong
- Ada kemungkinan job kecil dimasukkan ke partisi yang besar
Analogi fixed dan dyamic partition dlm bahasa C:
Fixed: array, cth int x[100];
Dynamic: linked list, cth:
int *ptr;
ptr = (int *) malloc (sizeof(int));
free(ptr);
Dynamic Partition
Fragmentation
-> Internal: sisa memory tdk dapat digunakan
-> eksternal: sisa memory (hole) msh dpt digunakan
*HOLE: free space dr hsl fragmentasi
Algoritma Pengalokasian Memori:
- First Fit: yang paling pertama muat yang dimasukkin
- Next Fit
- Best fit: cari tempat yang kalo dimasukin, sisa free spacenya paling kecil
- Worst fit: kebalikan best fit
Contoh Soal!!
Diketahui hole dengan urutan sbb: 100KB, 500KB, 200KB, 300KB, 600KB
Jika ada 3 proses dgn urutan sbb: 417KB, 212KB dan 90KB
Tentukan hole" mana yg akan dialokasikan jika digunakan algo:
a) First Fit
b) Next Fit
c) Best Fit
d) Worst Fit
(Jawaban di post selanjutnya. Stay tuned! (?))
*) No Memory Abstraction -> langsung mengakses ke physical memory
Umumnya digunakan pada:
- Komp. mainframe awal (sblm 2960)
- Minicomputer (sblm 1970)
- PC awal (sblm 1980)
*) Memory Abstraction
Contoh dlm gambar:
No memory abstraction dapat menjalankan bbrp program dalam waktu bersamaan. Proses di switch dengan swap.
RELOKASI: penyesuaian alamat program pada saat dipindah ke RAM
Relokasi ada 2:
- Jump Absolute
- Jump Relative -> tergantung posisinya
Fixed partition: kelas ada banyak, tapi jumlah bangku di masing" kelas 40.
Dynamic partition: seminar di FH, bangku yg dipake disesuaikan.
Multiple Input Queue:
+ Besarnya job" disesuaikan dengan besarnya partisi, menghemat memori
- Ada kemungkinan partisi yang kosong
Single Input Queue:
+ Tidak ada partisi yang kosong
- Ada kemungkinan job kecil dimasukkan ke partisi yang besar
Analogi fixed dan dyamic partition dlm bahasa C:
Fixed: array, cth int x[100];
Dynamic: linked list, cth:
int *ptr;
ptr = (int *) malloc (sizeof(int));
free(ptr);
Dynamic Partition
Fragmentation
-> Internal: sisa memory tdk dapat digunakan
-> eksternal: sisa memory (hole) msh dpt digunakan
*HOLE: free space dr hsl fragmentasi
Algoritma Pengalokasian Memori:
- First Fit: yang paling pertama muat yang dimasukkin
- Next Fit
- Best fit: cari tempat yang kalo dimasukin, sisa free spacenya paling kecil
- Worst fit: kebalikan best fit
Contoh Soal!!
Diketahui hole dengan urutan sbb: 100KB, 500KB, 200KB, 300KB, 600KB
Jika ada 3 proses dgn urutan sbb: 417KB, 212KB dan 90KB
Tentukan hole" mana yg akan dialokasikan jika digunakan algo:
a) First Fit
b) Next Fit
c) Best Fit
d) Worst Fit
(Jawaban di post selanjutnya. Stay tuned! (?))
Tuesday, October 27, 2015
Materi Sistem Basis Data (Bahan UTS) (1)
Pengantar
> Database = Kumpulan data" yang saling berhubungan
Contoh: data universitas bagian akademik
Data mahasiswa -> berhubungan dengan data Matkul -> berhubungan dengan data Dosen Pengampu
> Database Systems = essential components of everyday life in modern society
> Database dibuat untuk tujuan tertentu.
> Database merepresentasikan hal yang ada di dunia nyata -> mini world
yang disimpan datanya, di dunia nyata ada barangnya
> Database dapat memiliki Size kecil maupun besar
Contoh: buku telepon -> nama, nomor telpon
Katalog buku perpus -> nama, nomor rak, edisi, dll
Database Management System
> adalah kumpulan program-program yang membantu user membuat dan maintain database
> Meta-data: data tentang data
contohnya: data gender hanya boleh diisi dengan M/F, tidak dapat diisi dgn yang lain (diatur oleh meta data)
> Query: statement untuk manipulasi data
Contoh: dari database mahasiswa cuma mau ambil yang huruf depan namanya A
Characteristic of Database Approach:
1. Self-describing nature of database systems
contoh: ada data 14110110001#Dennis di sebuah file .txt
kalau di Dev-C, tipe datanya ditentukan saat di program
kalau di Database, ditentukan tipe datanya langsung di DataBase
2. Program dan data terpisah (program-data independence)
contoh: file .txt biasanya harus disimpan di file yg sama dengan programnya. Bila di database bisa terpisah
3. Insulation between programs and data, and data abstraction
Contoh: mau menambahkan kategori baru dalam database
4. Supprot multiple views of Data -> tergantung kebutuhan, data apa yang ditampilkan
Contoh: bagian keuangan bs liat mahasiswa udh lunas atau belum, tapi dia ga butuh liat nilai mahasiswa. Dosen gabutuh tau lunas/ngganya, tapi butuh liat nilainya
5. Sharing of data and multi user transaction processing
-> concurrency control = mengatur transaksi mana yang dilakukan duluan apabila ada tabrakan transaksi
-> ada 2 proses dalam transaksi
1) pengurangan/ perubahan saldo pengirim
2) penambahan saldo penerima
Ingat analogi transfer uang di ATM! Misalnya Kenny punya 10 juta Febrian punya 3 juta. Kenny mau transfer 3 juta ke Feb. Yang dilakukan ATM adalah mengurangi saldo punya Kenny, baru menambahkan saldo Feb
Advantage of using DBMS approach:
1. Controlling redundancy
2. Restricting unauthorized access
3. Providing storage structures for efficient query processing
4. Providing backup and recovery
5. Enforcing integrity constraints -> contohnya bila di DB mahasiswa udah ada data nama, maka di DB nilai tidak perlu ada kolom untuk data nama, ckup pakai primary key nya saja (nanti dibahas mengenai primary key)
When NOT to use DBMS?
- Program yang simpel
- Program yang real-time
- No multiple user access to data
Data Model
> menggambarkan struktur database
> ada 3 macam:
- High level/ conceptual data models -> paling mudah dimengerti
- Representational/ implementation data models
- Low level/ physical data model -> sudah dalam bentuk dtaabase
Contoh High-level:
Contoh Representational:
Database schema: deskripsi dari sebuah database. dibuat saat mendesain database dan tidak diharapkan untuk berganti terus-menerus. isi dari database schema berupa nama dari record types dan data items, serta beberapa tipe constraints
Three Schema Architecture:
Low-level = database di komputer
Data Independence
> kemampuan untuk mengubah schema pada satu level dalam database
> ada 2 macam:
- Physical data independence = mengubah internal schema tanpa memengaruhi conceptual schema dan external schema
- Logical data independence = mengubah conceptual schema tanpa memengaruhi external schema/application programs
DBMS Languages
> Data Definition Language (DDL) -> banyak dipakai oleh admin
Analogi: ticketer kereta api, menentukan siapa bisa masuk
contoh:
-> DROP : hapus objek di DB
-> CREATE
-> ALTER : mengubah struktur di DB
-> TRUNCATE
> Data Manipulation Language (DML)
Contoh:
-> SELECT
-> INSERT
-> UPDATE
-> DELETE
>Transaction Control
Contoh
-> COMMIT (berhasil)
-> ROLLBACK (gagal)
Database Systems
> Functional Requirements: sistem dapat berfungsi untuk user kategori apa (user/admin) -> what function do users need
> Data Requirements: untuk fungsi tersebut dapat berjalan, data apa saja yang dibutuhkan
Entities
- Entity (persegi panjang) = sesuatu yang memang ada di dunia nyata, bisa disentuh/ abstrak (tangible/intangible) contoh, mahasiswa, mata kuliah
- Attribute (oval) = data-data yang ada pada entity
- Relationship
Jenis-jenis atribut:
1. Simple/atomic attribute: data tdk dapat dipecah-pecah, contohnya umur
2. Composite: data dapat dipecah-pecah, contoh data alamat bisa dipecah jadi jalan, kota, kode pos
3. Multivalue: data dapat terdiri dari lebih dari 1 value, contoh nomor telepon seseorang dapat lebih dari satu
4. Stored attribute: data yang sudah ada/diinput
5. Derived attribute data yang dapat dihasilkan dari data lain, contoh data umur dapat dihasilkan dari data tanggal lahir
6. Complex attribute: gabungan multivalue dan composite, contoh jika seseorang dpaat memiliki lebih dr 1 rumah dan setiap alamat rumah dipecah datanya menjadi jalan, kode pos, kota
7. NULL values -> tidak sama dengan nol, tidak sama dengan blank space
Mengapa diperlukan?
1. Nilai tidak dapat dipakai, contoh mahasiswa masukin form yang harus isi jabatan kerja
2. Data tidak diketahui, contoh pendaftaran maba, nomor telpon belum diketahui
Entity Types dan Entity Set
- Entity Types: kategori
- Entity Set: detail" datanya
contoh: data karyawan
karyawan -> entity type
Nama: John Smith, Umur: 55, Tempat tinggal: Jln Scientia Residence -> entity set
Key attributes ( data digarisbawah)
= data yang pasti beda satu dengan lainnya
Value Set (domains) of attribute
= restriction" yang ada yntuk tiap data berbeda
= Contoh: gender hanya boleh M/F
Relationship ( belah ketupat )
- Unary (rekursif) : relationship type dengan 1 degree, contoh karyawan supervise karyawan lainnya
- Binary: satu relationship dengan 2 degree/ entity
- Ternary: satu relationship dengan 3 degree
- N-ary: satu relationship dengan > 3 degree
Cardinality Ratios for Binary Relationships
- 1:1
- 1:N atau N:1
- M:N
Contoh:
Attribute dari Relationship
> Hanya akan muncul jika telah terhubung antara 2 entity
Attribute bukan punya salah satu entity, melainkan relationshipnya
Strong VS Weak entity
> Strong entity: punya key attribute (yang digarisbawah)
> Weak entity: tidak punya key attribute, sehingga digantikan dengan partial key (garis bawah putus-putus)
Simbol-simbol:
> Database = Kumpulan data" yang saling berhubungan
Contoh: data universitas bagian akademik
Data mahasiswa -> berhubungan dengan data Matkul -> berhubungan dengan data Dosen Pengampu
> Database Systems = essential components of everyday life in modern society
> Database dibuat untuk tujuan tertentu.
> Database merepresentasikan hal yang ada di dunia nyata -> mini world
yang disimpan datanya, di dunia nyata ada barangnya
> Database dapat memiliki Size kecil maupun besar
Contoh: buku telepon -> nama, nomor telpon
Katalog buku perpus -> nama, nomor rak, edisi, dll
Database Management System
> adalah kumpulan program-program yang membantu user membuat dan maintain database
> Meta-data: data tentang data
contohnya: data gender hanya boleh diisi dengan M/F, tidak dapat diisi dgn yang lain (diatur oleh meta data)
> Query: statement untuk manipulasi data
Contoh: dari database mahasiswa cuma mau ambil yang huruf depan namanya A
Characteristic of Database Approach:
1. Self-describing nature of database systems
contoh: ada data 14110110001#Dennis di sebuah file .txt
kalau di Dev-C, tipe datanya ditentukan saat di program
kalau di Database, ditentukan tipe datanya langsung di DataBase
2. Program dan data terpisah (program-data independence)
contoh: file .txt biasanya harus disimpan di file yg sama dengan programnya. Bila di database bisa terpisah
3. Insulation between programs and data, and data abstraction
Contoh: mau menambahkan kategori baru dalam database
4. Supprot multiple views of Data -> tergantung kebutuhan, data apa yang ditampilkan
Contoh: bagian keuangan bs liat mahasiswa udh lunas atau belum, tapi dia ga butuh liat nilai mahasiswa. Dosen gabutuh tau lunas/ngganya, tapi butuh liat nilainya
5. Sharing of data and multi user transaction processing
-> concurrency control = mengatur transaksi mana yang dilakukan duluan apabila ada tabrakan transaksi
-> ada 2 proses dalam transaksi
1) pengurangan/ perubahan saldo pengirim
2) penambahan saldo penerima
Ingat analogi transfer uang di ATM! Misalnya Kenny punya 10 juta Febrian punya 3 juta. Kenny mau transfer 3 juta ke Feb. Yang dilakukan ATM adalah mengurangi saldo punya Kenny, baru menambahkan saldo Feb
Advantage of using DBMS approach:
1. Controlling redundancy
2. Restricting unauthorized access
3. Providing storage structures for efficient query processing
4. Providing backup and recovery
5. Enforcing integrity constraints -> contohnya bila di DB mahasiswa udah ada data nama, maka di DB nilai tidak perlu ada kolom untuk data nama, ckup pakai primary key nya saja (nanti dibahas mengenai primary key)
When NOT to use DBMS?
- Program yang simpel
- Program yang real-time
- No multiple user access to data
Data Model
> menggambarkan struktur database
> ada 3 macam:
- High level/ conceptual data models -> paling mudah dimengerti
- Representational/ implementation data models
- Low level/ physical data model -> sudah dalam bentuk dtaabase
Contoh High-level:
Contoh Representational:
Three Schema Architecture:
Low-level = database di komputer
Data Independence
> kemampuan untuk mengubah schema pada satu level dalam database
> ada 2 macam:
- Physical data independence = mengubah internal schema tanpa memengaruhi conceptual schema dan external schema
DBMS Languages
> Data Definition Language (DDL) -> banyak dipakai oleh admin
Analogi: ticketer kereta api, menentukan siapa bisa masuk
contoh:
-> DROP : hapus objek di DB
-> CREATE
-> ALTER : mengubah struktur di DB
-> TRUNCATE
> Data Manipulation Language (DML)
Contoh:
-> SELECT
-> INSERT
-> UPDATE
-> DELETE
>Transaction Control
Contoh
-> COMMIT (berhasil)
-> ROLLBACK (gagal)
Database Systems
> Functional Requirements: sistem dapat berfungsi untuk user kategori apa (user/admin) -> what function do users need
> Data Requirements: untuk fungsi tersebut dapat berjalan, data apa saja yang dibutuhkan
Entities
- Entity (persegi panjang) = sesuatu yang memang ada di dunia nyata, bisa disentuh/ abstrak (tangible/intangible) contoh, mahasiswa, mata kuliah
- Attribute (oval) = data-data yang ada pada entity
- Relationship
Jenis-jenis atribut:
1. Simple/atomic attribute: data tdk dapat dipecah-pecah, contohnya umur
2. Composite: data dapat dipecah-pecah, contoh data alamat bisa dipecah jadi jalan, kota, kode pos
3. Multivalue: data dapat terdiri dari lebih dari 1 value, contoh nomor telepon seseorang dapat lebih dari satu
4. Stored attribute: data yang sudah ada/diinput
5. Derived attribute data yang dapat dihasilkan dari data lain, contoh data umur dapat dihasilkan dari data tanggal lahir
6. Complex attribute: gabungan multivalue dan composite, contoh jika seseorang dpaat memiliki lebih dr 1 rumah dan setiap alamat rumah dipecah datanya menjadi jalan, kode pos, kota
7. NULL values -> tidak sama dengan nol, tidak sama dengan blank space
Mengapa diperlukan?
1. Nilai tidak dapat dipakai, contoh mahasiswa masukin form yang harus isi jabatan kerja
2. Data tidak diketahui, contoh pendaftaran maba, nomor telpon belum diketahui
Entity Types dan Entity Set
- Entity Types: kategori
- Entity Set: detail" datanya
contoh: data karyawan
karyawan -> entity type
Nama: John Smith, Umur: 55, Tempat tinggal: Jln Scientia Residence -> entity set
Key attributes ( data digarisbawah)
= data yang pasti beda satu dengan lainnya
Value Set (domains) of attribute
= restriction" yang ada yntuk tiap data berbeda
= Contoh: gender hanya boleh M/F
Relationship ( belah ketupat )
- Unary (rekursif) : relationship type dengan 1 degree, contoh karyawan supervise karyawan lainnya
- Binary: satu relationship dengan 2 degree/ entity
- Ternary: satu relationship dengan 3 degree
- N-ary: satu relationship dengan > 3 degree
Cardinality Ratios for Binary Relationships
- 1:1
- 1:N atau N:1
- M:N
Contoh:
Attribute dari Relationship
> Hanya akan muncul jika telah terhubung antara 2 entity
Attribute bukan punya salah satu entity, melainkan relationshipnya
Strong VS Weak entity
> Strong entity: punya key attribute (yang digarisbawah)
> Weak entity: tidak punya key attribute, sehingga digantikan dengan partial key (garis bawah putus-putus)
Simbol-simbol:
Teori Bahasa dan Automata - Soal Kuis
SOAL KUIS
1. RE = (a+b)^+ a*b
a. Buat Transition Diagram menggunakan epsilon-NFA !
b. Buat E-closurenya untuk menentukan DFA ekivalen!
c. Minimalisasi DFA tersebut!
2. Buatlah minimalisasi dari NFA berikut
3. Buatlah RE dari FSA dibawah ini!
1. RE = (a+b)^+ a*b
a. Buat Transition Diagram menggunakan epsilon-NFA !
b. Buat E-closurenya untuk menentukan DFA ekivalen!
c. Minimalisasi DFA tersebut!
2. Buatlah minimalisasi dari NFA berikut
3. Buatlah RE dari FSA dibawah ini!
