Slide 1
Operating Systems
CSCI-GA.2250-001
Introduction
Hubertus Franke
.edu
Components of a Modern Computer
– One or more processors
– Main memory
– Disks
– Printers
– Keyboard
– Mouse
– Display
– Network interfaces
– I/O devices
Media
Player
emails Games Word
Processing
Media
Player
emails Games Word
Processing
Does a programmer need to understand all this hardware
in order to write these software programs?
Media
Player
emails Games Word
Processing
Operating System
Components of a
Modern Computer
Figure 1-1. Where the operating system fits in.
The Operating System as an
Extended Machine
Operating systems turn ugly hardware
into beautiful abstractions (arguable).
Assembler
Bitmapping
Hardware
APIs
Documented
Man(ual)-pages
The Operating System as a
Resource Manager
• Top down view
– Provide abstractions to application programs
• Bottom up view
– Manage pieces of complex systems
(hardware and events)
• Alternative view
– Provide orderly, controlled allocation of
resources
The Two Main Tasks of OS
• Provide programmers (and programs) a
clean set of abstract resources and
services to manipulate these resources
• Manage the hardware resources
A Glimpse on Hardware
Simplified view: System Components are interlinked through a
shared bus and communicate over that bus.
This is done through bus transactions
(e.g. load/store to/from memroy, interprocessor notifications,
device accesses, … )
A Glimpse on Hardware
Reality Check:
In reality there are many buses between the components one set
relates to memory accesses (load/store) and one to I/O subsystems
A few conventions
• Computer Scientists think in 2^N
• Remember a few tricks
• Know:
2^0 .. 2^9
2^10 ~10^3 = 1KB
• and the rest is easy (e.g.):
– 2^20 ~10^6 = 1MB
– 2^30 ~10^9 = 1GB
– 2^32 = 2^(30+2) = 4GB
– 2^16 = 2^(10+6) = 64KB
Expected you can do 2^N math on the spot
A few assembler conventions used
• Occasionally we need to use some assembler
notation, I utilize a general fictious notation that
should be easily understood
• Loads and stores:
– basic means to obtain a data item from/to memory
– ld r3,addr for loading a piece of memory (addr) into a
register (r3) (will cover that in a bit)
– st r3,addr for storing a value in register (r3) back to
memory (addr)
• Arithmetic operations:
– takes operands and performs basic operations
– add r3, r4, r5 ( r3 = r4+r5)
What Is an OS?
Resources
• Allocation
• Protection
• Reclamation
• Virtualization
Services
• Abstraction
• Simplification
• Convenience
• Standardization
Makes computer usage simpler
CONTAINER
What Is an OS?
Resources
• Allocation
• Protection
• Reclamation
• Virtualization
Finite resources
Competing demands
Examples:
• CPU
• Memory
• Disk
• Network
Limited budget,
Land,
Oil,
Gas,
Government
What Is an OS?
Resources
• Allocation
• Protection
• Reclamation
• Virtualization
You can’t hurt me
I can’t hurt you
Implies some degree of
safety & security
Law and order
Government
What Is an OS?
Resources
• Allocation
• Protection
• Reclamation
• Virtualization
The OS gives
The OS takes away
Voluntary at run time
Implied at termination
Involuntary
Cooperative
Income Tax
Government
What Is an OS?
Resources
• Allocation
• Protection
• Reclamation
• Virtualization
illusion of infinite
private resources
Memory versus disk
Timeshared CPU
More extreme cases
possible (& exist)
Social security
Government
Operating System
• OS (kernel) is really just a program that
runs with special privileges to implement
the features of allocation, protection,
reclamation and virtualization
and
the services that are structured on top
of it.
Booting Sequence
• BIOS starts
– checks how much RAM
– keyboard
– other basic devices
• BIOS determines boot Device
• The first sector in boot device is read into memory and
executed to determine active partition
• Secondary boot loader is loaded from that partition.
• This loaders loads the OS from the active partition and
starts it.
POST (Power On Self Test)
• BIOS: Binary Input/Output System
• e.g. UEFI: Unified Extensible Firmware Interface (UEFI) is a specification
for a software program that connects a computer’s firmware to its operating system (OS)
and functions as nowadays BIOS
OS
Types Concepts
Different
Structures
Different aspects of
looking at an
operating system
OS
Types Concepts
• Mainframe/supercomputer OS
•batch
•transaction processing
•timesharing
•e.g. OS/390
•Server OS
•Multiprocessor OS
•PC OS
•Embedded OS
•Sensor node OS
•RTOS
•Smart card OS
Different
Structures
OS
Types Concepts
• Mainframe OS/supercomputer
•batch
•transaction processing
•timesharing
•e.g. OS/390
•Server OS
•Multiprocessor OS
•PC OS
•Embedded OS
•Sensor node OS
•RTOS
•Smart card OS
•Processes
•Its address space
•Its resources
•Process table
•Address space
•File system
•I/O
•Protection
Different
Structures
OS
Types
Different
StructuresConcepts
• Mainframe OS/supercomputer
•batch
•transaction processing
•timesharing
•e.g. OS/390
•Server OS
•Multiprocessor OS
•PC OS
•Embedded OS
•Sensor node OS
•RTOS
•Smart card OS
•Processes
•Its address space
•Its resources
•Process table
•Address space
•File system
•I/O
•Protection
•Monolithic
•Layered systems
•Microkernels
•Client-server
•Virtual machines
OS
Types
Different
StructuresConcepts
• Mainframe OS
•batch
•transaction processing
•timesharing
•e.g. OS/390
•Server OS
•Multiprocessor OS
•PC OS
•Embedded OS
•Sensor node OS
•RTOS
•Smart card OS
•Processes
•Its address space
•Its resources
•Process table
•Address space
•File system
•I/O
•Protection
•Monolithic
•Layered systems
•Microkernels
•Client-server
•Virtual machines
Main objectives of an OS:
• Convenience
• Efficiency
• Ability to evolve
OS Services
• Program development
• Program execution
• Access I/O devices
• Controlled access to files
• System access
• Error detection and response
• Accounting
Hardware and Software
Infrastructure
Figure 2.1 Computer Hardware and Software Infrastructure
In a nutshell
• OS is really a manager:
– programs, applications, and processes are the
customers
– The hardware provide the resources
• OS works in different environments and
under different restrictions
(supercomputers, workstations, notebooks,
tablets, smartphones, real-time, …)
History of Operating Systems
• “We can chart our future clearly and wisely only when we know the
path which has led to the present.”
– Adlai E. Stevenson, Lawyer and Politician
• First generation 1945 – 1955
– vacuum tubes, plug boards (no OS)
• Second generation 1955 – 1965
– transistors, batch systems
• Third generation 1965 – 1980
– ICs and multiprogramming
• Fourth generation 1980 – present
– server computers
– personal computers
– Fifth generation 2005 – present
– hand-held devices, sensors
History of Operating Systems (1945-55)
• Programming and Control tied to the Computer
Source: wikipedia
History of Operating Systems
(1945-1955)
• Vacuum tubes, plug boards (no OS)
– ENIAC (UPenn 1944)
• 30 tons, 150m, 5000calcs/sec
– Zuse’s Z3 (1941)
• 2000 relays
• 22 bit words
• 5-10 Hz
• What’s a bug?
History of Operating Systems
(1955-65)
• Structure of a typical JCL job – 2nd generation
• Single user
• Programmer/User as the operator
• Secure, but inefficient use of expensive resources
• Low CPU utilization-slow mechanical I/O devices
• Emergence of the Mainframe
• Programmers isolated from machine
• Programming Languages emerge
• Fortran
• Cobol
History of Operating System
(1955-65)
Early batch system
– bring cards to 1401
– read cards to tape
– put tape on 7094 which does computing
– put tape on 1401 which prints output
History of Operating Systems
(1965-80)
• Multiprogramming systems
– Multiple jobs in memory – 3rd generation
– Allow overlap of CPU and I/O activity
– Polling/Interrupts, Timesharing
– Spooling
• Different types
– Epitomized by the IBM 360 machine
– MFT (IBM OS/MFT) Fixed Number of Tasks
– MVT (IBM OS/MVT) Variable Number of Tasks
• Birth of Modern Operating System Concepts
– Time Sharing: when and what to run → scheduling
– Resource Control: memory management, protection
The Operating System Jungle / Zoo
(1980-present)
• Mainframe operating systems
• Server operating systems
• Multiprocessor operating systems
• Personal computer operating systems
• Real-time operating systems
• Embedded operating systems
• Smart card operating systems
• Cellphone/tablet operating systems
• Sensor operating systems
Computer Architecture
( a closer look )
We must know and understand
what is actually managed by an OS
Processors
• Each CPU has a specific set of instructions
– ISA (Instruction Set Architecture) largely epitomized in the assembler
• RISC: Sparc, MIPS, PowerPC
• CISC: x86, zSeries
• All CPUs contain
– General registers inside to hold key variables and temporary results
– Special registers visible to the programmer
• Program counter contains the memory address of the next instruction to be
fetched
• Stack pointer points to the top of the current stack in memory
• PSW (Program Status Word) contains the condition code bits which are set by
comparison instructions, the CPU priority, the mode (user or kernel) and
various other control bits.
How Processors Work
• Execute instructions
– CPU cycles
• Fetch (from mem) → decode → execute
• Program counter (PC)
– When is PC changed?
• Pipeline: fetch n+2 while decode n+1 while execute n
(a) A three-stage pipeline. (b) A superscalar CPU.
Memory-Storage Hierarchy
• Other metrics:
– Bandwidth (e.g. MemBandwidth 30GB/s → 200GB/s, Disk ~70-200MB/s)
• What can an OS do to increase its “performance”
– Active management where to place data !!!
< - 4MB -1GB 2GB- 1TB -TB Latency Capacity 1ns 32+32 10ns 8KB – 2MB (L1 – L3) 100ns GBs - TBs 10msec 10s * TBs 10secs 500s * TBs CPU Caches • Principle: – Data/Instruction that were recently used are “likely” used again in short period – Caching is principle used in “many” subsystems ( I/O, filesystems, … ) [ hardware and software] • Cache hit: – no need to access memory • Cache miss: – data obtained from mem, possibly update cache • Issues – Operation MUST be correct – Cache management for Memory done in hardware – Data can be in read state in multiple caches but only in one cache when in write state CPU Cache CPU Cache Mem CPU Cache Example of real cache/memory access times • Modern systems have multiple CPUs with their own attached memory and multiple level of caches. • Non-uniform memory access. http://software.intel.com/en-us/forums/showthread.php?t=77966 CPU1 Core1 Core1 L1 L2 L1 Ram CPU2 Core1 Core1 L1 L2 L1 Ram CPU3 Core1 Core1 L1 L2 L1 Ram CPU4 Core1 Core1 L1 L2 L1 Ram CPU-0 Cache CPU-1 Cache Mem A=5 A[s]=5 C0 loads A ( A on C0 in shared mode [s]) Scenarios of Cache Coherency Scenario 1 Scenario 2 CPU-0 Cache CPU-1 Cache Mem A=5 A[x]=9 C0 stores A=9 ( A on C0 is now in exclusive mode [x] ) CPU-0 Cache CPU-1 Cache Mem A=5 A[s]=5 CPU-0 Cache CPU-1 Cache Mem A=5 A[s]=5A[s]=5 C0 loads A ( A on C0 in shared mode [s]) C1 now loads A (cache line is copied) ( A on C0 and C1 in shared mode [s]) C1 stores A=12 ( A on C1 in exclusive mode ) cache line is just moved CPU-0 Cache CPU-1 Cache Mem A=5 A[s]=5 C0 loads A ( A on C0 in shared mode [s]) Scenarios of Cache Coherency Scenario 3 CPU-0 Cache CPU-1 Cache Mem A=5 A[x]=9 C0 stores A=9 ( A on C0 is now in exclusive mode [x] ) CPU-0 Cache CPU-1 Cache Mem A=5 A[x]=12 (1) (2) C1 loads A Forces C0 to write back A to mem (or lowest level of shared cache) and put A into shared mode for C0/C1 Scenarios of Cache Coherency Scenario 4 CPU-0 Cache CPU-1 Cache Mem A=5 A[x]=2 CPU-0 Cache CPU-1 Cache Mem A=2 A[s]=2 A[s]=2 • A can be in [s] across several CPUs • A can be at most in ONE CPU in [x] and nowhere else in [s] Imperative at all times Now C0 sets A=9 All cache lines on other cpus must be invalidated and A on C0 in [x] Scenarios of Cache Coherency Scenario 5 Both thread C0, C1, C2 load A ( A on C0, C1, C2 in shared mode )CPU-0 Cache CPU-1 Cache Mem A=5 A[s]=5A[s]=5 CPU-2 Cache A[s]=5 CPU-0 Cache CPU-1 Cache Mem A=5 A[x]=9 CPU-2 Cache Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin, "Operating System Concepts, Eighth Edition ", Chapter 12 Example of Device (resource and operation) • Disk: – Multiple-subdevices – Translations • Block -> sector
– Head Movement
– Seek Time
– Data Placement
– Power Management
OS Major Components
• Process and thread management
• Resource management
– CPU
– Memory
– Device (I/O)
• File system
• Bootstrapping
Process: a running program
• A process includes
– Address space
– Process table entries (state, registers)
• Open files, thread(s) state, resources held
• A process tree
– A created two child processes, B and C
– B created three child processes, D, E, and F
Address Space
• Defines where sections of data and
code are located in 32 or 64
address space
• Defines protection of such
sections
– ReadOnly, ReadWrite, Execute
• Confined “private” addressing
concept
– ➔ requires form of address
virtualization
#include
#include
#define NUMS (4)
int a;
int b = 2;
int x;
int y = 3;
int main(int argc, char* argv[])
{
int *values;
int i;
values = (int*) malloc(NUMS*sizeof(int));
for (i=0 ; i
– Trap
– Interrupt (also Kernel2Kernel)
– Execption (also Kernel2Kernel)
KernelMode -> UserMode
– rfi (return from interrupt)
(also kernel to kernel)
Interrupt / Exception / Traps
• Understand similarity and differences between these 3 “events”
• Interrupts:
– asynchronous :Triggered by an event from a “device” (device needs attention)
• Exceptions:
– Synchronous: triggered by a “fault condition” of an instruction condition
• Traps (instruction, aka sc [ system call ] ) == special kind of exception
– Synchronous: triggered by “trap instruction” for syscall
• They all end up in the so called “interrupt handler”:
assembler code aka __entry in the kernel
from there the assembler identifies whether an interrupt, execption,
or trap and jumps to their respective handlers.
Protected Hardware register is initialized in OS bootstrap with the
address of __entry so the hardware knows where to jump to when an
Interrupt or Trap or Exception is raised.
Attention all Personnel
• __entry is the ONLY means to enter
into the operating system kernel
either by
– hw-interrupt
– exception
– trap
A peek into Unix/Linux
Application
Portable OS Layer
Libraries
Machine-dependent layer
User space/level
Kernel space/level
• User/kernel modes are
supported by hardware
•Some systems do not have
clear user-kernel boundary
Unix: Application
Application
(E.g., emacs)
Portable OS Layer
Libraries
Machine-dependent layer
Written by programmer
Compiled by programmer
Uses function calls
Unix: Libraries
Application
Portable OS Layer
Libraries (e.g., stdio.h)
Machine-dependent layer
Provided pre-compiled
Defined in headers
Input to linker (compiler)
Invoked like functions
May be “resolved” when
program is loaded
Typical Unix OS Structure
Application
Portable OS Layer
Libraries
Machine-dependent layer
system calls (read, open..)
All “high-level” code
Typical Unix OS Structure
Application
Portable OS Layer
Libraries
Machine-dependent layer
Bootstrap
System initialization
Interrupt and exception
I/O device driver
Memory management
Kernel/user mode
switching
Processor management
Service Requests
from user to kernel (OS)
• Basic means to request services from the
operating system kernel is to make
system calls
(which end up in a “trap / sc” event)
• It’s a well architected and “secure” API
between kernel and userspace
Some System Calls For Process Management
Signal
Call Description
kill(pid, signal) Deliver signal to the process pid
signal( signal, function ) Define which function to call for signal
System Calls (POSIX)
• System calls for process management
• Example of fork()used in simplified shell program
#define TRUE 1
while(TRUE) {
type_prompt();
read_command(command, parameters);
if (fork()!=0) {
/* some code*/
waitpid(-1,&status, 0);}
else {
/* some code*/
execve(command, parameters,0);
}
}
Portable Operating System Interface for Unix (IEEE standard 90’s)
System Calls (POSIX)
• System calls for file/directory
management
– fd = open(file,how,….)
– n = write(fd,buffer,nbytes)
– e = rmdir(name)
• Miscellaneous
– e = kill(pid,signal)
– e = chmod(name,mode)
List of important syscalls
System Call == OS kernel service request
• Invoked via non-priviliged instruction ( trap / sc)
– Treated often like an interrupt, but its “somewhat” different
• Synchronous transfer control from user to kernel
• Side-effect of executing a trap in userspace is that
an “exception” is raised and program execution
continues at a prescribed instruction in the kernel
see __entry -> syscall_handler
How are syscalls implemented
• First one has to understand how arguments in any regular function call are passed.
• For this a calling code convention is defined.
• Typically arguments are passed through registers
(sometimes as offsets on the stack)
• Those registers can be modified by the function called, any other registers most be
saved and restored by the callee function
– Volatile register (args,stackptr) and non-volative registers (callee must save and restore)
• Generally referred to as ABI: Application Binary Interface
• Syscalls are simply an extension on this. All compilers need to agree on this or code
will no cooperate/work.
Excellent writeup: https://lwn.net/Articles/604287/
Trap/SC instruction
syscall implementation (user side)
/usr/include/asm-generic/unistd.h
unistd.h:extern ssize_t pread64 (int __fd, void *__buf, size_t __nbytes)
ABI: Application Binary Interface
Definition agreed upon by libc and kernel
➔ ABI is known. Compiler assembles args
#define __SYSCALL(number) syscall(number…)
syscall is implemented as assembler largely
taking the arguments already in the right
registers and TRAP-ing into the kernel.
• Kernel defines a table (using the compiler help )
int syscall_table [ __NR_SYSCALL_MAX ] = {
:
[ __NR_READ] = sys_read,
[ __NR_WRITE] = sys_write,
:
}
• On system trap, architecture automatically and immediately
enters kernel mode and runs a small piece of assembler code that is
stored at a machine register address set by the OS at boot time.
• Said trap assembler code (aka interrupt handler) does the following:
– Checks the syscall number in well known register ( see ABI ) to be in range
– Assembler equivalent:
• Change stack to kernel ( more on this in a bit )
• All arguments are already in right place thanks to the ABI and the compiler’s help
• “Call/jmp” to syscall_table[ registers.syscall_number ]; // see ABI definition
• After return from ^^^^, switch back from kernel stack to user stack and RFI
(return from kernel mode).
syscall implementation (kernel side)
The compiler does the magic
and associates the syscall
number with the kernel
internal function
Putting it all together (based on ARM/EABI)
r0 = fd
r1 = buf
r2 = 64
r7 = __NR_READ
Your app.c
libc.so
Regular function call
assembler based on compiler
Function expects args in r0,r1,r2,…
Regular function call
All argument registers must stay intact:
r0,r1,r2,…
User
kernel
System Call with args passed
over the stack (different ABI)
Example:
read (fd, buffer,nbytes)
In this example the ABI
dictates that function arguments
are pushed on the stack not through
registers
(older architectures)
System Calls (Windows Win32 API)
• Process Management
– CreateProcess- new process (combined work of fork and
execve in UNIX)
• In Windows – no process hierarchy, event concept implemented
– WaitForSingleObject – wait for an event (can wait for
process to exit)
• File Management
– CreateFile, CloseHandle, CreateDirectory, …
– Windows does not have signals, links to files, …, but has a
large number of system calls for managing GUI
Other implicit/explicit
OS Services Examples
• Services that can be provided at user level
(because they only read unprotected data)
– Read time of the day
• Services that need to be provided at kernel level
– System calls: file open, close, read and write
– Control the CPU so that users won’t stuck by running
while ( 1 ) ;
– Protection:
• Keep user programs from crashing OS
• Keep user programs from crashing each other
Is Any OS Complete?
(Criteria to Evaluate OS)
Portability
Security
Fairness
Robustness
Efficiency
Interfaces
When you look at these criteria you should see that
they can’t all be satisfied at the same time.
Recap: What is an OS ?
• Code that:
– Sits between programs & hardware
– Sits between different programs
– Sits betweens different users
• Job of OS:
– Manage hardware resources
• Allocation, protection, reclamation, virtualization
– Provide services to app. How ? → system call
• Abstraction, simplification, standardization
Application
OS
Hardware
Monolithic systems – basic structure
1. A main program that invokes the
requested service procedure.
2. A set of service procedures that carry
out the system calls.
3. A set of utility procedures that help
the service procedures.
Operating Systems Structure
(Chapter 1)
Monolithic Systems
By far the most common OS organization
A simple structuring model for a
monolithic system.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Layered Systems
• Layer-n services are comprised of services provided by Layer-(n-1)..
• Structure of the THE operating system (Dijkstra 1968)
•
• THE used this approach as a design AID
• Multics Operating System relied on Hardware Protection to enforce
layering
• Microkernels move the layering boundaries between kernel and
userspace
• Move only most rudimentary services to kernel
• Move other services to Userspace
• Higher Overhead, but more flexibility, higher robustness
– Minix (Tanenbaum is only 3200 lines of C and 800 lines assembler)
– L4, K42,
Microkernels
• Assumes generic network model (network, bus)
• Communication via message passing
Client-Server Model
• VM/370: Timesharing system should be comprised of:
– Multiprogramming
– extended machine with more interface than bare HW
– Completely separate these two functions
• Provides ability to “self-virtualize”
• Beginning of “modern day” virtualization technology
Virtual Machines (1)
• A type 1 hypervisor
(like virtual machine monitor)
– Priviliged instructions are trapped and “emulated”
• A type 2 hypervisor (runs on top of a host OS)
– Unmodified ( trapped )
– Modified ( paravirtualization )
Virtual Machines (2)
Other areas of virtual machines
usage
• Java virtual machines
• Dynamic scripting languages (e.g. Python)
• Typically define a instruction set that is
“interpreted” by the associate virtual
machine
– JVM, PVM
– Modern system then JIT (Just In Time)
compile the VM instructions into native code.
History of the UNIX Operating System
(source: wikipedia)
Bell Labs: Thomson, Richie, Kernigan et.al
DLL
DLL
Loader
Source Code to Execution
Assembly
Assembler Object File
Object File
Object File
Assembly
Assembly
Executable
Linker
Library
Library
Library
Assembly
Assembly
C source
Compiler
DLL
DLL
DLL
Loader
Source Code to Execution
Object File
Object File
Object File
Executable
Linker
Library
Library
Library
DLL
What happens to your program
after it is compiled but before
it can be executed?
The OS Expectation
• The OS expects executable files to have a
specific format
– Header info
• Code locations and size
• Data locations and size
– Code & data
– Symbol Table
• List of names of things defined in your program and
where they are defined
• List of names of things defined elsewhere that are
used by your program, and where they are used.
Example of Things
#include
extern int errno;
int main () {
printf (“hello,
world\n”)
}
• Symbol defined in
your program and
used elsewhere
• main
• Symbol defined
elsewhere and used
by your program
• printf
• errno
Two Steps Operation:
Parts of OS
Linking
• Stitches independently
created object files into
a single executable file
(i.e., a.out)
• Resolves cross-file
references to labels
• Listing symbols needing
to be resolved by loader
Loading
• copying a program image
from hard disk to the main
memory in order to put
the program in a ready-to-
run state
• Maps addresses within file
to memory addresses
• Resolves names of dynamic
library items
• schedule program as a new
process
Libraries (I)
• Programmers are expensive.
• Applications are more sophisticated.
– Pop-down menus, streaming video, etc
• Application programmers rely more on
library code to make high quality apps
while reducing development time.
– This means that most of the executable is
library code
Libraries (II)
• A collection of subprograms
• Libraries are distinguished from
executables in that they are not
independent programs
• Libraries are “helper” code that provides
services to some other programs
• Main advantages: reusability and
modularity
Large Programming Projects
The process of compiling C and header
files to make an executable.
#include
#include
#define NUMS (4)
int a;
int b = 2;
int x;
int y = 3;
extern int myfunc(int);
int main(int argc, char* argv[])
{
int *values;
int i;
values = (int*)
malloc(NUMS*sizeof(int));
for (i=0 ; i