HW2 SOL - Homework assignment number 2 for CYSE 211 PDF

Preview

Summary

Homework assignment number 2 for CYSE 211...

Description

1 .Gi v e nt hef o l l o wi n gc o nfig u r a t i o nwi t hj ob sa r r i v i n gi no r d e r( J o bA, B, C, D)a n dwi t h bl o c k ss h o wni no r d e rf r o ml o wo r d e rme mo r yt oh i g ho r d e rme mo r y : [ St a r tUNTp. 5 3 2he r e ]Edi t or :t he s es ho ul da ppe ara s2t abl e s J o bLi s t :

Me mo r yBl o c kLi s t :

J o bNumbe r

Me mor y

Me mo r yBl o c k

Re que s t e d

Me mo r y Bl oc kSi z e

J o bA

2 5 6K

Bl o c k1

91 0 K

J o bB

9 0 0K

Bl o c k2

90 0 K

J o bC

5 0 K

Bl o c k3

20 0 K

J o bD

3 5 0K

Bl o c k4

30 0 K

[ EndUNTp. 5 3 2he r e ] a .

Us et h eb e s t fita l g o r i t h mt oi n d i c a t ewh i c hme mo r yb l o c k sa r ea l l o c a t e dt oe a c h o ft h ea r r i vi n gj o b s . ANSWER: J obA( 2 5 6 K)ge t sBl oc k4( 3 0 0 K) J obB( 9 0 0 K)g e t sBl o c k2( 9 00 K) J obC( 5 0 K)g e t sBl o c k3( 2 0 0K) J obD( 3 5 0 K)ge t sBl oc k1( 9 1 0 K)

b .

Us et h efir s t fita l g o r i t h mt oi nd i c a t ewh i c hme mo r yb l o c k sa r ea l l o c a t e dt oe a c h o ft h ea r r i vi n gj o b s . ANSWER: J obA( 2 5 6 K)ge t sBl oc k1 , J obB( 9 0 0 K)g e t sBl o c k2 . J obC( 5 0 K)g e t sBl o c k3 .

J obDi sn otp r o c e s s e di mme d i a t e l yb e c a u s ei ti st ool a r g ef o rt h el a s ta v a i l a bl eb l o c k ( wh i c hi sBl o c k4 ) . Ho we v e r , i twi l lb ep r o c e s s e da f t e re i t h e rBl o c k1o rBl o c k2 b e c o mea v a i l a b l ea n di sa l l o c a t e dt oJ o bD, wh i c hi swa i t i n g . c .

Ca l c u l a t et h et o t a la mo u n to fi n t e r n a lf r a gme n t a t i o ni na l lf o u rb l o c k su s i n gt he b e s t fit a l g o r i t h m. ANSWER: o Bl o c k4( wi t hJ obA)h a s4 4Kf r a g me n t a t i o n . o Bl o c k2( wi t hJ obB)h a sz e r of r a g me n t a t i o nbe c a u s et h ej o ba n db l o c ka r et h e s a mes i z e , 9 0 0K. o Bl o c k3( wi t hJ obC)h a s1 50 Ki nf r a g me n t a t i o n . o Bl o c k1( wi t hJ obD)h a s5 6 0 Ki nf r a g me n t a t i o n . o To t a lf r a g me n t a t i o nf o ra l lf o u rb l o c k s( 4 4 +0 +1 50 +5 6 0)i s7 5 4 K.

2 .Ne x t fit i sa na l l o c a t i o na l g or i t h mt h a ts t a r t sb yu s i n gt h efir s t fita l g or i t h mb u ti t k e e p s t r a c ko ft h ep a r t i t i o nt h a twa sl a s ta l l o c a t e ds ot h a ti tc a ns t a r ti t sne x ts e a r c hf r o mt h a t e x a c ts p o ti n s t e a do fr e s t a r t i n gt h es e a r c hwi t hBl oc k1 . I not h e rwo r ds , i t s t a r t ss e a r c h i n g f r om t h emo s tr e c e nt l ya l l o c a t e db l oc kwh e nt hen e xtj o ba r r i v e s . Us i n gt h ef ol l o wi n g c o n fig u r a t i o nwi t hj o b sa r r i v i n gi no r d e r( J o bA, B,C, D)a n dwi t hbl o c k ss h o wni no r d e r f r om l o wo r d e rme mo r yt oh i g ho r d e rme mo r y :

[ St a r tUNTp. 5 41he r e ]Edi t or :t he s es ho ul da ppe a ra s2s i de b y s i det a bl e s

J o bLi s t :

Me mo r yBl o c kLi s t :

J o b

Me mo r y

