Transcript 15.a The Internal Operating System

Chapter 15 – Part 1
The Internal Operating System
The Architecture of Computer Hardware
and Systems Software:
An Information Technology Approach
3rd Edition, Irv Englander
John Wiley and Sons 2003
OS Internals – Part I




Process Scheduling
CPU Scheduling
Memory Management
Virtual Storage
Chapter 15
The Internal Operating System – Part 1
15.1-2
Target Model
Chapter 15
The Internal Operating System – Part 1
15.1-3
Loading and Executing a Program
Network Services
Translates logical file
requests
File management
IOCS (I/O control system)
Device management /
Resource allocation
Load programs into MM
Allocates execution time
Provides overall system
control
Chapter 15
The Internal Operating System – Part 1
Memory management /
Scheduling
Monitor
15.1-4
Multi-Tasking System
 The OS must allocate resources (CPU,
memory, I/O) to multiple processes
 Different scheduling routines are used
for different objectives
Chapter 15
The Internal Operating System – Part 1
15.1-5
Processes
 Process: basic unit of work in the OS
 A program together with all the resources that are
associated with it as it is executed
 Program: a file or listing
 Process: a program being executed
 Independent vs. cooperating processes
 PID (process ID): a unique identifier for each
process
 Process creation: user vs. system
 Forking, spawning, cloning a new process
 Parent and child processes
Chapter 15
The Internal Operating System – Part 1
15.1-6
Process Control Block
 A block of data for
each process in the
system
 Contains all relevant
information about the
process
 Typical process
control block on the
right 
Chapter 15
The Internal Operating System – Part 1
15.1-7
Two Processes Sharing a
Single Program
Chapter 15
The Internal Operating System – Part 1
15.1-8
Process States
 Three primary process operating states
 Ready state
 Running state
 Blocked state




Dispatching - Move from ready state to running state
Wake-up - Move from blocked state to ready state
Time-out - Move from running state to ready state
Process completion
 killed, terminated, destroyed
 Additional states – suspend, swap
 Resumption – Move from suspended state to ready
state
Chapter 15
The Internal Operating System – Part 1
15.1-9
Process State Diagram
Chapter 15
The Internal Operating System – Part 1
15.1-10
Threads
 ‘Miniprocess’ that can be run independent of
other parts of the process
 Event-driven programs
 No control blocks
 Shares resources allocated to its parent process
including primary storage, files and I/O devices
 Advantage of process/thread families over
multiple independent processes:
 Reduced OS overhead for resource allocation and
process management
 Substantially less information than a normal PCB
Chapter 15
The Internal Operating System – Part 1
15.1-11
CPU Scheduling
High-level scheduling
Short-term scheduling
(dispatcher)
Mid-level scheduling
I/O scheduling
Chapter 15
The Internal Operating System – Part 1
Adding a program to the pool of
programs to be executed
Deciding which process shall be
executed next by the processor
Swapping processes
Deciding which process’s pending
I/O request shall be handled by an
available I/O device
15.1-12
Dispatching Objectives






Maximize throughput
Minimize turnaround time
Maximize CPU utilization
Maximize resource allocation
Promote graceful degradation
Provide minimal and consistent
response time
 Prevent starvation
Chapter 15
The Internal Operating System – Part 1
15.1-13
Nonpreemptive Dispatching
 First in, first out (FIFO)
 Unfair to short processes and I/O based
processes
 Shortest Job First (SJF)
 Longer jobs can be starved
 Priority Scheduling
 Dispatcher selects among jobs with the
same priorities
Chapter 15
The Internal Operating System – Part 1
15.1-14
Preemptive Dispatching
 Round robin
 Inherently fair and maximizes throughput
 Dynamic Priority
 Based on ratio of CPU time to total time process has been in
the system
 Smallest ratio has highest priority
 Linux, Windows 2000
Chapter 15
The Internal Operating System – Part 1
15.1-15
Preemptive Dispatching
 Multilevel feedback queues
 Favors short jobs, I/O bound jobs
 Each level assigns more CPU time
