ࡱ>  " 6bjbjT~T~ :,66( =====QQQ8$Q ($mJ=====pIaQt0 =`\  : Operating Systems: Homework 3 1) Tanenbaum problem 2-9 for edition 3. [5 pts] 2) Tanenbaum problem 2-13 for edition 3. [5 pts] 3) Tanenbaum problem 2-14 for edition 3. [5 pts] 4) Tanenbaum problem 2-17 for edition 3. [5 pts] 5) Tanenbaum problem 2-23 for edition 3. [5 pts] 6) Tanenbaum problem 2-25 for edition 3. [5 pts] 7) There are two flow charts below. Each is intended to provide mutual exclusion in the use of resource X by two processes executing that flowchart (process 1 executes the left half of the flowchart; process 2 executes the right half). The Boolean variables P1 and P2 are intended to be flags which provide mutually exclusive access to resource X. Both processes initially enter and start at the top block. Assume that the processes are interruptible between any two rectangles/triangles in the flowchart. Also assume that the scheduler can switch between the two processes in any arbitrary order. Analyze both flowchart (a) and (b). Does either flowchart provide effective mutual exclusion without any other problems ? If so, explain in words how it is accomplished. If not, explain why not and give an execution sequence (by numbering the rectangles/triangles) for the two processes that would violate the mutual exclusion condition or cause some other problem. (a) [15 pts] (b) [15 pts]  EMBED Word.Picture.8   EMBED Word.Picture.8  8) A pipe can be thought of as a scratch file created by a system call. It can be used as a communications channel between concurrently running processes. The interface call to a pipe is similar to that for any file. In fact, the process reads and writes to a pipe just like to a file. Unlike files, however, pipes do not represent actual devices or areas on disk. Instead, they are transient areas in memory. Just as a pipe is used by the shell to pass information on the command line, a program pipe is used to pass information from one process to another. A pipe's main advantage is that it can provide much higher bandwidths than if the processes read and write from a physically moving media (as would be the case with ordinary disk files). Pipes have a finite capacity and relay their information on a first-in, first-out (FIFO) basis. The system blocks a process until the read/write can be satisfied. That is, if the reader gets ahead of the writer, the reader just waits for more data. If the writer gets too far ahead of the reader and manages to completely fill the pipe (the size of which is system dependent), it sleeps until the reader has a chance to catch up. Also, once information is read from the pipe, it is erased, thereby freeing up pipe space. It should be noted that pipes do have some disadvantages. One of the more notable ones is the fact that the processes communicating over the pipe must be related, typically as a parent and child, or as two siblings. The reason for this is because one process has to tell the other what the file (pipe) descriptor is. This descriptor is only valid in the context of a particular execution environment. Therefore, two unrelated processes generally cannot share a pipe. This can be a constraint for many applications where the potential reader and writer of the pipe originate from different, unrelated processes. On the other hand, if a pipe is established in a process before creating (forking) another process, the new process will inherit the pipe file descriptor thereby making it valid in both execution environments. A sample initialization sequence for a pipe that will enable messages of 15 characters to be exchanged between processes is of the form: #include #define MSGSIZE 16 /* This figure should include room for a terminating null */ int pfd[2], retval; char msg [MSGSIZE], buffer[MSGSIZE]; retval = pipe(pfd); write (pfd[1], msg, MSGSIZE); read (pfd[0], buffer, MSGSIZE); The call creates a pipe represented by two file descriptors that are returned in the pfd array. Writing to pfd[1] puts data in the pipe; reading from pfd[0] gets data out. Execution of the above code sequence creates an execution environment which can allow for IPC (Inter-Process Comm.) to occur via a pipe. a) Write a single program which will create a pipe, write at least four messages down it, and then read them back. Although this particular exercise does not demonstrate IPC (since there is only one process), it demonstrates how pipes can be used as a scratchpad FIFO buffer within a process. [20 pts] b) Write a program which will spawn a child process and establish communication between the parent and child via a pipe. The parent process should write at least four messages down the pipe. The child process should read all the messages from the pipe. Insert process ID statements so that the progress of the two processes can be traced. [20 pts] For example: "This is the parent process. Writing first message into pipe." . . . . . . "This is the child process. Reading first message from pipe. Contents is:" . . . . . .      !#7HINTUWk}~   ! " ( ) * + ? Q R W ] ^ _ ` ߺ߰հߟ߰հߟ߰հߟߊՊߟߟherOJQJ^JhR!5OJQJ^J hR!hR!CJOJQJ^JaJhR!OJQJ^J hR!hPXCJOJQJ^JaJh1kYOJQJ^Jh5?OJQJ^JhPXOJQJ^JhPX5OJQJ^Jh5?5OJQJ^J4 !TU( ) ] ^ , - . X Y  $1$a$gdR! $1$a$gdC $dh1$a$gdC  % * J  + , - . 3 6 : K N R Y Z q r s t w x 쿵쿵쭩{jV'j-E hChPXOJQJUV^J!j-E hCOJQJUV^JhCOJQJ^JjhCOJQJU^Jj.E hPXUVj.E hCUVhCjp1hCUh1kYOJQJ^JhPX5OJQJ^JhPXCJOJQJ^JaJhR!OJQJ^Jh<OJQJ^JhPXOJQJ^JhI4OJQJ^J! ab'39TZno{ 2I35<ĺĬĬĺĬĞĞĞĞĺĔĊuĊh_RNOJQJ^Jh_RN5OJQJ^Jh1kYOJQJ^Jh)?OJQJ^JhR!CJOJQJ^JaJhR!CJOJQJ^JaJh= OJQJ^JhR!OJQJ^JhR!5OJQJ^JhPXCJOJQJ^JaJhPXOJQJ^JjhCOJQJU^J.aby(JnoJK $1$a$gd< $1$a$gdI4 $ 1$a$gdR! $1$a$gdR!<=JK'()+,./1256ƾhg*jhg*UhI4h<OJQJ^JhI4OJQJ^JhR!CJOJQJ^JaJhR!OJQJ^Jh_RNOJQJ^J(*+-.013456 $1$a$gd< 8P:p</ =!8"8#$@% Dp !/0$%&'()*+,-.17234568>9:;<=?ABCDEFGHIJKLMNORoot Entry F ha#1Data WordDocument:,ObjectPoolpIa ha_1169532206  FpIapIaPIC dMETA  PICT 1   !"#$%&'()*+,-./023456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[^`abcdefghijklmnopqrstuvwxyz{|}~d ,! ,   ? .  & --E)e t Geneva 8؟ww w f/- !Start & & - & -$WWW &  & y]H,tXxWW & --$WSWZW-WW &    & -$VGGGV- G &  & -$W,SWZW,-WW & GWXWtXX &  & & -)) & --$ &  &  y ]H ,t X x & --$- & 000 & -$-0 &  & -$,,- & GXt &  &    ;<5<55< &  & 77766>6 &  & -$z^vOzO}Oz^-DzOz &  & -$]OOO]-DO &  & -$))- &  GenevaI 8؟ww w f/- ! P1 = False 4 ! P2 = FalseB Geneva 8؟ww w f/- ! Non-Criticaln3 ! Non-Criticaln ! P1 = Truee; ! P2 = Truee!P1!P2P!T!T"!F]!F !Read X<D !Read X= !Update Xi> !Update Xi ! P1 = False; ! P2 = False & -$>^:O>OBO>^-6>O> &  & -$\NN N\-5N &  & ' > > 1)eE 8 At H  , Geneva .+Start > ""qWWW  "W$##8###7###  > #$#8##7#ܠ 1 8 1]y 8 1,H 8 1Xt 8 1 8"xWd MDPL qSZWSWZW"WdMDPL "" ɡd MDPL qGVVGGGV" ;dMDPL d MDPL qS,Z,WSWZ,W"WdMDPL "GW"tX ")"q  "8$#######7#  > #8$####7ܠ 1 8 1]y 8 1,H 8 1Xt 8 1 8"xd MDPL q"dMDPL "#ɡd MDPL q"0dMDPL d MDPL q,,,"dMDPL "G"t" #/ <5<"55"7 #!6"6>d MDPL qOv^}^zOvOzO}^z"Dz dMDPL d MDPL qO]]OOO]"D dMDPL d MDPL q)))" dMDPL  *F (4 P1 = False * P2 = False & b2r (n3 Non-Critical & br ) Non-Critical  :v(; P1 = True  ( P2 = True  +QP1  O`(PP2  (T  !*("T  \d(]F  (F  0C@l(<DRead X  1A+Read X  ]=ms(i>Update X  ]m)Update X  :{(; P1 = False  ) P2 = Falsed MDPL  >qO:^B^>O:O>OB^>"6>dMDPL d MDPL qN\ \NNN \"5dMDPL d ,! , ~  ? .ObjInfo\_1169532205  FpIapIaPIC ]dMETA  _   & --E)e t Genevax ,8؟ww w f- !Starty]H,tXGWXWtXXy ]H ,t X GXt;<5<5 5<XXX66>6 & --$z^vOzO}Oz^-DzOz &  & -$]OOO]-DO &  & -$))- &  Geneva 18؟ww w f- ! P1 = False 4 ! P2 = FalseB Genevax -8؟ww w f- ! Non-Criticaln3 ! Non-Criticaln-W+W+ ! P1 = Truee : ! P2 = Truee  & - & -$WWW &  &  & --$WSWZW-zWW &    & -$VGGGV- G &  & -$WSWZW-WW &  & -)) & --$ &  &  & --$-z & 000 & -$-0 &  & -$- & !P1!P2P!T!T"!F]!F !Read X<D !Read X= !Update Xi> !Update Xi ! P1 = False; ! P2 = False & -$ \N N N \-5 N  &  & -$>];O>OBO>]-6>O> &  & ' > > 1)eE 8 At H  , Geneva .+Start > 1]y 8 1,H 8 1Xt PICT  ObjInfo1Table@SummaryInformation(8 1 8"GW"tX 1]y 8 1,H 8 1Xt 8 1 8"G"t" #V <5<"5 2"X # 6"6>d MDPL qOv^}^zOvOzO}^z"Dz dMDPL d MDPL qO]]OOO]"D dMDPL d MDPL q)))" dMDPL  *F (4 P1 = False * P2 = False & b2r (n3 Non-Critical & br ) Non-Critical > 1 8"W 1 8"  9u( : P1 = True  ( P2 = True > ""qWWW  "W$##8###7###  > #$#8##7#ܠd MDPL qSZWSWZW"zWdMDPL "" ɡd MDPL qGVVGGGV" ;dMDPL d MDPL qSZWSWZW"WdMDPL ")"q  "8$#######7#  > #8$####7ܠd MDPL q"zdMDPL "#ɡd MDPL q"0dMDPL d MDPL q"dMDPL  (P1  O`(PP2  (T  !*("T  \d(]F  (F  0C@l(<DRead X  1A+Read X  ]=ms(i>Update X  ]m)Update X  :{(; P1 = False  ) P2 = Falsed MDPL  >qN\ \ NN N \ "5 dMDPL d MDPL qO;]B]>O;O>OB]>"6>dMDPL Oh+'0  0 < H T`hpxM 2White, KathyNormal 4Microsoft Office Word@H'@2nXm@-3@Za&DocumentSummaryInformation8CompObjy՜.+,0 hp|   $  M 2 Title  F'Microsoft Office Word 97-2003 Document MSWordDocWord.Document.89qf 666666666vvvvvvvvv666666>6666666666666666666666666666666666666666666666666hH6666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~OJQJ_HmH nH sH tH @`@ NormalCJ^J_HmH sH tH DA D Default Paragraph FontRiR  Table Normal4 l4a (k (No List 4 4 Footer  !44 Header  !H&H Footnote Reference CJEHaJ:": Footnote TextCJ.)1. Page NumberRBR viewgraph textd5CJ$OJQJ^JPK![Content_Types].xmlj0Eжr(΢Iw},-j4 wP-t#bΙ{UTU^hd}㨫)*1P' ^W0)T9<l#$yi};~@(Hu* Dנz/0ǰ $ X3aZ,D0j~3߶b~i>3\`?/[G\!-Rk.sԻ..a濭?PK!֧6 _rels/.relsj0 }Q%v/C/}(h"O = C?hv=Ʌ%[xp{۵_Pѣ<1H0ORBdJE4b$q_6LR7`0̞O,En7Lib/SeеPK!kytheme/theme/themeManager.xml M @}w7c(EbˮCAǠҟ7՛K Y, e.|,H,lxɴIsQ}#Ր ֵ+!,^$j=GW)E+& 8PK!Ptheme/theme/theme1.xmlYOo6w toc'vuر-MniP@I}úama[إ4:lЯGRX^6؊>$ !)O^rC$y@/yH*񄴽)޵߻UDb`}"qۋJחX^)I`nEp)liV[]1M<OP6r=zgbIguSebORD۫qu gZo~ٺlAplxpT0+[}`jzAV2Fi@qv֬5\|ʜ̭NleXdsjcs7f W+Ն7`g ȘJj|h(KD- dXiJ؇(x$( :;˹! I_TS 1?E??ZBΪmU/?~xY'y5g&΋/ɋ>GMGeD3Vq%'#q$8K)fw9:ĵ x}rxwr:\TZaG*y8IjbRc|XŻǿI u3KGnD1NIBs RuK>V.EL+M2#'fi ~V vl{u8zH *:(W☕ ~JTe\O*tHGHY}KNP*ݾ˦TѼ9/#A7qZ$*c?qUnwN%Oi4 =3ڗP 1Pm \\9Mؓ2aD];Yt\[x]}Wr|]g- eW )6-rCSj id DЇAΜIqbJ#x꺃 6k#ASh&ʌt(Q%p%m&]caSl=X\P1Mh9MVdDAaVB[݈fJíP|8 քAV^f Hn- "d>znNJ ة>b&2vKyϼD:,AGm\nziÙ.uχYC6OMf3or$5NHT[XF64T,ќM0E)`#5XY`פ;%1U٥m;R>QD DcpU'&LE/pm%]8firS4d 7y\`JnίI R3U~7+׸#m qBiDi*L69mY&iHE=(K&N!V.KeLDĕ{D vEꦚdeNƟe(MN9ߜR6&3(a/DUz<{ˊYȳV)9Z[4^n5!J?Q3eBoCM m<.vpIYfZY_p[=al-Y}Nc͙ŋ4vfavl'SA8|*u{-ߟ0%M07%<ҍPK! ѐ'theme/theme/_rels/themeManager.xml.relsM 0wooӺ&݈Э5 6?$Q ,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}|$b{P8g/]QAsم(#L[PK-![Content_Types].xmlPK-!֧6 +_rels/.relsPK-!kytheme/theme/themeManager.xmlPK-!Ptheme/theme/theme1.xmlPK-! ѐ' theme/theme/_rels/themeManager.xml.relsPK] 6,  <66Yqsw6::8@0(  B S  ?Yb-6pw;>((**++-.01347!I+5,1NRm((**++-.0134733333333333377HIMNUkk}~  )??QRVW %+39:QRY {2I35<='777HIkk}~  ??QR 7PXe( ]+I4Cy,H_RN1kYerxlw 6g*= R!5?<Vf)?(*@$$p $$6@UnknownG* Times New Roman5Symbol3. * Arial3* TimesY New YorkTimes New Roman;. * HelveticaA BCambria Math hZF 2 & & $& $$+xxd2+HX?C2!xxM 2 White, Kathy