CIS 415 Operating Systems - Spring 2003

Navigate

Discussion: Week 10 session 1

Memory Management

Virtual memory uses relocation (the fact that each page can be placed anywhere in memory). But suppose the system doesn't support relocation. A price is paid in the memory efficiency department because of the "Birthday" phenomenon. Trace the following sequence of page references through both systems (with and without relocation) and show where the page faults occur.

Memory capacity: 16 frames
Process P1: 3 pages, initially loaded in frames 0..2
Process P2: 10 pages, initially loaded in frames 3..12
Process P3: 5 pages, initially loaded in frames 2..6 but completely swapped out for now.

Reference string (pages): P1.0 P2.0 P3.1 P2.0 P2.1 P3.0 P1.2 P3.1 P3.2

With relocation:

0  P1.0
1  P1.1
2  P1.2
3  P2.0
4  P2.1
5  P2.2
6  P2.3
7  P2.4
8  P2.5
9  P2.6
10 P2.7
11 P2.8
12 P2.9
13  -	
14  -	
15  -

Without relocation:

0  P1.0
1  P1.1
2  P1.2
3  P2.0
4  P2.1
5  P2.2
6  P2.3
7  P2.4
8  P2.5
9  P2.6
10 P2.7
11 P2.8
12 P2.9
13 -
14 -
15 -

Processes and Threads

Suppose you are writing a set of programs to be run concurrently and operate on some shared global data structure. The programs are identical, having 500K of code and operating on 1MB of global data. Each instance of the program also allocates 1MB of private data from the heap during its execution. There will be 10 instances of this program running at once on a uniprocessor system.

How much total memory is necessary if each instance is a separate process?

How much is needed if each instance is a thread, and all instances are part of a single process? What other benefits does this approach give?

If each instance periodically calls for I/O and the system's threads implementation is User-Level Threads, which of the two implementations would you choose?

Scheduling

Trace the following processes through the given scheduling policies, showing their time on the processor in a Gannt chart:

Process	Arrival Time	Service Time
A	1	5
B	3	7
C	7	1
D	8	3
E	10	6

FCFS

SRT

SPN

HRRN

RR
q=1

RR
q=2

FB
q=1

FB
q=2ⁱ

Scheduling

What does it mean for a process to be:

Ready?
Blocked?
Suspended?

Are they mutually exclusive, or can a process have more than one of these states at a time?

DMA, Caching

Consider a system with a 32-bit 100MHz memory bus. What is the effective memory bandwidth for random RAM-to-processor transfers, using 1 cycle to send the request and 1 cycle to read the data? (i.e. how much data can be transferred per second?)

Now suppose that the DMA controller uses 2 out of every 6 bus cycles for its purposes. When in use, what is the effective memory bandwidth for random RAM-to-processor transfers?

Now suppose the processor would make 10 memory requests per bus cycle if it didn't have to wait for the memory transfer to complete. If the processor cache has a 99% hit rate, then how many bus cycles will be left idle while DMA is in use?

Semaphores

Suppose Reza and his two GTF's hold their office hours at the same time, and whoever is not busy serves the next student. There are three general questions that students need help with, and each instructor can help up to three people with the same question, but the question is not known to the instructor until the first student in the group is selected. Assume an endless supply of students with each question.

Implement this system using semaphores in pseudocode.

Semaphores (you may add to these or ignore these at your peril/convenience):

BinarySemaphore instructorAvailable; //initialized to 0
CountingSemaphore ask[3]; //initialized to 3, 1 per question
CountingSemaphore ready[3]; //initialized to 0, 1 per instructor
CountingSemaphore release[3]; //initialized to 0, 1 per instructor
CountingSemaphore leave[3]; //initialized to 0, 1 per instructor
BinarySemaphore studentMutex[3]; //initialized to 1, 1 per question
BinarySemaphore instructorMutex; //initialized to 1

Student() {

}

Instructor() {

}