Chapter 15
The Internal Operating System – Part 1
15.1-16
Memory Management
 Memory Partitioning
 Fixed
 Variable

Best fit, first-fit, largest-fit algorithms
 Memory fragmentation
 Overlays
 Programs are divided into small logical pieces for
execution
 Pieces are loaded into memory as needed
 Memory Relocation
 Addresses have to be adjusted unless relative
addressing is used
Chapter 15
The Internal Operating System – Part 1
15.1-17
Memory Overlays
Chapter 15
The Internal Operating System – Part 1
15.1-18
Virtual Memory
 Virtual memory increases the apparent
amount of memory by using far less
expensive hard disk space
 Provides for process separation
 Demand paging
 Pages brought into memory as needed
 Page table
 Keeps track of what is in memory and what is still
out on hard disk
Chapter 15
The Internal Operating System – Part 1
15.1-19
Frames and Pages
Program
Memory
Unit
Page
Frame
Address
Logical
Physical
Size
2 to 4KB
2 to 4KB
Amount
# of bits in
Installed memory
instruction word
Chapter 15
The Internal Operating System – Part 1
15.1-20
Frames and Pages
Binary Paging
Chapter 15
The Internal Operating System – Part 1
15.1-21
Dynamic Address Translation
Chapter 15
The Internal Operating System – Part 1
15.1-22
Page Table
Page Frame
1
2
3
4
5
6
7
8
9
10
11
6
4
Pages not in main memory:
page fault when accessed
8
10
1
2
Disk
1
2
3
4
5
6
7
8
9
10 11
7
Swap space
Chapter 15
The Internal Operating System – Part 1
Virtual Memory Pages
15.1-23
Steps in
Handling a
Page Fault
Chapter 15
The Internal Operating System – Part 1
15.1-24
Locality of Reference
 Most memory references confined to small
region
 Well-written program in small loop, procedure or
function
 Data likely in array and variables stored
together
 Working set
 Number of pages sufficient to run program normally,
i.e., satisfy locality of a particular program
Chapter 15
The Internal Operating System – Part 1
15.1-25
Page Replacement Algorithms
 Page fault - page is not in memory and must
be loaded from disk
 Algorithms to manage swapping




First-In, First-Out FIFO – Belady’s Anomaly
Least Recently Used LRU
Least Frequently Used LFU
Not Used Recently NUR

Referenced bit, Modified (dirty) bit
 Second Chance Replacement algorithms
 Thrashing
 too many page faults affect system performance
Chapter 15
The Internal Operating System – Part 1
15.1-26
Virtual Memory Tradeoffs
Disadvantages
 SWAP file takes up space on disk
 Paging takes up resources of the CPU
Advantages
 Programs share memory space
 More programs run at the same time
 Programs run even if they cannot fit into
memory all at once
 Process separation
Chapter 15
The Internal Operating System – Part 1
15.1-27
Virtual Memory vs. Caching
 Cache speeds up memory access
 Virtual memory increases amount of
perceived storage
 Independence from the configuration and
capacity of the memory system
 Low cost per bit compared to main memory
Chapter 15
The Internal Operating System – Part 1
15.1-28
Secondary Storage Scheduling
 First-Come, First-Served
 Shortest Distance First
 Indefinite postponement problem
 Scan
 Middle of disk gets serviced twice
 N-Step C-Scan
 Disk seek in only one direction
 Return after last request in queue served
 Two queues


Queue of requests being processed
Queue of new requests
Chapter 15
The Internal Operating System – Part 1
15.1-29
Other OS Issues
 Deadlock
 Two processes have one another’s
resources that the other needs in order to
proceed
 Prevention
 Avoidance
 Detection and recovery
 Process Synchronization
Chapter 15
The Internal Operating System – Part 1
15.1-30
Java Virtual Machine
Chapter 15
The Internal Operating System – Part 1
15.1-31