One or more CPUs, device controllers connect through common bus providing access to shared memory
Concurrent execution of CPUs and devices competing for memory cycles
Kernel Data Structures
Many similar to standard programming data structures
Singly linked list
Doubly linked list
Circular linked list
Binary search tree left <= right
Search performance is O(n)
Balanced binary search tree is O(lgn)
Hash function can create a hash map
Bitmap - string of n binary digits representing the status of n items
Linux data structures defined in include files <linux/list.h>,<linux/kfifo.h>,<linux/rbtree.h>
Four Fundamental OS Concepts
Thread
Single unique execution context: fully describes program state
Program Counter, Register, Execution Flags, Stack
Address space(with translation)
Programs execute in an address space that is distinct from the memory space of the physical machine
Process
An instance of an executing program is "a progress consisting of an address and one or more threads of control"
Dual mode operation / Protection
Only the "system" has the ability to access certain resources
The OS and the hardware are protected from user programs and user programs are isolated from one another by "controlling the translation" from program virtual addresses to machine physical addresses.
OS Bottom Line: Run Programs
Load instruction and data segments of executable file into memory
Create stack andd heap
Transfer control to program
Provide services to program
While protecting OS and program
First OS Concept: Thread of Control
Certain registers hold the context of thread
Stack pointer holds the address of the top of stack
Other conventions: Frame pointer, Heap pointer, Data
May be defined by the instruction set architecture or by compiler conventions
Thread; Single unique execution context
Program Counter, Register, Execution Flag, Stack
A thread is executing on a processor when it is resident in the processor registers
PC register holds the address of executing instruction in the thread
Registers hold the root state fo the tread
The rest is "in memory"
Second OS Concept: Program's address space
Address space: the set of accessible addresses + state associated with them
For a 32-bit processor there are 2^32 = 4 billion address
What happens when you read or write to an address?
Perhaps nothing
Perhaps acs like regular memory
Perhaps ignore writes
Perhaps causes I/O operation
Perhaps causes exception(fault)
Multiprogramming - Multiple Threads of Control
How can we give the illusion of multiple processors?
Assume a single processor: How do we provide the illusion of multiple processors?
Multiplex in time!
Each virtual "CPU" needs a structure to hold:
Program Counter(PC), Stack Pointer(SP)
Registers(Integer, Floating point, others)
How switch from one virtual CPU to the next
Save PC, SP, and registers in current state block
Load PC, SP, and registers from new state block
what triggers switch?
Timer, voluntary yield, I/O, other things
The Basic Problem of Concurrency
The basic problem of concurrency involves resources:
Hardware: single CPU, single DRAM, single I/O devices
Multiprogramming API: processes think they have exclusive(独属的 ) access to shared resources
OS has to coordinate all activities
Multiple processes, I/O interrupts, ...
How can it keep all these things straight?
Basic Idea: Use Virtual Machine abstraction
Simple machine abstraction for processes
Multiplex these abstract machine
Dra did this for "THE system"
Few thousand lines vs 1 million lines in OS 360(1K bugs)
Properties of this simple multiprogramming technique
All virtual CPUs share same non-CPU resources
I/O devices the same
Memory the same
Consequence of sharing:
Each thread can access the data of every other thread(good for sharing, bad for protection)
Threads can share instructions(good for sharing, bad for protection)
Can threads overwrite OS functions?
This (unprotected) model is common in:
Embedded application
Windows 3.1 / Early Macintosh(switch only with yield)
windows 95 - ME(switch with both yield and timer)
Protection
Operating System must protect itself from user programs
Reliability: compromising the operating system generally causes it to crash
Security: limit the scope of what processes can do
Privacy: limit each process to the data it is permitted to access
Fairness: each should be limited to its appropriate share of system resources(CPU time, memory, I/O, etc)
It must protect User programs from one another
Primary Mechanism: limit the translation from program address space to physical memory space
Can only touch what is mapped into process "address space"
Additional Mechanisms:
Privileged instructions, in/out instructions, special register
syscall processing, subsystem implementation
e.g., file access rights, etc
Third OS Concept: Process
Process: execution environment with Restricted Rights
Address Space with One or More Threads
Owns memory(address space)
Owns file descriptors, file system context, ...
Encapsulate one or more threads sharing process resources
Why processes?
Protected from each other!
OS Protected from them
Processes provides memory protection
Threads more efficient than processes(later)
Fundamental tradeoff between protection andd efficiency
Communication easier within a process
Communication harder between processes
Application instance consists of one or more processes