Me mo r yBl o c k

Me mor yBl o c kSi z e

Numbe r

Re que s t e d

J o bA

6 2 5 K

Bl o c k1

2 5 0 K

J o bB

4 4 K

Bl o c k2

9 0 0 K

J o bC

9 0 0 K

Bl o c k3

2 8 0 K

J o bD

2 2 0 K

Bl o c k4

2 0 0 K

Bl o c k5

5 0 K

[ EndUNTp. 5 4 1he r e ] ( a )I n d i c a t ewh i c hme mo r yb l o c k sa r ea l l o c a t e dt oe a c ho ft h ea r r i v i n gj o b s . ANSWER: J o bA( 6 2 5 K)d o e s n ’ tfiti n t oBl o c k1a n ds og e t sBl o c k2( 9 0 0 K) . Wh e nJ o bB( 4 4 K)a r r i v e s , i t d o e sn o tg e tBl oc k1( 2 5 0 K)b e c a u s et h en e x t fits y s t e m c h o os e st h en e x tb l o c ka f t e rt h eo n emo s tr e c e n t l ya l l o c a t e d ,wh i c hi sBl o c k2 . Th e r e f or e , J o bBg e t sBl o c k3( 2 80 K) . J o bCc a n n o tb ea l l o c a t e da n ds oh a st owa i tb e c a u s ei ti sv e r yl a r g ea n dt h eo n l y b l o c kt ha t ’ sl a r g ee n o u g h( Bl o c k2 )h a sa l r e a d yb e e na l l o c a t e dt oJ o bA. Att h i spo i n t , t h el a s ta l l o c a t e dj o bi sBl oc k3s ot h en e x ti nc omi n gj o b , J o bD, i sa l l o c a t e dt ot h en e x tb l o c kt h a t ’ sl a r g ee n o u g ht oh ol di t , Bl o c k1( 25 0 K) . La t e r , wh e nJ o bAi sd o ne , Bl o c k2c a nb ea l l o c a t e dt ot h ewa i t i n gJ o bC. ( b )Ex p l a i ni ny o u ro wnwo r d swh a ta d v a n t a g e st h en e x t fita l g o r i t h mc o u l do ffe r . ANSWER:Th i sa l l o c a t i o ns c h e mei sd e s i g n e dt oma k ep r o c e s s i n gt i memo r ee ffic i e n t b utd o e sn o tn e c e s s a r i l yr e d u c ef r a g me n t a t i o n .I two u l da l s oa l l o c a t et h eb l o c ksa t t h e b o t t o moft h el i s t mo r eo f t e nt h a tfir s t fit o rb e s t fit , b o t hofwh i c hb e g i ns e a r c h i n gf o r a v a i l a b l eb l o c k sf r o mt h efir s tb l o c k .

3 .Wo r s t fiti sa na l l oc a t i o na l g o r i t hm t h a ta l l o c a t e st hel a r g e s tf r e eb l o c kt oan e wj o b .I ti s t h eop p o s i t eo ft heb e s t fita l g o r i t h m. Us i n gt h ef o l l o wi n gc o n fig ur a t i onwi t hj o b sa r r i vi n g i nor d e r( J o bA,B, C, D)a ndwi t hb l o c k ss h o wni no r d e rf r o ml o wo r de rme mo r yt oh i g h or d e rme mo r y : [ St a r tUNTp. 5 41he r e ]Edi t or :t he s es ho ul da ppe a ra s2s i de b y s i det a bl e s J o bLi s t :

Me mo r yBl o c kLi s t :

J o b

Me mo r y

Me mo r yBl o c k

Me mor yBl o c kSi z e

Numbe r

Re que s t e d

J o bA

4 4 K

Bl o c k1

2 5 0 K

J o bB

2 2 0 K

Bl o c k2

9 0 0 K

J o bC

6 7 0 K

Bl o c k3

2 8 0 K

J o bD

6 4 K

Bl o c k4

2 0 0 K

Bl o c k5

7 5 0 K

