Transcript Introduction

Operating Systems (202-1-3031)
Meni Adler
 Office: Alon, 211
 [email protected]
 Office hours:
Wed…..
Danny Hendler
Office: Alon, 218
 [email protected]
 Office hours: 11:30-13:30
Amnon Meisels
Office: Alon, 206
 [email protected]
 Office hours: Wed. 9-11
Lecturers: Meni Adler, Danny Hendler and Amnon
Meisels
TAs: Vadim Levitt, Ehud Barnea, Matan Drori, Yeri Sofer
and Dan Brownstein (Zohar Komarovski & Tomer Sidi)
Course site: http://www.cs.bgu.ac.il/~os142/Main
1
Assignments and grade structure
Assignment
Subject
Weight
Programming 1 + 2 Scheduling +
Synchronization
Programming 3 + 4 Memory Management
+ Files
15%
Midterm
15%
Final
Processes, scheduling,
synchronization,
memory (TBD)
All
15%
55%
 Assignments and exams are mandatory
 Must pass final exam
2
Textbooks
 A. Tanenbaum: Modern Operating Systems, Prentice-Hall, 3rd
Edition, 2008
 A. Silbetschatz et al.: Operating System Concepts (9th ed.),
Addison Wesley, 2012
 G. Nutt: Operating Systems (a modern perspective) (3rd ed.),
