As mentioned in my recent post on taking a multi pass approach for midterm preparation, I’m taking a stab at answering the midterm questions myself and below are my unfiltered attempts followed by the correct answer that I pulled from the answer key.
OS Structures
Question 1a
Protection domains allow providing independence, integrity, and isolation for the memory space occupied by a specific subsystem of the operating system, e.g., a CPU scheduler. As opposed to procedure calls in a program, going from one protection domain to another results in overhead. Succinctly define (one bullet for each) the implicit cost and explicit cost of going from one protection domain to another.
My first guess
- Implicit Cost
- Cache pollution
- Flushing of the TLB (unless we are using virtually indexed physically tagged)
- Explicit Cost
- Context Switch
- Hardware address space change
Solution
- Explicit cost
- latency incurred in switching address spaces from one domain to another and copy of data structures with the cross-domain call
- Implicit Cost
- latency incurred due to change of locality, including TLB and cache misses
Reflection
I sort of got the answer right but I could be more specific with the implicit costs. Instead of cache pollution, let’s just say: latency due to change of locality due to TLB and cache misses. Same specificity required for explicit costs as well: instead of saying context switch and hardware address space change, let’s go with latency incurred in switching address spaces due to copying of data structures required for a cross-domain call.
Question 1b
A and B are protection domains. Consider two implementation alternatives: (1) A and B are given distinct architecture-supported hardware address spaces. (2) A and B are packed into the same hardware address space but each is given a portion of the available virtual address space enforced through architecture-supported segment registers.
(i) Alternative 1 gives more memory isolation than alternative 2 for the two protection domains.
(ii) Alternative 2 is expected to perform better than alternative 1 for cross-domain calls
My First Guess
I would say i (i.e. more memory isolation) is false (although my intuition initially said that it is true) because the hardware itself check the bounds (lower and upper) of the virtual addresses that the process tries to access. However, on some level, I feel hardware separation equates to true separation.
I would also say that (ii) is false as well. During cross domain calls, doesn’t the OS need to copy user space buffers into the kernel? Why would using a virtual address have any positive impact? If anything, there’s additional overhead required of virtual address memory although the performance degredation is a good trade off for security.
Solution
False. In both implementations, the hardware enforces the memory isolation for the two domains. In option (1) the hardware associates a distinct page table with each domain; and in (2) the hardware ensures that each memory access is confined to the allocated virtual address space for the domain via the segment registers (lower and upper bounds).
True. Alternative 2 in this scenario would not require a page table swap/TLB flush as there is not virtual address space switch (only a very cheap segment switch) when calling between domains in the same address space, reducing the cost of the operation.
Reflection
Again, need to be more specific here and use specific keywords. In particular, I should mention page tables — distinct page tables — and how the hardware associates each process with a unique page table. Otherwise, I nailed it by calling out the lower and upper bounds stored in the hardware registers.
Apparently having a virtual address space does improve performance because no page table/TLB flush is required (I don’t agree with this since the answer assumes a virtually indexed physically tagged cache. Otherwise how would you ensure virtual address spaces do not overlap).
Question 1c
Consider a user program running on a vanilla operating system such as Unix. It makes a call “open” to the file system (which is part of the operating system). Open can be viewed as a cross-domain call between the user-space and the kernel. We are not interested in the details of what “open” does for the user program. Please succinctly specify the steps that transfer control from the user-space to the kernel’s implementation of open.
My Guess
- Open makes a system call
- System makes a trap into the OS
- OS verifies process (and user) can perform system call
- OS verifies user permissions to location on file system
- OS sends instruction to disk (via memory mapped IO), sending the block number
- Once device fetches block data is returned to CPU via bus (or in DMA data copied to memory)
- Devices sends interrupt to OS, signaling that data is now available
- User can now access data stored via virtual address
Solution
- The call results in a trap (vai the TRAP instruction in the processor) into the kernel
into the kernel. (-1 if trap not mentioned) - The processor mode changes to “kernel” (i.e., privileged mode) as a result of the trap. (-1 if mode change not mentioned)
- Trap instruction (which is a program discontinuity) will automatically transfer control to the entry point of the Trap handler (code for open call in the kernel) via the interrupt vector table. (+2 for any reasonable description that captures this sense)
Reflection
I got points 1 and 2 right but my answer appears to be a little too comprehensive. Basically there’s a trap instruction and need to explictly call out processor changing from user to kernel mode and calling out transfer of control to the trap handler via interrupt vector table.
Question 1d
Consider a process P1 executing on top of SPIN operating system. P1 makes a system call. Servicing this system call results in 3 cross domain calls within SPIN. How many hardware address spaces are involved in this system call (including the user-process’s address space)? (Justify your answer)
My Guess
Only two hardware address spaces are involved, including the user-process’s address space because SPIN, in order to achieve performance, groups all the OS services into the same hardware address space, enforcing security using Modula-3 programming language
Solution
- There will be 2 hardware address space switches.
- The first switch is from the user space to the protection domain of
SPIN kernel which requires hardware address switch. - The second switch is from this protection domain to the user domain to
return the results back to the user process P1 - 4. The 3 cross domain calls will happen in same hardware address space
because of the way SPIN is constructed.