bab3-permodelan dengan petri
TRANSCRIPT
-
PEMODELAN DENGAN
JARINGAN PETRI
-
JaringanPetritelahdirancangdanterutamadigunakanuntukpemodelan.Banyaksituasi,terutamasistimyangmemilikikomponen-komponenyangsalingbebas,dapatdimodelkanolehJaringanPetri.
3.1.EVENT DAN KONDISI
Jaringanfetri secarasederhanadalammeninjausuatusistemmengkonsentrasikanpada2 konsepprimitive:
8. Event
Eventadalahaksiyangterjadidalamsistimtersebut.Kemunculandarievent-eventinidi kontrololehstatadarisistemtersebut.Statadarisistemdapatdijelaskansebagaisekumpulankondisi-kondisi.
b. Kondisi
Kondisiadalahpredikatataudeskripsilojikterhadapstatadarisistem.Karenanya,suatukondisibisahold(menjadibenar)ataunothold(menjadisalah).
Karenaeventadalahaksi,makaeventtersebuthamsada.Agarsuatueventterjadi,makadiperlukanadanyakondisi-kondisitertentusebelumnya.Halinidisebutsebagaiprekondisidarievent.Kemunculandarieventdapatmenyebabkantimbulnyakondisilain,yangdisebutsebagaipostkondisi,menjadibenar.
Contoh1 :
Pemodelanterhadapsuatumesintoko.Mesintersebutmenungguhinggamunculnyasuatuorderyangkemudianmemprosesordertersebutsertamengirimkanuntukpengantaran.
Kondisi-kondisiuntuksistemtersebutdiatasadalah:
32
-
a. Mesintokosedangmenunggu
b. Satuordertelahtibadansedangmenunggu
c. Mesintokosedangmengerjakanordertersebut.d. Ordertelahselesai
Sedangkanevent-eventnyaadalah:1. Satuordertiba
2. Mesintokomulaimengerjakanordertersebut
3. Mesintokoselesaimengerjakanordertersebut
4. Orderdikirimuntukdelivery
Kitadefinisikanprekondisi-prekondisidanpostkondisi-postkondisidarievent-eventdi atasdanbentukbaganevent-eventnyasebagaiberikut:
Terlihatbahwaprekondisidarievent2(mesintokomulaimengerjakanorder)adalah(a)mesintokosedangmenunggu,dan(b)ordertelahtibadansedangmenunggu.Postkondisidarievent1 adalah(c) mesintokosedangmengerjakanorder.PeninjauansuatusistemsepertiinidapatdenganmudahdimodelkanmenjadisuatumodelJaringanPetri.Event-eventdandimodelkandenganplace-placedankondisi-kondisidimodelkandengantransisi-transisi.Input-inputdarisuatutransisiadalahprekondisidarieventyangbersesuaiandanoutputdaritransisiadalahpostkondisi.Kemunculandari suatueventberkorespondensidenganfiring dari transisiyangbersesuaian.
33
;:::;:::::::;:;:::::;:::::::::;:;:;:::::;:;:;:;:;:;:;:;:;:;:::::::;:;:;:::;:;:;:;:;:;:;:;:;:;:;:;:::;:;:;:;:;:::;:::::;:::::::;:::::::;::::..............................................................................................................................................
::H:::::::::BIIIIIIIIt:::::m::::::::::::'::::::::::::::::::::::::::::::::::11I.:::::::::::::::;::::j:::::::I:::::::::1:'/',1:11',1'::::111:111111111::':::::'1::::,1:11":':,:' i@iUi. . :.;::.. : ,':.::.}. .:: . .. """ :: ..:.::;:.:. .: .,::.. ::.'..:. }m:m;n..........................................................................................................................................::i::i:i::i:;:::;:;:::::::j::::j:j:j:j:j:i:i:i:j:i:j:i:i:j:i:i:i:i:i:i:i:i:i:i:i:i:j:j:j:j:j:j:j;j:j:j::j::j:::::::::::i::i:;:;::i:}i::i:i::i::;::1::i:1:i:1:i:j:j:j:j:j:j:;:j:i:i:;:i@i:i@i:i:i:i:i:j:j:j:j:;:;:;:;:j:j:j:j:j:j:;:;:::::::::::::=::::::::::::;::::::::::::::::;::::::::::::::;:;:;:;::::::::::::::::::::::::::::;:::::::::;::::::::::;:::::::::::::::::::::
1 Tidakada. b2 .a, b c
3 ' ' c, d, a4 d Tidak ada
-
. _. u.. .. --- -.-..-.
Holdingdarisuatukondisidirepresentasikanolehsuatutokenyangberadadalamplaceyangbersesuaianke kondisitersebut.Bila transisitersebutditembakmakatoken-tokenyangmempresentasikanholdingdariprekondisidipindahkandan menciptakantoken-tokenbaru yangmerepresentasikanholdingdaripostkondisi-postkondisi.
Berdasarkanhal-halyangtelahditerangkandiatas,makamodelJaringanPetridaricontohmesintokotersebutdapatditunjukkanpadagambar3-1.
Anorder Anorder Processingarrives iswaiting starts
Processing Theorderis complete iscomplete
The m3chine shopis idle, w3iting ror work
Gambar3-1.Modeljaringanpetri.darisistemmesintoko.
ContohSistemyanglebihrumit:
Mesintokobisaterdiridari3mesinyangberbeda,sebutMI, M2,danM3 sertaduaoperatorFI danF2. OperatorFI dapatmengoperasikanmesinMI danM2 sedangkanoperatorF2dapatmengoperasikanMI danM3. SetiaporderharusselaludiproS'esoleh2 mesin.Pertama-tamaordertersebutharusdikerjakanolehmesinMI dankemudiandikerjakanolehsatumesinM2 atauM3.
Kondisi-kondisiclariSistemadalah:
a. OrdertelahtibadansedangmenungguuntukdiprosesMl.
34
-
b. OrdertelahdiprosesM1dansedangmenungguuntukdiprosesolehM2 atauM3.
c. Ordertelahselesaidiproses
d. MesinMl menganggur
e. MesinM2 menganggur
f. MesinM3 menganggur
g. OperatorFl menganggur
h. OperatorF2 menganggur
1. MesinMl sedangdioperasikanolehFl
J. MesinMl sedangdioperasikanolehF2
k. MesinM2 sedangdioperasikanolehFl
( MesinM3 sedangdioperasikanolehF2
Eventyangdapatmuncul.
1. Suatuordertiba
2. OperatorFl mulaimemprosesorderpadamesinMl
3. OperatorFl mulaimemprosesorderpadamesinMl
4. OperatorF2 mulaimemprosesorderpadamesinMl
5. OperatorF2 mulaimemprosesorderpactamesinMl
6. OperatorFl mulaimemprosesorderpactamesinM2
7. OperatorFl mulaimemprosesorderpadamesinM2
8. OperatorF2 mulaimemprosesorderpactamesinM3
9. OperatorF2 mulaimemprosesorderpadamesinM3
10.Orderdikirimuntukdelivery
35
-
Baganprekondisi-prekondisidanpostkondisi-postkondisidarisetiapevent.
Adapunmodeljaringanpetrinyadapatditunjukkanpadagambar3-2.
Gambar3-2.Modeljaringanpetridarisistemtokoyanglebihrumit.
36
Event Prekondisi-prekondisi Postkondisi-postkondisi1 Tidakada a2 a,g,d 13 1 g, d,b4 a,h,d J5 J b, h, d6 b, g, e k7 k c, g,e8 b, f, h I9 I c, f, h10 c tidakada
-
Contoh ,3 :
Suatusistemkomputeryangmemprosesjob-jobdarisuatupirantiinputdanmengeluarkanhasilnyapadasuatupirantioutput.Job-jobmunculpadapirantiinput.Bila processorbebasdanterdapatsuatujob padapirantiinput,makaprocessormulaiuntukmemprosesjobtersebut.Bilajobtersebutselesai,makajob dikirimkepirantioutput,processordapatmelanjutkanpemrosesanjoblainjikabersediasatujobpadapirantiinputataumenungguhinggadatangnyasatujob kepirantiinputyangsaatitusedangkosong.
SistemkomputertersebutdiatasdapatdimodelkanolehJaringanPetrisepertigambar3-3.
A job is put in inputqueue
Ajobis waiting
Ajubisstarted
Ajob;~waitingto beoutput
Gambar3-3.Modeldarisistemkomputersederhana.
37
-
3.2. KONKURENSI DAN KONFLIK
PadamodelJaringanPetritersebut,2 eventyangenableddantidaksalingberinteraksidapatmunculsecaraindepenbebas.Untukkasusini,event-eventtidakperludisinkronkankecualidibutuhkanolehsistemyangsedangdimodelkan.Biladibutuhkansinkronisasi,makahalinijugadapatdimodelkandenganmudah.Jaditerlihatbahwajaringanpetriidealuntukmemodelkansistem-sistemdarikontroltersebardenganbanyakprosesyangsedangeksekusisecarakonkuren(paralleldalarnwaktu).
Hal lainyangmenjadikeistimewaanutarnadarijaringanpetriadalahsifatke-asinkron-annya(tidakterdapatukuranwaktuataualiranwaktudalarnsuatujaringanpetri).Hal ini merefleksikansuatufilosofiwaktuyangmenyatakanbahwasifatwaktuyangpenting,darisudutpandanglogikadalahdalarnmenentukanbagiandariurutankemunculanevent-event.Padakehidupannyata,setiapeventmembutuhkanwaktuyangberbeda-beda,dankeberbedaanini direfleksikandalarnmodeljaringanpetridengantidakbergantungpadaartidariwaktuuntukmengontrolderetandarievent-eventtersebut.Strukturjaringanpetriitusendiriberisisemuainformasiuntukmenentukanderetandarievent-eventyangmungkin.Jadi,padagarnbar3.3,event"A jobis completed"harnsmengikutieventyangbersesuaian,yaitu"A job is started".Narnunsarnasekalitidakterdapatinformasiyangdiberikanataudibutuhkanberkenaandenganjumlahwaktuuntukmenyeksekusisuatujob.
EksekusiterhadapsuatuJaringanPetri (danprilakusistemyangdimodelkan)ditinjaudisinisebagaisuatuderetanevent-eventyangdiskrit.Urutankemunculanlaindarievent-eventtersebutadalahsalahsatudaribeberapakemungkinanyangdiperbolehkanolehstrukturdasarnya.HalinimengakibatkansifatnondeterministikterhadapeksekusidariJaringanPetri.Jika padasatusaatterdapatlebihdarisatutransisiyangenabledmakasalahsatudaribeberapatransisiyangenabledtersebutmenjaditransisiberikutyangdi "tembak".DitinjaudarisisieksekusiJaringanPetriyangklasikmakapemilihanterhadaptransisiyangakanditembakdilakukandengancarayangnondeterministik,atausecaraacak.
Dengansifatini makatimbulkerumitandalarnmendeskripsikandanmenganalisaprilakudinarnisdari JaringanPetribila ditinjausebagai
38
-
sederetandari transisiyangditembak.Untukmembantumembatasikerumitanini makadilakukansuatupembatasandalampemodelansistemke modelJaringanPetriyangditerimasecaraumum.Penembakandarisuatutransisi(daneventyangberkaitan)adalahinstantaneous,tidakmembutuhkanwaktu,dankemunculandari2eventtakdapatterjadisecarasimultan,atausecarabersama-sama.
Event-eventyangdimodelkandisebutevent-eventprimitif,yaituinstantaneousdannonsimultaneous.Suatueventyangnonprimitifadalahsuatueventyang blIa dilaksanakanakan membutuhkanwaktu.Operasi-operasinonprimitifadalahsemultandankarenanyaoverlapdalamwaktu.Karenabanyakeventdalamdunianyatadalammelaksanakannyamembutuhkanwaktu(event-eventnonprimitit)makatidakdapatdimodelkansecaratepatmenjaditransisipadasuatuJaringanPetri.Namunkebutuhanakanhalini tidakmenimbulkanmasalahdalammemodelkansuatusistem.
Suatueventnonprimitifdapatdipecahdalam2 eventyangprimitif,yaitu:
a) Awaleventnonprimitif,dan
b) Akhireventnonprimitif,sertaSuatukondisi"e,ventnonprimitifsedangterjadi"
The nonprimiliveevenlSlarlS
The nonprimiliveevent finishes
Gambar3-4.Pemodelansuatueventnonprimitif.
39
-
Penembakanyangnondeterministikdannonsimultandaritransisipadapemodelandarisistemyangkonkurenada2cara.Salahsatunyaditunjukkanpadagambar3-5.Padasituasiini,duatransisiyangenabledtidaksalingmempengaruhisatudenganlainnya.Halinidiistilahkansebagaikonkurensi.
0-+--0
Gambar3-5. Konkurensi.Keduatransisiinidapatditembakdalamurutansembarang.
Situasilainnya,dimanasifatkebersamaansangatsulituntukditanganidanhanyadapatdiselesaikandenganmenentukanevent-eventyangmunculsecaratidakbersamaan,diilustrasikanolehgambar3-6.PadasituasiiniduatransisiyangenabledadalahdalamkeadaankonflikHanyasatutransisiyangdapatditembakdanjikadilakukanpenembakanakanmemindahkantokenpadainputplaceyangdigunakanbersamadanmembuattidakenabledtransisilain.
40
-
3.3 PERANGKAT KERAS KOMPUTER
PerangkatkeraskomputerQapatditinjaudaribeberapaleveldanJaringanPetridapatmemodelkanmasing-masinglevelini. Padalevelterendah,komputerterbentukdaripiranti-pirantimemorisederhanadangerbang-gerbang.Padalevellebihtinggi,unit-unitfungsionaldanregister-registerdigunakansebagaikomponen-komponendasardarisistemtersebut.Masihlevelyanglebihtinggi,sistemkomputersecarakeseluruhanterdiridarikomponen-komponenyangmembentuksuatujaringanmultikomputer.
1',
Gambar3-6. Konflik. Transisi-transisi tj dan tk konflik karenapenembakansalahsatutransisiakanmenghilangkantokendariPi dantidakmeng-enabledtransisilainnya.
3.3.1FiniteStateMachine(MesinStatahingga)
Padalevelterendah,sistemkomputerdapatdijelaskansebagaistatemachine.
State-machineadalahsuatu5-tuppledimana: (8, I" Ll,0, r )
8 adalahhimpunanberhinggadaristate-state{q1,q2, ,qk}
41
-
L adalahinputalfabetberhingga~ adalahoutputalfabetberhingga
() : E>X L ~ E>adalahfungsinext-state,memetakanpasanganstatadaninputterakhirkestataberikut.
r : E>X L ~ ~ adalahfungsioutput,yangmemetakanpasanganstatadaninputterakhirkesimboloutput.
MesinStateseringdinyatakanolehsuatustatediagram.Padasuatustatediagram,state-statedinyatakanoleh lingkaran-lingkaranyangmerupakannode-nodedarigraph.Arkusdaristateqi ke stateq. diberi~labela/byangmengartikanbahwadalamstateqi denganinputa makamesinakanmengubahkestateq.denganmengoutputsimbolb.~
Secaraformal,dapatdituliskan() (qi, a) =qj danr(qi, a)=b. Inputalfabetmendefinisikaninputkemesindariluarsedangkanoutputalfabetmenyatakanoutputdarimesinkeluarsistem.
Contoh: Perhatikanstate-machineberikutini :
Statemachineini mengkonversikansuatubilanganbinerkebilanganbiner2'S - complementnegatifnyadengancaramemprosesdaribitlow-ordemya.Inputalfabetdanoutputalfabetnyaterdiridari3 simbol: 0, 1danR. Mesinmulaipadastateq1.Simbolreset(R) memberikansinyalakhir(atauawal)darisuatubilangandanmeresetmesintersebutkestateawal.Outputdarimesinuntuksimbolresetadalahsimbolreset.
0/0 011
III
R/R
I/O
Gambar3-7. Diagramstatauntuksuatumesinstatahinggayangmenghitung2'scomplementdarisuatubilanganbiner.
42
-
UntukmerepresentasikansuatustatemachinesebagaisuatuJaringanPetrimembutuhkansedikitpemikirankarenapadaJaringanPetritidakterdapatfasilitasuntukberkomunikasidengandunialuar.Olehkarenaitu,dalammemodelkaninteraksidengandunialuardapatdirealisa.sikandalam2 cara,yaitu:
a. Denganhimpunanplace-placekhusus(inputdanoutputjaringan).Padacontoh,setiapsimbolinputdinyatakandengansatuplacedansetiapsimboloutputjugadinyatakandengansatuplace.
Kitaasumsikanbahwadunialuarmendepositkansatutokenpadaplaceyangbersesuaiandengansimbolinputdankemudianmenunggusatutokenmunculdalamsatuplaceyangbersesuaiandengansatusimboloutputyangkemudianakandiremove.Haliniberulangsesuaidengankebutuhan.
b. Denganhimpunantransisikhusus.
Untukmenunjukkansimbolinputberikutmakadunialuarharusmemilihsuatutransisiinputdanmenembaknya.
Untuksuatufinitestatemachine(8, L, d, 0,r) kitadapatmenentukansuatuJaringanPetri(P,T, I, 0) dimana:
T ={tq,(JI q E 8 dancrE L}
I(tq,(J)={q, cr}
O(tq,a) ={o(q, cr), r (q,cr)}
JaringanpetrimerupakansuatumodeldariFiniteStateMachiQe.
43
-
RepresentasiJaringanPetridaricontohstatemachinesebelumnya:
Garnbar3-8. Jaringanpetriyangekivalendenganmesinstatahinggadarigarnbar3.7.
Terlihatdarigarnbar3-8bahwa:
a. Setiapsimbolinputdanoutputdinyatakandalarnplace-place
b. Setiapstatedanstatemachinedinyatakandalarnplace
c. Untuksetiappasanganstatedansimbolinput,kitatentukansuatutransisiyanginputplace-placenyaadalahplace-placeyangbersesuaiandenganstatedansimbolinputsertaoutputplace-placenyaadalahplace-placeyangbersesuaiankestateberikutdanoutputnya.
Suatubentukmesinserupadigarnbarkanpadagarnbar3.9denganmasukanyangsarna,mesinstataini menghitungparitasdaribilanganbilanganbinerinput.Mesinini dimulaipadaposisistataq1.Keluarannyahanyamengulangmasukannyahinggasimbolmasukannyamerupakansuatusimbolreset.Keluarandarisimbolresetini adalahbit0 untukbilangandenganparitasganjildanbit1untuksuatubilangandenganparitasgenap.
44
-
Sedangkanrepresentasijaringanpetrinyaditunjukkanpadagarnbar3-10.
IVI
Garnbar3-9. Mesinstatahinggauntukmenghitungparitasdarisuatubilanganbinerinput.
Di sarnpingitumodelJaringanPetrimemilikikeuntungan-keuntungantertentudalarnmengkombinasikanbeberapamesinstatahingga.Sebagaicontoh,karenakeluaranalfabetdarimesinpadagarnbar3,.8adalahsarnadenganmasukanalfabetpadagarnbar3.10.Denganmenjalankankeluarandari3-8kedalarnmasukandalarndarigarnbar3.10,kitadapatmembuatsuatumesinyangdapatmenghitungtwo'scO!Illementnegativedanparitasnya.
45
-
oGambar3.10 JaringanPetriyangekivalenke mesinstatahinggadarigambar3-9.
Kombinasidalammesinstatainisangatkomplek,membutuhkansuatustatakomposisidengankomponen-komponendarikeduamesinstatahinggatersebut,yanghasilnyaberupasuatumesincross-product.Gambar3-11menunjukkanmesincross-product.Untukmesinjaringanpetri,komposisitersebutdilakukandenganmenumpang-tindihkanplace-placeoutputdarijaringanpertamadenganplace-placeinputdarijaringankedua.Gambar3-12menunjukkankomposisidarikeduajaringanpetrigmbar3-8dangambar3-10.Keuntunganlaindarirepresentasijaringanpetriadalahdapatmembuatbentukkomposisiyanglain dari sebelumnya.Sebagaicontoh,suatukomposisiyangparalelmemungkinkankomponenmesintersebutdapatbekerjasecaraserempak.Untuksuatumesinstata,sekalilagimelibatkanmesincross-product,sementaraituuntukjaringanpetri,hanyalahmelibatkanpenduplikatantandamasukanyangmenggambarkansimbolmasukandan
46
-
memasukansemuanyake setiapkomponendarimesinJaringanPetri.Terakhir,padaoutputdenganmudahkitaseleksiplace-placeoutputyangtepat.Sebagaicontoh,jika kitainginmengkombinasikankeduamesinjaringanpetridarigambar3-8dan3-10secaraparalel,makahalini akanmenjadisuatujaringanpetriyangditunjukkanpadagambar3-13,yangmenghitung2'scomplementnegatifdarisuatubilanganbinerdanparitasnya.Paritasini merupakanoutputbilasimbolresetmerupaJeanoutput.
Gambar3-11.KomposisimesinjaringanPetriyangmerupakankomposisisecaraserialdarijaringan-jaringanpetrigambar3-8dan3-10.
47
-
Gambar3-12.Komposisiparalel~arigambar3-8dan3-10.Suatusub-JaringanduplikatordiperlukanuntukmenyediakaninputbagikeduakomponenJaringanPetri.
48
-
3.3.2PipelineKomputer
KemampuanuntukmembuatmodelParalelismedankemudahanmengkombinasikanbeberapasubsistemyangdimodelkansebagaiJaringanPetrimembuatmodeljaringanpetrisangatbergunadalammemodelkanhardwarekomputeryanglebihkompleks.Sistem-sistemkomputertersusun.dari beberapakomponen,danbeberaparancanganmencobauntukmeningkatkanhasildenganmenjalankanbeberapafungsisecaraparalel.Hal ini menjadikanJaringanPetritepatsekaliuntukmerepresentasikansistemtersebut.
Contohdaripendekatanini untukmembentuksuatukomputerdenganperformasiyangtinggiadalahdenganmenggunakanpipelines.
Teknikini ini miripdenganoperasidarisuatujalurdankhususnyabermanfaatuntukpemrosesanvektordanarray.Perakitansuatupipelineterdiriatasbeberapatingkatan,dimanaeksekusidarisetiaptingkatandapatsecaraserempak.Bila tingkatk selesai,menungguhasildarihasilyangdimilikinyaditeruskanketingkat(k+l)dantingkatan(k-l) untukpekerjaanselanjutnya.Jikasetiaptingkatmenghabiskant satuanwaktudanterdapatn tingkatan,makaoperasilengkapnyauntuk1operandimembutuhkann.tsatuanwaktu.Bagaimanapun,jikapipelinetersebuttetapdisuplydenganoperandiyangbaru,iadapatmengeluarkantiap-tiaphasilnyarata-ratasetiapt satuanwaktu.
Sebagaicontoh,penambahan2 bilanganfloatingpointsecarakasarlangkahyangdapatdiambiladalahberikutini :
1. Ekstrasikaneksponen-eksponendarikeduaangkatersebut.2. Bandingkaneksponen-eksponentersebutdanmenukartempatjikaperlu
untukmengurutkansecaratepatdariyanglebihbesardanyanglebihkedl padaeksponen-eksponentersebut.
3. Pindahkanpecahanyanglebihkedl untukmenyamakan/meratakaneksponen-eksponen.
4. Jumlahkanpecahan-pecahan5. Postnormalize.
6. Perhatikanapakaheksponenterlalubanyakatausebaliknya,satukaneksponendanpecahandarihasiltersebut.
49
-
-.-..- ... .._u. __. .. __ .....
Setiaplangkah-Iangkahdi atasdapatdilakukandengansebuahunitperhitunganyangterpisah,dengansebuahoperandikhususyangdilewatkandariunitke unitagaroperasipenambahanselesai.Hal ini memberikansebanyak6 penambahanuntukkeadaanyangsedangberlangsungsecaraserempak.
Kordinasidariunit-unityangberbedadapatdiatasidalambeberapacara.Secarakhusus,kontrolpipelineberoperasipadawaktuyangbersamaan;waktuyangdisediakanuntuksetiaplangkahdaripipelinetersebutadala4sebuahkonstantawaktuyaitut.Setiapsatuanwaktut,hasildatitiapunitdigeserkebawahpipelinetersebutuntukmasukanbagiunitselanjutnya.Bagaimanapunpendekatanoperasipadawaktuyangbersamaantersebuttidakperlumenundapengolahankarenawaktuyangdibutuhkandapatberbedaantaraunitsatudenganunitlainnyadanjugadapatberbedauntuksuatuunityangdiketahuiuntukmasukanyangberbeda.Sebagaicontohpadalangkahpostnormalizationdaripenjumlahanfloatingpointdi atasdapatmenghabiskanjumlahwaktuyangberbedatergantungpadaberapalamapergeserannormalisasidilakukandanapakahpergeseranyangdilakukankekiriataukekanan.Padakasusini,karenawaktut harnsdipilihsebagaiwaktumaksimumyangmanadiperlukanolehunitdaripipelineyangpalinglambat,ini dapatdilihatdarisetiapkasusdarisemuaunitsdimanahampirseluruhnyadariwaktutunggudigunakanuntukmembentukselamat waktuunit.
Suatupipelinetidaksinkronrata-ratadapatmempercepatkanhaldiatasdenganmemberisinyalsaatsetiaptingkatandaripipelinetersebutselesaidansiapuntukmelewatkanoperannyadanmenerimaoperanbarn.Hasiltingkatk daripipelinedapatdikirimke stage(k+l)segerasetelahtingkatk selesai& state(k+l)bebas.
Perhatikansuatutingkatansembarangpadapipelinetersebut.Jelasbahwaharusterdapatsatuplaceuntukmeletakaninp..l!.t;~...ut.4an
output-outpu~~elam~merekas~dangdi~unak~ataui~~ksi1 ,~~khusus,hal1mmehbatkanregIster-regIsterumtte
~f ~ ..,' ~~~,n~l~-n~l~tersebut.dalamregisterinputnya(bUffer}'.\;. . ...
'e
..
g.
.
_
.
~
.
lmsl.:~.~.
:.
.
.
.
..
.
'"
.
4
~'~
mlat-mlatpadaregIsteroutputnya(buffer). . "~t'":'._
.
.
..
'..
.
:~
.
. ", ;
-
Semuanyaharnsmenunggusampai:
1. Registeroutputnyatelahkosongdenganmenyalinnyakedalamregis-terinputdaritingkatberikutnya,dan
2. Suatuinputbarntelahbersediadidalamregisterinputnya.
Dalamhal ini, kontroluntuktingkatk daripipelinetersebutperluuntuktahukapankondisiberikutnyahold:
Registerinputpenuh
Registerinputkosong
RegisterOutputpenuh
RegisterOutputkosong
Unitdalamkeadaansibuk
Unitdalamkeadaanmenganggur
Transfer/copyingsedangberlangsung
Gambar3-13danGambar3-14menunjukanbagaimanasebuahpipelineyangtidaksinkronlasinkrondapatdimodelkan.Gambar3-13adalahsebuahdiagramblokdaripipelineyangdimodelkansebagaijaringanpetrisepertipadagambar3-14
Perludiingatbahwadalammodelinikitatelahmemodelkaneksekusiyangaktualdariunit-unitpipelinesebagaievent-eventnonprimitive.Halinimembolehkankitauntukmengabaikan,padaleveUni,detail-detailyangspecifikdarihal-halyangdilakukansetiapunitdanmengkonsentrasikanpadainteraksinyayangmemungkinkan.SetiapoperasijugadapatdibuatkanmodelJaringanPetrinya.JaringanPetriuntuksetiapunitdapatdisubtitusikedalamJaringanPetridarigambar3.19untukmendapatkanjaringanpetriyanglebihmendetail.Kemampuanuntukmemodelkansuatusistempadabeberapalevelabstraksiyangberbeda,dalamsuatucarayanghierarki,dapatbergunasekali.
51
-
unit k - 1
Output r~gistcrk - 1
Input registerk
Outputregisterk
I:-:putr~gist~rk - :
Gambar3-13.Diagramblokdaricontrolunityangtidaksinkronuntukkomputerpipeline.
52
-
'utork - I empty
Inputork rull
'utputork empty
,putof k + I full
, ,
'\.'\.,
Outputork- I rull
Inputork empty
Outputof k full
Inputuf k + I empty
Gambar3-14.Model JaringanPetridariunitkontrolsuatukomputerpipelineyangtidaksinkron.
53
-
3.3.3 Unit Mu(tiFungsi
StrukturKontrolPipelineadalahsalahsatupendekatanyangdigunakanuntukmembangunsistemkomputerbesaryangcepat.PendekatanlainyangdigunakandalamCDC 6600(Thornton1970)danIBM 360/91(Aderson1967)sebagaicontohdaIampenyediaanunitMultiFungsi.Dalam6600,terdapat10unitfungsiyangtersedia,yaitu:
1 Unitpencabangan(untuklompat'berkondisi)
1 Unitboolean(untukoperasiboolean)1 Unitshift
1 Unitpenambahanfloatingpoint
1 Unitpenambahanfixedpoint
2 UnitMultiply(perkalian)
1 UnitDivide(pembagian)
2 UnitIncrement(untukpengindexan)
Selainitubanyakregisterdiberikanuntukmenahaninput/outputdariunit fungsi.Unit Kontrold'arikomputermencobauntukmenyimpanbeberapadariunit-unityangbebasdalamoperasisecarasimultan.,
Sebagaicontoh,perhatikanbarisaninstruksiberikutiniyangdidasarkansistemkomputerCDC 6600:
1. KalikanXl denganXl, hasilnyasimpankedalamXO.
2. KalikanX3 denganXl, hasilnyasimpankedalamX3.
3. TambahkanX2 keX4, hasilnyasimpankedalamX4.
4. TambahkanXOkeX3, hasilnyasimpankedalamX3.
5. BagiXOdenganX4, hasilnyasimpankedalamX6.
Ketikainstruksi-instruksidijalankan,controlunitmengeluarkaninstruksipertamakeunitperkalian.Kemudian,karenaada2unitperkalian,instruksikeduadapatjugadikeluarkan.Memperhatikankeduaunitinidapatmembaca
54
-
Xl tanpamasalah.Instruksi3 dapatmengeluarkankeunitpenambahan.Sekaranguntukmengeluarkaninstruksi4, kitaharusmenunggusampaiInstruksi1,2,3selesai,karenainstruksi4menggunakanunitpenambahan(yangsedangdigunakanolehinstruksi3) untukmemprosesXO (sedangdiprosesolehInstruksi1)danX3(sedangdiprosesolehInstruksi2).Instruksi5harusmenungguInstruksi1(untukmenyelesaikanprosesXO)danInstruksi3 (untukmenyelesaikanprosesX4).
Pengenalandaritypeparalelini, pengerjaanbeberapainstruksidariprogramsecarasimultan,harusdikontrolsehinggahasildaripengerjaanprogramdenganatautidakdenganparaleladalahsamasaja.Instruksitertentudalamprogramakanmembutuhkanhasildariinstruksiterdahulu,telahsuksesdiprosessebeluminstruksisebelumnyadiproses.
SistemyangmemperkenalkanparalelkedalamsebuahprogramsequensialsedemikianrupamenyokonghasilyangbenaradalahDeterminate(terbatas).Kondisi-kondisiuntukmenyokongketetapantelahdipikir~anolehBersten(1966)sebagaiberikut:
Untukduaoperasia x b, sedemikianhinggaa mendahuluib dalamprogramlinier,b dapatdimulaisebelumaselesaidikerjakanjika danhanyajikabtidakmemerlukanhasildariasebagaiinputdan.hasildarib tidakmerubahinputatauhasildaria.
Sebuah tabel reservasiadalah salah satu metodeaplikasiketidakleluasaandarikonstruksiunitkontrolyangmengeluarkaninstruksinyauntukmemisahkanunit-unitfungsi.Instruksiunit-unitfungsionalamemakairegisterI, J danK dapatdikeluarkanjikakeempatkomponentidakdipesan.KetikaInstruksidikeluarkanpadawaktuyangsamakarenasalahsatuunitfungsiatauregistersedangdipakaimakaunitkontrolmenunggusampaiinstruksitersebutdapatdikeluarkansebelummelanjutkaninstruksiberikutnya.
Skemapendekini dapatdimodelkansebagaiJaringanPetri.Untuktiap-tiapunitfungsidanregister,kitamenghubungkansebuahtempat/ruang.Jika unit/registerbebas,sebuahtokenakanmasukketempattersebut,jikatidak,tidakadatokenyangmasuk.Fungsimultiindentikalunitdapatdiindentitikasikandenganmultitokenditempat-rempattersebut.Gambar
55
-
3.20menunjukkansebuahporsidariJaringanPetriyangdapatdigunakansebagaimodeleksekusiinstruksimenggunakanunitu danregisteri, j dank.MemodelkanseluruhunitkontroltentunyaakanmembuktikanJaringanPetriyangbesar.
Instructionusesunit uand registersi. i. and Ie
Readyto decodeneJttinstruction
Unit uis free
Register;is free
Registeriisfree
RegisterIeisfree
Gambar3.15 BagiandarisuatumodelJaringanPetriuntuksuatukomputerdenganbeberaparegisterdanbeberapaunitfungsional.
Skemainimenggambarkanbetapasimpelnyametodepengenalanparaleldantidakbisadisangkal.SebagaicontohunitMultiFungsijadi,skemainidapatmenghasilkanjadwal-jadwaldenganparalelmaksimum(Keller1975).Bagaimanapunjuga,adabeberapaskemayangdapatdimodelkanjuga.Skemaini dapatjugadimodelkansebagaiJaringanPetri(lebihrumit),jaringaninimungkinbesarsekali.MenyadaribahwaCDC6600mempunyai24registerdibedakandalam64instruksiberbeda.Tiap-tiapinstruksidanregistertripelmemerlukansebuahtempatJruangsesuaidenganunityangdioperasikandenganre.gisteri, j, k, kemudianlebihdari1/2jutaplacetransisiakandiperlukan.
56
-
3.4 PERANGKAT LUNAK KOMPUTER
Selainke H/W komputer,SIW komputerdapatdi modelkanolehJaringanPetri.
3.4.1 Flowchart
Kasustermudahterhadapsuatusistem.dariproseskonkruenadalahsuatusistemyanghanyamemilikitepat1 prosespertama-tamakitamemeriksabagaimanasatuprosestunggaldapatdinyatakanolehsuatuJaringanPetridankemudianmenggabungkanJaringanPetri-JaringanPetriyangmenpresentasikanbeberapaprosesyangmembentuksistemdariproses-proseskonkruen.
Satu prosestungaldijelaskandengansatuprogram.Programmerepresentasikanduaaspekterpisahdariproses,yaitu:
Komputasi;berkenaandenganoperasi-operasilogikdanaritmatikyangsebenarnya,inputdanoutputdanmanipulasidarilokasi-Iokasimemori.
Kontrol; berkenaandenganurutandariperformancenya.
JaringanPetridapatdenganbaikmempresentasikankontrolstrukturdariprogram.JaringanPetridigunakanuntukmemodelkansederetaninstruksi-instruksilainaliraninformasisertakomputasitetapibahannilai-nilaiinformasiyangsesungguhnya.
Modeldarisuatusistemadalahabstraksidarrisistemyangdimodelkan.Jadimengabaikandetail-detailtertentusebanyakmungkin.Jikasemuadetaildimodelkanmakamodeltersebutakanmenjadiduplikasidarisistemyangdi modelkandanbahanmerupakanabstraksi.
Satualatstandaruntukmerepresentasikanstrukturkontroldarisuatuprogramadalahflowchart.Flowchartmerepresentasikanalirankontroldarisuatuprogram.
57
-
Contoh: Suatuprogramberikutini
Begin
Input(y1);
Input(y2);
Y3 : =1;Whiley1>0do
begin
If odd(y1)Then
begin
y3 : =y3 * y2 ;y1:=y1- 1;
end;
y2 : =y2 * y2 ;y1:=y1-2 ;
end;
output(y3) ;
end;
58
-
Flowchartdariprogramdiatasadalahberikutini.
a
F
c/
('
f
Gambar3-16.Flowchartdaricontohprogram
Perhatikanbahwaflowchartdiatastidakmenentukankomputasiyangdilakukanmelainkanhanyastrukturdariprogramtersebut.Flowchartinitidakdapatditerjemahkan.Tabelberikutmenunjukkanbagaimanasuatuinterpretasidapatdipergunakanke aksi-aksidari flowchartumukmenyatakanprogramcontoh.
59
-
Alesi Interpretasi
a Input(y1);Input(y2);y3=1b y1>0 ?
c Odd(y1)?
d y3 :=y3 * y2 : y1 :=y1- 1
e y2 :=y2 * y2 ; y1 :=y1/ 2
f Output(y3)
Setiapprogramsekuensialdapatdinyatakansebagaisuatuflowchart.Jadi, denganmenunjukkanbagaimanasuatu flowchart dapatdirepresentasikanolehsuatujaringanpetrimakakita dapatmelihatbagaimanamerepresentasikansuatuprogramyangtakdapatditerjemahkandengansuatujaringanpetri.
Carauntukmentranslasikannode-nodekomputasidandecisionyangterdapatpadasuatuflowchartke transisi-transisidanplace-placedalamsuatuJaringanPetriditunjukkanolehgambar3-17.
Translasiyangtepatdarisuatuflowchartke JaringanPetriadalahmenggantinode-nodedariflowchartdengantransisi-transisipadaJaringanPetridanarkus-arkusdariflowchartdenganplace-placepadaJaringanPetri.SetiaparkusdariflowchartdirepresentasikantepatsatuplacepadaJaringanPetriyangbersesuaian.Sedangkannode-nodedari flowchartdipresentasikanmenjaditransisidengancarayangberbeda,yaitutergantungpadatipedarinode: komputasiataudecision.
60
-
ComputationT
ComputationT
T F
Gambar3-17.Mentranslasikannode-nodekomputasidandecisionpadasuatuflowchartke transisi-transisidanplace-placesuatujaringanpetri.
Gambar3-18menggunakancaratranslasidiatasterhadapflowchartgambar3-17untukmenghasilkansuatujariq.ganpetriyangekivalen.
3.4.2Parallelisme
Parallelismeataukonkurensidapatdinyatakandalambeberapacara.Perhatikankasusduaprosesyangkonkuren.SetiapprosesdapatdinyatakanolehsuatuJaringanPetri.Jadi penggabunganJaringanPetrimerupakanpenggabungandari Jaringan Petri untuk masing-masingprosesmerepresentasikaneksekusikonkurendarikeduaprosestersebut.PenandaanawaldariJaringanPetrigabungantersebutmemiliki2 token,satupadaplaceyangmerepresentasikanprogramcounterawaldarisuatuproses.Halinimenimbulkansuatuparalellismeyangtakdapatdinyatakandalamsuatuflowchart,tetapibukanmerupakansesuatuyangbermanfaat.
61
-
b.F
I
Gambar3-18.Representasijaringanpetriyangditurunkandariflowchartgambar3-1.7
Pendekatanlainnyaadalahmemperhatikanbagaimanaparallelismesecaranormaldiperkenalkanpadasuatuprosesyangberadapadasuatusistemkomputer.Beberapausulantelahdiajukan.SalahsatuyangtermudahadalahoperasiFORK danJOIN. OperasiFORK j dieksekusipadalokasi1mengakibatkanprosesterakhirberlanjutpadalokasi1+1,dansatuprosesbarnyangsedangdibuatdenganeksekusiyangberawalpadalokasij.OperasiJOIN akanmenggabungkankembaliduaprosesmenjadisatu.
62
-
Operasioperasiini dapatdimodelkanpadasuatujaringanpetriyangditunjukkanpadagambar3-19.
Usulanlainuntukmemperkenalkanparallelismeadalahstrukturkontrolparbegindanparend.StrukturkontrolinidiusulkanolehdjikstradanbentukumumnyaadalahparbeginSI;S2;S3; ;Snparend,dimanaSj adalahstatement-statemen.Arti dari strukturparbegin/parendadalahuntukmengeksekusisetiapstatemen,SI,S2,S3,Snsecaraparalel.Bentukinidapatdireprsentasikandalamsuatujaringanpetriyangditunjukkanpadagambar3-20.
(a)
(b)
Gambar3-19. Pemodelanjaringanpetridari operasi-operasiFORK danJOIN. (a) FORK (dieksekusipadalkasi I, membuatduaprosesbampadalokasij dank). (b)JOIN, (menggabungkankeduaprosestersebutyangberakhirpadalokasi I danjmenjadisatuprosesyangberlanjutpadalokasik)
63
-
Gambar3-20.PemodelanjaringanpetridariparbeginS\;S2;S3; ;Snparend.Setiapkotakmerepresentasikanrepresentasijaringanpetridaristatement-statemenS\'S2,s3''Sn.Gambarinijugamengilustrasikansifathirarkidaripemodelanjaringanpetri.
3.4.3Sinkronisai
Paralellismeyangtelahdijelaskansebelumnyasangatbergunauntukmemecahkansuatumasalahhanyajikakomponendariprosesdapatsalingbekerjasarnadalammenyelesaikanmasalahtersebut.Kerjasamayangdimaksudadalahpemakaiansecarabersamainformasidansumberdiantaraproses.,prosestersebut.Hal ini hamsdikontroluntukmenjaminoperasiyangbenardari keseluruhansistem.BeberapamasalahsinkronisasidikemukakanolehDijkstra,yaitu: masalahmutualexclusion,masalahProducer/Consumer,masalahThe DiningPhilosopherssertamasalahReaderslWriters.Semuamasalahdiatasmerupakanmasalahklasikdalam
64
-
bidangsinkronisasi.WalaupunJaringanPetrimerupakansuatuskemapemodelan,danbukanmerupakansuatumekanismesinkronisasi,JaringanPetriharusdapatsecaratepatmemodelkanmekanismesinkronisasitersebutdanmenyelesaikanmasalah-masalahini.
3.4.4MasalahmutualExclusion.
Asumsikanbahwabeberapaprosesmenggunakansecarabersamasuatuvariabel,record,file,atauitemdatalainnya.Itemdatayangdigunakansecarabersamainidapatdigunakandalamberbagaicaraolehproses-prosestetapisecarakasarpemakaianini dapatdigolongkansebagaikebutuhanuntukmembacanilaidariitemdataataumenulissuatunilaiyangbaru.Keduaoperasiini seringmerupakanoperasi-operasiprimitif.Ini berartibahwauntukmeremajakanitemdatayangdipergunakansecarabersamamakasuatuprosespertama-tamaharusmembacanilaiyanglama,kemudianmenghitungnilaiyangbarudanterakhirmenulisnilaiyangbarutersebutketempatnyasemula.Suatumasalahdapatterjadijikaduaprosesmencobauntukmengeksekusibarisaninstruksiberikutini padawaktuyangbersamaan.Barisaninstruksiberikutmungkinterjadi:
1. ProsesI membacanilaix dariobjekyangdigunakanbersama2. ProsesII membacanilaix dariobjekyangdigunakanbersama3. ProsesI menghitungsuatunilaiyangdiremajakanx' =f(x)4. ProsesII menghitungsuatunilaiyangdiremajakanx" =g(x)5. ProsesI menulisx' keobjekyangdigunakanbersama
6. prosesII menulisx" keobjekyangdigunakanbersamadanmenghapusnilaix'
Efekkomputasidariprosespertamatelahhilangdannilaidariobjekyangdigunakanbersamasekarangadalahg(x), sementaranilainyaseharusnyaadalahg(f(xatauf(g(x.Bayangkanpengaruhnyajika g(x)adalah"penarikan$1000keaccountx" sertaprosesI danII adalahbaktellers.
Untukmencegahmasalahdiatasmakaperluuntukmenyediakansuatumekanismeuntukmutualexclusion.MutualExclusionadalahsuatuteknik
65
-
pendefinisiankodeentry danexitsehinggapalingbanyaksatuprosesdapatmengaksessuatuobjekdatayangdigunakanbersamapadasuatusaat.Kodeyangmengaksesobjekyangdigunakanbersamatersebutdanmembutuhkanperlindungandaricampurtanganproseslaindisebutseksikritis.
Idenyaadalahbila suatuprosesakanmengeksekusiseksikritisnyamakapertama-tamaprosestersebutharnsmenungguhinggatidakadaproseslainyangsedangmengeksekusiseksikrisisnya.Kemudianprosestersebutmengunciakseske seksikritisuntukmencegahproseslainmemasukiseksikritisnya.Prosestersebutmemasukiseksikritis,mengeksekusinyadanmeninggalkanseksikritis tersebutdenganmembukakunciagarmembolehkanproses-proseslainmengaksesnya.
Masalahinidapatdipecahkandengansuatujaringanpetri,sepertiyangditunjukkanpadagambar3-21.Placem merepresentasikanijin untukmemasukiseksikritis.Agarsuatuprosesdapamasukkeseksikritis,makaprosestersebutharnsmemilikisatutokendipi atauP2yangmensinyalkanbahwaprosestersebutberkeinginanuntukmasuk.Jikakeduaprosesinginmasuksecarabersamaanmakatransisi-transisitl dant2beradadalamsituasikonflik,danhanyasatudarimerekayangdapatditembak.
66
-
Critic:llsection
Criticalsection
..
ProcessI Process2
Gambar3-21.Masalahmutualexclusion.Akseskeseksi-seksikritisdarikeduaprosesterkendalisehinggakeduanyatidakdapatsecarabersamaanmengeksekusiseksikritisoya.
3.4.5 MasalahProducer/Consumer
MasalahProducer/Consumerjugamelibatkansuatuobjekdatayangdipakaibersama.Tapi padaproblemini objekyangdigunakansecarabersamaadalahsuatubuffer.Prosesprodusermenciptakanobjek-objekyangkemudiandi letakkandi buffer,konsumenmenunggusampaisuatuobyek telah dileta~kandi buffer, mengambil,dan akhirnyamengkonsumsinya.Hal ini dapatdimodelkansepertiyangditunjukkanpadagambar3-22.PlaceB merepresentasikanQuffer;setiaptokenmerepresentasikansuatuitemyangtelahdiproduksitetapibelumdikonsumsi.
67
-
Variasidarimasalahini adalahmasalahmultipleproducer/consumer.Padavariasiini, beberapaproducermenghasilkanitem-itemyangditempatkanpadasuatubufferuntukbeberapakonsumer.Gambar3-23merupakansuatusolusiatasmasalahini
Producer Consumer
Gambar3-22.MasalahProducer/ConsumeryangdimodelkansebagaisuatuJaringanPetri.
68
-
"..r
Produce
Producer Consumer
dambar3-23.MasalahmultipleProducer/Consumer.Terdapatsproducerdant Consumeruntuks dant yangtepat.
Variasiyanglainadalahmasalahproducer/consumerdenganbufferterbatas.Padaversiini, dinyatakanbahwabufferantaraproducerdanconsumerseolah-olahterbata,yaituhanyatersedian posisiuntukitem-item.Jadi producertidakdapatselalumenghasilkansesuaidengankeinginannya,tetapiharnsmenunggujika consumerlambatdanbuffertelahterisipenuh.Gambar3-24merupakansuatusolusidarimasalahini.
69
-
Produce
T?
Producer Consumer
Gambar3-24.MasalahProducer/Consumerdenganbufferyangterbatas.Buffer,direpresentasikanolehplace-placeB danB',terbataspalingbanyakn item.
3.4.6MasalahDining Philosophers
Problemini diusulkanolehDijsktra(1968)danberkenaandengan5philosophertentangkemungkinanberfikirdanmakan.Paraphilosophertelahdudukpadamejabundarberi,sibanyakmakananCina.Diantaratiapphilosopherterdapatsebuahsumpit.Padahaluntukmakandiperlukan2sumpit.Masalahnya,bilasemuaphilosopherhamsmengambilsumpitdikiri dankanan,makatangankiri pertama-tamaakanmengambilsumpitkemudianmenungguuntuksumpitdi kanan,merekaakanmenungguselamanyadankelaparan.Place-placeCl,C2...CSmewakilisumpitdansejakinitialnyabebas,sebuahtokenterletakdi dalamsetiaptandainisial.Tiapphilosopherdiwakili oleh2 placeMj danEj yangmenggambarkanperencanaandancaramakansecaraberurutan.Untukseorangphilosopheruntukmajudarlbagianperencanaanke bagianmakanan,keduasumpithamstersedia.
70
-
Garnbar3-25.Masalah dining philosopher. Setiap philosopherdimodelkanolehduaplace,sedangberfikiradalahMj dansedangmakanEr
3.4.7MasalahReader/Writer
Ada beberapamasalahreader/ writeryangberlainan,tetapipadadasarnyamempunyaistrukturyangsarna.Prosesnyaada2 tipe,yaitu:ReaderdanWriters.SemuaprosesdibagimenjadiCommonfile,variabledanobyekdata.Prosesreadertidakpernahmerubahobyekketikaproseswritermelakukanperubahan.Prosespenulisandemikiansatusarnalainharnsmengeluarkansemuaprosesreaderdlli1writerlainnya,tapiproses
71
-
readeryangmultipledapatmengaksesdatayangterbagisecaraserempak.Masalahnyaadalahmemberidefinisisebuahstrukturkontrolyangtidakdeadlockataumemperbolehkanpelanggarankriteriamutualexclusion.
Gambar3.26mengilustrasikansuatusolusibilajumlahprosesreaderdibatasin. padasuatusistemdimanajumlahprosesreadertidakterbatasmakahanyan readerdapatmembacapadasatusaat.
Readers Writers
Gambar3-26.MasalahReaderlWriterbilajumlahreaderdibatasisejumlahn. Padaawalnyaterdapatsejumlahs readerdant writer.
72
-
sGambar3-27.Permodelanoperasi-operasiP dan V pada suatusemaporeS.
Tiap-tiapsemaphoredimodelkanolehplace,nomerpadatokenpadaplacemenunjukkannilaidarisemaphore.SebuahoperasiP menggunakansemaphoreplacesebagaiinputdanoperasiV sebagm,outputnya.
Keuntungandarikemampuaniniuntukmemodelkanoperasi-operasiPdanV adalahbanyaknyasistemyangditulisataudirancangdenganmnggunakanoperasi-operasiPdanV. Sebagaicontoh,sistemoperasiVenusmenyediakanoperasi-operasiP danV sebagaibasismekanismeomunikasiantarproses.Sistemini kemudiandimodelkansebagaijaringan-jaringanpetri.
73
-
3.5 SISTEM-5ISTEM LAINNYA
DiagramPERTsudahlamadipakaidalamperencanaanproyek-proyekyangbesar.DiagramPERT adalahpresentasidalambentukgrafikdarihubunganantarabeberapakegiatanyangbermacam-macamyangmembuatsuatuproyekbesar.Proyekterdiridarisejumlahkegiatan,beberapakegiatanharnslengkapsebelumkegiatanlain dimulai.Di penjumlahanwaktuberhubungandengansalahsatukegiatanyangmenunjukanjumlahwaktuyangdiambil(kadang-kadangtigamacamwaktu-waktuterburuk,wakturata-rata,danwaktuterbaikberhubungandengansalahsatukegiatan).Kegiatan- kegi~tandipresentasikansecaragrafikolehnode,busurdipergunakanuntukmenghubungkankegiatandari node-nodeyangmemperlihatkansyarat-syaratyanghamsdidahulukan.
DiagramPERT memperlihatkantipeyangsamadariJaringanPetri.Kita dapatdenganmudahmengubahdiagramPERT ke JaringanPetri.SlahsatikegiatandaridiagramPERT dipresentasikanolehplace,dimanasyarat-syaratnyadipresentasikanolehtransisi.DiagramPERT(gambar3.28)dapatdiubahkeJaringanPetriyangditunjukkanpadagambar3-29.
Padaawalnya,.aplikasidariJaringanPetriadalahsebagaialatuntukmengoptimalkankodepadakompilerfortranCDC6600.PendekatanyangdiberikanolehShapirodanSaint(1970)adalahmemodelkanprogramFORTRAN sebagaiJaringanPetri,sesuaidengancarayangterdapatpadamodelflowchartpadabagian3.4.1.Kemudianstatement-statementdariprogramsecarasatupersatudiperiksauntukmnentukankendala-kendalapresedenminimaldiantarastatement-statementtersebut,yangmengijinkanJaringanPetriuntukmeletakkanbeberapabarisankendala-kendalabuatandariprogramtersebutKendala-kendalabuataninimembuatpadapemrogramFORTRANhamsdapatmengekspresikanprogramsesuaidenganpemyataanyangberurutan,meskipunhanyasebagianperintahyangdiperlukan.Sebagaicontoh,perhatikantigastatementberikutini :
lOx=x+l
20 y = y + 1
30 z = x + y
74
-
WalksandJandscapinl
Excavate
Key: Job timerequiRment
Job r;;JIdentiCic~
Stormdr:ains
Rouchplumbinc
FinishpJumbin,
P~int
FinishcJcctric~1work
Gambar3-28. DiagramPertpembuatansuaturumah.
75
-
Gambar3-29.RepresentasijaringanpetridaridiagramPertgambar3-28.
76
-
Statemen-statemen10dan20 ditulissebagaistatemen10sebelumstatemen20,tetapikendalaini tidaklahperIu.Statement-statement10dan20dapatdieksekusidalamurutansembarangdengantidakmempengaruhiprogram.Namun,statement30dibatasiuntukmengikutistatement10dan20.Alirankontroljugaharusdiperhatikanpadadalammenstatementkanulangkebutuhan-kebutuhanpengurutan.AnalisainimerupakananalisadarikondisiBernstein'suntukmenjamindeterminacy.HasildarianalisainiadalahsebuahJaringanPetri yangmenampilkanprogramdenganpembatasanrangkaianyangminimal.Masalahnyakini adalahuntukmengkompilasiprogramini.Hal ini membutuhkanpemetaanvariablekedalambentukregister-registerdaninstruksi-intruksipermintaanuntukmenghsilkansuatujumlahdarirangkaianperintahinstruksibahasamesin.6600adalahsuatuperkalianregister,perkaliandariunitfungsionalcomputer,sepertiyangdijelaskandalambagian3.3.3.Sejakunitfungsionaldapatdieksekusisecaraparalelpadabeberapainstruksi.Hal ini sangatpentinguntukmenggerakkaninstruksigunamemaksimalkancaraparaleldalamsuatueksekusipadafungsionalunit.Halinijugaberakibatpadapenugasanvariablekeregister.ModelJaringanPetridariprogrammenampilkanbatasandariprogramyangdigabungkandenganmodelJaringanPetriunitpengontrolCDC 6600,menampilkanbatasanyangditanggungolehperangkatkeras.Jaringangabunganini akanmenjelaskansemuainstruksirangkaianyangmungkindapatdiksekusipadaperangkatkerasdanmenampilkanalgoritrnaprogram.Jaringanini akandieksekusiuntukmenghasilkanbeberaparangkaianinstruksi.Duaataulebihrangkaiandiciptakanketika2 ataulebihtransisisecarabersamaansiap.Penembakansebuahtransisiakanmnghasilkansaturangkaian,penembakanyanglainnyamenghasilkanrangkaianyanglain.Sebagaicontoh,JaringanPetripadagambar3.30menggambarkanrangkaianabcdef,bacdef,danbacedf.Sepertipadarangkaianyangdihasilkan,jumlahdariwaktupengeksekusiuntukmasing-maingdiolah,danpadarangkaianyangtercepatakandigerakandengankompileruntukkemudiandieksekusiyangsebenamya.
77
-
Gambar3-30.JaringanPetriyangmerepresentasikanbeberapabarisaneksekusiinstruksi
SistemkimiaadalahcontohlaindarisistemyangdapatdimodelkandenganJaringanPetri.Persamaankimiadimodelkandengantransisi,sedangkanreaktandimodelkandenganplace,Nomortokendisuatuplacemenerangkanjumlahreaktandalamsistem.
Contoh: JaringanPetri dalamgambar3.31menggambarkan2persamaankimiaberikutini :
H2C204~ 2C02+2H++2e2e+2H++H202~ 2H20
Gambar3-31. Suatujaringanpetriyangmenyatakanreduksi-oksidasidariasamaxalicdanidrogenporoksidamenjadikarbondioksidadanair.
78
-
Reaksikatalisjugadapatdipresentasikan.KombinasiHidrogendanetilenkebentuketana(H2+C2~) hanyaterjadijika terdapatPlatinum.Hal ini digambarkanpadagambar3.32.
Gambar3-32. Produksiethanedarihidrogendanethylane
SistemyanglainyangdapatdimodelkanolehJaringanPetrimeliputibarisanJaringankerja(dimanabarisanini dimisalkanolehplacedanpekerjaanolehtoken),modelotak(garisneurondimodelkanolehgaristransisi),keseimbangankalkulus[Genrich1975;GenrichK Lauconbach1978](ini mewakilkanliteraturdankombinasitransisimerekauntukmengabungkanklausadalambentuknormal)danbanyaklagilainnya.
Panjangdibatasiolehwaktudanimajinasidaripemodelitusendiri,dantidakdibatasiolehmodelJaringanpetri.Walaupunbegitu,kitamelihatpalingsedikitsatucontoh(masalahpenulisI pembaca)dimanatidakdapatdimodelkankedalamJaringanPetri.Dan,walaupunmodeldariJaringanPetri dapatmenolongmenjelaskansebuahsistem,kita perlujugamenggunakanalat-alatanalisauntukmengujiJaringanPetridanmenentukankepemilikanJaringanPetritersebut.Ini akanmembawakitake bagianberikutnya,dimanakitamenampilkanmetodaanalisuntukJaringanPetri.
79