Transcript Advanced Operating Systems

Advanced
Operating Systems
Lecture 1: Introduction
University of Tehran
Dept. of EE and Computer Engineering
By:
Dr. Nasser Yazdani
Univ. of Tehran
Advanced Operating Systems
1
Goal



Introducing the course and policies
Some reviews from OS
References:


Review any undergraduate level OS book. We
suggest Silbershutz , Galvin, .. Book
Read “ On building Systems that will fail” by
Fernando J. CorBato
Univ. of Tehran
Advanced Operating Systems
2
Outline






Agenda
Policy, Grading, reading materials, etc.
Some review from OS
Overview of course materials
Some deep question in OS
Some general guides (Taken mostly from
Dr. Shenoy, Univ. of Massachusetts
Amherst, website)
Univ. of Tehran
Advanced Operating Systems
3
Agenda





To well understand OS architecture and design.
To establish a base for future Operating System
research and development.
To discuss latest developments in OS computer
via class lectures and assigned readings.
To find the current research issues in the field.
Finally, prepare to perform some projects in OS
which are essential in national development and
grows.
Univ. of Tehran
Advanced Operating Systems
4
Course Materials

Course Web page
visit regularly
Htt://cec.ut.ac.ir/classpages/advanceOS


Research papers



Textbooks: It is mostly paper based but the following
book is good for some parts


On pdf/ps format on the Website
Combination of classic and recent work.
“Distributed Systems” , Andrew Tanenbaum. Last edition
Other good books



“Modern Operating Systems” , Andrew Tanenbaum.
Coulouris, et al., “Distributed Systems: Concepts and
Design”, 2nd ed., 004.36 C85d2
Linux Kernel Development (2.6 kernel)
Univ. of Tehran
Advanced Operating Systems
5
Grading

Homework assignments, around %30

Presentations




Paper reviews.
Homework




Paper presentation, each paper around 1 hour.
(For PhD student only)
Final project presentation, around 20 minutes.
Mostly kernel simulation and programming.
Late penalties!
Project around %30
Exam, final around %40.
Univ. of Tehran
Advanced Operating Systems
6
Policy



The course is research oriented. Then, the
main focus will be on paper reading and
projects.
We will focus more on essential OS concepts
and problems and especially on Distributed
Systems.
There will be reading and work. Then, be
prepared!.
Univ. of Tehran
Advanced Operating Systems
7
Prerequisites




We assume Programming experience in C
Some familiarity with Unix and system
calls
Undergraduate Operating system course
An undergraduate “textbook” OS class


Familiar with concepts like Virtual Memory, processes,
etc.
But maybe never seen a real implementation, or
written code to do things like manipulate page tables
Univ. of Tehran
Advanced Operating Systems
8
Basic Question?



What is OS?
Why do we need OS?
What does OS provide to us?
OS is a facilitator and make life easier for user
We will see more later?
Univ. of Tehran
Advanced Operating Systems
9
Why Study OS?


Operating systems are a maturing field
High-performance servers are an OS issue


Resource consumption is an OS issue


Hard to achieve security without a solid foundation
New smart devices need new Oses


Battery life, radio spectrum, etc.
Security is an OS issue


Face many of the same issues as OSes
Today, everything is embedded systems and OS an
essential part of it.
We
need good knowledge
on OS inside the
Univ. of Tehran
Advanced Operating Systems
10
Operating System?
Software that turns silicon into something
useful:
 Provides abstractions for applications



Manages and hides details of hardware
Accesses hardware through low/level
interfaces unavailable to applications.
Provides isolation/protection

Prevents one process/user from clobbering
another
Univ. of Tehran
Advanced Operating Systems
11
Operating System?
It is an extended machine



Hides the messy details which must be performed
Presents user with a virtual machine, easier to use
It is a resource manager



Each program gets time with the resource
Each program gets space on the resource
Real life example:

Government
Univ. of Tehran
Advanced Operating Systems
12
History of OS (1)

First generation 1945 – 1955


Second generation 1955 – 1965



ICs and multiprogramming
Fourth generation 1980 – present
–

transistors, batch systems, IBM 360
Third generation 1965 – 1980


