(1)
Fall 2021 CS 450 Midterm
Page 7 of 9
Student Name: ___________________________________
This is an open book exam. You have 75 minutes to complete all the questions. You will be graded on whether your answer is concise and clear.
Fall 2021 CS450 Mid Term
Student Name _________________________________________
Part 1 (50 pts)
Q1 (3 pts)
Q2 (3 pts)
Q3 (3 pts)
Q4 (3 pts)
Q5 (3 pts)
Q6 (3 pts)
Q7 (3 pts)
Q8 (3 pts)
Q9 (3 pts)
Q10 (3 pts)
Q11 (10 pts)
Q12 (10 pts)
Total Part 1 Score
Part 2 (50 pts)
Q13 (15 pts)
Q14 (12 pts)
Q15 (12 pts)
Q16(12 pts)
Total Part 2 Score
Part 1: Questions (1) to (10) are multiple choices; fill in the blanks and short questions. Each is worth three points. In multiple choice questions, you choose one or more statements or terms that are true.
xv6 is an interrupt driven operating system.
Give an interrupt that will cause a process to change from Ready to Running.
_____________________________________________________________
Why is there no transition from Ready to Blocked?
_____________________________________________________________
SHAPE \* MERGEFORMAT
The address space of a process contains a stack segment, a heap segment, a .bss segment, a .data segment and a .txt segment. Where are the following stored?
Dynamic data allocated by malloc() ___________________
An initialized external static variable ___________________
A static integer variable declared within a function but not initialized_______
Give two methods that the operating system uses to encapsulate the address space of a user process.
____________________________________________________________
____________________________________________________________
Say whether the following statements are true or false in general.
Programs in kernel mode run faster. (T / F)
The SJF scheduling policy minimizes average response time. (T / F)
MLFQ scheduling with many queues approximates SJF. (T / F)
Give one statement each on how software interrupts are different from and similar to hardware interrupts.
Difference:
_________________________________________________________________
Similarity:
_________________________________________________________________
For a 32-bit microprocessor with page size of 4KB,
How many entries are needed in the linear page table? _________
If each entry requires 4 bytes, how many pages are needed to store the table? ___________
The following picture given by the textbook shows the format of a virtual address with segmentation.
How big is the largest segment size with this address format?
What is the maximum number of segments a program can have?
Underline the correct term(s) in the following statements.
A segment is contiguous in the (virtual, physical) address space but not in the (virtual, physical) address space.
A (segment, page) is a unit of protection.
The address space of a process can be (greater than, equal to, less than) the amount of physical memory.
An MMU improves address translation performance. Which one of the following helps in its performance (true or false).
It operates in a pipeline with the ALU (arithmetic logic unit). (T/F)
It stores used data. (T/F)
It searches the used data in parallel. (T/F)
Give one advantage and one disadvantage of an inverted page table.
____________________________________________________________
____________________________________________________________
(10 points) The following are the five original rules of the MLFQ policy. What concerns are addressed by R1, R3, R4a, R4b and R5 respectively?
R1: If priority(A) > priority(B), A runs
R2: If priority (A) = priority(B), A, B runs in RR
R3: new job at highest priority
R4a: If a job uses up all time slice T, its priority is reduced
R4b: If a job gives up the CPU before its time slice, it stays at the same priority
R5: After some time S, move all the jobs to the topmost queue
R1: ___________________________________________________________
R3: ____________________________________________________________
R4a: ___________________________________________________________
R4b: ___________________________________________________________
R5: ____________________________________________________________
(10 points) The optimal TLB replacement algorithm would replace the entry that will be referenced the furthest away.
What does “optimal” in the above statement mean?
_____________________________________________________________
Why is it optimal?
_____________________________________________________________
Why it cannot be implemented?
____________________________________________________________
Why the LRU algorithm is a good approximation?
____________________________________________________________
Part 2: Longer questions
(15 points) Fill in the following table to show what will happen while process A is executing, a timer interrupt occurs indicating process A has used up its time slice, and the operating system chooses process B to execute.
Kernel Mode
Hardware
User Mode
Process A executes
(12 points) The following code segment describes the control flow in converting a virtual address to a physical address via a TLB. (a) Explain line 13 (What does (PDE.valid == False) mean?); (b) Explain line 19; (c) Modify the algorithm to handle the case when there is a miss and the cache is full.
(12 points) The following is a code fragment intended to handle the parallel execution operator “&” of a shell command line in programming assignment 1. Point out errors in the code and correct them. Note that the parallel execution should end before returning to shell, and error commands should not return silently.
void runcmd(struct cmd *cmd) {
struct execcmd *ecmd; struct parallelrcmd *pcmd;
switch(cmd->type){
case ‘ ‘:
ecmd = (struct execcmd*) cmd;
if(ecmd->argv[0] == 0) exit(0);
execvp(ecmd->argv[0],ecmd->argv); //execute the command
break;
…
case ‘&’:
pcmd = (struct parallelrcmd*) cmd;
if(fork() == 0)
runcmd(pcmd->left); //execute the command before “&”
wait(NULL);
runcmd(pcmd->right); //execute the command after “&”
break;
exit(0);
}
(12 points) Give four test cases (command strings) that you used in programming assignment 1, give their expected output and the reasons that you used them (best if illustrated with your equivalence partitioning). Discuss how do you know that the & operator is correctly implemented.
(Intentionally blank)