Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 5 / 2 (Operating Systems)

The working set $W(t,\Delta )$ is the set of virtual pages referenced by an operating-system process within a recent window of $\Delta$ execution time or memory references. Its size estimates the number of frames needed for the process's current locality of execution. It is a set of recently used pages, not the entirety of the process's address space.

An operating system can estimate it from reference bits or fault history and try to keep those pages resident. Process scheduling and admission control should avoid simultaneously running processes whose combined working sets exceed physical memory; suspending some processes or reducing multiprogramming then allows the rest to make useful progress. If too many active pages compete for too few frames, repeated page faults produce memory thrashing. Working sets connect memory allocation to the choice of processes allowed to run.

Both kinds of context switch save and restore registers, a program counter, stack pointer and scheduler state. Switching between operating-system processes additionally changes the address-space and protection context, including the page-table root. Cached translations must be invalidated or distinguished by address-space identifiers, and the new process may have a different memory and cache locality.

Software threads of one process share its address space and most resources, so a thread switch normally preserves the page-table root and valid cached translations; only the execution context, stack and thread-specific state need change. Thus a process switch requires address-space management which a same-process thread switch usually avoids. Tagged translation caches can reduce the extra cost, so a complete translation lookaside buffer flush is not an inevitable feature of every process switch.

First, suppressing kernel preemption simplifies protection of shared kernel data on a uniprocessor: another ordinary kernel execution cannot be scheduled in the middle of a short update which temporarily breaks an invariant. Fewer paths require preemption-specific locking and reentrancy handling, making the operating-system kernel easier to implement correctly.

Second, it avoids involuntary kernel context switches and their scheduler, register-save and cache-disruption costs, and can make the execution of short kernel operations more predictable. The tradeoff is greater scheduling latency if a kernel operation runs too long. Simpler synchronization and lower switching overhead are the two reasons. Non-preemptive kernel code can still receive interrupts or block voluntarily, and multiprocessor execution still requires synchronization; non-preemption is not a substitute for all locking.

Set-user-ID execution of a suitable executable makes its effective user identity that of the owner. When that owner is root, running it can give root privileges even to an otherwise unprivileged caller. World-write permission destroys the trust boundary: any user can alter the privileged executable, potentially substituting code which performs arbitrary privileged operations. World-execute permission then makes the compromised program available to everyone.

World-read access can reveal implementation details or embedded secrets, but reading alone is not the decisive privilege-escalation flaw; properly designed public set-user-ID utilities need not keep their code secret. Some Unix kernels clear the set-user-ID bit after an unprivileged modification. That is a mitigation, not a reason to maintain a world-writable privileged program: if the bit persists or is restored without validating the changed code, the privilege escalation remains. Root-owned privileged executables must not be writable by untrusted users.