Operating Systems: Process Management, Memory, and Kernel Modes

HW2 Q: Which is SHARED by all threads in a process? A) registers B) stack C) global variables D) program counter

C) Global variables (each thread has its own registers, PC and stack)

HW2 Q: What is an upcall?

A message from the kernel to the upcall handler in the thread library telling it about an event (e.g., a thread is about to block). Part of scheduler activations

HW2 Q: What is the purpose of the PCB?

Stores everything the OS needs to manage a process: state, PID, program counter, CPU registers, scheduling, memory, accounting and I/O info

HW2 Q: What does fork() do? A) Terminates a process B) Creates a new process C) Replaces memory D) Waits for a child

B) Creates a new process (a copy of the parent)

HW2 Q: A process that has terminated but whose parent has not yet called wait() is a(n) ____

Zombie process

HW2 Q: Circular buffer FULL condition

((in + 1) % BUFFER_SIZE) == out

HW2 Q: Circular buffer EMPTY condition

in == out

HW2 Q: Which is NOT a benefit of multithreading? (Responsiveness / Resource sharing / Economy / Uses more memory)

Uses more memory. Threads use LESS memory than processes (that is the Economy benefit)

HW2 Q: Running more than one task at exactly the same time on multiple cores is ____

Parallelism (interleaving tasks over time is concurrency)

HW2 Q: In which model does one blocking system call block ALL threads, and threads cannot run in parallel on multicore?

Many-to-One

HW2 Q: Two advantages of a thread pool

1) Reusing an existing thread is faster than creating a new one 2) Limits how many threads exist at once

Operating system (definition)

Software that acts as an intermediary between the user and the hardware; controls and coordinates hardware use among programs and users

Monolithic structure (+ / -)

Whole kernel is one binary in one address space (original UNIX). + Fast, little overhead. - Hard to implement, extend and debug

Layered approach (+ / -)

Layer 0 = hardware, layer N = user interface; each layer uses only lower layers. + Easy to build and debug. - Poor performance (calls pass through many layers)

Q: The major difficulty in designing a layered OS is ____

Appropriately defining the various layers

Microkernel (+ / -)

Kernel keeps only essential services; the rest runs in user space; communicates by message passing. + Easy to extend, reliable, secure. - Message-passing overhead. Example: Mach

Q: A microkernel is a kernel ____

That is stripped of all nonessential components

Loadable kernel modules (modular approach)

Kernel has a core set of components and links in extra services (modules) at boot or run time, each with a known interface. Used by Linux, macOS, Solaris

Modular approach: ADVANTAGES

Load/unload services dynamically without recompiling the kernel; any module can call any other directly; faster than microkernel (no message passing); flexible like layered

Modular approach: DISADVANTAGES

Modules still run in kernel mode, so a buggy module can crash the whole system; less isolation/protection than a microkernel; kernel can grow large

Q: ____ allows operating system services to be loaded dynamically

Modules (loadable kernel modules)

Dual-mode operation (purpose)

User mode and kernel mode; protects the OS and system components from accidental or malicious user programs

User mode

Mode bit = 1; applications run here; privileged instructions are NOT allowed

Kernel mode

Mode bit = 0; OS code runs here; privileged instructions ARE allowed

Mode bit

Hardware bit showing the current mode: 0 = kernel, 1 = user

How does the CPU switch from user mode to kernel mode?

A system call, trap or interrupt sets the mode bit to kernel; returning from it sets the bit back to user

Q: Another term for kernel mode? A) supervisor B) system C) privileged D) All of the above

D) All of the above

Q: Which should run ONLY in kernel mode? Read the clock / Clear memory / Issue an instruction / Turn off interrupts / Modify device-status table

Clear memory, Turn off interrupts, Modify device-status table

What happens if a user program tries a privileged instruction?

Hardware does not run it; it traps to the OS, which treats it as illegal (usually terminates the program)

Q: A ____ prevents a user program from never returning control to the OS

Timer

T/F: System calls can be run in either user mode or kernel mode

False. Called from user mode, executed in kernel mode

T/F: Interrupts may be triggered by either hardware or software

True

System call

Programming interface to the services provided by the OS; runs in kernel mode

API (Application Programming Interface)

Set of functions a programmer calls; the API function invokes the actual system call. Examples: Windows API, POSIX API (UNIX/Linux/macOS), Java API

Why use an API instead of calling system calls directly?

Portability (same code on any system with that API) and simplicity (system calls are more detailed/harder to use)

T/F: The system call interface is the boundary between user programs and OS services

True

Q: ____ is NOT a technique for passing parameters to a system call. A) Cache memory B) Registers C) Stack D) Block in memory

A) Cache memory

Process

A program in execution; ACTIVE entity

Program

PASSIVE entity: an executable file on disk; becomes a process when loaded into memory

Process memory layout, top (high address) to bottom (low address)

Stack -> (free space) -> Heap -> Data -> Text

Text section

Holds the executable program code

Data section

Holds global (and static) variables

Heap

Memory allocated dynamically at run time (malloc/new); grows UP toward the stack

Stack

