CS 354 (Park) Midterm March 4 (Mon.), 2019
Remarks: Keep the answers compact, yet precise and to-the-point. Long-winded answers that do not address the key points are of limited value. Binary answers that give little indication of understanding are no good either. Time is not meant to be plentiful. Make sure not to get bogged down on a single problem.
PROBLEM 1 (52 pts)
(a) What is the role of the upper half in a modern kernel? What are the two main di↵erences of XINU’s imple- mentation of its upper half in x86 compared to x86 versions of Linux and Windows? Which of the two impacts reliability/security and which e↵ects kernel responsiveness?
(b) What is the role of the lower half? What has been the main component of the lower half of XINU discussed in the course so far? What are the three chores performed by this component? Which two of the three chores can prompt invocation of XINU’s scheduler, and why?
(c) We discussed two hardware primitives and one software primitive for performing mutual exclusion. Why is interrupt disabling, in general, considered preferable to test-and-set (tset)? Why is using counting semaphores, in general, considered preferable to interrupt disabling? What is an example of a Linux system call where interrupt disabling would be especially detrimental for the system as a whole? Why are counting semaphore primitives (e.g., wait() and signal()) not a pure software solution for achieving mutual exclusion?
(d) In the XINU context-switch function, ctxsw(), EBP followed by EFLAGS which is followed by 8 general-purpose registers are pushed onto the stack of the process being context-switched out. When a process is context-switched in, instead of the reverse sequence—popal followed by popfl followed by restoring EBP—the order of EFLAGS and EBP is reversed. What is the reason? In our x86 XINU, is this necessary? Explain your reasoning. In the CDECL caller/callee convention as well as in x86’s software interrupt int, the return address EIP is pushed onto a stack so that ret or iret can find their way back. Why is EIP not saved by ctxsw()?
PROBLEM 2 (48 pts)
(a) Suppose you are tasked to select a scheduler for an operating system that is to be a used in a computing system where all processes are CPU-bound. What is the simplest and most e cient solution that accomplishes fair sharing of CPU cycles? Explain its scheduling overhead. In operating environments with a mixture of CPU- and I/O-bound processes, why is the above solution considered insu cient? What rules are imposed by UNIX Solaris to a↵ect improved scheduling? In what way is scheduling improved? As a consequence of the rules, could it happen that some CPU-bound processes end up not receiving CPU cycles for a prolonged period (e.g., 1 second)? What might be such a scenario? What is the basic idea behind Solaris’s “safety net” that aims to prevent starvation?
(b) If the data structure being shared by two processes is a producer/consumer queue—in place of using mutual exclusion—a preferred way of protecting the shared data structure from corruption due to concurrent access is to use a pair of counting semaphores. What is the role of the two semaphores? What prologue code should the producer (i.e., writer) execute before writing to the queue? What epilogue code should it execute after completing a write operation? Under what condition is the producer prevented from writing? Given that mutual exclusion primitives su ce to protect a producer/consumer queue, what is gained by using a solution that involves not one, but two, semaphores?
(c) In lab2, you implemented a trapped version of XINU’s chprio() that utilized x86’s software interrupt support. What was the role of the wrapper function uchprio()? What was the role of the code at Xint36 in intr.S? What was the role of XINU’s legacy chprio()? In ctxsw(), we used pushal/popal to save/restore the 8 general purpose registers. Why does doing the same in Xint36 lead to a problem? What was the work-around? Compared to trapped system call implementation in x86 Linux or Windows, your implementation did not switch stacks. Why not?
BONUS PROBLEM (10 pts)
Why does performing fair scheduling based on process CPU usage lead to logarithmic scheduling overhead? Rules (i) and (ii) in lab3 (and variants thereof) are needed when implementing fair scheduling in operating systems. What can go wrong if rule (ii) is omitted? How is this related to rule (i)?
CS 354 (Park) Midterm March 2 (Fri.), 2018
Remarks: Keep the answers compact, yet precise and to-the-point. Long-winded answers that do not address the key points are of limited value. Binary answers that give little indication of understanding are no good either. Time is not meant to be plentiful. Make sure not to get bogged down on a single problem.
PROBLEM 1 (60 pts)
(a) What is the practical motivation for isolation/protection? What are the four hardware support features re- quired to achieve isolation/protection? What software support feature is required? What is XINU’s approach to isolation/protection?
(b) What are the two hardware support features for providing mutual exclusion? Why is one considered preferable to the other? Can the techniques for providing mutual exclusion be used to prevent producer/consumer queues from becoming corrupted by multiple readers/writers? Explain your reasoning.
(c) What are the roles of the upper and lower halves of XINU and other operating systems? We noted that the scheduler (resched() in XINU) is located between the two halves. Give an example in XINU where the upper half invokes resched(). Do the same for the lower half.
(d) What is the first action that a XINU system call executes when it is entered? What is its last action? Why are these actions performance by XINU? Why are they considered, in general, detrimental to operating system re- sponsiveness? Use the sleepms() system call which enqueues the calling process into a sleep queue (a priority queue similar to XINU’s ready list) to explain. What other operations are performed by system calls at their beginning that increase overhead?
PROBLEM 2 (40 pts)
(a) Describe in words—in sequence and correct order—the logical steps that XINU’s context switch function ctxsw() takes to save the state of the current process before it is switched out. You don’t need to go into address calculation using o↵sets and indirection. When a new process is context switched in, how does XINU know where in memory (i.e., RAM) to find its saved state? Why does writing the code of ctxsw() require knowledge of how a C compiler (in our case gcc) manages function calls?
(b) Explain the scheduling overhead (i.e., time complexity) of XINU. What is the corresponding overhead of fair scheduling used by Linux? Why is the scheduling overhead of UNIX Solaris which uses a multilevel feedback queue constant? In your answers to XINU, Linux, and Solaris scheduling, explain enqueue and dequeue operations and their overhead separately.
BONUS PROBLEM (10 pts)
We noted in class that modern kernels are reactive systems. What does that mean? Is XINU (the same goes for other kernels such as Linux/UNIX and Windows), as an operating system, a collection of dedicated system processes performing kernel chores? Explain.
CS 354 (Park) Midterm March 8 (Fri.), 2013
Remarks: Keep the answers compact, yet precise and to-the-point. Long-winded answers that do not address the key points are of limited value. Binary answers that give little indication of understanding are no good either. Time is not meant to be plentiful. Make sure not to get bogged down on a single problem.
PROBLEM 1 (36 pts)
(a) Xinu system calls begin by disabling all interrupts and end by re-enabling them before returning. What purpose does this serve? In the case of the create() system call which updates (i.e., writes to) the process table, what may go wrong if interrupts are not disabled? Why is interrupt disabling not a method preferred by modern operating systems?
(b) What are the hardware features of processors, including x86 CPUs, that help operating systems such as UNIX, Linux and Windows achieve isolation/protection? What role do system calls play for realizing isolation/protection?
(c) In x86 Xinu, when context-switching out a process, what pieces of information does ctxsw() save? Most of the pieces are saved on the process’s run-time stack, however, the stack pointer is recorded in the process table. Why is this a reasonable strategy as opposed to, say, saving everything in the process table?
PROBLEM 2 (32 pts)
(a) UNIX Solaris, among other operating systems, implements time-shared (TS) process scheduling by changing the priority and time slice of a process based on whether it makes a blocking system call or depletes its allocated time slice. How are the adjustments qualitatively made and what is the rationale behind them? Are there potential issues? How does Solaris go about preventing starvation?
(b) What are the pros/cons of implementing multithreading entirely in user space versus with kernel support? Which approach may be more suited for today’s multicore processors?
PROBLEM 3 (32 pts)
(a) Kernel code must be extremely e cient, preferably incurring only constant overhead (i.e., constant time), and, if not, logarithmic overhead. What is the overhead of Xinu’s default scheduler used in Lab1? What is the overhead of TS scheduling which uses a multi-level feedback queue? Explain how you arrive at the overhead estimation.
(b) When aiming to achieve mutual exclusion by guarding critical section code of processes that operate on shared data structures, what is the advantage of using tset over interrupt disabling, and what is the advantage of using semaphores over both tset and interrupt disabling? Might using semaphores have a drawback? Can semaphores be considered a purely software-based solution or is there a hidden hardware dependence? Explain.
BONUS PROBLEM (10 pts)
In modern operating systems, it is not enough that a process has a private run-time stack to manage user space function calls. To achieve isolation/protection, a process must also be provided with a kernel space run-time stack that is used when executing system calls. Why is this the case?
SOLUTIONS TO CS 354 MIDTERM, SPRING 2013 (PARK)
P1(a) 12 pts
Disabling interrupts guarantees that a system call runs uninterrupted
which ensures integrity of shared kernel data structures through mutual
exclusion.
4 pts
create() has to update the kernel’s process table. Without interrupt
disabling, the process table may get corrupted if two processes executing
create() try to access it concurrently.
4 pts
Interrupt disabling is a drastic action that can prevent other important
events, such as handling packets arriving at a network interface card
and clock interrupts, from being processed by the kernel in a timely manner.
4 pts
P1(b) 12 pts
Three hardware features: privileged/non-privileged instruction set,
kernel/user mode, memory protection.
6 pts
System calls (i) change a process’s status from user mode to kernel mode,
(ii) branch to a specific kernel function to handle the user request
in kernel space. The kernel function may include privileged instructions
for accessing shared hardware resources which can now be executed without
triggering a fault. When a system call returns the process is switched
back to user mode.
6 pts
P1(c) 12 pts
Four pieces: the caller’s frame pointer (ebp), flags register bits, 8
general purpose registers, stack pointer.
6 pts
The stack pointer of a context-switched out process needs to be easily
accessible when context-switching in the process at a later time. The process
table serves this purpose well.
3 pts
Accessing the process table entails several instructions for memory
indirection. Using hardware supplied instructions (push/pop variety for
stack manipulation) is more efficient.
3 pts
P2(a) 16 pts
Processes that make blocking system calls and give up CPU voluntarily
are treated as IO-intensive and their priority is increased while their
time slice is decreased. Processes that deplete their time slice and
are preempted by the clock interrupt handler are treated as CPU-intensive
processes and their priority is decreased and their time slice increased.
6 pts
The rationale is to give I/O-intensive processes preference over
CPU-intensive processes when they are in ready state, since by their
nature, they consume less CPU cycles. A small time slice is given to
I/O-intensive processes, just in case a CPU-intensive process was
misclassified.
6 pts
A potential issue is that for real-world processes that are a mix —
exhibit both CPU- and I/O-intensive behavior over time — how they fare
relative to CPU- and I/O-intensive processes is less clear.
https://www.coursehero.com/file/9690382/mid-354-13s-sol/
This study resource was shared via CourseHero.com
2 pts
Solaris monitors how long a ready process has not received CPU cycles,
and if this time period exceeds a threshold, its priority is increased.
2 pts
P2(b) 16 pts
Pro: Thread creation and management does not entail system calls which
tend to be slow.
6 pts
Cons: (i) User space threads cannot make blocking system calls (e.g.,
for I/O) since a single thread blocking ends up blocking all user space
threads. (ii) Multiple CPUs (or cores) cannot be utilized.
8 pts
Due to (ii), multithreading with kernel support is more suited for multicore
processors.
2 pts
P3(a) 16 pts
Xinu’s default scheduler requires linear over head (i.e., O(n) where n
is the number of processes) since inserting a process into a priority
queue, in the worst case, requires traversing the whole list.
6 pts
With k priority levels, where k is treated as a constant: (i) Dequeue
requires finding the highest priority level at which there are one or more
ready processes enqueued. At worst, this requires k comparisons. After
finding the highest non-empty priority level, we can pick the first
process (constant cost) since all processes at the same level are serviced
round-robin. (ii) Enqueue requires going to a process’s priority level
(constant since multi-level feedback queue is an array of linked lists
indexed by priority), which is constant, then inserting at the end of
the list (also constant) by round-robin property.
10 pts
P3(b) 16 pts
tset does not disable interrupts, thus important events such as packet
arrivals can continue to be processed by a kernel’s interrupt handling
routines.
6 pts
tset wastes CPU cycles by waiting on tset to return false in an infinite
loop (busy waiting). A process that uses semaphores does not busy wait
but gets blocked (and context-switched out) by the kernel which avoids
wasting CPU cycles.
6 pts
Yes, semaphore calls wait() and signal(), internally, must disable
interrupts to ensure that their code is run atomically. Since the codes
of wait() and signal() are relatively short, the disruption to kernel
due to interrupt disabling is kept small.
4 pts
Bonus 10 pts
Without a kernel stack, two processes A and B that share memory where
their run-time stacks reside can collude and run their own code in kernel
mode. For example, A makes a blocking system call, say, read(). read()
may entail internal kernel function calls which are managed (push/pop)
using A’s user space run-time stack. read() blocks and A is context
switched out while in kernel mode. Process B is scheduled next, B has
access to A’s run-time stack, overwrites one of the return addresses
(EIP) of read()’s callees so that it points to B’s own code. When A
https://www.coursehero.com/file/9690382/mid-354-13s-sol/
This study resource was shared via CourseHero.com
Powered by TCPDF (www.tcpdf.org)
unblocks and is context switched in again, returning from read()’s nested
function calls will cause a jump to B’s code while A is still in kernel
mode.
https://www.coursehero.com/file/9690382/mid-354-13s-sol/
This study resource was shared via CourseHero.com
CS 354 (Park) Midterm 1 Feb. 24 (Fri.), 2017
Remarks: Keep the answers compact, yet precise and to-the-point. Long-winded answers that do not address the key points are of limited value. Binary answers that give little indication of understanding are no good either. Time is not meant to be plentiful. Make sure not to get bogged down on a single problem.
PROBLEM 1 (45 pts)
(a) What are the responsibilities of the upper and lower halves of XINU and modern kernels such as Linux/UNIX and Windows? In XINU, what is the first task that is performed after entering the upper or lower half? In our x86 Galileo backends, what change in hardware state (think of register flags) does this software action result in? What is the main di↵erence of XINU’s upper half when compared to Linux/UNIX and Windows? Name three XINU kernel functions: one belonging to the upper half, another to the lower half, and a third belonging to neither.
(b) How do kernels determine if a process is CPU- or I/O-bound? In Solaris UNIX, what happens to a TS process when it is deemed to be CPU-bound? What happens to an I/O-bound process? What is the rationale behind these actions? In the fair scheduling implementation discussed in class (and part of lab3), how are I/O-bound processes treated when compared to CPU-bound processes? Explain your reasoning.
(c) The memory layout of XINU on a backend machine after it has created a number of concurrent processes is di↵erent from that of Linux/UNIX and Windows. In what way is this so? How is this related to the heavy- weight/light-weight process model? In principle, a process in Linux that makes a very large number of nested function calls can face what type of run-time problem? In XINU, a process that makes a comparatively moderate number of nested function calls can cause what type of problem? What x86 hardware support that is currently “disabled in software” (recall our discussion of segmentation) may be utilized to mitigate the problem in XINU?
PROBLEM 2 (34 pts)
(a) What are the hardware support features provided for achieving isolation/protection in modern operating sys- tems? What software feature is required? If this software feature is not implemented, what can an attacker do to bypass isolation/protection and take over a computing system? Describe the steps involved. Is super user/root the same concept as kernel mode in modern kernels? When might super user/root become relevant in XINU?
(b) When XINU performs context-switching on our x86 backends, what pieces of hardware state does it save on a process’s run-time stack? What information is also saved elsewhere, and why? When a function calls another function, the compiler makes sure that the return address (i.e., EIP in Galileo x86) is checkpointed so that when the callee returns the caller can resume where it left o↵. In XINU’s context-switching code where we are switching from one process to another—a much more drastic change—the EIP of the process being context-switched out is not saved. Why is that so? Is this specific to XINU?
PROBLEM 3 (21 pts)
What is the overhead (i.e., time complexity) of XINU’s static priority scheduler? State your answer with respect to the two main operations: enqueueing and dequeueing a ready process. Why can we implement TS process scheduling of Solaris UNIX in constant time with the help of the multilevel feedback queue data structure? Why is the overhead of Linux’s fair scheduler logarithmic? Practically speaking, is this a major weakness when compared to constant time schedulers? Explain your reasoning.
BONUS PROBLEM (10 pts)
What is the role of the clock interrupt handler in the lower half of a kernel (including XINU) with respect to process scheduling? Describe in words what it does to assist in process scheduling. When implementing fair scheduling in lab3, do you still require the help of the clock interrupt handler? Discuss your reasoning.
CS354 Midterm1 Solution, spring 2017
P1(a) 15 pts
Upper half: respond to system calls.
Lower half: respond to interrupts.
4 pts
Disable all interrupts.
2 pts
IF flag in the EFLAGS register is set to 0.
2 pts
XINU does not implement trap (i.e., system calls are regular function
calls) hence the upper half runs without isolation/protection.
4 pts
upper half: sleepms()
lower half: clkdisp()
neither: resched()
3 pts
P1(b) 15 pts
The last action associated with a running process is used to determine
if a process’s recent behavior is CPU- or I/O-bound.
If a process makes a blocking system call: I/O-bound.
If a process depleted its time slice: CPU-bound.
4 pts
Solaris:
If CPU-bound: decrease priority, increase time slice.
If I/O-bound: opposite.
4 pts
A process that is I/O-bound and relinquishes the CPU voluntarily without
depleting its time slice is “rewarded” by promoting its priority which
makes it likely to be scheduled sooner than CPU-bound processes when it
becomes unblocked in the future. This enhances its responsiveness which is
beneficial to interactive applications. Since it does not need much CPU
time, the time slice is kept small.
2 pts
On the other hand, a process that is CPU-bound and depletes its time slice
has its priority lowered to allow I/O-bound processes timely access to
CPU cycles. Its time slice is increased to reflect its CPU-bound nature.
This does not starve I/O-bound processes since their higher priority allows
them to preempt the lower priority CPU-bound process when they become
unblocked.
2 pts
In fair scheduling where we use CPU usage as an indicator of priority
(smaller CPU usage corresponds to higher priority), I/O-bound processes
whose CPU usage tends to be small get higher priority compared to CPU-bound
processes.
3 pts
P1(c) 15 pts
In Linux/UNIX and Windows, by default, a process has its own text, data,
heap, and stack area in memory that is not shared with other processes. In
XINU, text, data, and heap are shared, and stack areas of processes are
placed adjacent to each other.
4 pts
XINU memory layout corresponds to the layout of a single heavy-weight process
that has multiple light-weight processes which share text, data, and heap,
but have individual/separate stacks per light-weight process.
3 pts
Although unlikely due to the large memory afforded in today’s systems, a very
large number of nested function calls could cause the stack area of a
process to overflow into its heap area.
3 pts
Depending on the stack size specified when spawning a process using create(),
a moderate number of nested function calls could overflow into the stack area
of another process since in XINU’s memory layout stack areas of processes are
placed adjacent to each other.
3 pts
We may use stack segment (SS) memory bound checking provided by x86 to prevent
a process from exceeding the memory allocated to its stack area. By default, the
base is set to zero and the limit to maximum memory by kernel software so that
memory bound checking is effectively disabled.
2 pts
P2(a) 17 pts
Hardware support features:
privileged/non-privileged instructions
user mode/kernel mode
trap instruction/mechanism to enter kernel mode
memory protection
4 pts
Software support:
per-process kernel stack
2 pts
An attacker can create two processes that share their memory. One process makes a
blocking system call that puts the process in kernel mode and while in kernel
mode pushes stacks frames when making kernel function calls into the process’s
run-time stack. The second process, because it shares memory with the first process,
access the run-time stack and changes the return address in one of the kernel
stack frames to point to malware. When the blocked process resumes, it eventually
jumps to malware code while in kernel mode.
6 pts
No. Super-user/root are concepts that relate to the notion of users of an operating
system, i.e., user name/user ID. This is primarily a software construct. Kernel mode
is part of core hardware support for isolation/protection.
3 pts
As is, XINU is a single user system without a notion of user name/user ID. The
XINU version we are using does not have a file system and does not implement
isolation/protection. If these two components are added, it may be meaningful to
add user name/user ID to XINU that supports the notion of ownership of files.
2 pts
P2(b) 17 pts
EFLAGS
8 “general purpose” registers (EAX, EBX, ECX, EDX, ESP, EBP, two more)
4 pts
ESP is also separately stored in the saved stack pointer field (prstkprt) of
the process’s process table entry. To restore the hardware using the information
saved on the process’s stack, we need to know the address of the top of the
stack.
3 pts
In XINU all code (i.e., text) is shared by all processes and that includes the
code of the kernel. This implies that kernel functions such as resched() and
ctxsw() reside at the same address for all processes. Since both the process
being context-switched out and the process being context-switched in call the
same functions to checkpoint and restore their states, there is no need to
save EIP.
7 pts
This is not specific to XINU. In modern kernels such as Linux/UNIX and Windows,
kernel code (but not user code) is shared by all processes. Therefore addresses
of kernel functions are the same for all processes.
3 pts
P3 21 pts
XINU static priority scheduler:
Dequeue: constant (i.e., O(1)) since XINU’s ready list is a priority queue that
sorts ready processes by their priority in nonincreasing order. Therefore a
highest priority ready process is always at the head of the list.
Enqueue: in the worst case, the ready list has to be traversed until the end to
find the place where a ready process has to be inserted. Since the ready list
can include all other processes, the cost is linear (i.e., O(n) where n is the
number of processes).
6 pts
Solaris TS with multilevel feedback queue:
With 60 priority levels for TS processes (i.e., number of priorities is fixed
or constant):
Dequeue: find the highest priority level at which there are one or more ready
processes enqueued. At worst, this requires 60 comparisons. After finding the
highest non-empty priority level, we pick the first in the list of processes
pointed to by the data structure since all processes at the same priority level
are serviced round-robin. Hence overhead is constant.
Enqueue: the priority of the ready process to be inserted acts as the index to
the data structure (array of struct which contains two pointers) which is constant.
We use the second pointer which points to the end of the list to insert the
process. This incurs constant overhead. Again, this only works because all
processes of equal priority are assumed to be served round-robin.
8 pts
In Linux fair scheduling where CPU usage is utilized in determining the priority
of processes, a process’s priority is inversely related to its CPU usage. The
kernel’s scheduling invariant — always pick a highest priority ready process to
run next — dictates that we choose a ready process which has received least
CPU usage. Instead of using a linear cost priority queue, we can use data structures
that implement balanced trees to enqueue and dequeue ready processes in logarithmic
time (i.e., the depth of a balanced tree is logarithmic in the number of elements
stored). Linux uses a particular data structure called R-B tree for this purpose.
4 pts
Practically, it is not such a big weakness since the logarithm of even a super
astronomical number such as 2^300 is still 300, a relatively small constant. For
servers which may manage thousands of processes, the depth will be in the teens
or less. Reducing constants is practically important hence logarithmic cost is
a weakness, just not a major weakness.
3 pts
Bonus 10 pts
One of the tasks of the clock interrupt handler is to implement count down of a
process’s time slice. If the count reaches zero (i.e., a process has depleted its time
slice), the clock interrupt handler calls the scheduler so that it may decide which
process to run next.
5 pts
Assuming a process is not being preempted by a higher priority process that has
become unblocked and ready, we need to ensure that the current process (which has
the least CPU usage) does not excessively use CPU cycles uninterrupted where it
may overtake the process with the second least CPU usage. Thus we need to apply
a time limit so that if the process does not give up the CPU before then, the kernel
is able to intervene and decide who to schedule next.
5 pts