Q: Differentiate between internal and external fragmentation. Q: Suggest a scheme to control thrashing using the instantaneous page fault rate observed by the operating system. Q: (Answer True/False with justification) In an architecture that supports virtual memory, it always takes at least 2 trips to the physical memory for every memory access generated by the processor. Q: A memory hierarchy has the following resources: L1 cache 2 ns access time 98% hit rate L2 cache 10 ns access time ?? Memory 60 ns access time Assume that for each of L1 and L2 caches, a lookup is necessary to determine whether a reference is a hit or miss. What should be the hit rate of L2 cache to ensure that the effective memory access time (P&H book also calls this the Average memory access time) is no more than 3 ns. Q: Consider a pre-emptive priority processor scheduler. There are three processes P1, P2, and P3 in the job mix that have the following characteristics: Process Arrival Priority Activity Time ----------- ----------- --------------- --------------------------- P1 0 sec 1 8 sec CPU burst followed by 4 sec I/O burst followed by 6 sec CPU burst and quit P2 2 sec 3 64 sec CPU burst and quit P3 4 sec 2 2 sec CPU burst followed by 2 sec I/O burst followed by 2 sec CPU burst followed by 2 sec I/O burst followed by 2 sec CPU burst followed by 2 sec I/O burst followed by 2 sec CPU burst and quit What is the turnaround time for each of P1, P2, and P3? What is the average waiting time for this job mix? Q: Consider an architecture wherein for each entry in the TLB there is 1 reference bit (that is set by hardware when the associated TLB entry is referenced by the CPU for address translation), and 1 dirty bit (that is set by hardware when the associated TLB entry is referenced by the CPU for a store access). These bits are in addition to the other fields of the TLB that we have discussed in the class. The architecture provides three special instructions: one for sampling the reference bit for a particular TLB entry (Sample_TLB(entry_num)) one for clearing the reference bit for a particular TLB entry (Clear_refbit_TLB(entry_num)) one for clearing the reference bits in all the TLB entries (Clear_all_refbits_TLB()). Come up with a scheme to implement page replacement using this additional help from the TLB. For full credit, you should show data structures and pseudo code that the algorithm maintains to implement page replacement. Use back of the page if necessary. Q: What are the important deficiencies of FCFS CPU scheduling? Q: In a processor with a five stage pipeline as discussed in the class and shown in the picture below (with buffers between the stages), explain the problem posed by a branch instruction. Present a solution. +--------+ +--------+ +--------+ +--------+ |Pipeline| |Pipeline| |Pipeline| |Pipeline| IF->| |->ID->| |->EX->| |->MEM->| |->WB |Register| |Register| |Register| |Register| +--------+ +--------+ +--------+ +--------+ ^ ^ | | Reg ALU File here Here Q: A process has a memory reference pattern as follows: 0 0 1 2 3 4 0 0 1 2 3 4 The above pattern (which are the virtual page numbers of the process) repeats throughout the execution of the process. ======= Assume that there are 3 physical frames. Show the paging activity for a True LRU page replacement policy. For full credit show an LRU stack and the page that gets replaced (if any) for the first 12 accesses. Clearly indicate which accesses are hits and which are page faults. Q: A process has a memory reference pattern as follows: 0 0 1 2 3 4 0 0 1 2 3 4 The above pattern (which are the virtual page numbers of the process) repeats throughout the execution of the process. ======= What would be the paging activity for an optimal page replacement policy for the first 12 accesses? For such a policy indicate which accesses are hits and which are page faults. Q: For the scheduling algorithms we discussed fill in the following table: Algorithm Starvation High variance Provably optimal MUST be Possible? in turnaround (min. average preemptive time? waiting time) ----------- ----------- --------------- ------------------- ---------- First Come First Served Shortest Job First Priority Round Robin Multilevel Queue Multilevel Feedback Queue Q: A pipelined processor has a forwarding unit installed in the EX stage (the one with the ALU). Assuming that the following instruction is passing through the pipeline write an instruction that would use the forwarding unit. add R1, R2, R3 # Add contents of R2 and R3 store result in R1 __________________ # Instruction that will use forwarding unit to # avoid # stalling the pipeline. Q: You are designing a cache for a 32-bit processor. Memory is organized into words but byte addressing is used. You have been told to make the cache 2-way set associative with 64 words (256 bytes) per block. You are allowed to use a total of 64K words (256K bytes) for the data (excluding tags, status bits, etc.) Sketch the layout of the cache (note: no control logic should be shown): [We are interested in the number and size of things.] Show how a memory reference will be subdivided: Byte offset, block offset, index(set), tag. 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 +---------------------------------------------------------------+ | | | | +---------------------------------------------------------------+ Q: A processor asks for the contents of virtual memory address 0x30020. The paging scheme in use breaks this into a VPN of 0x30 and an offset of 0x020. PTB (a CPU register that holds the address of the page table) has a value of 0x100 indicating that this processes page table starts at location 0x100. The machine uses word addressing and the page table entries are each one word long. +---+-----+ |PTB|0x100| +---+-----+ +---+------+ |VPN|Offset| | 30|020 | +---+------+ The contents of selected memory locations are: Physical Contents Address 0x00000 0x00000 0x00100 0x00010 0x00110 0x00000 0x00120 0x00045 0x00130 0x00022 0x10000 0x03333 0x10020 0x04444 0x22000 0x01111 0x22020 0x02222 0x45000 0x05555 0x45020 0x06666 What is the physical address calculated? What is the contents of this address returned to the processor? How many memory references would be required (worst case)? Q: From the following statements regarding cache memory, select the ones that are True. It can usually be manipulated just like registers from the instruction-set architecture of a processor It cannot usually be directly manipulated from the instruction- set architecture of a processor It is usually implemented using the same technology as the main memory It is usually much larger than a register file but much smaller than main memory Q: What is meant by cache coherency? ___ Cache is operating faster than main memory ___ Cache is operating on a higher plain of consciousness ___ Cache and memory agree or they don't and we know and can do something about it ___ Cache is on a single chip ___ Cache is on same chip as processor ___ Cache is physically between processor and main memory ___ cache is physically located on prime meridian Q: In a pipelined processor where each instruction could be broken up into 5 stages and where each stage takes 1 ns what is the best we could hope to do in terms of average time to execute 1,000,000,000 instructions? Q: What are the three main types of hazards we encounter in a pipelined processor. Q: Define Locality and discuss the various types. Q: Define Cache Hit Ratio Q: These next two questions assume that you are in your page fault handler. On a page fault when is the only time you should save a page from disk? Q: When should you load a page from disk? Q: Is a megabyte exactly 1 million bytes? ___ Yes ___ No ___ I'm not sure? ___ I'm changing my major Q: Assume a processor with CPI = 1.0 (if all references hit in primary cache). Clock is 1000 MHz. Main memory access time is 100 ns. Miss rate at primary cache is 6%. What is clock cycle time? What is miss penalty in clock cycles? What is effective CPI? Now we add in a second level cache with a 10 ns access time. This cache has a miss rate to main memory of 3% What is the miss penalty for the second level cache? What is the total effective CPI? Q: Name a scheduling algorithm where starvation is impossible Q: Which scheduling algorithm was noted as having a high variance in turnaround time Q: Which scheduling algorithm is provable optimal (minimum average waiting time). Q: Which scheduling algorithm must be preemptive?