BAB II TEORI PERFORMANSI SISTEM 2.1
Konsep Dasar dan Ukuran Performansi
Konfigurasi dari elemen-elemen pada sistem komputer yang berhubungan dengan performansi sistem harus memenuhi suatu ukuran yang ditetapkan. Ada banyak kemungkinan pemilihan pengukuran performansi, diantaranya adalah ukuran system-
oriented atau user-oriented[4]. Ukuran system-oriented berhubungan dengan konsep throughput dan utilisasi. Throughput didefinisikan sebagai jumlah rata-rata request seperti transaksi, proses, pelanggan, job, dan lain-lain, yang diproses per satuan waktu. Utilisasi merupakan suatu ukuran persentase waktu, dimana resource sibuk. Sedangkan untuk ukuran performansi user-oriented, yaitu response time atau
turnaround time. Response time dan turnaround time berhubungan dengan cara pandang sistem terhadap waktu yang digunakan pada saat user memulai sebuah job pada sistem, sampai pada saat job tesebut memberikan jawaban, atau balasan yang dikembalikan ke user. Konsep dasar yang dibutuhkan dalam melakukan analisis performansi sistem komputer, dijelaskan seperti berikut. 2.1.1 Waktu Waktu merupakan konsep yang sangat mendasar dari semua ukuran performansi komputer, sehingga disebut dengan zeroth-order performance metric[5]. Dalam konteks analisis performansi komputer, waktu digunakan pada banyak metrik, seperti
service time, response time, round-trip time, memory latency, dan lain-lain. Sistem komputer menggunakan konsep interval waktu yang tetap. Interval ini mewakili frame waktu yang terbatas pada clock dari sistem komputer. Clock dari sistem komputer atau cycle time diukur dalam nanodetik (10-9 detik). Contohnya,
processor 1.5-GHz, menunjukkan bahwa processor tersebut memiliki clock cycle sekitar 0.67 nanodetik, atau 6.67-10 detik. Untuk mengetahui seberapa cepat data dan
instruksi dapat dikirim dari perangkat luar ke internal memori utama, dan seberapa cepat memori utama dapat mengirim informasi, dan instruksi ke processor, diukur dengan CPU speed[4]. 2.1.2 Event Waktu merupakan suatu ukuran yang penting, tetapi waktu berguna jika memiliki suatu cara untuk menggunakannya dalam pengukuran yang tepat. Dalam sistem komputer, suatu event menggambarkan suatu entitas dalam sebuah sistem, yang umumnya mewakili suatu tindakan, sebagai contoh, permulaan suatu clock cycle (Gambar 2.1) atau akhir dari clock cycle. Permulaan dari sebuah cycle yang mengeksekusi instruksi komputer, akhir cycle, membaca suatu lokasi memori, permulaan pengiriman sebuah blok data dari perangkat penyimpanan sekunder, dan permulaan sebuah proses atau task, juga merupakan sebuah event.
Waktu Gambar 2.1 Contoh dari sebuah clock komputer[4]. 2.1.3 Interval Pengukuran membutuhkan suatu domain atau environment, dimana pada sistem komputer, environment merupakan clock sistem dan cycle untuk mengeksekusi instruksi. Untuk mengukur item-item ini, maka diperlukan interval ekekusi. Interval merupakan suatu perioda waktu yang membatasi antara awal dari serangkaian event dan akhir dari serangkaian event (Gambar 2.2).
Gambar 2.2 Contoh Interval[4]. Pada Gambar 2.2, terlihat bahwa interval I1 terdiri dari time tag event kesatu dan time
tag event kedua. Interval digunakan untuk mengukur perioda eksekusi dari serangkaian event, atau perioda waktu antara eksekusi (Gambar 2.2 interval 2). Dua
interval adalah sama, jika merepresentasikan serangkaian event yang sama (saling berhubungan) dan interval waktu antara event adalah ekivalen. Dua interval yang merepresentasikan dua rangkaian event berbeda yang terpisah, dapat juga memiliki
interval yang ekivalen, tetapi tidak berhubungan. 2.1.4 Response
Response merupakan konsep yang penting dalam performansi sistem komputer. Response time merupakan interval waktu yang dimulai pada saat suatu request datang ke sebuah sistem, sampai request tersebut menyelesaikan layanan, dan meninggalkan sistem
[4,5]
. Kurva pada Gambar 2.3, menunjukkan hubungan antara
response time dengan load sistem. Interpretasi dari kurva ini adalah suatu cara untuk mengevaluasi sistem. Pada Gambar 2.3 terlihat bahwa response time dari serangkaian event yang diukur, tetap dalam range yang dapat ditoleransi (antara 0.1 dan 0.3) untuk load di bawah kirakira 60 persen dari kapasitas sistem yang diukur. Pada saat load meningkat di atas titik ini, maka response time akan meningkat secara eksponensial mencapai level saturasi pada saat sistem diberi load penuh, sehingga menghasilkan suatu asymptotic
response time yang mendekati tak terbatas.
Gambar 2.3 Response time vs load sistem[4]. 2.1.5 Independence Konsep penting lainnya dalam memodelkan dan menganalisis performansi adalah
independence. Suatu event bebas dari event yang lain, jika kejadian dari salah satu event tidak mempengaruhi outcome yang lain. Sebagai contoh, lemparan koin dan diikuti dengan lemparan mata dadu, adalah bebas, karena lemparan koin tidak memiliki pengaruh pada outcome. Independence event dalam sistem merupakan konsep penting untuk mengevaluasi sistem. Jika 2 event independent, maka tidak perlu mempertimbangkannya dalam pengujian response time terhadap yang lain dan
environment-nya. Pada suatu sistem komputer, dua program yang tidak dapat berjalan secara bersamaan dengan yang lain dapat dipandang sebagai item yang bebas, dan dianalisis secara bebas. Bahkan, meski kedua program tersebut berjalan pada hardware yang sama, dan mengunakan sistem operasi yang sama, karena kedua program tersebut tidak dapat mengganggu satu sama lain, dan tidak tergantung pada hubungan urutan, sehingga dapat dievaluasi secara terpisah. Hal ini menjadi bagian penting untuk memodelkan dan menganalisis sistem, untuk menentukan semua elemen dan hubungannya masing-masing.
2.1.6 Randomness
Randomness merupakan suatu properti dari sebuah event dan kemunculannya. Jika sebuah event adalah random, maka dinyatakan bahwa tidak ada suatu pola yang dapat dipetakan atas event tersebut, untuk menentukan kapan event tersebut akan terjadi lagi.
Randomness merupakan suatu konsep matematis. Dimana suatu bilangan random berasal dari random infinite source. Pada prakteknya, randomness merupakan serangkaian dari bilangan yang terbatas, dan salah satunya dibangkitkan secara acak. Sebagai contoh, melempar mata dadu, dimana sebelum dilempar, tidak dapat diketahui angka mana yang akan muncul; tetapi setelah dilempar hanya ada satu
outcome yang dihasilkan. Pada sebuah sistem komputer, event disebabkan oleh sumber eksternal (misalnya, penekanan tombol keyboard oleh user, panggilan jarak jauh ke server) dapat dipandang sebagai random event. Sehingga, kedatangan event tersebut tidak dapat diprediksi. 2.1.7 Workloads
Workload merepresentasikan suatu elemen yang sangat penting dalam masalah permodelan sistem komputer. Workload atau load menunjukkan suatu event atau serangkaian event yang ada dalam sistem untuk memodelkan sistem. Load merepresentasikan berapa banyak dari serangkaian event yang diberikan, dieksekusi selama perioda waktu yang diberikan. Sebagai contoh, jumlah instruksi per detik dan gabungan dari jenis-jenis instruksi untuk suatu eksekusi per detik. Parameter-parameter workload mengindikasikan jumlah dari transaksi, request, proses, customer atau job, yang bersaing untuk mendapatkan suatu resource dalam sebuah sistem. Model dengan transaction workload dihubungkan dengan kelas open model, karena jumlah kedatangan customer adalah tidak terbatas, sedangkan model
batch dan terminal workload, dihubungkan dengan kelas closed model,
karena
customer hanya bersikulasi di dalam sistem. Masing-masing dari kelas workload ini dibedakan sebagai berikut [3,4,5]. 1. Transaction workload, memiliki intensitas yang ditetapkan dengan sebuah parameter arrival rate λ , yang mengindikasikan kecepatan request (customer) yang datang. Transaction workload digunakan pada saat jumlah user tidak diketahui. Populasi yang efektif membuat request dapat dipandang tidak terbatas, karena kecepatan request yang datang ke suatu antrian, tidak dipengaruhi oleh jumlah request yang ada dalam sistem, baik yang dilayani atau yang menunggu layanan. Request yang sudah menyelesaikan layanan, akan meninggalkan sistem. 2. Batch workload, memiliki intensitas yang ditetapkan dengan parameter M, yang mengindikasikan jumlah rata-rata job (customer) yang aktif. Tujuan dari batch
workload adalah untuk memaksimalkan utilisasi waktu processor atau I/O, sehingga dapat selesai dalam waktu yang ditetapkan atau dikenal dengan batch
window. Karena proses batch tidak melibatkan setiap delay dari interaksi user, maka parameter think time tidak dapat digunakan. 3. Terminal workload, memiliki intensitas yang ditetapkan dengan 2 parameter yaitu M yang mengindikasikan jumlah terminal (customer) yang aktif, dan Z yang mengindikasikan panjang rata-rata waktu dimana customer menggunakan terminal (think time) diantara interaksi. 2.2
Distribusi Waktu
Distribusi waktu yang akan dijelaskan pada subbab ini, adalah distrbusi Poisson dan distribusi eksponensial, karena dalam penelitian ini digunakan asumsi Markovian. 2.2.1 Distribusi Poisson[4, 5] Distribusi Poisson digunakan untuk merepresentasikan kejadian diskrit yang terjadi secara acak dalam waktu kontinyu t. Contoh kejadiannya adalah jumlah kedatangan panggilan telepon ke suatu sentral atau jumlah pelanggan yang memasuki bank, dalam interval waktu tertentu, t = T. Perioda T dibagi menjadi interval dalam jumlah besar N. Jika events terjadi pada kecepatan tetap λ, probabilitas dimana ada n events dalam perioda T dinyatakan
dengan hasil perkalian dari probabilitas dimana ada satu event pada setiap n interval dengan lebar T/N, probabilitas waktu dimana tidak ada events dalam sisa interval
N − n: n
N! ⎛ λT ⎞ ⎛ λT ⎞ × Pr( n event ) = lim ⎜ ⎟ ⎜1 − ⎟ N →∝ N N ⎠ ⎝ ⎠ n!( N − n)! ⎝
N −n
(2.2.3.1)
Probability density function (PDF) adalah : f ( n, t ) = e − λ t
(λt )n , n!
n = 1,2,...
(2.2.3.2)
Persamaan (2.2.3.2) disebut diskrit probability mass function (PMF), pada saat
random variable adalah diskrit. Dari persamaan ini, maka probabilitas tidak ada event selama perioda T adalah: f (0, t ) = e − λt
(2.2.3.3)
Dengan kata lain, distribusi dari interval waktu adalah eksponensial. Hal ini merupakan dasar hubungan antara distribusi Poisson dan eksponensial. Jika jumlah events adalah distribusi poisson, maka interval waktu antara event adalah distribusi eksponensial. Karena, jika kedatangan ke sebuah antrian dihasilkan oleh proses Poisson, maka waktu interarrival merupakan distribusi eksponensial.
Cumulative distribution function (CDF) adalah : n
F ( n, t ) = ∑ f ( k , t )
(2.2.3.4)
k =0
Dalam batasan dimana jumlah menjadi tidak terbatas, maka pendekatan yang berhubungan dengan fungsi kontinyu eλt dan persamaan (2.2.3.4) menjadi: ∝
∑ f (k , t ) = e λ eλ − t
t
=1
(2.2.3.5)
k =0
Rata-rata dan variance dari distribusi Poisson adalah identik dengan persamaan (2.2.3.6).
E(n) = λt , V ar(n) = λt .
(2.2.3.6)
2.2.2 Distribusi Eksponensial[4][5] Distribusi eksponensial memiliki sifat Markovian, yaitu state dimana probabilitas kejadian dari suatu event, adalah sama sekali bebas dari eksperimen sebelumnya. Karakteristik ini juga disebut dengan sifat memoryless. Persamaan untuk distribusi eksponensial adalah :
⎧λe − λx f ( x) = ⎨ ⎩0
x>0 x<0
Grafik dari kurva eksponensial ditunjukkan pada Gambar 2.4.
λ
Gambar 2.4 Kurva distribusi eksponensial[4].
Gambar 2.5 Eksponensial density dan fungsi distribusi[4].
(2.2.4.1)
Dengan rata-rata = 1/λ dan variance = 1/λ2, maka fungsi distribusi eksponensial dinyatakan sebagai berikut:
⎧1 − e − λx x ≥ 0 f ( x) = ⎨ x<0 ⎩0
(2.2.4.2)
Fungsi densitas (x) eksponensial dan fungsi distribusi f(x) ditunjukan pada Gambar 2.5 untuk nilai parameter λ = 1. Distibusi eksponensial sering digunakan dalam analisis performansi komputer, untuk mengkarakterisasi waktu interarrival dan
service time. 2.3
Teori Antrian
Teori antrian merupakan suatu cabang dari teori probabilitas terapan, dimana aplikasinya mencakup bidang yang berbeda seperti jaringan komunikasi, sistem komputer, dan lain-lain. Subjek dari teori antrian dapat digambarkan sebagai suatu service center dan suatu populasi dari customers, dimana pada suatu waktu masuk ke service center untuk memperoleh layanan. Kasus yang sering terjadi adalah service center hanya dapat melayani customer dalam jumlah terbatas. Jika customer yang baru datang, mendapati layanan penuh, maka customer akan masuk ke waiting line dan menunggu sampai fasilitas layanan menjadi tersedia. Sehingga, dapat diidentifikasi 3 elemen utama dari suatu service center yaitu populasi customer, fasilitas layanan dan waiting
line. Sehingga Antrian merupakan suatu paradigma untuk menggambarkan sebuah waiting line atau buffer[6]. Sebagian besar dari sistem nyata dapat dibagi menjadi komponen-komponen yang dapat dimodelkan dengan konsep antrian. Ide dasar dari konsep ini diambil dari pengalaman sehari-hari, misalnya antrian pada kasir di supermarket. Sebuah antrian terdiri dari sebuah sistem, dimana terdapat user yang membutuhkan layanan sistem pada interval waktu tertentu, dan meninggalkan sistem. Dimana user dilayani dalam sistem oleh satu atau banyak service center[7].
Gambar 2.6, memperlihatkan suatu sistem dengan satu service center, dan Gambar 2.7 menunjukkan suatu sistem dengan beberapa service center yang identik dan paralel. Dimana customer datang pada suatu service center, menunggu dalam antrian jika tidak ada server yang tersedia, kemudian menerima layanan dari server dan meninggalkan sistem.
Gambar 2.6 Antrian dengan service center tunggal[7, 8]. Buffer Antrian Server 1 Kedatangan Customer
Buffer Antrian Server 2
Keberangkatan Customer
Server N Buffer Antrian
Gambar 2.7 Antrian dengan beberapa service center paralel[7, [8]. 2.4
Model Jaringan Antrian
Jaringan antrian merupakan suatu jaringan yang dihubungkan dengan suatu antrian, yang dapat menggambarkan suatu sistem komputer. Antrian dalam jaringan antrian ini dapat terdiri dari; sebuah resource atau beberapa resource (misalnya CPU, disk dan lain-lain), dan antrian dari request yang menunggu untuk menggunakan
resource. Jaringan antrian merupakan kumpulan dari service center yang mewakili resource sistem, dan customer atau request yang mewakili user atau transaksi. Pada model jaringan antrian dengan service center tunggal seperti pada Gambar 2.6, memiliki 2 parameter. Pertama adalah menentukan intensitas workload, kedua adalah
menentukan service demand[3], yaitu rata-rata layanan yang dibutuhkan oleh seorang
customer. Dengan menetapkan nilai dari kedua parameter ini, maka dapat digunakan untuk mengevaluasi model dengan menyelesaikan beberapa persamaan, yang menghasilkan ukuran-ukuran kinerja seperti utilisasi (ukuran waktu server sibuk),
residence time (rata-rata waktu yang dibutuhkan pada service center untuk satu customer, baik ketika menunggu atau menerima layanan), queue length (rata-rata jumlah customer pada service center yang menunggu layanan) dan throughput (kecepatan dimana customer meninggalkan sercive center). Sedangkan pada model dimana terdapat beberapa service center, seperti Gambar 2.7, sama dengan parameter pada model service center tunggal, yaitu menentukan intensitas workload,
yang merupakan kecepatan dari kedatangan customer dan
menentukan service demand, tetapi pada service demand, ditetapkan untuk setiap
service center. Intensitas workload pada model ini, berhubungan dengan kecepatan user memberikan sebuah transaksi ke sistem, dan service demand pada setiap service center berhubungan dengan kebutuhan total layanan per transaksi, yang berhubungan dengan resource dalam sistem. Pada sistem ini customer datang, beredar diantara
service center, dan kemudian keluar. 2.5
Hukum-Hukum Dasar Performansi
Pada subbab ini, dijelaskan sejumlah kuantitas yang penting dan diperkenalkan notasi-notasi yang akan digunakan untuk kuantitas ini, memperoleh berbagai hubungan aljabar antara kuantitas ini, dan dikenal dengan Fundamental Laws[3,5,6,7,8]. 2.5.1
Hukum Utilisasi
Gambar 2.8 menunjukkan service center tunggal, yang dilihat sebagai antrian
resource tungal, sehingga utilisasi (Ui) dari resource didefenisikan sebagai persentase waktu dimana resource sibuk. Jika antrian i tersebut dimonitor selama τ detik, dan menemukan resource sibuk selama Bi detik, maka diperoleh utilisasi,
Ui =
Bi
τ
. Diasumsikan bahwa selama interval τ yang sama, C0 transaksi telah
selesai dari antrian. Hal ini berarti bahwa rata-rata throughput dari antrian adalah
Xi =
C0
τ
. Dengan menggabungkan hubungan rata-rata throughput ini dengan
defenisi utilisasi, maka diperoleh persamaan (2.5.1.1).
Ui =
Bi
τ
=
Bi × X i = Si × X i C0
(2.5.1.1)
Persamaan (2.5.1.1) di atas menyatakan bahwa rata-rata waktu resource sibuk per transaksi, merupakan rata-rata service time (Si) per transaksi, yang diperoleh dari total waktu resource sibuk (Bi), dibagi dengan jumlah transaksi yang dilayani selama perioda waktu yang dimonitor. Pada kondisi equilibrium, λi = X i , dan service time
Si = 1 , maka diperoleh persamaan (2.5.1.2).
μ
U i = S i × X i = S i × λi = λi × 1
λi μi = μ i
(2.5.1.2)
Utilisasi dapat juga diinterpretasikan sebagai jumlah rata-rata transaksi dalam
resource, karena ada satu transaksi yang menggunakan resource selama Ui persen waktu dan nol transaksi selama (1- Ui) persen waktu. Untuk kasus multiple service center seperti yang ditunjukkan pada Gambar 2.9, yang memiliki banyak antrian resource, maka utilisasi didefenisikan sebagai jumlah ratarata transaksi yang menggunakan suatu resource, dan dinormalisasikan dengan jumlah resource, maka diperoleh persamaan (2.5.1.3) untuk utilisasi dari antrian m resource.
U i = Si ×
Xi
m
(2.5.1.3)
2.5.2 Hukum Forced Flow Dengan defenisi dari rata-rata jumlah kunjungan Vi, dimana setiap penyelesaian transaksi harus melalui Vi kali, pada rata-rata, dari antrian i. Sehingga, jika X0 transaksi selesai per satuan waktu, maka Vi × X 0 transaksi akan mengunjungi antrian
i per satuan waktu. Sehingga, diperoleh persamaan (2.5.2.1) untuk rata-rata throughput dari antrian i. X i = Vi × X 0 .
(2.5.2.1)
Persamaan (2.5.2.1) di atas dikenal dengan hukum Forced Flow. 2.5.3 Hukum Service Demand Total waktu yang dibutuhkan oleh sebuah request pada suatu server dapat dibagi menjadi 2 jenis interval; yaitu service time dan waiting time. Service time (Si), merupakan perioda waktu selama request menerima layanan dari suatu resource (misalnya, CPU dan disk). Sedangkan waktu yang dibutuhkan oleh sebuah request untuk menunggu mendapatkan layanan dari resource i, disebut dengan waiting time (Wi). Jumlah dari service time ( Si ), untuk sebuah request pada resource i, dikalikan dengan
rata-rata jumlah kunjungan ( Vi ) disebut dengan service demand dan
dilambangkan dengan (Di), sehingga diperoleh persamaan (2.5.3.1).
Di = Vi × S i
(2.5.3.1)
Dengan persamaan (2.5.3.1) di atas, jika dihubungakan dengan throughput dan utilisasi sistem, dan menggabungkan hukum Utilisasi dengan Forced Flow, maka diperoleh persamaan (2.5.3.2).
Di = Vi × S i = ⎛⎜ ⎝
Xi
⎞ × ⎛U i ⎞ = Ui X 0 ⎟⎠ ⎜⎝ X i ⎟⎠ X0
(2.5.3.2)
2.5.4 Hukum Little’s
Gambar 2.8 Kotak Little’s[5]. Kotak pada Gambar 2.8 di atas, dapat berisi apa saja, contoh yang paling sederhana adalah disk, atau yang kompleks adalah internet. Diasumsikan bahwa customer datang ke black box tersebut menggunakan rata-rata R detik dalam black box, dan kemudian meninggalkan black box tersebut. Rata-rata
kecepatan keberangkatan
yaitu throughput dari black box adalah X customer/detik dan jumlah rata-rata
customer dalam black box adalah N.
τ
Gambar 2.9 Grafik hubungan n(t) terhadap t[5]. Pada Gambar 2.9 terlihat sebuah grafik jumlah customer n(t) di dalam black box pada waktu t. Misalkan, aliran customer dimulai dari waktu 0 sampai waktu τ . Maka, jumlah rata-rata customer selama interval tersebut adalah sama dengan jumlah semua hasil perkalian dari k × f k , dimana k merupakan jumlah customer dalam black
box, dan fk merupakan persentase waktu dimana k customer ada dalam black box. fk
=
rk
τ , dimana rk adalah total waktu dimana ada k customer dalam black box.
Sehingga diperoleh persamaan (2.5.4.1).
N = ∑k × fk = ∑ k × k
k
rk
τ
(2.5.4.1)
Dengan mengalikan dan membagi sisi bagian kanan dari persamaan (2.5.4.1) dengan jumlah customer C0, maka diperoleh persamaan (2.5.4.2) untuk keberangkatan dari
black box dalam interval [0,τ ] .
N=
C0
τ
C0
τ
×
∑
k
k × rk
C0
(2.5.4.2)
merupakan throughput X, maka persamaan (2.5.4.2) di atas menjadi jumlah total
customer (customer × detik) yang diakumulasi dalam sistem. Jika dibagi jumlah ini dengan jumlah total customer C0 yang selesai, maka diperoleh rata-rata waktu R, setiap customer dalam black box, sehingga diperoleh persamaan (2.5.4.3).
N = X ×R
(2.5.4.3)
Jika hukum Little’s ini diaplikasikan untuk sekumpulan m resource, maka diperoleh persamaan (2.5.4.4).
N i = X i × Ri 2.6
(2.5.4.4)
Input Parameter Performansi Model[3, 5]
Input Parameter untuk performansi model menggambarkan konfigurasi hardware,
software dan workload sistem. Parameter-parameter ini terdiri dari 4 kelompok informasi, yaitu sebagai berikut: 1. queue atau device, 2. kelas workload,
3. intensitas workload, 4. service demand. 2.6.1 Queue atau device Langkah pertama dalam menentukan input parameter yaitu menentukan antrian untuk membangun sebuah model, dimana dipilih antrian yang relevan untuk performansi model, dan menentukan komponen-komponen untuk performansi model. Sebagai contoh, suatu model untuk sistem terdistribusi terdiri dari file server dan workstation yang dihubungkan melalui LAN. Dalam contoh ini, sistem digambarkan dengan sebuah model jaringan antrian open yang terdiri dari 3 antrian, yaitu satu processor dan 2 disk. Workstation digambarkan dengan kecepatan kedatangan request yang read /write, dan dihasilkan oleh workstation. 2.6.2 Kelas Workload Langkah kedua dalam menentukan input parameter untuk performansi model adalah menentukan tipe kelas workload. Tergantung pada cara suatu kelas dilihat oleh sistem, dan dari jumlah customer dalam sistem apakah tak terbatas, atau dalam jumlah yang tetap, maka kelas workload dapat diklasifikasikan menjadi open dan
closed. Pada kelas open, jumlah customer atau request dalam sistem adalah tidak terbatas. Dimana, customer datang, menggunakan berbagai resource, dan kemudian meninggalkan sistem. Sedangkan pada kelas closed, memiliki jumlah request atau
customer yang tetap. Tetapi terkadang suatu sistem dapat terdiri dari gabungan dari kelas open dan closed, dan disebut dengan mixed queueing network model. 2.6.3 Intensitas Workload Parameter-parameter workload mengindikasikan jumlah dari transaksi, request, proses, customer atau job, yang bersaing untuk mendapatkan suatu resource dalam sebuah sistem. Intensitas workload sudah dijelaskan pada subbab 2.2.7. 2.6.4 Service Demand
Service demand dari sebuah request pada suatu antrian merupakan jumlah total dari service time yang dibutuhkan oleh request selama eksekusi pada suatu resource.
Jumlah dari service time ( Si ), untuk sebuah request pada resource i, dikali dengan rata-rata jumlah kunjungan ( Vi ) akan menghasilkan service demand dan dilambangkan dengan (Di), sehingga diperoleh Di = Vi × S i . Pandangan lain dari service demand adalah diperoleh dari pengukuran data. Jika sistem dimonitor selama perioda waktu τ , maka utilisasi dari resource i adalah Ui, yang menyatakan bahwa sistem sibuk selama U i × τ satuan waktu. Jika dihitung jumlah request yang selesai selama perioda waktu tersebut adalah C0 , maka diperoleh service demand adalah: Di = U i × τ 2.7
C0
.
Level Performansi Model Sistem
Performansi model dapat dikembangkan pada level
yang berbeda. Level
performansi model sistem ini memandang sebuah sistem sebagai suatu black box. Dalam hal ini, detil dari internal black box tidak dimodelkan secara eksplisit, tetapi
throughput dari black box yang akan menjadi pertimbangan. Fungsi throughput X 0 (k ) , dinyatakan sebagai rata-rata throughput dari black box, sebagai suatu fungsi dari jumlah k request yang ada dalam black box. Level performansi model sistem ini direpresentasikan dengan state transition diagram (STD), yang menggambarkan
state dimana suatu sistem dapat melihat bagaimana transisi dari satu state ke state yang lain. Pada bagian ini hanya akan dijelaskan model dengan populasi yang tidak terbatas atau infinite dengan antrian yang terbatas (finite) dan tidak terbatas (infinite). 2.7.1 Simple Server Model I – Infinite Population/Infinite Queue
Infinite population adalah jika suatu sistem dapat diakses oleh suatu populasi yang sangat besar, dimana jumlah user tidak diketahui dan sangat besar, yang berarti bahwa arrival rate dari request ke suatu sistem tidak dipengaruhi oleh jumlah
request yang sudah ada dan sedang diproses. Dan sistem tidak akan menolak setiap
request, sehingga semua request yang datang akan mengantri untuk mendapat layanan. Asumsi ini dikenal dengan infinite queue. Asumsi yang digunakan untuk menganalisis sistem adalah bersifat operational
equilibrium. Dimana jumlah request yang ada dalam sistem pada awal interval observasi adalah sama dengan jumlah request yang ada pada akhir interval.
Request yang datang ke sistem pada kecepatan λ request/detik, akan mengantri untuk suatu layanan, dan mendapatkan layanan pada kecepetan μ request/detik, dan kemudian meninggalkan sistem. •
Persentase Waktu Server Memiliki k Request
Deskripsi state dalam suatu sistem merupakan parameter tunggal, yaitu jumlah
request yang ada dalam sistem, baik yang menunggu atau menerima layanan. Dimana tidak akan dipertimbangkan bagaimana sistem mencapai suatu state k tertentu, atau berapa lama sistem berada dalam state tersebut. Yang menjadi pertimbangan adalah masalah sistem ada pada state k. Hal ini dikenal dengan asumsi
memoryless atau markovian. State dinyatakan dengan integer 0,1,2,K , k . Gambar 2.10 menunjukkan sebuah state transition diagram (STD), dimana setiap state direpresentasikan dengan lingkaran. Transisi antara state yang berhubungan dalam sistem, direpresentasikan dengan tanda panah. Jika suatu request datang ke suatu sistem, dimana sistem memiliki k
request, maka state sistem adalah k+1. Tipe transaksi yang terjadi pada kedatangan request, dan kecepatan dari transisi yang terjadi adalah arrival rate ( λ transisi/detik). Dan jika sistem memiliki k request, dan salah satunya telah selesai, maka state menjadi k-1. Transisi terjadi pada kecepatan μ yaitu kecepatan request selesai. Karena digunakan asumsi operational equilibrium, maka aliran transisi menuju state
k akan sama dengan aliran transisi yang keluar dari state tersebut. Hal ini dikenal dengan prinsip flow equilibrium equation atau flow in = flow out.
Flow in = Flow out μ p1 = λ p 0
μ p2 = λ p1
(2.7.1.2)
. . . = . . .
(2.7.1.3)
μ pk
λ 0
λ 1
μ
(2.7.1.1)
λ pk
λ
λ
λ
2
k
μ
μ
μ
μ
Jumlah request dalam sistem
Gambar 2.10 State transition diagram – infinite population/infinite queue[5]. Jika digabungkan persamaan (2.7.1.1) sampai persamaan (2.7.1.3), maka diperoleh persamaan (2.7.1.4). k
⎞ ⎛λ⎞ λ λ ⎛λ p k = p k − 1 = ⎜⎜ p k − 2 ⎟⎟ = L = p0 ⎜⎜ ⎟⎟ , k = 0,1,... μ μ⎝μ ⎠ ⎝μ⎠
(2.7.1.4)
Dari persamaan (2.7.1.4) diperoleh pk sebagai suatu fungsi dari p 0 untuk semua nilai k = 1,2,... . Dalam hal ini, sistem hanya memiliki satu state yang mungkin setiap saat. Sehingga, jumlah persentase waktu dimana sistem ada pada suatu state, dari 0 sampai ∞ sama dengan satu. k
⎛λ⎞ p 0 + p1 + p 2 + L + p k + L = ∑ p k = ∑ p 0 ⎜⎜ ⎟⎟ = 1 k =0 k =0 ⎝μ⎠ ∝
∝
(2.7.1.5)
Diperoleh persentase sistem idle pada persamaan (2.7.1.6). k ⎡∝ ⎛λ⎞ ⎤ p 0 = ⎢∑ p 0 ⎜⎜ ⎟⎟ ⎥ ⎢⎣ k =0 ⎝ μ ⎠ ⎥⎦
−1
= 1−
λ μ
(2.7.1.6)
Dari persamaan (2.7.1.4) dan (2.7.1.6), diperoleh persentase waktu dimana ada k
request pada server adalah: k
k
⎛λ⎞ ⎛ λ ⎞⎛ λ ⎞ p k = p0 ⎜⎜ ⎟⎟ = ⎜⎜1 − ⎟⎟⎜⎜ ⎟⎟ , k = 0,1,... ⎝μ⎠ ⎝ μ ⎠⎝ μ ⎠ •
(2.7.1.8)
Utilisasi Sistem
Utilisasi dari sebuah sistem dapat diartikan sebagai persentase waktu dimana sistem sibuk. Utilisasi dilambangkan dengan U.
U = 1 − p0 =
λ μ
(2.7.1.9)
Sehingga persentase waktu dimana ada k request pada server menjadi p k = (1 − U )U k , k = 0,1,...
•
Jumlah Rata-rata Request dalam Sistem
Setelah diketahui nilai pk , maka dengan mudah dapat ditentukan jumlah rata-rata
request N pada sistem dengan menggunakan defenisi rata-rata. ∝
∝
∝
k =0
k =0
k =0
N = ∑ k × p k = ∑ k × (1 − U ) U k = (1 − U ) ∑ k × U k
Pada penyajian terkahir
∑
∝ k =0
k ×U k =
(2.7.1.10)
U , untuk U < 1, adalah pada (1 − U )2
persamaan (2.7.1.11)
N=
U (1 − U )
(2.7.1.11)
•
Rata-rata Throughput Sistem
Throughput dari sistem adalah μ pada saat ada paling sedikit satu request yang sedang diproses, hal ini terjadi selama persentase waktu sama dengan U. Throughput sama dengan 0 pada saat server idle. Sehingga rata-rata throughput X sistem ditunjukkan pada persamaan (2.7.1.12). ⎛λ⎞ X = (U × μ ) + (0 × (1 − U ) ) = ⎜⎜ ⎟⎟ μ = λ ⎝μ⎠
(2.7.1.12)
Throughput yang diharapkan adalah X= λ , karena tidak ada request yang hilang pada sistem. Sehingga, pada kondisi equilibrium, rata-rata arrival rate akan sama dengan rata-rata departure rate. •
Rata-rata Response Time
Untuk menghitung rata-rata response time (R), digunakan persamaan hukum Little’s. Dimana untuk throughput (X), dihitung dengan menggunakan persamaan (2.7.1.12) dan jumlah rata-rata request ( N ), dihitung dengan menggunakan persamaan (2.7.1.11), sehingga diperoleh persamaan (2.7.1.13).
R=
( ) (1 − U ) = ⎛⎜⎝ 1μ ⎞⎟⎠
N U = λ X
Dimana S = 1
(1 − U ) = S
(1 − U )
(2.7.1.13)
μ merupakan rata-rata service time dari sebuah request pada sistem.
Pada saat utilisasi sangat rendah, yaitu U mendekati 0, maka rata-rata response time akan sama dengan rata-rata service time. Hal ini diharapkan karena tidak ada waktu yang digunakan untuk menunggu layanan. Pada saat utilisasi sangat tinggi, yaitu U mendekati 1, maka R akan menuju tak hingga, karena denominator pada persamaan (2.7.1.13) akan menuju nol. 2.7.2 Simple Server Model II – Infinite Population/Finite Queue Pada model ini, kedatangan request yang menemukan ada W request dalam sistem baik diantrian atau yang sedang diproses, akan ditolak. Beberapa sistem membatasi jumlah request yang dapat ditangani untuk menjamin suatu performansi yang baik.
Karena sistem akan menolak setiap request tambahan pada saat ada W request dalam sistem, maka state yang mungkin terjadi adalah 0,1,…,W. Kedatangan request yang menemukan k (k < W) request dalam sistem, menyebabkan suatu transisi ke state k+1 pada kecepatan λ , dan menyelesaikan request pada state k (k=1,…,W), menyebabkan transisi ke state k-1 dengan kecepatan μ . Gambar 2.11 menunjukkan State Transition Diagram (STD) untuk kasus ini.
λ
λ
λ
λ
λ
λ
μ
μ
μ
μ
μ
μ
Gambar 2.11 State transition diagram – infinite population/finite queue[5]. •
Persentase Waktu Server Memiliki k Request k
⎛λ⎞ p k = p 0 ⎜⎜ ⎟⎟ , k = 1,...,W ⎝μ⎠
(2.7.2.1)
Perbedaan model untuk finite queue ini dengan infinite queue adalah pada p0, dimana pada model ini memiliki jumlah state yang terbatas. Sehingga diperoleh persamaan (2.7.2.2). ⎡ ⎛ λ ⎞W +1 ⎤ ⎢1 − ⎜⎜ ⎟⎟ ⎥ k W μ ⎛λ⎞ p 0 + p1 + p 2 + L + pW = p 0 ∑ ⎜⎜ ⎟⎟ = p 0 ⎢⎢ ⎝ ⎠ ⎥⎥ = 1 ⎛λ⎞ k =0 ⎝ μ ⎠ ⎢ 1 − ⎜⎜ ⎟⎟ ⎥ ⎢⎣ ⎝ μ ⎠ ⎥⎦
(2.7.2.2)
Persentase dimana sistem idle ditunjukkan pada persamaan (2.7.2.3)
⎛λ⎞ 1 − ⎜⎜ ⎟⎟ ⎝μ⎠ p0 = W +1 ⎛λ⎞ 1 − ⎜⎜ ⎟⎟ ⎝μ⎠
(2.7.2.3)
Dari persamaan (2.7.2.1) dan (2.7.2.3), diperoleh persentase waktu dimana ada k request pada server adalah ditunjukkan pada persamaan (2.7.2.4). ⎛λ⎞ 1 − ⎜⎜ ⎟⎟ ⎛λ⎞ ⎝μ⎠ p k = p0 ⎜⎜ ⎟⎟ = W +1 ⎝μ⎠ ⎛λ⎞ 1 − ⎜⎜ ⎟⎟ ⎝μ⎠ k
•
k
⎛λ⎞ ⎜⎜ ⎟⎟ , ⎝μ⎠
k = 0,K , W
(2.7.2.4)
Utilisasi Sistem
Utilisasi dari sebuah sistem adalah persentase waktu dimana sistem tidak idle. Utilisasi pada model infinite queue adalah U = 1 − p0 , dan p0 dinyatakan dengan persamaan (2.7.2.3), sehingga diperoleh persamaan (2.7.2.5).
U=
•
W ⎛⎜ λ ⎞⎟ ⎡1 − ⎛⎜ λ ⎞⎟ ⎤ ⎝ μ ⎠ ⎢⎣ ⎝ μ ⎠ ⎥⎦
1 − ⎛⎜ λ ⎞⎟ ⎝ μ⎠
(2.7.2.5)
W +1
Jumlah Rata-rata Request Dalam Sistem
Untuk jumlah rata-rata request N pada sistem ditunjukkan pada persamaan (2.7.2.6). W
W
k =0
k =0
N = ∑ k × p k = p 0 ∑ k (λ μ )
Tetapi menggunakan
∑
W k =0
k
(2.7.2.6)
[
]
k × a k = W × a W + 2 − W × a W +1 + a (1 − a ) digabungkan 2
dengan p0 pada persamaan (2.7.2.3) maka diperoleh persamaan (2.7.2.7).
N=
(λ μ ) [W (λ μ )W +1 − (W + 1) (λ μ )W [1 − (λ μ )W +1 ] (1 − (λ μ ))
]
+1
(2.7.2.7)
•
Rata-rata Throughput Sistem
Throughput (X) dari sistem adalah μ pada saat sistem sibuk (persentase waktu dimana sistem sibuk merupakan utilisasi), dan nol pada saat server idle. Sehingga rata-rata throughput (X) sistem ditunjukkan pada persamaan (2.7.2.8).
X = U × μ + 0 × (1 − U ) =
•
[
λ 1 − (λ μ )W W +1 1 − (λ μ )
]
(2.7.2.8)
Rata-rata Response Time
Untuk menghitung rata-rata response time (R) pada model ini, juga digunakan persamaan hukum Little’s. Dimana untuk throughput (X), dihitung dengan menggunakan persamaan (2.7.2.8), dan jumlah rata-rata request ( N ), dihitung dengan menggunakan persamaan (2.7.2.7), sehingga diperoleh persamaan (2.7.2.9).
[
]
N S W (λ μ ) − (W + 1)(λ μ ) + 1 R= = W X 1 − (λ μ ) (1 − (λ μ )) Dimana S = 1 •
W +1
[
W
]
(2.7.2.9)
μ adalah rata-rata service time dari sebuah request pada sistem.
Probablitas Lost
Pada sistem dengan finite queue, metrik performansi yang penting adalah persentase dari request yang hilang (lost), yang disebabkan karena antrian penuh, dinyatakan dengan pw, karena request hanya akan hilang ketika sistem berada pada state W, sehingga ploss = pw. ⎧ ⎛ λ ⎞W ⎪ p 0 ⎜⎜ ⎟⎟ ⎪ pW = ⎨ ⎝ μ ⎠ ⎪ 1 ⎪⎩W + 1
U ≠1
(2.7.2.10) U =1
2.8
Single Class Open Queueing Network
Sebuah antrian dilambangkan dengan fungsi S(n) yang merepresentasikan service time per request pada saat ada n request dalam antian. Jumlah request n dalam antrian disebut dengan panjang antrian. Ada 3 jenis resource dalam model jaringan antrian yaitu sebagai berikut: 1.
load independent resource : menggambarkan resource dimana ada antrian, tetapi rata-rata service time tidak tergantung pada load, yaitu S(n)=S, untuk semua nilai n, seperti yang terlihat pada Gambar 2.12a,
2.
load dependent resource : digunakan untuk menggambarkan resource dimana ada antrian, dan rata-rata service time tergantung pada load, yaitu S(n) merupakan fungsi arbitrary dari n, seperti yang terlihat pada Gambar 2.12b,
3.
delay resource : mengindikasikan situasi dimana tidak ada antrian. Sehingga, total waktu yang dibutuhkan oleh suatu request pada sebuah delay resource adalah request service time. Fungsi rata-rata service time tidak tergantung pada jumlah request yang ada pada resource, yaitu S(n)=S untuk semua nilai n, seperti yang terlihat pada Gambar 2.12c.
Gambar 2.12 Jenis resource pada jaringan antrian[5]. Pada jaringan antrian single class open, semua resource dipandang sebagai delay atau load independent resource. Notasi-notasi yang akan digunakan adalah sebagai berikut. •
λ : rata-rata arrival rate request ke jaringan antrian.
•
K : jumlah antrian.
•
X 0 : rata-rata throughput dari jaringan antrian. Pada open sistem dengan operational equilibrium, rata-rata throughput adalah sama dengan rata-rata arrival rate. Sehingga X 0 = λ .
•
Vi : rata-rata jumlah kunjungan ke antrian i oleh sebuah request.
•
S i : rata-rata service time dari sebuah request pada antrian i per kunjungan ke antrian.
•
Wi : rata-rata waiting time dari sebuah request pada antrian i per kunjungan ke antrian.
•
X i : rata-rata throughput antrian i.
•
Ri : rata-rata response time dari sebuah request pada antrian i, didefenisikan sebagai jumlah rata-rata waiting time ditambah rata-rata service time per kunjungan ke antrian. Sehingga, Ri = Wi + S i .
•
Ri' : rata-rata residence time dari sebuah request pada antrian i. yaitu merupakan
total waiting time (yaitu waktu mengantri) ditambah total service time (yaitu, service
demand),
untuk
semua
kunjungan
ke
antrian
i.
Sehingga,
Ri' = Qi + Di = Vi × Ri .
•
R0 : rata-rata response time; sama dengan jumlah dari residence time pada semua antrian. Sehingga, R0 = ∑i Ri' . K
•
ni : rata-rata jumlah request pada antrian i yang menunggu atau menerima layanan dari suatu resource pada antrian i.
•
N : rata-rata jumlah request pada jaringan antrian.
Rata-rata response time adalah sama dengan rata-rata service time ( S i ) ditambah dengan rata-rata waiting time ( Wi ) dari sebuah request. Rata-rata waiting time merupakan rata-rata jumlah request yang terlihat pada antrian i oleh sebuah kedatangan request ke antrian, dikalikan dengan rata-rata service time ( S i ) per request.
Pada open jaringan antrian, rata-rata jumlah request yang terlihat pada antrian i adalah sama dengan rata-rata jumlah request dalam antrian ( ni ). Sehingga, diperoleh rata-rata response time ( Ri ) pada antrian i seperti yang ditunjukkan pada persamaan (2.8.1). Ri = S i + ni × S i
(2.8.1)
Tetapi dari hukum Little’s, ni = X i × Ri , sehingga dengan menggabungkan persamaan (2.8.1) dengan hukum Little’s dan Utilisasi dimana U i = X i × S i , diperoleh persamaan (2.8.2). Ri = S i (1 − U i )
(2.8.2)
Dari persamaan (2.8.2), maka diperoleh residence time pada antrian i, seperti yang ditunjukkan pada persamaan (2.8.3).
Ri' = Vi + Ri =
Vi × Ri Di = 1−Ui 1−Ui
(2.8.3)
Menggunakan hukum Little’s, persamaan (2.8.3) dan hukum Utilisasi, maka dapat diperoleh jumlah rata-rata request pada antrian i, seperti pada persamaan (2.8.4).
ni =
Ui 1−Ui
2.9
Teorema Jackson[7, 9, 10, 11]
(2.8.4)
Teorema Jackson dapat digunakan untuk menganalisis suatu jaringan antrian. Teoreman ini didasarkan pada 3 asumsi yaitu: 1. jaringan antrian terdiri dari m node, dimana masing-masing node memberikan layanan eksponensial yang bebas, 2. sebuah request datang dari luar sistem ke suatu node, dengan arrival rate adalah Poisson,
3. setelah dilayani pada satu node, request tersebut akan menuju ke node yang lain dengan suatu probabilitas atau keluar dari sistem. State pada Jackson theorem merupakan suatu jaringan antrian, dimana masingmasing node adalah sistem antrian yang bebas, dengan input Poisson yang ditentukan dengan antrian partitioning, merging atau tandem. 1. Antrian partitioning. Request datang ke suatu antrian dengan rata-rata arrival rate λ , dan ada 2 kemungkinan tujuan dari request selanjutnya yaitu A dan B (Gambar 2.13a). Pada saat request telah selesai dilayani dan keluar dari jalur A dengan probabilitas p, dan dari jalur B dengan probabilitas 1-p. Secara umum, distribusi aliran request A dan B akan berbeda dengan distribusi incoming. Namun, jika distribusi incoming merupakan Poisson, maka 2 aliran keberangkatan request juga distribusi Poisson, sehingga arrival rate-nya adalah pλ dan (1 − p)λ . 2. Antrian Merging. Jika 2 distribusi Poisson dengan rata-rata arrival rate adalah λ1 dan λ2 digabung, maka menghasilkan distribusi Poisson dengan rata-rata arrival rate adalah λ1 + λ 2 , seperti yang terlihat pada Gambar 2.13b. 3. Antrian Tandem. Gambar 2.13c merupakan contoh rangkaian dari antrian server tandem tunggal. Masukan untuk setiap antrian kecuali antrian yang pertama, merupakan keluaran untuk antrian selanjutnya. Jika diasumsikan masukan untuk antrian pertama adalah Poisson, maka service time untuk setiap antrian adalah eksponensial dan waiting line adalah infinite. Keluaran dari masing-masing antrian adalah distribusi Poisson yang identik dengan masukan. Pada saat suatu request menuju ke antrian berikutnya, delay pada antrian kedua adalah sama, jika request orisinil sudah melalui antrian yang pertama, dan lansung menuju antrian kedua. Jadi, antrian adalah independent, dan akan dianalisis satu kali pada satu waktu. Sehingga, rata-rata total delay dalam sistem tandem ini adalah sama dengan jumlah rata-rata delay pada setiap stage.
Ρλ
A
(1 − Ρ)λ
B
A
λ1
λ1 + λ2
λ B
λ2
(a)
(b)
λ
λ
λ
Node1
Node2
Node3
λ
(c)
Gambar 2.13 Elemen jaringan antrian[10]. Pada bagian ini yang akan dibahas lebih detil adalah antrian partitioning. Pada Gambar 2.14 terlihat suatu open jaringan antrian dengan partitioning dan feedback. Dimana eksternal request datang dengan arrival rate λ . Request yang sudah menyelesaikan layanan akan keluar dari sistem, atau akan kembali ke antrian untuk memperoleh layanan lagi, dengan probabilitas p, dengan kecepatan pλ1 , dan digabungkan dengan
request eksternal, sehingga arrival rate pada antrian ini
ditunjukkan pada persamaan (2.9.1).
λ1 = λ + pλ1 =
λ
(2.9.1)
1− p pλ1
λ
λ1
λ1
(1 − p )λ1
Gambar 2.14 Open antrian dengan partitioning dan feedback [7]. Untuk utilisasi server didefenisikan seperti pada persamaan (2.9.2).
ρ = λ1 S
(2.9.2)
Aliran feedback akan membuat suatu masalah, dimana tidak diketahui bagaimana merepresentasikan pengaruh dari antrian yang menerima dua masukan, dari masukan bagian luar dan masukan bagian dalam.
Untuk menentukan rata-rata jumlah kunjungan ke server dinyatakan dengan persamaan (2.9.3). Vsrv =
C srv C sys
(2.9.3)
Dimana Csrv merupakan jumlah request yang selesai pada server dan Csys merupakan jumlah request yang selesai pada level sistem, dimana mungkin memiliki lebih dari satu antrian. Dengan menerapkan defenisi throughput pada subbab 2.5.1 yaitu X i =
C0
τ
dan persamaan (2.9.3), maka diperoleh persamaan (2.9.4).
C srv
Vsrv =
λ1 τ = λ srv = C sys λ (1 − p )λ1 τ
(2.9.4)
Dimana sudah diketahui dari persamaan (2.9.1) bahwa λ = (1 − p )λ1 , maka rata-rata jumlah kunjungan ke server dapat dinyatakan dalam hubungan dengan probabilitas p yaitu ditunjukkan pada persamaan (2.9.5). Vsrv =
1 (1 − p)
(2.9.5)
2.10 Batasan Performansi
Penggunaan beberapa komputasi untuk menentukan batas atas dan batas bawah pada throughput sistem dan response time, sebagai fungsi dari intensitas workload sistem (jumlah atau arrival rate customer). Teknik untuk menghitung batasan performansi ini adalah asymptotic bound dan balanced system bound. Yang akan dijelaskan pada bagian ini hanya untuk asymptotic bound. Untuk model dengan tipe transaction workload, batasan throughput mengindikasikan maksimum arrival rate customer yang dapat diproses oleh sistem, sementara batasan response time, menggambarkan response time yang terbesar dan terkecil, dimana customer dapat mengalami sebagai suatu fungsi dari arival rate sistem. Untuk model dengan tipe batch atau terminal workload, batasan mengindikasikan kemungkinan maksimum dan minimum throughput sistem, dan response time sebagai fungsi dari
jumlah customer dalam sistem. Untuk batas atas throughput dan batas bawah response
time,
dihubungkan
dengan
batasan
yang
optimistik,
karena
mengindikasikan kemungkinan performansi yang terbaik, dan untuk batas bawah throughput dan batas atas response time, dihubungkan dengan batasan yang pesimistis, karena mengindikasikan kemungkinan performansi yang terburuk. Aysmptotic bound analisis memberikan batasan yang optimistik dan pesimistik dari throughput sistem, dan response time pada single class jaringan antrian. Seperti namanya, analisis ini diperoleh dengan mempertimbangkan (asymptotically) kondisikondisi ekstrim dari load yang ringan dan load yang berat. Validitas dari batasan ini hanya tergantung pada sebuah asumsi tunggal yaitu service demand dari customer pada service center, dan tidak tergantung pada berapa banyak customer lain ada di dalam sistem atau pada service center. Jenis informasi yang disediakan oleh asymptotic bound tergantung pada workload sistem yaitu open untuk transaction workload, atau closed untuk terminal dan batch workload. Dan yang akan dijelaskan hanya untuk transaction workload. Untuk transaction workload, batasan throughput mengindikasikan kemungkinan maksimum arrival rate dari customer, dimana sistem dapat memproses secara sukses. Jika arrival rate melebihi batasan ini, maka suatu backlog dari customer yang tidak diproses akan meningkat secara kontinyu mengikuti kedatagan job. Sehingga, suatu job yang datang akan menunggu untuk jangka waktu yang tidak tentu, karena mungkin ada beberapa job yang sudah ada dalam antrian, ketika job yang baru tersebut datang. Dalam hal ini dikatakan bahwa sistem saturasi. Batasan throughput merupakan arrival rate yang pemrosesannya mungkin terpisah dari saturasi. Untuk menentukan batasan throughput adalah menggunakan hukum Utilisasi, U i = X i × S i untuk setiap i. Jika arrival rate ke sistem dinotasikan sebagai λ , maka X i = λ × Vi dan hukum Utilisasi menjadi U i = λ × Di , yaitu service demand pada resource i. Untuk mendapatkan batasan throughput, jika selama semua service center memiliki kapasitas yang tidak digunakan, dimana utilisasi kurang dari 1, maka
peningkatan arrival rate dapat diakomodasi. Namun, pada saat setiap service center menjadi saturasi, yaitu memiliki utilisasi sama dengan 1, maka seluruh sistem menjadi saturasi, karena peningkatan arrival rate customer tidak dapat ditangani secara sukses. Sehingga batasan throughput adalah arrival rate yang terkecil λ sat pada setiap saturasi service center. Service center yang saturasi pada arrival rate yang terendah merupakan bottleneck service center, yaitu service center dengan service demand terbesar. Dan max merupakan indeks dari bottleneck service center. Maka diperoleh[3, 5] U max (λ )
= λ Dmax ≤ 1
λsat
=
1 Dmax
≤
1 Dmax
X (λ )
D
≤ R (λ )
Untuk arrival rate yang lebih besar atau sama dengan
1 , maka sistem adalah Dmax
saturasi, sementara sistem mampu memproses arrival rate adalah yang kurang dari 1 . Dmax
2.11 Performansi Harddisk[5]
Magnetik disk merupakan komponen penting untuk setiap sistem komputer. Jumlah akses informasi yang disimpan pada magnetik disk, lebih banyak dibandingkan jumlah akses informasi pada Random Access Memory (RAM). Gambar 2.15 menunjukkan sebuah disk terdiri dari satu atau banyak platter yang berputar pada lockstep, dipasang ke spindle. Informasi secara magnetik direkam pada permukaan bagian atas dan permukaan bagian bawah setiap platter. Permukaan platter dibagi menjadi lingkaran kosentris yang disebut dengan track. Read/write head ditempelkan pada ujung arm, yang dihubungkan dengan setiap platter. Hanya satu read/write head yang dapat aktif pada satu saat. Actuator menggerakkan semua arm secara bersamaan sepanjang radius platter. Sekumpulan track ditempatkan pada jarak yang
sama dari pusat yang disebut cylinder. Track dibagi menjadi sektor-sektor dengan ukuran yang sama. Untuk read/wite dari/ke sebuah magnetik disk, actuator bergerak ke cylinder yang tepat. Hal ini disebut dengan seek. Read/write head berhubungan untuk meminta track yang aktif. Mekanisme disk untuk menunggu sampai putaran disk membawa sektor yang diinginkan di bawah read/write head disebut dengan rotational latency. Setelah mencapai titik ini, maka pemindahan data dapat dimulai. Gambar 2.16 menunjukan arsitektur I/O subsistem dari sebuah server. I/O request diberikan ke sistem. Cache pada sistem menyimpan blok file yang paling sering digunakan. Jika blok yang dinginkan ada dalam cache, maka akses disk tidak diperlukan dan request dipenuhi secara langsung oleh cache. Hal ini disebut dengan cache hit. Sebaliknya, cache miss bisa terjadi, dan request dikirim ke device driver. Request akan mengantri pada device driver, yang akan mengulang urutan untuk mengoptimalkan performansi. Request kemudian dikirim ke disk controller. Cache pada disk controller (disebut dengan disk cache) digunakan untuk mencocokkan kecepatan antara disk dan I/O bus. Disk cache dapat digunakan untuk menjemput dulu blok yang dibutuhkan dalam waktu dekat. Sebagai contoh, jika sebuah file yang sedang diakses secara berurutan, hal ini berati bahwa untuk membawa ke cache sejumlah blok tertentu yang mengikuti blok yang baru saja diminta, sehingga cache hit terjadi pada saat blok-blok ini diminta. Teknik ini dikenal dengan raed-ahead atau preftetch. Disk controller menggunakan disiplin penjadwalan disk pada antriannya, yang bertujuan untuk meminimalkan jumlah ratarata cylinder yang dilewati oleh arm untuk melayani disk request. Contoh disiplin penjadwalan disk adalah LOOK, CSCAN, Shortest Seek Time First (SSTF) dan Shortest Partitioning Time First (SPTF).
Gambar 2.15 Bagian-bagian dari magnetik disk.
Gambar 2.16 Arsitektur subsistem I/O.
Notasi-notasi yang digunakan adalah sebagai berikut. •
S d : rata-rata waktu (detik) yang dibutuhkan pada controller ditambah dengan waktu untuk akses sebuah blok dari disk.
•
SeekTime: rata-rata seek time (detik), yaitu rata-rata waktu untuk menempatkan arm ke cylinder yang tepat.
•
Seek rand : rata-rata seek time (detik) untuk sebuah request ke sebuah random cylinder, yang diberikan oleh pabrik disk; terkadang, rata-rata seek time untuk read dan write requet sedikit berbeda.
•
DiskSpeed: kecepatan perputaran disk, dalam revolution per minute (RPM), yang diberikan oleh pabrik disk.
•
DiskRevolutionTime: waktu (detik) untuk sebuah disk menyelesaikan sebuah putaran penuh, sama dengan 60 DiskSpeed .
•
RotationalLatency: rata-rata rotational latency (detik), yaitu rata-rata waktu yang dilewatkan sejak akhir pencarian sampai pengiriman data dimulai. Waktu ini merupakan waktu yang digunakan menuggu disk berputar sampai sektor yang diinginkan berada di bawah read/write head.
•
BlockSize: ukuran blok dalam byte.
•
TransferRate: kecepatan dimana data dikirim ke/dari disk (MB/sec)
•
TransferTime: waktu (detik) untuk mengirimkan satu blok dari disk ke disk controller.
•
ControllerTime: waktu (detik) yang digunakan pada controller memproses sebuah I/O request. Hal ini termasuk waktu untuk memeriksa cache ditambah waktu untuk membaca/menulis sebuah blok dari/ke cache.
•
Pmiss : probabilitas dimana blok yang diinginkan tidak ada dalam cache.
Rata-rata waktu akses pada controller ditambah disk dapat dinyatakan sebagai berikut:
S d = ControllerTime + Pmiss × ( SeekTime + RotationalLatency + TransferTime)
(2.10.1)
Transfer time merupakan perbandingan sederhana antara ukuran blok dengan kecepatan transfer (byte/detik). Sehingga diperoleh, TransferTi me =
BlockSize TransferRa te
(2.10.2)
Probabilitas cache miss, rata-rata seek time dan rata-rata rotational latency tergantung pada jenis workload yang diberikan ke disk subsistem. Disk workload didefenisikan sebagai rangkaian dari angka-angka blok disk yang diberikan ke disk subsistem. Ada dua jenis workload yaitu random dan sequential. Random workload adalah blok yang diminta, secara acak tersebar pada blok-blok dalam disk. Sequential workload adalah subsequences yang diberikan disebut dengan run dari request untuk blok yang berurutan dalam disk. Sebagai contoh, workload 10, 201, 15, 1023, 45, 39, 782, merupakan random workload dan 4, 350, 351, 352, 353, 80, 104, 105, 106, 107, 108, merupakan contoh sequential workload dengan 2 run dengan panjang 4 blok dan 5 blok. Untuk random workload dinyatakan sebagai berikut: Pmiss = 1
(2.10.3)
RunLength = 1
(2.10.4)
SeekTime = Seekrand RotationalLatency =
1 × DiskRevolutionTime 2
(2.10.5) (2.10.6)
Sedangkan untuk sequential workload dinyatakan sebagai berikut: Pmiss = 1/RunLength SeekTime = Seekrand/RunLength 1 2 + ( RunLength − 1)[(1 + U d ) 2] × RotationalLatency = RunLength Disk Re volutionTi me
(2.10.7) (2.10.8) (2.10.9)
2.12 Performansi Central Processing Unit (CPU)[12]
CPU digerakkan oleh sebuah clock dengan cycle time yang tetap ( τ dalam nanodetik). Clock cycle time didefenisikan sebagai waktu antara dua rising edge sinyal clock periodik yang berurutan. Kebalikan dari cycle time ini adalah clock rate (f =
1
τ
dalam megahertz). Ukuran dari setiap program ditentukan oleh instruction
count (Ic), yaitu jumlah instruksi mesin yang dieksekusi oleh program. Instruksi mesin yang berbeda akan membutuhkan jumlah clock cycle yang berbeda. Sehingga, cycles per instruction (CPI) menjadi sebuah parameter penting untuk pengukuran waktu yang dibutuhkan untuk mengeksekusi setiap instruksi. Maka untuk sekumpulan instruksi, yang dihitung adalah rata-rata CPI untuk semua jenis instruksi. Ic merupakan jumlah instruksi dalam sebuah program atau instruction count. Sehingga waktu CPU (T dalam detik/program) diperlukan untuk mengeksekusi program yang ditunjukkan pada persamaan (2.11.1). T = I c × CPI × τ
(2.11.1)
C merupakan jumlah total clock cycle yang dibutuhkan untuk mengekesekusi suatu program. Maka, CPU time pada persamaan (2.11.1) menjadi : T = C × τ = Selanjutnya, CPI =
C Ic
dan T = I c × CPI × τ = I c ×
C . f
CPI . Kecepatan processor f
sering diukur dengan istilah million instruction per second (MIPS). MIPS rate dipengaruhi oleh sejumlah faktor, yaitu clock rate (f), instruction count (Ic) dan CPI, sehingga diperoleh persamaan (2.11.2).
MIPS rate =
Ic f × Ic f = = 6 6 T × 10 CPI × 10 C × 10 6
(2.11.2)
