Practice

Execute user programs and make solving user problems easier; make the computer system convenient to use; use the computer hardware in an efficient manner.

The kernel is the one program running at all times. System programs ship with the OS but are not part of the kernel. Application programs are all programs not associated with the operating system.

A software error such as division by zero, and a request for an operating-system service (a system call). Other process problems such as infinite loops also lead the OS to step in.

To prevent a process from looping forever or hogging resources: the OS sets a counter (privileged) that is decremented by the clock; at zero an interrupt returns control to the OS.

Multiprogramming keeps several jobs in memory so the CPU always has one to run when the current job waits. Multitasking (timesharing) switches so often that users can interact with each program; response time should be under one second.

SaaS: word processor in the browser. PaaS: database server ready for application use. IaaS: storage available over the Internet for backups.

For the user: user interface, program execution, I/O operations, file-system manipulation, communications, error detection. For the system: resource allocation, logging, protection and security.

The API (Win32, POSIX, Java) is portable and easier to use; the library hides the details of passing parameters and trapping into the kernel, so programs work across versions and systems that provide the same API.

Process control; device management; information maintenance; communications; protection; file management.

printf() is a C library function that formats the text in user mode; it then calls the write() system call, which runs in kernel mode and sends the bytes to the device.

Benefit: each layer uses only the layers below, so it is simple to build and debug one layer at a time. Drawback: defining the layers is hard and each request passes through several layers, which adds overhead.

The Application Binary Interface defines how binary code components interface on a given OS and architecture (calling conventions, binary formats, system-call numbers). A binary built for one ABI does not run on another.

Text: program code. Data: global variables. Heap: memory allocated at run time. Stack: temporary data — function parameters, return addresses, local variables. Plus the current activity: program counter and registers.

Process state, program counter, CPU registers, CPU-scheduling information, memory-management information, accounting information and I/O status information.

While saving one process’s state into its PCB and loading another’s, the system does no useful work for any process.

A zombie has terminated but its parent has not yet called wait(), so its entry remains. An orphan is a process whose parent terminated without calling wait().

Bounded: the buffer is full, so the producer must wait until the consumer removes an item. Unbounded: the producer never waits.

Message passing where both send and receive are blocking: the sender waits until the message is received, and the receiver waits until a message is available. A zero-capacity link forces it.

No. Legal addresses satisfy base ≤ a < base + limit = 420940, so 420940 is the first illegal address; the hardware traps to the OS (addressing error).

External: enough total free memory exists but it is not contiguous. Internal: an allocated block is larger than requested and the extra is unused. Paging avoids external fragmentation but still has internal fragmentation in the last page.

21,000 = 5 × 4096 + 520, so 6 frames; internal fragmentation = 4096 − 520 = 3,576 bytes.

2³² / 2¹² = 2²⁰ entries × 4 bytes = 4 MB per process.

Binary 0000 0000 0100 0000 0011 1010 1011 1100: p1 = first 10 bits = 1, p2 = next 10 bits = 3, d = 0xABC = 2748.

Swap out 2000 ms plus swap in of a same-sized process 2000 ms = 4000 ms.

A swapper that never brings a page into memory unless it will be needed; one that deals with pages is called a pager.

A victim page that has not been modified is already identical on disk, so it need not be written out; only dirty pages cost a write.

1. Find the desired page on disk. 2. Find a free frame, or select a victim with the replacement algorithm and write it out if dirty. 3. Read the page into the frame and update the tables. 4. Restart the instruction that caused the trap.

9 faults. It needs to know future references, so it is used only as a yardstick for other algorithms.

(0,0) not used, not modified; (0,1) not used but modified; (1,0) used but clean; (1,1) used and modified.

The page with the smallest count was probably just brought in and has yet to be used, so MFU replaces the page with the largest count instead.

FIFO 10, OPT 8, LRU 8. Use the simulator with 4 frames to see the steps.

Responsiveness, resource sharing, economy and scalability.

Concurrency: more than one task makes progress (possible on one core by interleaving). Parallelism: more than one task runs at the same instant, which needs multiple cores.

1 / (0.25 + 0.75 / 2) = 1 / 0.625 = 1.6.

The two-level model (a variation of many-to-many).

Asynchronous cancellation terminates the target thread immediately; deferred cancellation lets the target check periodically whether it should be cancelled, so it can stop at a safe point.

The child task shares the same memory space as the parent, which makes it behave like a thread.

Running → waiting, running → ready, waiting → ready, terminates. Scheduling only on 1 and 4 is nonpreemptive; deciding also on 2 or 3 makes it preemptive.

Turnaround: from submission to completion. Waiting: total time spent in the ready queue. Response: from submission until the first response is produced.

With FCFS, short processes wait behind one long process, like cars behind a slow truck; e.g. many I/O-bound processes behind one CPU-bound process.

The length of the next CPU burst is not known. It can be asked from the user or estimated (usually from the lengths of previous bursts).

The priority of a waiting process is gradually increased with time, so even a low-priority process eventually becomes the highest priority and runs.

Little’s law: n = λ × W = 5 × 3 = 15 processes.

Mutual exclusion, progress and bounded waiting.

It only prevents preemption on the CPU where it is done; processes on other CPUs can still enter. Disabling on all CPUs is slow, and long critical sections would block everything and starve others.

Progress: the processes must strictly alternate. If Pj stays in its remainder section with turn = j, Pi cannot enter even though nobody is in the critical section.

It atomically returns the original value of *target and sets *target to true. A lock is acquired when it returns false.

A binary semaphore ranges only between 0 and 1 (like a mutex lock); a counting semaphore can range over an unrestricted domain, e.g. the number of identical resources.

Only one process may be active within the monitor at a time; implemented with a semaphore mutex = 1, each procedure is wrapped in wait(mutex) … signal(mutex).

Mutual exclusion, hold and wait, no preemption and circular wait — all four must hold simultaneously.

If every resource type has only one instance, yes. If some have several instances, there may or may not be a deadlock.

Require a process to request all its resources before it starts, or to request only when it holds none. Resource utilization is low and starvation is possible.

Invalidating circular wait: number every resource type and require each process to request resources in increasing order.

Need = Max − Allocation = (6, 0, 0).

Any three of: priority; how long it has computed and how long it still needs; resources it has used; resources it needs to complete; how many processes must be terminated; interactive or batch.