UNIVERSITY OF CALIFORNIACollege of EngineeringDepartment of Electrical Engineeringand Computer SciencesComputer Science DivisionCS 162 Prof. Alan J. SmithProblem Set 2Please place the work for this assignment online, and submit in the usual manner.1. Suppose asystem has a virtual address containing 28 bits. Suppose that the page size is 1024 bytes,that physical addresses contain 24 bits, and that the system uses a segmented-and-paged scheme with 256segments and a segment size of one megabyte.(a) Describe the address translation mechanism, using a picture to showthe relevant tables and opera-tions. Don’tworry about a TLB. Be sure to showthe exact size of each table (howmanyentries,howmanybits wide).(b) Suppose that a byte of physical memory is to be shared by twoprocesses. Describe howthe tablescould be arranged to permit this.(c) Suppose that a particular segment in this system contains 4800 bytes. Howmuch memory will thesegment cause to be wasted in internal and external fragmentation? Consider only the memoryallocated to the segment itself; do not worry about memory used in the mapping tables.(d) Nowsuppose that the owner of the 4800-byte segment wishes to expand it by 200 bytes. Whatmust the operating system do in order to increase its size? Compare this to a system based on puresegmentation.(e) Suppose that the segment is expanded again, from 5000 bytes to 5500 bytes. What must the operat-ing system do to accomplish this?2. Consider aprogram that generates the following set of page references:AAAABBCACBBDDAEBCEAEDEAssuming that the program is given3page frames, howmanypage faults are generated using the follow-ing replacement algorithms:(a) FIFO(b) MIN(c) LRU(d) Working Set. Tau= 6 (if six references have been made without accessing a page then it is nolonger in the working set). Forthis case, the program may need to use more than 3 page frames.Indicate howlarge the working set is at each point in time. Assume that pages are thrown out ofmemory as soon as theyleave the working set.3. Consider the clock algorithm for LRUpage replacement (also called "FINUFO" (first in, not used, firstout), also called "first chance" replacement). Suppose that there are P pages of physical memory in thesystem and that overaparticular interval of time F page faults have occurred. What are the minimum and-2-maximum number of times that the clock hand could possibly have been advanced during the time inter-val? Give your answer in terms of P and F.4. Consider a demand paging system. Pages that are not in main memory are stored on the "pagingdevice", which may be a portion of a hard disk, an electronic disk, or something else. The size of the pag-ing device is its capacity.Measured utilizations (in terms of time, not space) are:center; l r.CPU utilization 20% Paging device 99.7% Other I/O devices 5%Which of the following, if any, will probably improve the CPU utilization? Whyorwhy not?(a) Get afaster CPU.(b) Get abigger paging device.(c) Increase the degree of multiprogramming.(d) Decrease the degree of multiprogramming.(e) Get faster other I/O devices.5. This question concerns translation lookaside buffers (TLBs).(a) In almost all computers with translation lookaside buffers, the TLB must be flushed (all the entriesmust be invalidated) during each context switch. Why?(b) Are large TLBs better than small ones from a performance standpoint?(c) A newcomputer has 32-bit virtual addresses, but uses 30-bit values as the input to the TLB. Thehigh-order 8 bits are a process identifier that is unique for each process, and the low-order 22 bitsare the virtual page being referenced (the high-order 22 bits of the virtual address; pages are 1024bytes long). What is the purpose of inputting the process identifier to the TLB?(d) Does this use of process IDs simplify or complicate the translation lookaside buffer?6. In this problem, all numbers are givenindecimal. Suppose three object files, A, B, and C, are to belinked together.Each of the object files contains twosegments, code and data, and the output of the linkerwill also contain twosegments. A contains 1400 bytes of code and 600 bytes of data. Bcontains 420bytes of code and 20 bytes of data. Ccontains 2600 bytes of code and 112 bytes of data. The file Adefines one external symbol, X, which is at location 760 in A. One external symbol is defined in B: itsname is Y and its location is 430. Cdefines 2 external symbols: Zisat2216 and W is at 2704. Supposethe linker processes the files in the order A, B, C, so that A’s segments end up before B’swhich end upbefore C’s.(a) Suppose that file A has an address at location 134 that is supposed eventually to refer to symbol X.What will be the contents of location 134 in A? What will its contents be after linking, and wherewill the contents be in the output file?(b) Suppose that file A has an address at location 136 that is supposed eventually to refer to symbol Y.What will be the contents of location 136 in A? What will its contents be after linking, and wherewill the contents be in the output file?(c) Suppose that file B has an address at location 430 that is supposed eventually to refer to symbol Z.What will be the contents of location 430 in B? What will its contents be after linking, and wherewill the contents be in the output
View Full Document
Unlocking...