Section 1: Fill in the Diagram (8 points; 2 each part)
1. On the diagram below, a new process is shown to go from the “new” state to the “ready” state via an
“admitted” transition. Similarly, a process goes from a “running” state to a “terminated” state via an
“exit” transition. Fill in the 4 blanks with descriptions or names of the transition (event) that causes a
process to move from one state to another.
D i a g r a m o f P r o c e s s S t a t e
e x i t
w a it in g
n e w
r e a d y
t e r m in a t e d
r u n n in g
1 )_ _ I n te r r u p t ____
4 ) _ I / O o r e v e n t
w a i t _
3 ) _ I / O o r e v e n t
c o m p l e ti o n _
a d m i t t e d
2 )_ D i s p a tc h _ (s c h e d
u l e r)_ _ _
Page 2 of 10
Section 2: Process Scheduling (16 points; 4 each part)
2. Given the following table, how will these processes be scheduled using each of the below algorithms?
Create a Gantt chart showing when each process will be scheduled, and calculate the average waiting time
for the processes. For simplicity, ignore any potential context switch time.
Process Arrival Time Processing Burst Time Priority
P1 0 7 2
P2 4 4 1
P3 6 3 2
P4 8 8 1
P5 18 2 3
a. First-Come, First-Served (FCFS)
0-P1-7-P2-11-P3-14-P4-22-P5-24
Avg. Wait = 0+3+5+6+4 / 5 = 18/5 = 3 3/5 = 3.6
b. Shortest-Job-First (SJF – non-preemptive)
0-P1-7-P3-10-P2-14-P4-22-P5-24
Avg. Wait = 0+6+1+6i+4 / 5 = 17/5 = 3 2/5 = 3.4
c. Shortest-Remaining-Time-First (SRTF - preemptive)
0-P1-7-P3-10-P2-14-P4-18-P5-20-P4-24
Avg. Wait = 0+6+1+(6+2)+0 / 5 = 15/5 = 3
d. Round Robin (RR) (with time quantum = 4)
0-P1-4-P2-8-P1-11-P3-14-P4-18-P5-20-P4-24
Avg. Wait = 4+0+5+(6+2)+0 / 5 = 17/5 = 3 2/5 = 3.4
CS4520 Operating Systems I Fall 2017 – Exam 1 (100 pts)
Page 3 of 10
Section 3: Short Answer (20 points)
3. (4 points; 2 each part) Dynamic Link Libraries (DLL’s) and Shared Libraries are similar constructs for two
popular platforms. Briefly answer the following questions about these technologies.
a. What is the advantage of using a DLL or Shared Library as opposed to a classical Static Link Library?
One need not re -link in order to update code that uses the shared library (i.e., many
programs can be updated via updating the shared code)
b. What (if any) disadvantages are there to using a DLL or Shared Library?
Versioning can sometimes be a problem (DLL Hell).
4. (8 points; 2 each part) Use one sentence to briefly describe each of the following terms:
a. Demand paging
This is swapping pages into memory only as they are needed (upon demand).
b. Internal fragmentation
This is memory within a partition which is not used (wasted).
c. External fragmentation
This is non-contiguous memory “holes” which prevent large processes from being loaded even when
total space available is sufficient.
d. Virtual memory
This is a technique allowing the execution of processes that may not be completely in physical memory.
5. (4 points; 2 each part) Please answer in powers of 2 for full points!
a. How many page table entries will we have with 16 GB virtual memory and 512 KB physical memory
frame. size?
16 GB = 2^34, 512 KB = 2^19, so 2^34/2^19 = 2^15 entries (approx. 32 thousand entries)
b. What is the corresponding page size?
2^19 = 512 KB (must be the same as the frame. size)
6. (2 points) The ability for a device controller to transfer blocks of data directly to main memory without
CPU intervention is called what?
Directory Memory Access (DMA) or Bus Mastering
7. (2 points) What is it called when the CPU switches to another process?
Context Switch
CS4520 Operating Systems I Fall 2017 – Exam 1 (100 pts)
Page 4 of 10
Section 4: Page Fault Time (16 points; 4 each part – 2 for data and 2 for time)
8. Consider a virtual memory system that includes both a translation look-aside buffer and cache memory.
Assume the system uses 5 bit logical addresses, with the high-order (left-most) 3 bits being a page number
and the low-order (right-most) 2 bits being an offset. Assume that the system uses 4 bit physical
addresses, with the high-order (left-most) 2 bits being a page frame. number and the low-order (right-
most) 2 bits being an offset. Further, assume that a page fault takes 100 time units, a regular memory
access takes 20 time units, a cache access takes 5 time units, and a TLB access takes 1 time unit. If a page
fault takes place, you will not know the data contained in the logical memory address, so answer
“unknown” for that part. Also, for a page fault, assume that the contents of the requested logical address
will be put into cache as part of the time to execute the page fault (and then the instruction referencing
the memory will be restarted).
Current contents of cache:
Logical Address Contents
10000 A
00001 F
10001 B
Current contents of Page Table:
Page Page Frame.
000 01
001 10
010 --
011 --
100 00
101 --
110 --
111 --
Available Frames:
Page Frame.
11
Current contents of TLB:
Page Page Frame.
000 01
001 10
Current contents of physical memory:
Physical Address Contents
0000 A
0001 B
0010 C
0011 D
0100 E
0101 F
0110 G
0111 H
1000 I
1001 J
1010 K
1011 L
a. What data is contained in logical memory address 10010 and how long will it take to retrieve it?
C, 5+1+20+20 = 46
b. What data is contained in logical memory address 00100 and how long will it take to retrieve it?
I, 5+1+20=26
c. What data is contained in logical memory address 00001 and how long will it take to retrieve it?
F, 5
d. What data is contained in logical memory address 01000 and how long will it take to retrieve it?
Unknown, 5+1+20+100+5 = 131
CS4520 Operating Systems I FS2017 – Exam 1 (100 pts)
Page 5 of 10
Section 5: Page Replacement (15 points; 5 each part)
9. Consider a memory system with 4 page frames. Show how each page replacement algorithm would
work for the page access string 1,2,3,4,5,1,2,5,3,4,5,4 by completing the following tables:
a. First-In-First-Out (FIFO)
Frame/Ref 1 2 3 4 5 1 2 5 3 4 5 4
1 1 1 1 1 5 5 5 5 5 4 4 4
2 X 2 2 2 2 1 1 1 1 1 5 5
3 X X 3 3 3 3 2 2 2 2 2 2
4 X X X 4 4 4 4 4 3 3 3 3
b. Least Recently Used (LRU)
Frame/Ref 1 2 3 4 5 1 2 5 3 4 5 4
1 1 1 1 1 5 5 5 5 5 5 5 5
2 X 2 2 2 2 1 1 1 1 4 4 4
3 X X 3 3 3 3 2 2 2 2 2 2
4 X X X 4 4 4 4 4 3 3 3 3
c. The Optimal Algorithm (assume future accesses in addition to the above string of 1,2,1,3)
Frame/Ref 1 2 3 4 5 1 2 5 3 4 5 4
1 1 1 1 1 1 1 1 1 1 1 1 1
2 X 2 2 2 2 2 2 2 2 2 2 2
3 X X 3 3 3 3 3 3 3 4 4 4
4 X X X 4 5 5 5 5 5 5 5 5
CS4520 Operating Systems I FS2017 – Exam 1 (100 pts)
Page 6 of 10
Section 6: True/False (18 points; 2 each part)
Choose True (T) or False (F) for each of the following by circling the appropriate letter.
10. T or F – The operating system is both a resource allocator and a control program.
11. T or F – A single-core, single-processor system can execute up to 2 instructions per clock cycle (1 OS
instruction and 1 user program instruction).
12. T or F – Modern operating systems no longer support interrupts.
13. T or F – The following is an example of a system call: fopen.
14. T or F – Modern NVMe drives are generally faster than registers in most computers.
15. T or F – Cache memory is generally faster than registers.
16. T or F – Registers are generally faster than main memory.
17. T or F – A process is a passive entity.
18. T or F – The portion of a process in memory that contains the executable code is called the text
segment.
Section 7: Multiple Choice (8 points; 2 each part)
Circle the letter of the best response.
19. What will the following C code do?
#include
#include
int main (int argc, char ** argv)
{
pid_t pid = fork();
printf("Hello.\n");
}
a. Print “Hello.\n” to the screen once.
b. Print “Hello.\n” to the screen twice.
c. Print “Hello.\n” to the screen until system resources are exhausted (fork bomb).
d. Nothing. This code will not compile.
20. Threads in a single process share which of the following resources:
a. Code only
b. Code, Data, and Files
c. Registers and Stack
d. Code, Data, and Stack
21. Thrashing is best described as:
a. An operating systems technique inspired by those who cannot swim.
b. A condition in the operating system in which physical memory exceeds logical memory.
c. A condition in which the total working sets of processes in the system exceeds physical
memory.
d. A condition in which the total working sets of processes in the system exceeds logical memory.
CS4520 Operating Systems I FS2017 – Exam 1 (100 pts)
Page 8 of 10
22. In reference to the following C code snippet we studied in class, select the best statement:
// Global variables
#define BIG 40960
int g_Table[BIG][BIG];
int i,j;
// Code from the main() function
for (i=0;i {
for (j=0;j {
if (IJ)
{
g_Table[i][j] = INT_MAX;
}
else
{
g_Table[j][i] = INT_MAX;
}
}
}
a. Referencing the table in i,j order is always the most efficient regardless of compiler or OS.
b. Referencing the table in j,i order is always the most efficient regardless of compiler or OS.
c. It doesn’t matter whether you reference the table in i,j order or j,i order regardless of compiler
or OS.
d. One of these two is dramatically better depending on the way the compiler lays out the
g_Table data structure.