AOK - CPU Structures and Functions
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! (?))