[ EndUNTp. 5 4 1he r e ] a )I n d i c a t ewh i c hme mor yb l o c k sa r ea l l o c a t e dt oe a c ho ft hea r r i v i n gj o b s . ANSWER: J o bA( 4 4 K)wi l l b ea l l o c a t e dt ot h eb i g g e s ta v a i l a b l eb l o c k , Bl o c k2( 9 0 0 K) . -Th e nJ o bB( 2 2 0 K)wi l lg e tt heb i g g e s ta v a i l a b l eb l o c k ,Bl o c k5( 7 5 0 K) . J o bC( 6 7 0 K)wi l ln e e dt owa i tu n t i lab l o c kt h a t ’ sl a r g ee n o u g h( Bl o c ks2o r5 )b e c o me s a v a i l a b l e . J o bD( 6 4 K)wi l lb ea l l o c a t e dBl o c k3b e c a u s ei t ’ st h el a r g e s ton ea v a i l a b l eo ft h efiv e b l o c k s . b )I nt hi sc h a p t e rwei n t r od u c e de x t e r n a la n di n t e r na lf r a g me n t a t i on . Ex p l a i ni ny o u ro wn wo r d swh i c ho n ewo ul db ee x p e c t e di nawo r s t fitme mo r ya l l oc a t i o ns c h e me

ANSWER:Th ewo r s t fitme mo r ya l l o c a t i o ns c h e mel e n d si t s e l ft oi n t e r n a lf r a g me n t a t i o n b e c a us et h eb l o c ksa l l o c a t e dt ot hei n c o mi n gj o b sc a nb emu c hl a r g e rt h a nn e c e s s a r y ,c a u s i n g wa s t e ds p a c ewi t h i nt h eb l o c k( i n t e r n a lf r a g me n t a t i o n )a n dn o tb e t we e nb l o c k s( e x t e r n a l f r a g me n t a t i o n ) . 4 .I ma g i n ea no p e r a t i n gs y s t e mt h a tc a n no tp e r f o r mme mo r yd e a l l o c a t i o n . Na mea tl e a s t t h r e ee ffe c t so no v e r a l l s y s t e mp e r f o r ma n c et h a tmi gh tr e s u l ta n de x p l a i ny o u ra n s we r . ( An s we r ) An s we r sh e r ewi l lv a r yb u tc o u l di n c l u d et h ef ol l o wi n g . Th i sq u e s t i o nc o u l di n v i t ea d i s c u s s i o no ft h ep r o b l e m of“ me mor yl e a k s ”wh e r ea na p p l i c a t i o nr e l e a s e ss omeb u tno ta l l a l l o c a t e dme mo r ys p a c e( t h i si sas u b j e c tno td i s c u s s e di nt h i st e x t ) . • I two u l dr u no u to fa v a i l a b l eme mo r ya ss o o na se a c ha v a i l a b l eme mo r yl o c a t i o nwa s u s e do n c e . Me mo r yc o u l dn e v e rber e u s e db ya n o t he rp r o gr a m. • I ft h eo n l ywa yt oc l e a rme mo r ywa st or e b o o t , t h e nt h es y s t e m wo u l dn e e dt ob er e b o o t e d o f t e n . • Su c has y s t e mwo ul dne e dv a s tme mo r yr e s e r v e st owo r k . • Su c has y s t e mwo ul de n c o u r a g et hed e v e l o pme n to fa p pl i c a t i o n st ha tn e e d e dv e r ys ma l l me mo r yr e s o u r c e s . 5 .I nas y s t e mu s i n gt h er e l o c a t a b l ed y n a mi cp a r t i t i o n ss c he me ,g i v e nt hef o l l o wi n gs i t u a t i o n ( a n du s i n gd e c i ma l f o r m) :J o bQi sl o a d e di n t ome mo r ys t a r t i n ga t me mo r yl o c a t i o n4 2 K.

a . Ca l c u l a t et hee x a c t s t a r t i n ga d d r e s sf orJ o bQi nb y t e s .An s we r :4 30 0 8( 4 2 * 1 0 2 4= 43 0 0 8 ) b . I ft h eme mor yb l o c kh a s3 Ki nf r a g me n t a t i o n, c a l c u l a t et h es i z eoft h eme mo r ybl o c k . An s we r :4 6 0 8 0( 3* 1 0 2 4=3 07 2 )+( 42 * 1 0 2 4=43 0 0 8 )=4 6 0 8 0

