Flashcards in Final Exam Part 1 Deck (36):
True/False: Only one thread can be in monitor at a time
Difference between p() and wait()?
P only blocks if c < 0, wait() ALWAYS blocks
Difference between v() and signal()?
The v() signal is NEVER lost, where signal() may be lost if the queue is empty.
What is the output of the following code if T1 goes first? if T2 goes first?
T1 first: deadlock
T2 first: [ab]*
A file is to be shared among different processes, each of which has a unique number. The file can be accessed simultaneously by several processes, subject to the following constraint: The sum of all unique numbers associated with all the processes currently accessing the file must be less than n. Write a monitor to coordinate access to the file.
void AccessFile(int num)
void FinishAccessing(int num)
A technique to implement virtual memory
The key issue in virtual memory is WHEN to bind variables to a location. What are three different ways of doing this? Which one is used today?
1. At compile time. Compiler determines where to place program in MM.
Disadvantages: program has to be recompiled every time it is run.
2. At load time.
Disadvantage: Program has to remain in the same location, and the entirety of the program needs to be loaded in MM.
3. At runtime. This one is used regularly.
What are the four different memory management techniques?
4. Segmentation + Paging
Address binding is done by the _____.
MMU (Memory management unit)
How is a virtual address converted to a physical address in the contiguous memory management scheme?
1. CPU generates virtual address.
2. There is a MBR and an MLR in the MMU. The physical address created is the virtual address + MBR so long as it is <= the MLR.
What would the physical address be if a CPU generated a virtual address of 5, and the MBR and MLR had values of 270 and 595 respectively?
Consider MM with holes as shown below:
Hole 1- 68K
Hole 2- 96K
Hole 3- 78K
Hole 4- 25K
Hole 5- 80K
If two processes wanted to get into main memory with sizes of 75K and 25K respectively, which hole would each process go into? Answer the question with all four contiguous memory policies.
First Fit: Hole 2, Hole 1
Next Fit: Hole 2, Hole 3
Best Fit: Hole 3, Hole 4
Worst Fit: Hole 2, Hole 5
What are the two major disadvantages of the contiguous memory management scheme?
1. Complete program must be loaded into MM.
2. Memory fragmentation.
Define the two different types of fragmentation.
Internal: Hole within program
External Fragmentation: Holes between programs
Out of the four contiguous memory policies, which leads to the most fragmentation? Which type of fragmentation is it? Why?
Best fit. Consider the following scenario:
Process will give entire 25K to process since the 2K will not be of any use elsewhere. This means that internal fragmentation is occurring because the process has 2K worth of space it isn't using.
True/False: In general, 1/2 of MM lost due to fragmentation.
False: approximately 1/3
What is the solution to fragmentation?
Compaction: move programs to one end so there is a large hole at the other end.
What five things must be true in the paging memory management scheme?
1. Program is divided into pages.
2. Every page is of the same size.
3. VM is divided into pages.
4. PM is divided into frames.
5. Page size = Frame size
True/False: Size of VM must be equal to size of PM in memory management scheme.
False: Does not matter as long as page and frame size are equal.
Why does page size need to equal frame size?
So the number of words are the same in pages and frames.
The page table is stored in the TLB normally rather than MM. Why is this the case?
1. HW is fast.
2. MM has to be accessed twice for every LA -> PA if page table is stored in MM.
a) Access Page table to get Frame #
b) Access Physical address.
Typically, how much internal fragmentation occurs in the paging memory management scheme? How much external fragmentation?
Internal: approximately 1/2 page per program.
External: None, page size = frame size.
Suppose the following:
Page size: 4 words
Virtual Memory: 64 words
Physical Memory: 1024 words
What is the frame size? number of frames? number of pages?
Give the page # and word # for the following LAs: 9, 43, 40.
Frame size: 4 words
number of pages: 16
number of frames: 256
VA 9: Page 2 word 1
VA 43: Page 10 word 3
VA 40 Page 10 word 0
What are the five parts of a page table entry?
1. Page replacement policy bits.
2. Protection bits
3. Dirty bit: whether page has been WRITTEN to.
4. Residency bit: whether page is loaded in MM.
5. Frame number
True/False: The OS will throw out pages with a dirty bit set.
False, the dirty bit of 1 means the page has been written to and the OS will assume that the page is in use.
Given 16 frames in MM, and that the residency bit is immediately to the left of the frame#, which address would result in a page fault?
439, 611, 606, 693.
Depict a step by step process of how contents are gotten from a logical address in the paging memory scheme.
1. Convert logical address to binary.
2. Find page and word number
3. Index into page + PTBR and get contents.
4. Convert contents from number 3 into binary.
5. Check if the page is loaded into MM.
6. Get frame #.
7. Append word number from step 2 to frame # in step 6.
8. Get contents with physical address obtained in step 7.
What is the major disadvantage of the paging memory management scheme?
Page faults are really high.
Define the segmentation memory management scheme.
Program is divided into segments, not pages. Each segment is a logical entity, and the entire segment into MM. A physical address is computed as the segment base + word # as long as it is <= the segment bound.
What are the advantages and disadvantages of the segmentation memory management scheme?
Advantage: Lower page faults.
Disadvantage: segments different sizes, external fragmentation occurs.
Define the segmentation + paging scheme.
Program is divided into segments AND pages. All pages of a segment must be loaded into MM. There is one segment table per process, 1 page table per segment all stored on the TLB.
What is the LA made up of in the segmentation + paging scheme? the PA?
LA: Seg# + page# + word#
PA: Frame# + word#
How much fragmentation occurs in the segmentation + paging scheme? What types?
External Fragmentation: 0
Internal Fragmentation: 1/2 page per segment.
What happens when the residency bit is 0? (more detailed than just page fault occurs...)
1. Page fault occurs.
2. Program is blocked.
3. OS finds a frame for the page and loads from disk using a page replacement algorithm.
4. Program goes from blocked to ready.
What is the formula for page access time?
memory access time + (fault rate) * disk access time