Operating Systems

COMP 3000
Operating Systems
Further into the Abstractions
Lianying Zhao
What Makes Abstraction/Virtualization Possible?
• The abstraction creator/enforcer must be:
• “Omnipotent”, that always has a higher privilege than the target
• “Omniscient”, that sees everything about the target
• All this leads to the requirement for hardware support
COMP 3000 (Winter 2023) 2
Virtualizing the CPU
COMP 3000 (Winter 2023) 3
• Recall: the few purposes
• Containing faults (reliability)
• Security
• Simplicity
• Also more:
• Maximum CPU utilization
• Therefore, what’s expected from the illusion:
• No need to think about others
• No access to others’ resources
The Execution Context
• The computer processor is like a state machine
• A program (a sequence of instructions), as input, just triggers transitions
• What determines the machine state?
• Take x86 as an example:
• The program counter – (E/R)IP
• Status/flag registers, e.g., (E/R)Flags
• General-purpose registers, e.g., (E/R)AX, BX, CX, …
• Other registers
• Memory info
• Much more in reality
COMP 3000 (Winter 2023) 4
The Process Abstraction (recap)
• Just a running program
• Typically loaded into memory from an executable (binary file)
• Or in any other less typical forms
• What is hidden:
• The fact that other processes are also sharing the same CPU
• All the (privileged) software/hardware facilities that back it up
• New semantics:
• Processes with unique identifiers (PIDs)
• API
COMP 3000 (Winter 2023) 5
We will discuss the specifics later
Scheduling
COMP 3000 (Winter 2023) 6
• Principle 1: To keep the CPU busy!
• Principle 2: To finish tasks as soon as possible
• Principle 3: To be fair to all processes
• Each process gets a time slice
• The scheduler of modern operating systems can be very complicated
Context Switch
• A fundamental mechanism, simply:
• Saving the context of one process and suspending it
• Restoring the context of another process and getting it to run
• The data structure where a process’s context is stored is (often) called:
• Process Control Block (PCB)
• There is a cost!
COMP 3000 (Winter 2023) 7
Concurrency vs. Parallelism
• Concurrency (one of the three “pieces”)
• Multiple tasks (contexts) progressing at the same time
• In overlapping time periods, but not necessarily exactly at the same time
• Posing a host of challenges (we will discuss in this course)
• Parallelism
• Literally at the same time
• E.g., on a multi-core CPU
• How to understand the two?
• Concurrent → interruptible/divisible Parallel → independent
• No true parallelism actually justifies the need for task scheduling
COMP 3000 (Winter 2023) 8
Working with Processes – Creation
• The fork system call
• The exec system call
• CreateProcess() on Windows
COMP 3000 (Winter 2023) 9
Processes vs. Threads
• Various ways to understand the difference
• Multiple points of execution for one program
• Threads are light-weight processes
• Actually, the kernel does not necessarily see (user) threads, i.e., they
are the same at the low level, so
• Context switch is also needed for scheduling threads
• Thread Control Block (TCB)
• Threads’ defining difference: shared address space
COMP 3000 (Winter 2023) 10
Working with Threads
• Pthreads (POSIX threads)
• E.g., pthread_create()
• Library calls, not system calls
• At the OS level, the actual system calls to create threads can be:
• Clone – Linux specific (recall: portability)
• by specifying CLONE_THREAD (there are also other levels of sharing for
processes)
• Shared address space causes more concurrency issues
COMP 3000 (Winter 2023) 11
Virtualizing the Memory
COMP 3000 (Winter 2023) 12
• How is memory (RAM) used/organized?
• Addressable at the granularity of bytes
• Accessed at the granularity of the width of the processor architecture
• Data storage + code execution
• The main problem to solve:
• Space allocation
• Mapping between physical and virtual
• Shared purposes with virtualizing the CPU:
• Security, reliability, simplicity and max efficiency
The Memory Hierarchy
COMP 3000 (Winter 2023) 13
Original (reality) Abstraction (illusion)
CPU registers CPU registers
Also in terms of access latency
L1 cache
L2 cache
L3 cache
Main memory
Hard disk
Memory
The Memory Layout
COMP 3000 (Winter 2023) 14
Original (reality) Abstraction (illusion)
Memory
The Address Space Abstraction
• A (seemingly) independent numbering system starting from 0
• Addresses in an address space are virtual
• Address translation happens behind the scene
• Other than the space, there are also other meta data, such as
• Stack
• Heap
COMP 3000 (Winter 2023) 15
Mechanism: Segmentation
• The idea: assign a segment for each purpose
• Code – CS
• Data – DS
• Stack – SS
• The start of a segment serves as the base address. An address is
formed by applying an offset:
• Pure segmentation was in the old days
COMP 3000 (Winter 2023) 16
Mechanism: Paging
• The need for contiguous allocation in physical memory
• External fragmentation
• Let’s go for finer granularity!
COMP 3000 (Winter 2023) 17
Caution: overloaded term, cf. swapping
Mechanism: Swapping
• Don’t want to be limited by physical memory?
• The swap partition (pagefile.sys on Windows)
• The page fault
• Paging (the other meaning): moving the pages
• Swapping: moving the entire process
COMP 3000 (Winter 2023) 18
Abstractions are Provided by the OS (Kernel)
• So most of the abstractions are not directly seen in kernel space
• E.g., don’t try to find processes in a kernel
• BUT the same or similar mechanisms still apply
• E.g., paging also happens in kernel space
COMP 3000 (Winter 2023) 19
COMP 3000 (Winter 2023) 20
COMP 3000
Operating Systems
Misc.
Command Arguments and Options
• What’s passed to the program
int main(int argc, char *argv[])
{
• argc: number of arguments
• argv: the array of arguments, each being a string
• The first one (argv[0]) is always the command name (or… should be)
• Subsequent ones are space-delimited strings
• Note: these are determined by the shell
• Example: ls -lais
• Conventions
COMP 3000 (Winter 2023) 21
Linking Options and System Calls
• Static linking:
• To avoid dependency issues at the cost of space (disk + memory)
• So, no library calls should be made by design
• Dynamic linking:
• Reuse of common functions
• The expected versions must be ensured
• System calls are invoked when any OS service is needed
• In general, I/O-intensive functions tend to generate more system calls
• Expensive
COMP 3000 (Winter 2023) 22
More about Program Binaries
• Relocatable object files (.o) → (archive, ar) → Static libraries (.a)
• ↓ (linking, ld)
• Shared libraries (.so) – ELF
• Executable files – ELF
COMP 3000 (Winter 2023) 23
Dynamic Library Dependencies
• Symbols
• Just variable names and function names
• Symbol tables
• Various ways to list symbols
• readelf
• nm
• objdump
COMP 3000 (Winter 2023) 24