Transcript Week-02

CS4023 – Operating Systems
(week 2)
Dr. Atif Azad
[email protected]
1
Acknowledgement
• Significant material in this set of lectures has
been borrowed from:
– http://www.cs.berkeley.edu/~kubitron/courses/cs
162/. Copyright © 2010 UCB
– http://www.os-book.com . © 2014 Silberschatz et
al.
– Dr Patrick Healy at CSIS Department, University of
Limerick.
2
Review
• Age of scaling is over
– Parallel computing is here!
• OS are complex systems: oversee interactions
of complicated systems
– CPU and I/O devices work in parallel
– Use interrupts to coordinate transfer of
information to and from Memory
– What more about Memory?
• Reminder: C language
3
Secondary Storage
• RAM is fast but limited and volatile.
• Need secondary storage.
– Different types.
– E.g. even hard drives are of various types
– Solid State Devices (SSD) are faster than typical
magnetic hard disk drive (HDD).
• Actually a whole storage hierarchy exists in a
computer System.
4
Storage-Device Hierarchy: Speed,
Cost and Volatility
Speed and Cost
Volatile
The point of Hierarchy?
Section 1.8/1.8.2
• Caching – copying information into faster
storage system; main memory can be
viewed as a cache for secondary storage
– Faster storage checked first. if info there use it,
else copy data into cache, because
– Information in use is likely to be used again
– Cache smaller than storage being cached. Thus
cache management is an important design
problem.
• Cache size?
• When to swap data in and out of cache?
Performance of Various Levels of
Storage
7
Issues with Cache?
X is a cached copy of Y.
• Cache Incoherence
1. CPU updates X in the cache  Y is stale.
2. Device (through DMA) updates Y  X is stale.
• Solution
– External (DMA) ‘write’ forces a cache read.
– External (DMA) ‘read’ forces a cache flush (write back)
– Either hardware or OS looks after cache coherence.
Details: http://en.wikipedia.org/wiki/Direct_memory_access#Cache_coherency
8
Multiprogramming in Operating
Systems – a background
9
Life without an OS
• Source CodeCompilerObject
CodeHardware
• How do you get object code onto the hardware?
• How do you print out the answer?
• Once upon a time, had to Toggle in program in
binary and read out answer from LED’s!
https://youtu.be/i8znuGj_yUY?t=304
Altair 8800
10
What if only one Application Runs:
Simple OS
• Happened in early PCs
• Still happens in special purpose processors
such as those in elevators, cars etc.
• The OS was simple library of services:
– standard device drivers
– Interrupt handlers
– Math libraries
– No protection from processes interfering with
each other or with OS e.g. MS DOS
11
Modern OS: Multiple Apps
Section 1.4
• Multi-programming: many processes
executing (not necessarily in parallel):
– Many loaded in RAM together
– While one has to wait, another starts.
– CPU remains busy.
– But response time may become a problem.
• Time sharing: extends multi-programming
– CPU switches from one process to another fast
– It appears all processes are running in parallel.
– But they are not: called concurrent programming.
12
Memory Structure with Multiprogramming
• Which job runs first: scheduling
• More jobs than RAM size?
– Use disk space to swap in and out of
RAM
– This disk space is Virtual Memory.
– Thus logical memory > physical
memory
• Jobs writing/reading into space of
other jobs or OS? Need
protection.
13
Protecting OS and other Processes
from each other
• Problem: run multiple applications such that
– User programs do not crash OS
– User programs do not crash each other
– Different parts of OS do not crash other parts.
• Solution: implement the following policy:
– Programs are not allowed to read/write memory of
other programs.
• Mechanisms:
– Address Translation
– Dual Mode Operation
14
Address Translation
• Address Space
– A group of memory addresses usable by something
– Each program (process) and OS kernel has
potentially different address spaces.
• Address Translation:
– Translate from Virtual Addresses (emitted by CPU)
into Physical Addresses (of memory)
– Mapping often performed in Hardware by Memory
Management Unit (MMU)
CPU
Virtual
Addresses
MMU
Physical
Addresses
15
Example of Address Translation
Code
Data
Heap
Stack
Data 2
Code
Data
Heap
Stack
Stack 1
Heap 1
Code 1
Stack 2
Prog 1
Virtual
Address
Space 1
Prog 2
Virtual
Address
Space 2
Data 1
Heap 2
Code 2
OS code
Translation Map 1
OS data
Translation Map 2
OS heap &
Stacks
Physical Address Space
Q: Still vulnerable?
•
Dual
Mode
Operation
Hardware provides at least two modes:
Section
1.5
– “Kernel” mode (or “supervisor” or “protected” or “previliged”)
– “User” mode: Normal programs executed
• Some instructions/ops prohibited in user mode:
– Example: cannot modify MMU functionality in user mode
• Attempt to modify  Exception generated
• System boots into kernel mode; then, goes into user mode.
• Transitions from user mode to kernel mode:
– System Calls, software Interrupts (traps or exceptions)
Dual Mode Operation (Contd.)
• Protection issues if no dual mode in hardware
– E.g. Intel 8088 processor and MS DOS.
– Buggy/malicious program can wipe out the OS
• Modern OS: Windows 7, Unix, Linux etc use dual
mode in modern intel CPUs.
• System call: conducts privileged operations on
behalf of user processes.
– System call generates a software interrupt (trap).
– Trap is serviced by an interrupt service routine in the
interrupt vector.
– Service routine executes in kernel mode.
18
Section 1.3
Computer System architecture
• All these facilities in a single processor system.
– difference between concurrency and parallel?
– Concurrent is not necessarily parallel
– May contain special purpose processors: e.g.
device controllers.
– 1 general purpose processor  single processor
system.
19
Multi-Processor Systems
• Multiprocessors systems have multiple general purpose
processors.
• Multiprocessors systems growing in use and importance
– Also known as parallel systems, tightly-coupled systems
– Advantages include:
• Increased throughput
• Economy of scale
• Increased reliability – graceful degradation or fault tolerance
– Two types:
• Asymmetric Multiprocessing – each processor is assigned a specific
task.
• Symmetric Multiprocessing (SMP) – each processor performs all
tasks
Symmetric Multiprocessing Architecture
• Independent cache and registers.
• Shared Memory. (minimise variance of mem.)
• Concern: utilization of all processors equally.
– Ineffciencies if some work while others are idle.
A Dual-Core Design
• Multicore machines have multiple cores on the
same chip.
• The design below: each core having its own
cache.
– Not always: possible to have a shared cache or
shared/local mix.
– Cache coherence[1] in local caches?
• Parallel software required to utilise multiple
cores.
[1]http://en.wikipedia.org/wiki/Cache_coherence
Clustered Systems.
• Independent computer systems (nodes)
connected through a network.
– Local area network (LAN)
– Internet/Wide Area Networks
– Through a switch
• Layer of cluster software.
http://en.citizendium.org/wiki/Beowulf_cluster
23
Clustered Systems
• High availability of services.
– Redundant nodes taking over if another node fails
• Can be more powerful than SMP systems.
– Application can run on independent systems
– Provide High Performance Computing.
• What should the software do?
– Be parallelizable to take advantage
– And then combine the results back
• Case study: MapReduce on Hadoop.
24
History of Operating Systems
• A history of resource driven choices.
• Reference in Book: section 1.12
25
Moore’s Law Effects
• Nothing like this in any other area of business
• Transportation in over 200 years:
– 2 orders of magnitude from horseback @10mph
to Concorde @1000mph
– Computers do this every decade (at least until
2002)!
• What does this mean for us?
– Techniques have to vary over time to adapt to
changing tradeoffs
26
Dawn of time
ENIAC: (1945—1955)
• “The machine designed by Drs. Eckert and Mauchly
was a monstrosity. When it was finished, the ENIAC
filled an entire room, weighed thirty tons, and
consumed 200,000 watts of power.”
• http://ei.cs.vt.edu/~history/ENIAC.Richey.HTML
History Phase 1 (1948—1970)
Hardware Expensive, Humans Cheap
• When computers cost millions of $’s, optimize
for more efficient use of the hardware!
– Lack of interaction between user and computer
• User at console: one user at a time
• Batch monitor: load program, run, print
• Optimize to better use hardware
– When user thinking at console, computer idleBAD!
– Feed computer batches and make users wait
• No protection: what if batch program has bug?
Core Memories (1950s & 60s)
The first magnetic core
memory, from the IBM 405
Alphabetical Accounting
Machine.
• Core Memory stored data as magnetization in iron
rings
– Iron “cores” woven into a 2-dimensional mesh of wires
– Origin of the term “Dump Core”
• See: http://www.columbia.edu/acis/history/core.html
History Phase 1½ (late 60s/early 70s)
• Important to keep machines busy: overlap I/O and compute
– DMA – Direct Memory Access for I/O devices
– I/O can be completed asynchronously
• Multiprogramming: several programs run simultaneously
– Small jobs not delayed by large jobs
– More overlap between I/O and CPU
– Need memory protection between programs and/or OS
• Operating Systems get incredibly complex:
– Multics: announced in 1963, ran in 1969
• 1777 people “contributed to Multics” (30-40 core dev)
• Turing award lecture from Fernando Corbató (key researcher): “On building
systems that will fail”
– OS 360: released with 1000 known bugs (APARs)
• “Anomalous Program Activity Report”
• OS finally becomes an important science:
– How to deal with complexity???
– UNIX based on Multics, but vastly simplified
Early Disk History
1973:
1. 7 Mbit/sq. in
140 MBytes
1979:
7. 7 Mbit/sq. in
2,300 MBytes
Contrast: Seagate 2TB,
400 Gbit/SQ in, 3½ in disk,
4 platters
History Phase 2 (1970 – 1985)
Hardware Cheaper, Humans Expensive
• Computers available for tens of thousands of
dollars instead of millions
• OS Technology maturing/stabilizing
• Interactive timesharing:
– Use cheap terminals (~$1000) to let multiple
users interact with the system at the same time
– Sacrifice CPU time to get better response time
– Users do debugging, editing, and email online
• Big deal at that time!
The
ARPANet
(1968-1970’s)
SRI
940
UCSB
IBM 360
IMPs
Utah
PDP 10
UCLA
Sigma 7
BBN team that implemented
the interface message processor (IMP)
• Paul Baran
– RAND Corp, early 1960s
– Communications networks
that would survive a major
enemy attack
• ARPANet: Research vehicle for
“Resource Sharing Computer
Networks”
– 2 September 1969: UCLA first
node on the ARPANet
– December 1969: 4 nodes
connected by 56 kbps phone
lines
– 1971: First Email
– 1970’s: <100 computers
History Phase 3 1981- Personal
Computing
• Computers Cheap (~ $1000); affordable for
personal use.
• Programmer Expensive ($100,000).
• Simple OS
– Initially without memory protection.
• Until later: memory protection in Windows NT
and OS2
34
History Phase 3 (con’t)
Graphical User Interfaces
• Xerox Star: 1981
• Apple Lisa/Machintosh: 1984
– “Look and Feel” suit 1988
Xerox Star
– Originally a research
project (Alto)
– First “mice”, “windows”
• Microsoft Windows:
Win 1.0 (1985)
Win 3.1 (1990)
Win 95 (1995)
Win NT (1993)
Win 2000 (2000)
Win XP (2001)
Win Vista (2007)
Windows 7
Full Prot
Windows 3.1
–
–
–
–
–
–
–
–
History Phase 4 (1988—): Internet
• Research community developed Internet Protocol (IP)
• IP is a technical basis for many other types of networks
– Intranet: internal to just an organisation (e.g. UL)
• Services Provided by the Internet
– Shared access to computing resources: telnet (1970’s)
– Shared access to data/files: FTP, NFS, AFS (1980’s)
– Communication medium over which people interact
• email (1980’s), on-line chat rooms, instant messaging (1990’s)
• audio, video (1990’s, early 00’s)
– Medium for information dissemination
• WWW (1990’s)
• Audio, video (late 90’s, early 00’s) – replacing radio, TV?
• File sharing (late 90’s, early 00’s)
History Phase 4 (1988—):
Distributed Systems
• Networking (Local Area Networking)
– Different machines share resources
– Printers, File Servers, Web Servers
– Client – Server Model
• Services
– Computing
– File Storage
Network “Cloud”
Section
1.11.7
History Phase 5 (1995—)
• Mobile Devices
– Laptops, PDAs, phones
– Small, portable, and inexpensive
• Many computers/person!
– Limited capabilities (memory, CPU, power, etc…)
• Traditional computers split into pieces. Wireless
keyboards/mice, CPU distributed, storage remote
• Peer-to-peer systems
– Many devices with equal responsibilities work together
– Components of “Operating System” spread across
globe
Open-Source Operating Systems
• Operating systems made available in source-code
format rather than just binary closed-source
• Counter to the copy protection and Digital Rights
Management (DRM) movement
• Started by Free Software Foundation (FSF), which
has “copyleft” GNU Public License (GPL)
• Examples include GNU/Linux and BSD UNIX
(including core of Mac OS X), and many more
• Can use VMM like VMware Player (Free on
Windows), Virtualbox (open source and free on many
platforms - http://www.virtualbox.com)
– Use to run guest operating systems for exploration
History of OS: Summary
• Change is continuous and OSs should adapt
– Not: look how stupid batch processing was
– But: Made sense at the time
• Diverse OSs
– Small OS: 100K lines
– Large OS: 10M lines (5M for the browser!)
• 100-1000 people-years
• Complexity still reigns
• Understand OSs to simplify them