c . I st h er e s u l t i n gf r a g me n t a t i o ni n t e r n a lo re x t e r n a l ?Ex p l a i ny o u rr e a s o n i n g . An s we r : Lo okf o raf u n d a me nt a lu n d e r s t a n d i n go ft h ed i ffe r e nc e sb e t we e ni n t e r n a la n de x t e r n a l f r a g me n t a t i on . 6 .I nas y s t e mu s i n gt h er e l o c a t a b l ed y n a mi cp a r t i t i o n ss c he me ,g i v e nt hef o l l o wi n gs i t u a t i o n ( a n du s i n gd e c i ma l f o r m) :J o bW i sl oa d e di n t ome mo r ys t a r t i n ga tme mor yl o c a t i o n 50 0 0 K. a . Ca l c ul a t et h ee x a c t s t a r t i n ga d d r e s sf o rJ o bW i nb y t e s .An s we r :51 2 0 0 0 0( 5 0 0 0* 1 0 2 4= 5 1 2 00 0 0 ) b . I ft h eme mo r yb l o c kh a s3 Ki nf r a g me n t a t i o n , c a l c u l a t et h es i z eo ft h eme mo r yb l o c k . An s we r :5 13 0 2 4 0( 1 0* 1 0 2 4=1 02 4 0 )+( 5 0 0 0 * 1 02 4=5 12 0 00 0 )=5 13 0 2 4 0 c . I st h er e s u l t i n gf r a gme n t a t i o ni n t e r n a lo re x t e r n a l ?Exp l a i ny o u rr e a s on i n g . An s we r :Lo ok f o raf un d a me n t a lu n d e r s t a n d i n go ft h ed i ffe r e n c e sb e t we e ni n t e r na la n de x t e r n a l f r a g me n t a t i o n .

7 .Us i n gy o u ro wnwo r d s , e x p l a i nt h er o l eo ft heb ou n d sr e g i s t e r . An s we r :Th i sh a r d wa r ee l e me n t , t h eb o un d sr e gi s t e r ,t r a c kst h el i mi t sofa d d r e s s a b l eme mo r y f o rt h i sj o ba n dpr e v e n t si tf r o mt r y i n gt oa c c e s sme mo r yt h a t ’ sa l l oc a t e dt oa n o t h e rj o b .

8 .De s c r i b ei ny o u ro wnwo r d st h er o l eo ft h er e l o c a t i o nr e g i s t e r . An s we r :Th i sh a r d wa r ee l e me n t , t h er e l o c a t i o nr e g i s t e r , t r a c k st h en u mb e ro fb y t e s t h a taj o bh a sb e e nmo v e di nma i nme mor ya sar e s u l to fme mo r yc o mp a c t i o n . I ti s u s e dt ot r a c ke a c hi n s t r u c t i o ns oi tc a nb ef o un ds u c c e s s f u l l ya f t e rt h ej o b ’ sr e l o c a t i o n 9 .I ft h er e l o c a t i o nr e g i s t e rh o l d st h ev a l u e8 3 9 6 8 ,wa st h er e l o c a t e dj o bmo v e dt o wa r dl o we r o rh i g he ra d d r e s s a b l ee n do fma i nme mo r y ?An s we r :I twa smo v e dt o wa r dt h el o we r

a d d r e s s a b l ee n do fme mo r y)Byh o wma n yki l o b y t e swa si tmo v e d ?An s we r :I twa smo v e d 8 2K( 83 9 6 8/1 02 4=8 2 )Ex p l a i ny o u rc o n c l u s i o n. St u d e n t ss h o u l de x p l a i nh o wt h e y r e a c h e dt h e i rc o n c l u s i o nb ys h o wi n gt h e i rwo r k . 1 0 . I nas y s t e mu s i n gt h efix e dp a r t i t i o nsme mo r ya l l o c a t i o ns c h e me , gi v e nt h ef o l l o wi n g s i t u a t i o n( a n du s i n gd e c i ma l f o r m) :Af t e rJ o bJi sl o a d e di n t oap a r t i t i o no fs i z e5 0 K, t h e r e s u l t i n gf r a g me n t a t i o ni s71 6 8b yt e s . Pe r f o r mt h ef o l l o wi n g : a .

Wh a ti st h es i z eo fJ o bJi nb yt e s ?An s we r :J o bJi s4 4 0 3 2b y t e s( 5 0 * 1 0 2 4= 5 1 2 0 0)–7 16 8=4 4 0 3 2b y t e s

b .

Wh a tt y p eo ff r a g me nt a t i o ni sc a us e d ?An s we r :I n t e r na lf r a g me n t a t i on