Addison Wesley, 2003
 W. Stallings: Operating Systems (6th ed.), Prentice-Hall, 2009
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
3
Syllabus
1. Introduction - History; Views; Concepts; Structure
2. Process Management - Processes; State + Resources; Threads;
Unix implementation of Processes
3. Scheduling – Paradigms; Unix; Modeling
4. Synchronization - Synchronization primitives and their
equivalence; Deadlocks
5. Memory Management - Virtual memory; Page replacement
algorithms; Segmentation
6. File Systems - Implementation; Directory and space management;
Unix file system; Distributed file systems (NFS)
7. Distributed Synchronization (if there's time)
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
4
Introduction: outline
What is an operating system?
Some history
OS concepts
OS structure
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
5
Layered Hardware-Software
Machine Model
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
6
Computer-System Architecture
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
7
What is an Operating System ?
An operating system is:
1. An Extended Machine
2. A Resource manager
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
8
Operating Systems as extended Machines
The problems:
Bare machine has complex structure
o Processors
o Many difficult-to-program devices
Primitive Instruction Set
Different for Different Machines
OS provides:
Abstraction!
– Simple, easier to use interface (machine-independent)
– Hiding of unnecessary details
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
9
OS abstraction example: read from disk
Read file data from disk (simplified)
…




Read linear sector 17,403 from disk 2
Convert linear sector number to: cylinder, sector, head
(may be complicated – outer cylinders have more sectors,
bad sectors remapped, etc.)
Move disk arm to requested cylinder
Wait for proper sector to appear
…
OS abstraction
return-code = read(fd, buff, nbytes)
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
10
UNIX high-level architecture
User
Interface
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
11
Operating Systems as Resource Managers
 Multiple resources
o Processors; Memory
o Disks; Tapes; Printers
o Network interfaces; Terminals
 Controlled allocation of Resources among:
o Groups, Users; Processes, Threads,…
 Means of control: sharing/multiplexing/scheduling,
monitoring, protection, report/payment
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
12
Introduction: outline
What is an operating system?
Some history
OS concepts
OS structure
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
13
History of Operating Systems
 First generation 1945 - 1955
o vacuum tubes, plug boards – user plugs-in program
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
14
The first computers
Electronic Numerical Integrator And Computer (ENIAC)
Mathematical Analyzer, Numeric Integrator And Computer(MANIAC)
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
15
History of Operating Systems (cont’d)
 Second generation 1955 - 1965
o transistors, batch systems – multiple programs on Disk
 Third generation 1965 – 1980
o ICs and multiprogramming - user interaction (time-sharing)
 Fourth generation 1980 – present
o personal computers – graphic user-interface
o Networks – file & computing services
o Web-computing, Handheld devices , Cellular phones, Cloud computing…
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
16
How Bill Gates became rich…
1974: Intel releases the 8080 processor, needs an OS
Please! develop
an OS
CP/M OS
Gary Kildall
Operating Systems, 2014, Meni Adler, Danny Hendler &
Amnon Meisels
17
How Bill Gates became rich…(cont’d)
1974: Intel releases the 8080 processor, needs an OS
CP/M OS
Sure!
Can you grant me
CP/M rights?
Gary Kildall
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
18
How Bill Gates became rich…(cont’d)
1980: IBM designs IMB PC, needs an OS
Can you find an
OS for our PC?
Please meet IBM, they need an OS
Gary Kildall
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
19
How Bill Gates became rich…(cont’d)
1980: IBM designs IMB PC, needs an OS
Kildall too busy.
Please develop an
OS!
I’de like to buy the DOS OS
Sure, it’s yours for $75,000
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
20
How Bill Gates became rich…(cont’d)
1980: IBM designs IMB PC, needs an OS
May I retain the
rights for MSDOS?
Sure, why not!!
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
21
How Bill Gates became rich…(cont’d)
Well, this is 20:20 hind vision…
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
22
Introduction: outline
What is an operating system?
Some history
OS concepts
OS structure
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
23
OS – Key Functions
 Process management
o process creation; deletion; suspension/preemption
o process synchronization; communication; scheduling
 Main-memory management
o Manage used parts and their current users
o Select processes to load from secondary storage
o Allocate memory to running processes
 Secondary storage management
o Free-space management
o Storage allocation
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
24
OS – Key Functions (cont’d)
 File system management
o File + directory - creation; deletion
o File manipulation primitives
o Mapping files onto secondary storage
 I/O system management
o General device-driver interface
o Drivers for specific hardware devices
 Protection system
o Distinguish between authorized and unauthorized usage
o Provide means of enforcement
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
25
Processes - a key concept
 Resource container for “program in execution”
 Timesharing, process suspension/preemption
 Process Table
 Process Groups
 Signals
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
26
Why do we need multiple processes?
• Single application: We want things to happen “concurrently”
(E.g.: paging and typing in a text editor)
•
Multiple applications: processes running in the background
(e.g., Anti Virus)
• Multiple users: The departmental computer; all types of Servers
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
27
Multiprogramming: how is it done?
 CPU much faster than I/O
o Computation/communication overlap
 Memory large enough – requires memory protection!
 Scheduler which manages flow of jobs in and out
and shares CPU between jobs – requires Timer
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
28
Process trees
• A process tree
 A created two child processes, B and C
 B created three child processes, D, E, and F
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
29
Inter-Process Communication (IPC)
Two processes communicating via a pipe
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
30
Files: non volatile data
File types and operations on files
Directories - hierarchical structure
Working directories
Root di re ctory
S tu de n ts
Facu l ty
Am n on
Gi l
Or
Ron i
Pape rs
Progs
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
Gran ts
31
Files: non volatile data (cont’d)
 Protection and Security
Unix - user; group; other (rwx bits)
 File descriptors (handles)
 I/O as a special file
 Block & Character special files
 Standard input; output; error
 Pipes
 Links
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
32
I/O is performed in kernel mode
 All I/O instructions are privileged instructions
 I/O devices and CPU can execute concurrently
 CPU moves data between main memory and device
controllers' buffers (done by device drivers)
 Device controllers interrupt upon completion
 Interrupts or Traps enable mode switching
 Operating systems are interrupt-driven
 Traps/signals: software interrupts
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
33
Interrupts and the
fetch-decode-execute loop
Do forever{
IR = memory[PC];
execute(IR);
PC++;
If(Interrupt_Request) {
memory[0] = PC;
PC = memory[1] }
}
 An interrupt is an asynchronous event
 The kernel interrupt handling routine may use a
disable_interrupts instruction to avoid losing data while
processing an interrupt request
 Interrupt handler is typically called indirectly via the interrupt
vector
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
34
Synchronous vs. Asynchronous I/O
execute
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
35
Steps in Making a System Call
There are 11 steps in making the system call: read (fd, buffer, nbytes)
Is this call Synchronous or Asynchronous?
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
36
System Calls
processes
files
directories
miscellaneous
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
37
The Shell Command Language
 sort < file1 > file2

cat file1 | sort | lpr
• The Shell is a process which executes its commands
as offspring processes
• Processes may call shell commands by using the
“system” system call
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
38
Shell structure – Parent & child
A stripped-down shell:
while (TRUE) {
type_prompt( );
read_command (command, parameters)
if (fork() > 0) {
/* Parent code */
wait();
} else {
/* Child code */
execvp (command, parameters);
}
/* repeat forever */
/* display prompt */
/* input from terminal */
/* fork off child process */
/* wait for child to exit */
/* execute command */
}
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
39
Linux Shell initialization
 The init program (process 1) runs getty on all ports
 Upon detecting a terminal, getty runs login
 Typing in a user name and a password – login checks the passwd
file and if correct runs a shell – the one specified in the UID entry
 The shell is run with that user ID environment parameters
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
40
Running user commands
 User types: ‘grep some_word file_name’
 Shell parses the command, inserts the strings grep, some_word,
file_name into argv and their number to argc
 Next, the shell uses fork() to create a process (same user ID)
 Now, it takes the executable name grep and the arguments, all
from argv, and uses execvp() (or a similar system call) to run the
grep executable
 On foreground execution, the shell would use the wait() system
call and continue its session only after the child process
terminates
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
41
UNIX Utility Programs
A few of the more common UNIX utility programs required by POSIX
Operating Systems, 2014, Meni Adler, Danny Hendler &
Amnon Meisels
42
Introduction: outline
What is an operating system?
Some history
OS concepts
OS structure )‫(חומר העשרה‬
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
43
Operating system structure
1. Monolithic systems
2. Virtual machines
3. Client-server model
…
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
44
Monolithic systems
Monolithic systems have little structure
Main procedure for
invoking OS service
Service
Routines
Utility
procedures
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
45
Monolithic systems
Service routines are system calls
Utility procedures serve multiple service routines
All compiled into a single system
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
46
Virtual Machines
 Provide an interface identical to the underlying bare machine
 VM monitor creates multiple VMs, each executing on its own
(virtual) processor and its own (virtual) memory
 Virtual machines provide complete protection of system
resources - even separate resources
 Difficult to implement, due to the effort required to provide an
exact duplicate of the underlying machine
 Well-known examples:
o MS-DOS on top of Windows
o JVM
o VMWare
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
47
Virtual Machines: IBM 370
user
CMS
CMS
CMS
kernel
VM/370
370 bare hardware
CMS: Conversational Monitor System, a single user OS
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
48
Virtual Machines (cont’d)
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
49
Modern virtual machines
Different legacy servers run on different OS
Host sharing for web servers
Use multiple operating systems on a single machine
Security through isolation
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
50
Microkernels
Small number of lines of code mostly in C
Catching interrupts and switching processes in
Assembly
C code manages and schedules processes, interprocess communication, i/o interaction
 Offers few (~40) system calls for the rest of OS
 Device drivers (Disk, Network,…) in user mode
 Upper level contains Servers – File, Process..
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
51
Client-Server Model
Client
Process
Client
Process
......
File
Server
Memory
Server
(Micro)Kernel
Machine1
Machine2
Client
File Server
Kernel
Kernel
....
Network
Machine4
Machine3
Process Server
Kernel
Kernel
...
Distributed System
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
52
Client/server architecture:
Mechanism vs. Policy
 Simple Kernel - modularity; minimal “privileged” operation
 Servers for files, memory, etc. - distribution; user mode
operation
 good for distributed systems
 Mechanism in kernel - how to do things..
 Policy outside - decide what to do; can be changed later..
 Critical servers in kernel – i/o disk server & the Scheduler – who
serves who….
Operating Systems, 2014, Meni Adler, Danny Hendler & Amnon Meisels
53