Transcript PPT

Introduction
Operating Systems
CS 550
Spring 2017
Kenneth Chiu
(adapted from Silberschatz, Tanenbaum, various)
What’s This Course About?
• Software systems design
•
•
•
•
•
•
•
•
Caching
Indirection
Interrupts/polling
When is it good to be lazy (copy-on-write)
When is it good to be eager (pre-fetching)
Modularity
Abstraction
Separation of concerns
• We study OS as an exemplar.
• Basic ideas are ubiquitous.
• Details will fade, hopefully basic concepts and techniques won’t.
• Studied under three facets:
• Virtualization
• Concurrency (which is actually also a kind of virtualization)
• Persistence
What Is an Operating
System?
Hardware
• One or more CPUs, device controllers connect through bus providing access
to shared memory.
• What is a bus?
• What’s not a bus?
• Concurrent execution of CPUs and devices competing for memory cycles
Processors
• What does a CPU do?
• Operates in “cycles”, at least conceptually.
• Fetch an instruction, decode, execute
• Can an Intel CPU execute a program written for a Sun
SPARC processor? Can an AMD CPU execute a program
written for an Intel CPU?
• Different CPUs may have different instruction set architectures
(ISA).
• What are key things that a CPU has? Why does it have
them? What would happen if you got rid of them?
•
•
•
•
Registers
Program counter
Stack pointer
Program status word (PSW)
Fundamental Questions
• What is software?
• What is hardware?
• What is firmware?
• What about FPGAs?
• What about ASICs?
What is an Operating System?
• No universally accepted definition.
• “Everything a vendor ships when you order an
operating system” is good approximation.
• But varies wildly.
• One way you can define OS is to use the kernelmode/user-mode separation as a clear, bright line.
• “The one program running at all times on the computer” is
the kernel. Everything else is either a system program
(ships with the operating system) or an application
program.
• Another loose, approximate definition: A program
that acts as an intermediary between a user of a
computer and the computer hardware.
• The OS is a resource allocator.
• Manages all resources.
• Decides between conflicting requests for efficient and fair
resource use.
• The OS is a control program.
• Controls execution of programs to prevent errors and improper
use of the computer.
• What is not part of the OS?
•
•
•
•
•
•
•
Firmware?
Word processor?
Window manager?
Windows Control Panel?
Device driver?
Browser?
Anti-virus?
Computer System Structure
• Computer systems have (at least) four interacting
components:
• Hardware: Provides basic computing resources
• CPU, memory, I/O devices
• Operating system: Controls and coordinates use of
hardware among various applications and users.
• Application programs:
• Word processors, compilers, web browsers, database systems,
video games
• Users
• People, machines, other computers
OS as an Abstraction Layer
• Let’s say you want to write a word processor.
Should you (as the application programmer) need
to understand the details of the hard drive
hardware?
• The OS abstracts hardware.
• Hardware is messy and complicated
• One of the purposes of an OS is to abstract the
hardware; to turn ugly into pretty abstractions.
• [Show virtualization examples.]
Design Goals
Goals
• What are some OS goals?
• Execute user programs and make solving user problems
easier.
• Make the computer system convenient to use.
• Use the computer hardware in an efficient manner.
• Create abstractions
• Performance, low overhead
• Protection
• Isolation
• Reliability
• Energy efficiency
Trade-Offs and Compromises
• Users want convenience, ease of use.
• Don’t care about resource utilization.
• What is resource utilization? Who cares about it?
• On a shared computer, such as the machines in the
remote.cs.binghamton.edu cluster, must keep all users happy.
• What if the computer doesn’t allow multiple users to login? Does this problem
just go away?
• What other shared resources are there commonly?
• Virtual machines
• Web servers
• Even on dedicated resources, frequently use shared resources from
servers.
• Mobile devices are resource poor, optimized for usability and battery
life.
• Some computers have little or no user interface, such as embedded
computers in devices and automobiles.
Some History
First Digital Computer
• Created by Charles Babbage (1792-1871)
• Gears, etc.
• Never worked. Mechanical precision of that age was not
good enough.
• First programmer: Ada Lovelace
Computers
• It’s 1920.
• You are a mechanical engineer in the US.
• You tell your boss in the morning, “I need a computer this
afternoon.”
• What would you expect to see in your office later that day?
• The computer room (1940’s NACA, precursor to NASA)
• Often parallel (pipelined or otherwise)
First Generation (1945-1955):
Vacuum Tubes
• What’s a vacuum tube
• No OS
• No assembly language
• Programmed by wires
• Two software engineers, hard at work:
Second Generation (1955-1965):
Transistors and Batch Systems
• Discrete transistors
• Mainframes: large and very expensive
• Programming:
• Write on paper
• Punch on cards
• Take to operator
• Put into card reader
• Program runs
• Output comes out
• Operator takes your output and puts it in a bin
• One OS of the time was called Fortran Monitor System
(FMS).
• Typical FMS card deck:
• What if you dropped your deck?
• What if there is a bug?
• What if you need to add a statement?
• Lots of time wasted while the operator walks around.
• Computer costs millions
• Batching:
Third Generation (1965-1980): ICs
and Multiprogramming
• What’s an IC?
• IBM 360
• Idea of a family of computers, all same OS
• Multiprogramming:
• In the past, when doing I/O, CPU was idle.
• Okay when just lots of computation
• Lot more data processing jobs now, with lots of I/O
• Spooling (Simultaneous Peripheral Operation On
Line):
• Card reader would put jobs on disk
• OS load new job from disk when done
• No longer really batching
• Though still often called a batch system
• Where do you see this today?
• Print spooling
• Programming was very inefficient
• Timesharing (interactive computing) became more
common.
• Use terminals, 80x24 was standard
• MULTICS, very advanced, precursor to UNIX
• DEC PDP-1, 1961
• 4K of 18-bit words
• $940,000
• First “minicomputer”.
concepts and terms
Process
• Do we need processes? Can a computer run with
no processes?
• Processes provide a way to group resources.
• A container.
• A program in execution.
• What resources?
• Memory, registers, open files, etc.
Address Space
2 GB
• A process has a range of possible
memory addresses.
• 0-2GB, 4G, etc.
• AS organizes the memory
belonging to a process.
• What happens when you write or
read from an address?
• If it is not mapped, a page fault, then
OS finds some disk space for it.
• Page/swap can be huge, can be many
GB.
0
Memory Regions
• Regions
Stack
Invalid
Heap
Data
Code
(Text)
• Stack is used for function calls.
• Heap is used for dynamically needed
memory
• Data is for memory that is “static”, like
global variables, etc.
• Text (code) is program machine code.
• How about threads?
• Is it all writable? Executable? Readable?
• What happens when you call new or
malloc(), in Java or C++?
• Memory allocation: first check to see
if any valid, but unused.
• If none available, then request more
valid memory regions from OS, and use
those.
Invalid
Used
Available
• Key point: There are two stages of
memory allocation.
• First, the memory has to mapped, which
is handled by the OS and hardware
together.
• Then the memory must be reserved
from the user-mode memory manager
(malloc())
• malloc() is a manager.
• What happens if you try to use the
available memory without going
through malloc()?
• Why two stages? Could you make
malloc a system call?
• Efficiency and flexibility.
Stack
• How do you get memory from the
OS?
• In older versions of UNIX, it is a limit
known as the “break”. Anything below
this is valid.
• Newer versions (and likely Windows)
allow regions to be requested via
mmap().
mmap’ed
mmap’ed
break
• When you free or delete something
in Java or C++, will the OS report less
memory usage?
• Not usually, because the user-level
memory manager keeps control of it.
• [Show malloc-return-os.]
• Important set of code that is missing. Where is it?
Files
• What is a file?
• A named, linear sequence of bytes.
• Hide physical details of storage, such as drives, tracks,
etc.
• Organized into directories (folders).
• Files and directories are specified using a path name.
• Can be absolute (begin with a /) or relative (does not begin with /).
• Note that in UNIX/Linux it is the link that is named, not the directory or
file itself.
• This means that a directory or file may have multiple path names.
• Every process has a current working directory.
• Used for relative path names.
• Before a file can be read or written, it must be opened first.
• This returns a file handle of some type. In UNIX/Linux, it’s called a file
descriptor (just an int).
• Could we design an OS that didn’t require opening first? What would
the implications be?
• UNIX/Linux integrate all files on a computer, even from
multiple devices, into a single, unified file system tree.
• What does Windows do?
• There is a single root file system.
• Everything else is a subtree of the root.
• Hard links vs soft links
• Hard link two files.
• Remove one.
• Recreate.
• Accessing anything requires naming and a way to organize the names.
• Devices require some naming scheme.
• Could come up with one, and then some set of system calls to access using
those names.
• But simpler is always better, so in UNIX, the idea is to leverage an API and
naming that already exists, and that is the file system naming and API.
• These are device files (also known as special files), files that refer to
devices.
• The linear sequence of bytes ideas is fit to the device as well as possible.
• Some devices fit into this abstraction better than others.
• Of course, since they are not really files, some degree of compromise is
necessary. Some system calls don’t really make sense for device files. And a
system call (ioctl()) was added which doesn’t make sense for regular
files.
• Sometimes they are not real devices, but what are called pseudo-devices.
• [Show /dev/pts, writing and reading.]
• There are also files which are not files at all, but “virtual files”.
• Examples?
• [Show /proc and /proc/self in two windows.]
• Another kind of virtual file is a pipe.
– [Show code/pipe later.]
• How does another process access the pipe?
– Can’t, pipes are an example of an anonymous entity.
• You can also have named pipes.
– [Interactive.]
Kernel (Supervisor) mode
• CPU can run in one of two modes:
• Kernel (supervisor)
• User
• What’s different about these?
• How to switch?
• Why does this help anything?
Interrupts
Let’s say that you want to go sledding with your
friend, but he hasn’t yet finished his OS assignment.
• How to determine when your friend has finished
his task?
• You call him every N minutes to check.
• You ask him to call you when he is done.
• First is called polling, second is called an interrupt.
• Asking him to call you is registering an interrupt.
• Interrupts are used to signal an event.
• Interrupt transfers control to the interrupt service
routine generally, through the interrupt vector, which
contains the addresses of all the service routines.
• Interrupt architecture must save the address of the
interrupted instruction.
• Incoming interrupts are disabled while another
interrupt is being processed to prevent a lost
interrupt.
• A trap (or exception) is a software-generated
interrupt caused either by an error or a user request.
• An operating system is interrupt driven.
Interrupt Handling
• The operating system preserves the state of the
CPU by storing registers and the program counter
• Determines which type of interrupt has occurred:
• polling
• vectored interrupt system
• Separate segments of code determine what action
should be taken for each type of interrupt
Interrupt Timeline
I/O
• Through device drivers, accessed by device files.
• Systems calls (such as read) on a device file are
passed to the device driver.
• A special system call (ioctl()) is used to provide
device-specific control.
• [Show man 2 ioctl_list.]
System Calls
• Can a user process that wants to execute kernel
code just call it?
• A system call is the main way that interact with the
kernel.
• Main way of providing abstraction.
• Why can’t the OS just provide functionality via
normal function calls?
• Functionally, it’s like a function call, except that
because you are calling into the kernel, the CPU
needs to switch into kernel mode.
count = read(fd, buffer, nbytes);
POSIX System Calls for Process
Management
POSIX System Calls for File Access
POSIX System Calls for File System
Management
Miscellaneous System Calls
Win32
• [Show code/pipe]
Shell
• OS is the code that carries out the system calls.
• A user process can invoke syscalls.
• How does a human user interact with the OS?
• It's just a program, can be graphical or not.
A Simple Command-Line Shell
• Simple command-line (text) shell:
• while (true) {
// Loop forever.
type_prompt();
// Display prompt.
read_command(comm, params);
// Now create process to execute the command.
if (fork() != 0) {
// This branch is the parent.
waitpid(-1, &status, 0);
// Wait for command to finish.
} else {
// This branch is the child.
// Overlay the child process with new executable.
execve(comm, params, 0);
// When is this code executed?
}
startup
What Happens When You Boot
the Computer
Where does the term come from?
• There is a phrase: “...pull yourself up by your bootstraps”.
Pull Hard!
What happens when you power-on your computer?
• For a computer to do something, it must have machine
instructions.
• For example, to start Windows Vista, it must run the NTFS file
system code.
But how does it run the NTFS file system if it has no instructions in
the first place?
• Typically, there must be some amount of hard-coded
ROM.
Does this mean that NTFS must be in ROM?
• To avoid putting Windows Vista in ROM, things are done
incrementally, through a number of stages.
• Only enough is put in ROM to allow it to pull in code from
modifiable places, such as disk.
• When power is applied, the system is hard-wired to set
the PC to a specific address, and load the first instruction
from there.
Does this address refer to ROM or RAM?
• The BIOS (basic input/output system) is there.
• BIOS does some basic things, mainly hardware related.
• Then it loads a small chunk of memory from the boot
device, and starts executing it.
• Typically, if from hard drive, this will be in the MBR.
• This then goes and loads something from the boot
partition.
• Then typically there is another stage loader.
• So typically there will be at least 4 stages.
Which stages are easy to modify?
operating system
structure
Monolithic
• Basically everything linked into one giant
executable.
• Anything can call anything.
• The most common.
• Can still have modules, but they are just like
modules in a regular C program.
• How is modularity in a C program enforced?
• Generally roughly layered:
• Main procedure to unpack system calls.
• Dispatched to service procedures, each system call goes to one,
but may not be an exact one-to-one mapping.
• Various utility procedures, interrupt service routines, etc.
Layered
• Can be layered in a more “official” way.
• What does “layering” mean?
• Something in a lower layer cannot call something in a
higher layer.
• What about callbacks?
• The THE system.
•
•
•
•
1968 batch system.
32K of 27 bit words.
512K word magnetic drum for “paging”.
Not enforced by hardware.
• MULTICS had rings, enforced by hardware.
Microkernels
• Why does the kernel run in supervisor mode?
• What does the file system do that needs it?
• Could some things that a kernel does be moved out of
supervisor mode?
• For a given functionality that must be implemented, is it
better to do it in kernel mode or user mode?
• Idea:
• Move anything that doesn’t really require supervisor mode out of
the kernel and into a user-mode root process.
• Advantages?
• Easier to debug and possibly more robust.
• Disadvantages?
• Possibly slower.
• MINIX 3
• How do device drivers access I/O ports?
Client-Server Model
• Usually thought of in relation to distributed
systems, but can be used locally also.
VMs
• In the late 60s, IBM noticed that many users
wanted to run different operating systems.
• In particular, one for timesharing and also one for
batch jobs.
• Solution was to write a timesharing system (CMS)
that ran single user on a single machine, then use
VMs to support multiple users.
• This was VM/370, released in early 1970s.
• Non-mainframe VMs.
Java Virtual Machine
• JVM can also be thought of as a virtual machine.
• Why?
other system
architectures
Symmetric Multiprocessing Architecture
• What is Moore’s Law?
• Are CPUs getting faster?
Multicore
• Some CPUs have completely separate CPUs inside of
them. This is known as multicore.
Hybrid Computing
CPU
GPU
Memory
Memory
• The GPU is fully programmable, and can be used for general
computation.
• GPU memory can only be accessed by GPU.
Clustered Systems
• Like multiprocessor systems, but multiple systems
working together
• Usually sharing storage via a storage-area network
(SAN)
• Provides a high-availability service which survives
failures
• Asymmetric clustering has one machine in hot-standby mode
• Symmetric clustering has multiple nodes running applications,
monitoring each other
• Some clusters are for high-performance computing
(HPC)
• Applications must be written to use parallelization
Clustered Systems
• How do clustered systems compare to SMP and
multicore systems?
•
•
•
•
Ease of programming?
Cost?
Performance?
Application type?
Unused
Direct Memory Access Structure
• Used for high-speed I/O devices able to transmit
information at close to memory speeds
• Device controller transfers blocks of data from
buffer storage directly to main memory without
CPU intervention
• Only one interrupt is generated per block, rather
than the one interrupt per byte
Storage Structure
• Main memory – only large storage medium that the CPU can access
directly
• Random access
• Typically volatile
• Secondary storage – extension of main memory that provides large
nonvolatile storage capacity
• Magnetic disks – rigid metal or glass platters covered with magnetic
recording material
• Disk surface is logically divided into tracks, which are subdivided into sectors
• The disk controller determines the logical interaction between the device and
the computer
• Solid State Drives – Flash-based devices that are more expensive that
disks, but generally faster.
• Optical drives
• Magnetic tape
Storage Hierarchy
• Storage systems organized in hierarchy
• Speed
• Cost
• Volatility
Disks
computer system
architecture
Let’s say you download a computer game. It will take
30 minutes. What do you do while it’s downloading?
Let’s say you click on a link in your browser and it takes
10 seconds to load. What do you do while it’s loading?
What happens when a CPU needs to fetch something
from RAM?
Why not switch to another thread or process while waiting?
• Simultaneous multithreading (SMT)/hyperthreading:
• Some CPUs have multiple hardware contexts. They can
switch instantly between threads.
Computer-System Architecture
• Most systems use a single general-purpose processor
(PDAs through mainframes)
• Most systems have special-purpose processors as well, in
devices such as the disk drive.
• Multiprocessors systems growing in use and
importance
• Also known as parallel systems, tightly-coupled systems
• Advantages include:
1. Increased throughput
2. Economy of scale
3. Increased reliability – graceful degradation or fault tolerance
• Two types:
1. Asymmetric Multiprocessing
2. Symmetric Multiprocessing
Multicore
History Repeats
• Things happen in cycles as hardware advances.
• Ideas are introduced into expensive, “high-end”
hardware.
• Often not powerful at all by today’s standards, but it was
expensive.
• So had to be used well.
• As the hardware moves to a more personal level,
those tend to be lost, then gradually reintroduced.
• Virtual memory, multiprogramming.
• VMs.
(Hard) Linking
• Linking /usr/jim/memo to /usr/ast/note.
• [Interactive.]