Homework 2

Due: May 9, 2022
Points: 100

When you do the homework, please put the answers to questions 1-4 on one page, and the answers to each of the others on separate pages. You can save this file and put your answers on it. This will make. using Gradescope to grade the assignment much easier than if you submitted everything without regard to pages.

Remember, you must justify all your answers.

Short-answer

1. (8 points) What are the four conditions that are necessary for a deadlock to occur?

2. (7 points) Consider a logical address space of 16 pages of 4096 words each, mapped onto a physical memory of 1024 frames. How many bits are there in the logical address? In the physical address?

3. (10 points) How does the Working Set replacement strategy relate job scheduling to memory management?

Long Answer Questions

1. (30 points) Consider a system with three model airplane building processes and one agent process. Each building process requires a tube of glue, a piece of newspaper, and a model kit to put a model airplane together. One of the processes has tubes of glue, another pieces of newspaper, and the third model kits. The agent has an infinite supply of all three. The agent places two of the ingredients for the model builders on the table. The process who has the remaining ingredient can then build one model airplane. It signals the agent upon completion. The agent then puts out another two of the three ingredients and the cycle repeats.

   Write a program to synchronize the agent and the model building processes using monitors. Assume that if a process signals on a condition variable that another process is waiting on, the signaler blocks until the other process either leaves the monitor or blocks.

2. (20 points) Assume that we have a paged memory system with a cache to hold the most active page table entries. It takes 20ns to search the cache. If the page table is normally held in memory, and memory access time is 1μs, what is the effective access time if the hit ratio is 85%? What hit ratio will be necessary to reduce the effective memory access time to 1.1μs?

3. (25 points) A virtual memory has a page size of 1024 words, 8 virtual pages, and 4 physical page frames. The page table is as follows:

   virtual page	page frame
   0	3
   1	1
   2	not in main memory
   3	not in main memory
   4	2
   5	not in main memory
   6	0
   7	not in main memory

   1. Which virtual addresses will cause page faults?
   2. What are the physical addresses for 0, 3728, 1023, 1024, 1025, 7800, and 4096?

Matt Bishop Office: 2209 Watershed Sciences Phone: +1 (530) 752-8060 Email: mabishop@ucdavis.edu

ECS 150, Operating Systems Version of April 28, 2022 at 9:47AM

You can also obtain a PDF version of this.