Final Exam Part 1 Flashcards
True/False: Only one thread can be in monitor at a time
True
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?
procudere procA{
b.signal
a.wait
}
procedure procB{
b.wait
a.signal
}
T1
while(1){
AB.procA
print(a)
}
T2
while(1){
AB.procB
print(b)
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.
Monitor resourceAllocate
{
int sum;
condition c;
void AccessFile(int num)
{
while(sum+num>=n)
{
c.wait();
}
sum+=num; }
void FinishAccessing(int num)
{
sum= sum-n;
c.signal();
}
void init()
{
sum=0;
}
}
Define paging
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?
- At compile time. Compiler determines where to place program in MM.
Disadvantages: program has to be recompiled every time it is run. - At load time.
Disadvantage: Program has to remain in the same location, and the entirety of the program needs to be loaded in MM. - At runtime. This one is used regularly.
What are the four different memory management techniques?
- Contiguous
- Paging
- Segmentation
- 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?
- CPU generates virtual address.
- 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?
275
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?
- 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:
Hole: 25K
Process 23K
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?
- Program is divided into pages.
- Every page is of the same size.
- VM is divided into pages.
- PM is divided into frames.
- 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?
- HW is fast.
- 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?
- Page replacement policy bits.
- Protection bits
- Dirty bit: whether page has been WRITTEN to.
- Residency bit: whether page is loaded in MM.
- Frame number