Temporary data: function parameters, return addresses, local variables; grows DOWN toward the heap

Q: Function parameters, return addresses and local variables are stored in the ____

Stack

Q: A global variable is stored in the ____ section

Data section

Q: Memory from malloc() comes from the ____

Heap

Q: Which sections are fixed size and which grow?

Text and data are fixed size. Stack and heap grow and shrink during execution

5 process states

New, Ready, Running, Waiting, Terminated

Process state transitions

New->Ready (admitted); Ready->Running (scheduler dispatch); Running->Ready (interrupt); Running->Waiting (I/O or event wait); Waiting->Ready (I/O or event done); Running->Terminated (exit)

Q: A process may move to Ready by A) I/O completion B) awaiting its CPU turn C) being newly admitted D) All of the above

D) All of the above

Process Control Block (PCB)

Kernel data structure for each process: state, PID, program counter, registers, scheduling, memory, accounting, I/O info. Linux: task_struct

Context switch

CPU switches from one process to another: SAVE the old process's state into its PCB, then LOAD the new process's state from its PCB

Q: A ____ saves the state of the current process and restores the state of the next process

Context switch

When does a context switch happen?

On an interrupt, a system call, a timer/time-quantum expiring, or when the running process waits for I/O

fork() return values

0 in the child; the child's PID (> 0) in the parent; negative if fork failed

Which UNIX system call CREATES a new process?

fork()

Which system call REPLACES a process's memory with a new program?

exec() (used after fork(); if it succeeds it never returns)

wait()

Parent waits for a child to finish; returns the child's PID and exit status

Orphan process

Child whose parent terminated without calling wait(); init (systemd) becomes its parent

Q: The ____ process becomes the parent of orphan processes

init (systemd)

Q: When a child process is created, which is possible? A) Runs concurrently with parent B) New program loaded C) Duplicate of parent D) All of the above

D) All of the above

Thread

Basic unit of CPU utilization: thread ID, program counter, register set and stack

What does each thread have of its OWN?

Thread ID, program counter, register set, stack

What do threads in a process SHARE?

Code (text), data (globals), heap, open files and other OS resources

T/F: A thread is composed of a thread ID, program counter, register set, and heap

False (stack, not heap)

4 benefits of multithreading

Responsiveness, resource sharing, economy, scalability

Concurrency

Multiple tasks make progress by interleaving; possible on a single core

Parallelism

Multiple tasks run at the same time; requires multiple cores

T/F: It is possible to have concurrency without parallelism

True

User threads

Managed by a user-level thread library without kernel support

Kernel threads

Supported and managed directly by the OS kernel

Many-to-One model

Many user threads -> 1 kernel thread. One blocking call blocks all; no parallelism on multicore. Rarely used

One-to-One model

Each user thread -> its own kernel thread. More concurrency and parallelism; too many kernel threads burden the system. Linux and Windows

Many-to-Many model

Many user threads multiplexed onto a smaller or equal number of kernel threads

Two-level model

Like many-to-many, but also lets a user thread be bound to one kernel thread

Q: Which model do Linux and Windows use?

One-to-One

3 main thread libraries

POSIX Pthreads, Windows threads, Java threads

Pthreads

POSIX standard API for thread creation and synchronization; a specification, implemented at user or kernel level

pthread_create()

Creates a new thread that runs a given function

pthread_join()

Waits for a thread to terminate (like wait() for processes)

Thread pool

Creates threads in advance; they wait for work and are reused instead of creating a new thread per task

Scheduler activations

Kernel gives the app LWPs and informs the thread library of events via upcalls

Amdahl's Law formula

Speedup

Amdahl: what happens as N goes to infinity?

Speedup approaches 1 / S; the serial part limits the maximum gain

CPU scheduler (short-term scheduler)

Selects a process from the ready queue and allocates the CPU to it

Dispatcher

Gives the CPU to the selected process: context switch, switch to user mode, jump to the right place in the program

Nonpreemptive scheduling

Once a process has the CPU it keeps it until it terminates or waits

Preemptive scheduling

The OS can take the CPU away from a running process (e.g., time quantum expires)

Turnaround time formula

Completion time - Arrival time

Waiting time formula

Turnaround time - Burst time

Response time

Time from submission until the first response (first time on CPU)

Q: ____ is the number of processes completed per time unit

Throughput

FCFS

First-come, first-served; FIFO ready queue; nonpreemptive

Convoy effect

In FCFS, short processes wait behind one long process

SJF

Run the process with the shortest next CPU burst; optimal (minimum) average waiting time

SJF next-burst prediction formula

tau(n+1) = alpha * t(n) + (1 - alpha) * tau(n); usually alpha = 1/2

Round Robin (RR)

Each process gets a time quantum q, then is preempted and goes to the back of the ready queue. Designed for time-sharing

RR: what if q is too large or too small?

Too large = becomes FCFS. Too small = too many context switches (overhead). Rule: about 80% of CPU bursts should be shorter than q

Priority scheduling

CPU goes to the highest priority (smallest number). Problem: starvation. Fix: aging (raise priority of long-waiting processes)