vacuum tubes, plug boards (no OS)
personal computers, hand-held devices, sensors
Software has profound though slower impact on
computer architecture
Modern architects cannot avoid paying attention
to software and compilation issues
Univ. of Tehran
Advanced Operating Systems
13
History of OS (1945-55)
Early days, use of computer was very primitive, very
difficult and inefficient (why?)
Improvement: assembly language, Fortran, Compiler
and finally Batch Processing?
Univ. of Tehran
Advanced Operating Systems
14
History of OS (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
Univ. of Tehran
Advanced Operating Systems
15
Batch System

What it does?




Then,




Schedules task (Usually FIFO)
Starts and Terminates Jobs
Compile Programs & binds with libarary
Make life easier for user (user friendly)
Isolate user (Application) from Hardware
Resource manager
Problem?

Slow Response time
Univ. of Tehran
Advanced Operating Systems
16
History of Operating Systems
(1965-80)

Sharing System among user



Multitasking and time sharing system
Extend Resource management to memory, I/O, etc.
Protect programs
Univ. of Tehran
Advanced Operating Systems
17
The OS 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
Univ. of Tehran
Advanced Operating Systems
18
History of OS: Change!
1980
Speed
2000
Factor
CPU
1 MIPS
1000 MIPS
1000
Memory
500 ns
2 ns
250
Disk
18 ms
2 ms
9
Modem
300 bits/sec
56 Kbits/sec
200
Memory
64 Kbytes
128 Mbytes
2000
Disk
1 Mbytes
6 Gbytes
6000
Cost
Per MIP
$100K
<= $1
100000
Other
Address bits
8
64
8
Users/machine
10s
<=1
.01
Capacity
Univ. of Tehran
Advanced Operating Systems
19
What Is an OS?
Provide environment for application and go away
It is like government (?).
Resources
 Allocation
 Protection
 Reclamation
 Virtualization
Services
 Abstraction
 Simplification
 Convenience
 Standardization
Makes computers simpler
Univ. of Tehran
Advanced Operating Systems
20
What Is an OS?
Resources
 Allocation
 Protection
 Reclamation
 Virtualization
Government
Finite resources
Limited budget,
Competing demands Land,
Oil,
Gas,
Examples:
 CPU
 Memory
 Disk
 Network
Linux or Windows?
Univ. of Tehran
Advanced Operating Systems
Democrat or Republic?
21
What Is an OS?
Resources
 Allocation
 Protection
 Reclamation
 Virtualization
Univ. of Tehran
You can’t hurt me
I can’t hurt you
Government
Law and order
Implies some degree of
safety & security
Advanced Operating Systems
22
What Is an OS?
Resources
 Allocation
 Protection
 Reclamation
 Virtualization
Univ. of Tehran
Government
The OS gives
The OS takes away
Income Tax
Voluntary at run time
Implied at termination
Involuntary
Cooperative
Advanced Operating Systems
23
What Is an OS?
Resources
 Allocation
 Protection
 Reclamation
 Virtualization
illusion of infinite,
private resources
Government
Social security
Memory versus disk
Timeshared CPU
More extreme cases
possible (& exist)
Univ. of Tehran
Advanced Operating Systems
24
What we will do?
OS does a lot of things => It is a huge program
 How does it affect Hardware?
 How to organize, structure it?
 What are important?
Scalability
 Extensibility
 Manageability
 Robustness,
 Efficiency , Performance
 More important user-friendly
 Of course, cost

Univ. of Tehran
Advanced Operating Systems
25
Covered Topics
First, we look at some design principle? It is
usually general.
 Effects on the Hardware
 New design approach, micro kernel
 Some basic challenges

Threads
 Interprocess communication
 Scheduling
 Concurrency

File system
 Virtual machine
 Multicore OS

Univ. of Tehran
Advanced Operating Systems
26
Topics (Distributed)

Distributed system Architecture
 Clould
 Gride
 Peer to

peer
Process communication

RPC
Process migration, agents
 Naming
 Clock & time, synchronization
 Distributed file system
 Kernel support
Univ. of Tehran
Advanced Operating Systems
 Transaction

27
Some Deep Questions



How do we organize the OS effectively
for development, evolution, performance,
and security?
How do we design a distributed OS that
can be used on multiple machines?
How do we use multi-processor machines
effectively?
Univ. of Tehran
Advanced Operating Systems
28
Some Questions on
processes




How do processes communicate and share
states efficiently and securely on the same
machine? Across multiple machines?
How do we improve the computing process
model?
How do we achieve fairness, high
throughput, and responsiveness at the same
time?
How do we reduce or avoid the cost of
context switching?
Univ. of Tehran
Advanced Operating Systems
29
Some Deep Questions




How do systems achieve agreement across
multiple machines?
How do you represent the notion of time and
the ordering of events across multiple
machines?
How do we coordinate machines to share
memory?
How can we simplify memory management
as memory becomes abundant?
Univ. of Tehran
Advanced Operating Systems
30
Some Deep Questions





How do we make different file systems work
together, even across machines?
How do we provide consistency, availability, and
reliability to copies of a file across multiple
machines?
How do we handle very large data sets?
How do we coordinate the memory resources
across machines to enhance performance?
How do we handle new devices with new
characteristics?
Univ. of Tehran
Advanced Operating Systems
31
You Live in Interesting
Times…
Processors speed used to double in 18 months, but
we are reaching the upper bound (due to thermal
problems) and need to go towards processor
parallelism to increase the processing power
 Disk doubling every 12 months
 Global bandwidth every 6 month
 What will the future OS be?
(If population doubles every year, or people can move
twice faster every year, what does the government
do?)

Univ. of Tehran
Advanced Operating Systems
32
General guides (Broading)

Main Point
1. There aren't very many influential nerds, and
there never will be. Why? They're too narrow.
Real breakthroughs tend to come from people
with breadth.
2. One of the most important things you should
do is to force yourself to stay broad.
Univ. of Tehran
Advanced Operating Systems
33
General guides (Broading)

Reasons to Stay Broad
1. Breadth helps depth. The more you understand, the
more you'll understand about each individual thing.
Seeing how things in different areas are similar or
different is a very good way of seeing what's important.
2. Breakthroughs often occur when people can cross
traditional boundaries: compilers and architecture,
graphics and VLSI, etc.
3. Computers are tools: they serve people. In order to build
effective tools, you have to understand both the
capabilities of computers, and the needs of the
application areas where they'll be used.
4. Technology is changing fast. Why is there a shortage of
25-year-old engineers and a surplus of 45-year-old ones?
Companies encourage new graduates to get so narrow
Univ. of Tehran
Advanced Operating Systems
34
that they're instantly obsolete.
General guides (Broading)

Solutions
Continuing education. Try always to be learning
in whatever you do. Don't let your education
stop when you leave University.
2. Explore new areas, both inside and outside
Computer Science. Everything you learn will
someday be helpful, no matter how unlikely it
seems. English, art, hobbies, all things are
helpful. Here's an example: Steve Wozniak.
After building the Apple 2, came back to
Berkeley to get a masters. Around the same
time, he and Jobs visited Xerox PARC, learned
from the good ideas there, and built the
Macintosh.
1.
Univ. of Tehran
Advanced Operating Systems
35
A computer system
Univ. of Tehran
Advanced Operating Systems
36
Computer Hardware
Review (1)
Monitor
Bus

Components of a simple personal
computer Advanced Operating Systems
Univ. of Tehran
37
Computer Hardware
Review (2)
(a) A three-stage pipeline
(b) A superscalar CPU
Univ. of Tehran
Advanced Operating Systems
38
Computer Hardware
Review (3)

Typical memory hierarchy
–
numbers shown are rough approximations
Univ. of Tehran
Advanced Operating Systems
39
Computer Hardware
Review (4)
Structure of a disk drive
Univ. of Tehran
Advanced Operating Systems
40
Computer Hardware
Review (5)
One base-limit pair and two base-limit pairs
Univ. of Tehran
Advanced Operating Systems
41
Computer Hardware
Review (6)
(a)
(b)


Steps in starting an I/O device and getting interrupt
How the CPU is interrupted
Univ. of Tehran
Advanced Operating Systems
42
Computer Hardware
Review (7)
Structure of a large Pentium system
Univ. of Tehran
Advanced Operating Systems
43
Operating System
Concepts (1)



A process tree
A created two child processes, B and C
B created three child processes, D, E, and F
Univ. of Tehran
Advanced Operating Systems
44
Processor (CPU)
Management

Goals



Time sharing
Multiple CPU allocations
Issues




Do not waste CPU resources
Synchronization and mutual
exclusion
Fairness
deadlock free
Univ. of Tehran
Advanced Operating Systems
Analogy: Video Games
45
OS Concepts (2)
(a) A potential deadlock. (b) an actual deadlock.
Univ. of Tehran
Advanced Operating Systems
46
Operating System
Concepts (3)
File system for a university department
Univ. of Tehran
Advanced Operating Systems
47
Operating System
Concepts (4)


Before mounting,
 files on floppy are inaccessible
After mounting floppy on b,
– files on floppy are part of file hierarchy
Univ. of Tehran
Advanced Operating Systems
48
Operating System
Concepts (5)
Process
Process
Pipe
A
B
Two processes connected by a pipe
Univ. of Tehran
Advanced Operating Systems
49
Making a System Call
There are 11 steps in making the system call
read (fd, buffer, nbytes)
Univ. of Tehran
Advanced Operating Systems
50
System Calls (1)

A stripped down shell:
while (TRUE) {
type_prompt( );
read_command (command, parameters)
terminal */
if (fork() != 0) {
/* Parent code */
waitpid( -1, &status, 0);
exit */
} else {
/* Child code */
execve (command, parameters, 0);
}
}
Univ. of Tehran
/* repeat forever */
/* display prompt */
/* input from
/* fork off child process */
/* wait for child to
/* execute command */
Advanced Operating Systems
51
System Calls (2)

Processes have three segments: text, data,
stack
Univ. of Tehran
Advanced Operating Systems
52
System Calls (3)
(a) Two directories before linking
/usr/jim/memo to ast's directory
(b) The same directories after linking
Univ. of Tehran
Advanced Operating Systems
53
System Calls (4)
(a) File system before the mount
(b) File system after the mount
Univ. of Tehran
Advanced Operating Systems
54
Operating System
Structure (1)
Simple structuring model for a monolithic
system
Univ. of Tehran
Advanced Operating Systems
55
Operating System
Structure (2)
Structure of the THE operating system
Univ. of Tehran
Advanced Operating Systems
56
Operating System
Structure (3)
Structure of VM/370 with CMS
CMS- Conversational Monitor System
Univ. of Tehran
Advanced Operating Systems
57
Operating System
Structure (4)
The client-server model
Univ. of Tehran
Advanced Operating Systems
58
Operating System
Structure (5)
The client-server model in a distributed
system
Univ. of Tehran
Advanced Operating Systems
59
Scheduling: polling vs.
interrupts

Maintain peak performance under heavy load


Interrupts model can lead to livelock
Solution:


Use interrupts under low load (good latency)
Use polling under heavy load (good throughput)


Polling is typically more efficient than interrupts
Fits naturally into asynchronous I/O model
Univ. of Tehran
Advanced Operating Systems
60
Another Look: Unix
“Onion”
Applications
User and Kernel
boundary
OS Service
Device
Hardware
Driver
Univ. of Tehran
Advanced Operating Systems
61
Other design issues

Disk scheduling


Memory management


Elevator algorithm
File system buffer cache
Address spaces (VM management)

Fault isolate different servers


Efficient local communication?
Efficient transfers between disk and networks

Avoid copies
Univ. of Tehran
Advanced Operating Systems
62
More than one processor


Problem: single machine may not scale to
enough clients
Solutions:

Multiprocessors


Server clusters


Helps when CPU is bottleneck
Helps when bandwidth between server and
backbone is high
Distributed server clusters
Helps when bandwidth between client and distant
server
is low Advanced Operating Systems
Univ. of
Tehran

63
Bootstrapping






Power up a computer
Processor reset
 Set to known state
 Jump to ROM code
Load in the boot loader
from stable storage
Jump to the boot loader
Load the rest of the
operating system
Initialize and run
Univ. of Tehran
Boot
loader
Advanced Operating Systems
Boot
loader
OS
sector 1
OS
sector 2
.
.
.
OS
sector n
64
Design Tradeoffs

All in the kernel (Windows)



All at user level - Nemesis (Cambridge, UK) –
only device drivers exist, all other management
was done at user level), TinyOS (UCB) – runs
on Modes/ Sensors



Pros: efficient?
Cons: difficult to develop new services
Pros: easy to develop new apps
Cons: protection
Split between user and kernel (Unix/Linux)


Kernel: display driver and mouse driver
User: the rest
Univ. of Tehran
Advanced Operating Systems
65
Next Lecture

System design


Read “The Interaction of Architecture and
Operation System Design”, Thomas E.
Anderson, et al.
“Lisp: Good News, Bad news, How to Win
Big”, Richard P. Gabriel
Univ. of Tehran
Advanced Operating Systems
66