Transcript Chapter 10

Chapter 10
Operating
Systems
Chapter Goals
• Describe the two main responsibilities of an
operating system
• Define memory and process management
• Explain how timesharing creates the virtual
machine illusion
• Explain the relationship between logical and
physical addresses
• Compare and contrast memory management
techniques
2
Chapter Goals
• Distinguish between fixed and dynamic
partitions
• Define and apply partition selection algorithms
• Explain how demand paging creates the virtual
memory illusion
• Explain the stages and transitions of the process
life cycle
• Explain the processing of various CPU
scheduling algorithms
3
What is an Operating System?
• A collection of programs that carry out six basic
functions
–
–
–
–
–
–
Booting the Computer
Provides the User Interface
Provides File Management
Handles Input and Output Operations
Manages Memory
Provides Context Switching & Multitasking
• Examples of Operating Systems:
Windows (98, NT, ME, XP), MS-DOS, CPM, Mac OS X, UNIX, OS/2, LINUX, VMS, PALM OS,
SOLARIS
What is an Operating System?
A collection of programs that manages and controls software, and
coordinates the various hardware components to perform tasks requested
by the user
Isolate the
hardware from
users and direct
manipulation by
applications
What if the OS wasn’t there?
• Programs “poked” into RAM via switches
• First program loaded “read” other programs
• Next program added “device support”
• Devices could then be used to read in larger programs like
BASIC
• Overall process was tedious and slow (could take up to 30
minutes)
• You wouldn’t want to shut off the computer
BIOS to the rescue
• BIOS is the Basic Input Output System
• Collection of programs
• Provides the capability of communicating with peripheral
devices
– Keyboard
– Disk drives
– Monitor
• Allows the rest of the operating system to be read in from
the disk drive
• Stored in ROM so it is always there
Booting the Computer
• Process of automatically running a program in ROM which
in turn loads the operating system into RAM and turns
control over to it.
• Cold Boot – booting up when the power was originally off
• Warm Boot – booting up when the power was originally on
(re-booting)
– Gets a fresh copy of the operating system
• Multiple Operating Systems – partitioning the hard drive for
each OS
User Interfaces
• The user interface is the part of the Operating System that
the user sees and interacts with
• Different types of interfaces for different purposes
– GUI
– CLI
• GUI – Graphical user interface
– Mouse oriented and utilizes icons and buttons
– Allows symbolic manipulation of programs and files
• CLI – Command line interface
– Instructions are given by typing commands on the keyboard
– Requires technical understanding of commands
– Not user friendly or intuitive
Files and File Management
• A file is a collection of [data] that is treated as a
single unit
–
–
–
–
A picture
A spread sheet
A document
A program
• A file has a unique name
– Filename . Extension
• Extensions are used to associate files with
programs
Files and File Management
• There are two basic types of file systems
– Flat file structure
– Hierarchical file structure
• Flat file structure
– Organizes files in one flat list
– No subdivision or grouping possible
– Like dumping all of your papers in a pile on the top of
your desk
– Difficult to manage and keep track of files
Files and File Management
• Hierarchical file structure
– Organizes files in a tree like structure
– Subdivision is achieved via subdirectories (usually
depicted as folders)
– Similar to filing cabinets with drawers and folders within
them
– Easy to manage and keep track of files
– The folders become part of the naming convention for the
file
C:\Windows\System32\Regedit.exe
Input and Output Support
• I/O support provides basic support to read and
write information to peripheral devices
• Specialized devices may require special software
called a device driver
– Device drivers are usually provided by the manufacturer
of the specialized hardware
– Device drivers provide enhanced features that the
operating system doesn’t know about
• I/O support also provides error handling in case of
device failures
Memory Management
• Real vs Virtual Memory
• Computers have a physical amount of RAM
• All memory in the computer is “owned” by the
operating system
• The operating system allocates memory to
programs as they need it
• The operating system reclaims memory when
programs are done with it
Memory Management
• Memory “some” PC after boot up
Memory Management
• The user starts up a web browser
Memory Management
• The user starts up several more programs
Memory Management
The user wants to start a program that is 35M,
but only 20M is free
Memory Management
Windows will clear out 15M of memory that hasn’t been
used in a while and load the program
Memory Management
• The process of swapping memory in and out creates the
illusion that you have more than there really is (Virtual
Memory)
– Too much swapping is bad (poor performance)
– Windows hides the disk file from the user
• Pagefile.sys
• It is usually around 1.5 times the size of real memory
• Other uses of memory
– Disk cache
– RAM disk
– I/O buffers
Context Switching & Multitasking
• Context switching allows several application programs to be
in RAM at one time. The user controls which program is the
current one.
– The user switches back and forth between programs
• Multitasking allows several application programs to be in
RAM at one time. Each is allowed CPU time as needed, all
under the control of the CPU.
– Allows programs to continue to run in the back ground
• MS-DOS / Windows 3.1 / Windows XP
OS for the Networked World
• Parallel processing / multiprocessing takes place on a
computer with more than 1 CPU
– Requires more complex operating system
– Utilizes special programming techniques
• Distributed processing utilizes a network to decentralize and
distribute the computing needs over several dispersed
computers
– SETI screen saver
• Client / server computing – the server provides data and
programs for the clients
– Web server and web browsers
OS for the Networked World
• Real Time processing – involves human interaction with the
computer in a situation in which quick or timely return of
results is important
– ATM
– Airline reservation system
• Process control – is the control of a process by a computer.
It usually requires input to be accepted by the CPU,
processed, and then a task is executed based upon the
processed input.
– Automobile electronic ignition system
– Missile guidance system
– Usually require “feed back”
Software Categories
Application software
Software written to address specific needs—to solve
problems in the real world
System software
Software that manages a computer system at a
fundamental level
Can you name examples of each?
24
Roles of an Operating System
Operating system
System software that
– manages computer resources, such as memory and
input/output devices
– provides an interface through which a human can interact
with the computer
– allows an application program to interact with these other
system resources
25
Roles of an Operating System
The various roles of an operating system generally
revolve around the idea of “sharing nicely”
An operating system manages resources, and these
resources are often shared in one way or another
among programs that want to use them
26
Resource Management
Multiprogramming
The technique of keeping multiple programs that
compete for access to the CPU in main memory at
the same time so that they can execute
Memory management
The process of keeping track of what programs are in
memory and where in memory they reside
27
Resource Management
Process
A program in execution
Process management
The act of carefully tracking the progress of a
process and all of its intermediate states
CPU scheduling
Determining which process in memory is executed by
the CPU at any given point
28
Batch Processing
The first operating system was a human operator, who
organized various jobs from multiple users into batches of jobs
that needed the same resources
29
Timesharing
Timesharing system
A system that allows multiple users to interact with a
computer at the same time
Virtual machine
The illusion created by a time-sharing system that
each user has his/her own machine
As computer speed increased, the human
operator became the bottleneck
30
Other Factors
Real-time System
A system in which response time is crucial given the
nature of the application
Response time
The time delay between receiving a stimulus and
producing a response
Device driver
A small program that “knows” the way a particular
device expects to receive and deliver information
31
Memory Management
Operating systems must employ techniques to
– Track where and how a program resides in memory
– Convert logical addresses into actual addresses
Logical address
Reference to a stored value relative to the program
making the reference
Physical address
Actual address in main memory
32
Memory Management
Program 1:
sum is assigned memory
location 23, a location
relative to Program 1
OS must map sum (relative location 23)
to a specific physical address
Logical address for sum (23) is bound to a
physical address in memory before the
program runs
33
Single Contiguous MM
There are only two
programs in memory
The operating system
The application program
This approach is called
single contiguous
memory management
34
Single Contiguous MM
In concrete terms:
A logical address is simply an integer value
relative to the starting point of the program
A physical address is a logical address added
to the starting location of the program in main
memory
35
Single Contiguous MM
If A is location 100, and
the application program
is Program 1, then
sum is stored at location
123.
36
Partition Memory Management
Single contiguous MM has only the OS and one other
program in memory at one time
Partition MM has the OS and any number of other
programs in memory at one time
There are two schemes for dividing up memory for
programs:
– Fixed partitions Main memory is divided into a fixed
number of partitions into which programs can be loaded
– Dynamic partitions Partitions are created as needed to
fit the programs waiting to be loaded
37
Partition Memory Management
Memory is divided into a set of partitions, some
empty and some allocated to programs
Base register
A register that holds the beginning address of the
current partition (the one that is running)
Bounds register
A register that holds the length of the current
partition
38
Partition Memory Management
Why check?
39
Partition Selection Algorithms
Which partition should we allocate to a new program?
• First fit Allocate program to the first partition big
enough to hold it
• Best fit Allocated program to the smallest partition
big enough to hold it
• Worst fit Allocate program to the largest partition
big enough to hold it
Can you give a rationale for each?
40
Partition Selection Algorithms
A: 1000
B: 700
C: 750
D: 1500
E: 300
F: 350
41
Requests come in for blocks of
the following sizes:
1000, 25, 780, 1600, and 325
What block will be assigned
to each request if the
• first-fit algorithm is used?
• best-fit algorithm is used?
• worst-fit algorithm is used?
(Treat each request as an
independent event)
Paged Memory Management
Paged memory technique
A technique in which processes are divided into fixed-size
pages and stored in memory frames when loaded
Frame
A fixed-size portion of main memory that holds a process page
Page
A fixed-size portion of a process that is stored into a memory
frame
We assume that a frame and a page are the same size
42
Paged Memory Management
Prog. 2, Page 2
Prog. 1, Page 3
If Prog. 1 is running and
needs logical address 2566,
how is the actual address
calculated?
43
Paged Memory Management
Integer logical address is mapped into a
<page number, offset> logical address
Page number
Address divided by the page size (say 1024)
Offset
The remainder of the address divided by the page size
2566 DIV 1024 = 2
2566 MOD 1024 = 518 ==> <2, 518>
And???
44
Paged Memory Management
This new logical
address is mapped to
a physical address with
the help of a page-map
table (PMT)
Every program has a
PMT that shows into
which frame each page
of the program is
stored
What is the physical
address of <2, 518>?
45
Paged Memory Management
Demand paging
An extension of paged memory management in
which pages are brought into memory on demand
Page swap
The act of bringing in a page from secondary
memory, which often causes another page to be
written back to secondary memory
46
Paged Memory Management
Virtual memory
The illusion that there are no restrictions on the size
of a program because an entire process doesn't have
to be in memory at the same time
Thrashing
Inefficient processing caused by constant page
swaps
Relate the expression "all computing is a
tradeoff" to this process
47
Process Management
Process management
The act of managing the use of the CPU by
individual processes
Recall that a process is a program in
execution
What stages does a process go through?
48
Process Management
The Process States
What can
cause a
process to
move to
the
Waiting
state?
49
Process Management
Process control block (PCB)
A data structure used by the OS to manage
information about a process, including
–
–
–
–
current value of the program counter
values of all CPU registers for the process
base and bound register values (or page tables)
accounting information
Each state is represented by a list of PCBs, one for
each process in that state
50
Process Management
There is only one CPU and therefore only one set of CPU
registers, which contain the values for the currently
executing process
Each time a process is moved to the running state:
– Register values for the currently running process
are stored into its PCB
– Its PCB is moved to the list of the state into which it goes
– Register values of the new process moving into the running state
are loaded into the CPU
– This exchange of register information is called a context switch
51
CPU Scheduling
CPU Scheduling
The act of determining which process in the ready
state should be moved to the running state
– Many processes may be in the ready state
– Only one process can be in the running state, making
progress at any one time
Which one gets to move from ready to running?
52
CPU Scheduling
Nonpreemptive scheduling
The currently executing process gives up the CPU voluntarily
Preemptive scheduling
The operating system decides to favor another process,
preempting the currently executing process
Turnaround time
The amount of time between when a process arrives in the
ready state the first time and when it exits the running state for
the last time
53
CPU Scheduling Algorithms
First-Come, First-Served
Processes are moved to the CPU in the order in which they
arrive in the running state
Shortest Job Next
Process with shortest estimated running time in the ready state
is moved into the running state first
Round Robin
Each process runs for a specified time slice and moves from
the running state to the ready state to await its next turn if not
finished
54
First-Come, First-Served
What is the
average turnaround time?
55
Shortest Job Next
What is the
average turnaround time?
56
Round Robin
Every process is treated the same!
Time slice (quantum)
The amount of time each process receives
before being preempted and returned to the
ready state to allow another process its turn
57
Round Robin
Suppose the time slice is 50
What is the average
turnaround time?
58
CPU Scheduling Algorithms
Are these scheduling algorithms preemptive or
non-preemptive? Explain
First-Come, First-Served?
Shortest Job Next?
Round Robin?
59
Questions??
There should be . . . . .