1 1 .I nas y s t e mu s i n gt h ed y n a mi cp a r t i t i o nme mo r ya l l o c a t i o ns c h e me , g i v e nt h ef o l l o wi n g s i t u a t i o n( a n du s i n gd e c i ma lf o r m) : Af t e rJ o bCo fs i z e7 0 Ki sl o a d e di n t oap a r t i t i o nr e s u l t i n g i n7 Ko ff r a g me n t a t i o n , c a l c u l a t et h es i z e( i nb y t e s )o fi t sp a r t i t i o n( An s we r : 7 16 8 0 ( 7 0 * 1 02 4=7 1 6 8 0)a n di d e n t i f yt h et yp eo ff r a g me n t a t i ont h a t i sc a u s e d( Ex t e r n a l f r a g me n t a t i on ) . Ex p l a i ny o u ra n s we r .( St u d e n t ss h o ul ds h o wt h e i rc a l c u l a t i o nsa n d e x p l a i nh o wt h e ykn o wt ha tt hef r a g me n t a t i o ni sb e t we e np a r t i t i o n si n d i c a t i n ge x t e r n a l f r a g me n t a t i ona n dn o twi t h i np a r t i t i o n s , wh i c hwo u l di n d i c a t ei n t e r n a lf r a g me n t a t i on . )

Adv a nc e dEx e r c i s e s 1 2 . Th er e l o c a t i o ne x a mp l ep r e s e n t e di nt h ec h a p t e ri mpl i e st h a tc o mp a c t i o ni sd o n ee n t i r e l y i nme mo r y , wi t h o uts e c o n d a r ys t o r a g e . Ca na l lf r e es e c t i o n so fme mo r yb eme r g e di n t o on ec o n t i g u o usb l o c ku s i n gt h i sa p p r o a c h ?Wh yo rwh yn o t ? ( s e ea t t a c he dd o c u me n tf o ra n s we rt o2 1 6 )

13. In this chapter we described one of several ways to compact memory. Some people suggest an alternate method: all jobs could be copied to a secondary storage device and then reloaded (and relocated) contiguously into main memory, thus creating a single free block after all jobs have been recopied into memory. Is this viable? Could you devise a better way to compact memory? Write your algorithm and explain why it is better. (Answer: This type of compaction may prove to be more time consuming than the previous one because it requires access to a secondary storage device. If the operating system and computer are equipped with "block" transfer and buffers (these are discussed later in the text), then the transfer time could be optimized. In addition, if the disk was a device dedicated only to compaction, then its hardware components could also be set to optimize the seek time. When using secondary storage one needs to remember that a store and load operation are performed every time increasing the time needed to complete compaction.

1 4 . Gi v e nt heme mor yc o n figu r a t i o ni nFi g u r e2 . 1 0be l o w,a n s we rt h ef o l l o wi n gq u e s t i o n s g i v e nt h a ta tt h i sp o i n t , J o b4a r r i v e sr e q u e s t i n gab l o c ko f10 0 K. a .

Ca nJ o b4( 1 0 0 K)bea c c ommo d a t e d ?Wh yorwh yn o t ?ANSWER:J o b4c a n n o t b ea c c o mmo da t e db e c a u s et h e r ei sn o te n o u g hc on t i g uo u sf r e eme mo r ya v a i l a bl e .

b .

I fr e l o c a t i o ni sus e d , a f t e rme mo r yc o mp a c t i o n, wh a ta r et hec o nt e n t so ft h e r e l o c a t i o nr e g i s t e r sf o rJ o b1 , J ob2 ,a n dJ o b3 ?ANSWER: Contents of Relocation Registers 0 -20480 (-20K) -30720 (-30K)

c .

Job Number 1 2 3

Wh a ta r et h ec o n t e n t so ft her e l o c a t i o nr e g i s t e rf o rJ o b4a f t e ri tha sb e e nl o a d e d i n t ome mo r y ?An s we r :Th er e l o c a t i o nr e g i s t e rf o rJ ob4i ss e tt oz e r ob e c a u s ei th a s j u s tbe e nl oa d e di n t ome mo r y .

d .

Ani n s t r u c t i o nt ha ti sp a r to fJ o b1wa so r i gi n a l l yl o a de di nt ome mo r yl o c a t i o n 2 2 K.Wh a ti si t sn e wl o c a t i o na f t e rc o mp a c t i o n ?An s we rI t sl o c a t i o nha sn o tc h a n g e d b e c a u s eJ o b1h a sn o tb e e nr e l o c a t e d .

e .

Ani n s t r u c t i o nt ha ti sp a r to fJ o b2wa so r i gi n a l l yl o a de di nt ome mo r yl o c a t i o n 5 5 K.Wh a ti si t sn e wl o c a t i o na f t e rc o mp a c t i o n ?An s we rI t sl o c a t i o ni s :5 5 K-2 0 K= 3 5 K( or3 5 8 4 0 )

f .

Ani n s t r u c t i o nt ha ti sp a r to fJ o b3wa so r i gi n a l l yl o a de di nt ome mo r yl o c a t i o n 8 0 K.Wh a ti si t sn e wl o c a t i o na f t e rc o mp a c t i o n ?An s we rI t sl o c a t i o ni s :8 0 K-30 K= 5 0 K( or5 1 2 0 0 ) g. If an instruction was originally loaded into memory location 110K, what is its new location after compaction? Answer: Its location is: 110K - 30K = 80K (or 81920)...