CIS-512 WEEK 10 DISCUSSIONS
gabo22
ch18.pptxCHAPTER 18: The Internal Operating System
The Architecture of Computer Hardware, Systems Software & Networking: An Information Technology Approach
4th Edition, Irv Englander
John Wiley and Sons 2010
PowerPoint slides authored by Wilson Wong, Bentley University
PowerPoint slides for the 3rd edition were co-authored with Lynne Senne, Bentley College
Primary Kernel Functions
File manager translates logical file requests into specific physical I/O requests
I/O Control System (IOCS) performs resource allocation and device management
Memory management determines if it is possible to load programs and data into memory and if so where in memory
Scheduler allocates time for the program to execute
18-2
Copyright 2010 John Wiley & Sons, Inc.
Miniature Operating System
Block Diagram
Memory
Map
Process Dispatch
18-3
Copyright 2010 John Wiley & Sons, Inc.
Bootstrapping
Execution begins with bootstrap loader (mini-loader, IPL) stored in ROM
Looks for OS program in a fixed location (possibly on the network)
Loads OS into RAM
Transfers control to starting location of OS
Loader program in OS used to load and execute user programs
18-4
Copyright 2010 John Wiley & Sons, Inc.
4
Bootstrapping
Cold vs. warm boot (does not retest the system)
18-5
Copyright 2010 John Wiley & Sons, Inc.
5
Process (1)
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
18-6
Copyright 2010 John Wiley & Sons, Inc.
6
Process (2)
Process creation
Forking, spawning, cloning a new process
Parent and child processes
Process context
All relevant register data including the program counter
Allows interruption and restart invisibly
Copyright 2010 John Wiley & Sons, Inc.
18-7
Two Processes Sharing a Single Program
18-8
Copyright 2010 John Wiley & Sons, Inc.
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
18-9
Copyright 2010 John Wiley & Sons, Inc.
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
18-10
Copyright 2010 John Wiley & Sons, Inc.
Process State Diagram
18-11
Copyright 2010 John Wiley & Sons, Inc.
Threads
‘Miniprocess’ that can be run independent of other parts of the process
Event-driven programs
Shares resources allocated to its parent process including primary storage, files and I/O devices
Each thread has its own context
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
18-12
Copyright 2010 John Wiley & Sons, Inc.
12
Loading and Executing a Process
18-13
Copyright 2010 John Wiley & Sons, Inc.
CPU Scheduling
18-14
Copyright 2010 John Wiley & Sons, Inc.
14
Dispatching Objectives
Ensure Fairness
Maximize throughput
Minimize turnaround time
Maximize CPU utilization
Maximize resource allocation
Promote graceful degradation
Provide minimal and consistent response time
Prevent starvation
18-15
Copyright 2010 John Wiley & Sons, Inc.
15
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
Job with the highest priority is selected
If multiple jobs have the highest priority then dispatcher selects among them using FIFO
18-16
Copyright 2010 John Wiley & Sons, Inc.
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, XP, Vista, 7
18-17
Copyright 2010 John Wiley & Sons, Inc.
17
each process gets the same amount of time, simple and inherently fair, good on maximizing throughput, jobs penalized for IO,
UNIX variation - calculates a dynamic priority based on the ratio of CPU time to total time, if no jobs have IO this reduces to RR
Multi-level feedback - hybrid algorithm, favors short jobs, favors IO bound jobs, processes enter at the first queue, and are given almost immediate CPU access, if they don’t finish the first time through they are assigned to the second level queue,
Preemptive Dispatching
Multilevel feedback queues
Favors short jobs, I/O bound jobs
Each level assigns more CPU time
18-18
Copyright 2010 John Wiley & Sons, Inc.
Virtual Memory – Basic Ideas
Virtual memory increases the apparent amount of memory by using far less expensive hard disk space
Provides for process separation
Demand paging
Pages reside on hard disk and are brought into memory as needed
Page table
Keeps track of what is in memory and what is still out on hard disk
Inverted page table
Representation of physical memory with the page that resides in each frame
18-19
Copyright 2010 John Wiley & Sons, Inc.
19
Pages and Frames (1)
| Program | Memory | |
| Unit | Page | Frame |
| Address | Logical | Physical |
| Size | 2 to 4KB | 2 to 4KB |
| Amount | # of bits in instruction word | Installed memory |
18-20
Copyright 2010 John Wiley & Sons, Inc.
20
Pages and Frames (2)
Each program has its collection of pages.
The total number of pages can exceed the number of frames (physical memory).
A Simple Page Table Translation
Pages and Frames
18-21
Copyright 2010 John Wiley & Sons, Inc.
21
Page Translation Process
18-22
Copyright 2010 John Wiley & Sons, Inc.
Disk
Virtual Memory Pages
Page Frame
Pages not in main memory:
page fault when accessed
1
2
3
4
5
6
7
8
9
10
11
1
2
3
4
5
6
7
8
9
10
11
6
4
8
10
1
2
7
Page Table
Swap space
18-23
Copyright 2010 John Wiley & Sons, Inc.
23
Mapping for Three Processes
18-24
Copyright 2010 John Wiley & Sons, Inc.
Inverted Page Table
Inverted Page Table for the previous slide
The table represents what is in physical memory
18-25
Copyright 2010 John Wiley & Sons, Inc.
Steps in Handling a Page Fault
18-26
Copyright 2010 John Wiley & Sons, Inc.
26
Concept of Locality
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
18-27
Copyright 2010 John Wiley & Sons, Inc.
27
Page Replacement Algorithms
Page fault
Page is not in memory and must be loaded from disk
Algorithms to manage swapping
FIFO – First-In, First-Out
Belady’s Anomaly – when increasing number of pages results in more page faults
LRU – Least Recently Used
LFU – Least Frequently Used
NUR – Not Used Recently
Referenced bit
Modified (dirty) bit
Second Chance Replacement algorithms
Thrashing
too many page faults affect system performance
18-28
Copyright 2010 John Wiley & Sons, Inc.
28
Frame Lookup Procedures
18-29
Copyright 2010 John Wiley & Sons, Inc.
Segmentation
18-30
Copyright 2010 John Wiley & Sons, Inc.
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
18-31
Copyright 2010 John Wiley & Sons, Inc.
31
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
18-32
Copyright 2010 John Wiley & Sons, Inc.
32
Secondary Storage Scheduling
FCFS - 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
18-33
Copyright 2010 John Wiley & Sons, Inc.
Scan Scheduling Algorithm
18-34
Copyright 2010 John Wiley & Sons, Inc.
Comparison of Different Disk Algorithms
18-35
Copyright 2010 John Wiley & Sons, Inc.
Network OS Services
File transfer programs
Access to data files on other computers on the network
Computer naming scheme is required for some network systems
Print services
Print requests are redirected by the OS to the network station that manages the requested printer
Other peripheral sharing services
Web services
Messaging services
API network services
Security and network management services
Remote processing services
18-36
Copyright 2010 John Wiley & Sons, Inc.
Access for a Networked OS
18-37
Copyright 2010 John Wiley & Sons, Inc.
Other OS Issues
Deadlock
Two or more processes simultaneously have resources that are required by one another in order to proceed
Prevention
Avoidance
Detection and recovery
Process Synchronization
Required by cooperating processes when one process is dependent on the other
18-38
Copyright 2010 John Wiley & Sons, Inc.
Virtual Machines
Virtualization
Using a powerful computer to simulate a number of computers
Virtual machines
A simulated computer
Hypervisor
Layer of software and/or hardware that separates one or more operating systems from the hardware
Type 1 (native) – hypervisor software interfaces directly with the computer hardware
Type 2 (hosted) – hypervisor software runs as a program on the operating system
18-39
Copyright 2010 John Wiley & Sons, Inc.
Virtual Machine Configuration
18-40
Copyright 2010 John Wiley & Sons, Inc.
Copyright 2010 John Wiley & Sons
All rights reserved. Reproduction or translation of this work beyond that permitted in section 117 of the 1976 United States Copyright Act without express permission of the copyright owner is unlawful. Request for further information should be addressed to the Permissions Department, John Wiley & Sons, Inc. The purchaser may make back-up copies for his/her own use only and not for distribution or resale. The Publisher assumes no responsibility for errors, omissions, or damages caused by the use of these programs or from the use of the information contained herein.”
18-41
Copyright 2010 John Wiley & Sons, Inc.
High-level scheduling Adding a program to the pool of
programs to be executed
Short-term scheduling
(dispatcher)
Deciding which process shall be
executed next by the processor
Mid-level scheduling Swapping processes
I/O scheduling Deciding which process’s pending
I/O request shall be handled by an
available I/O device
Sheet1
| High-level scheduling | Adding a program to the pool of programs to be executed | |||
| Short-term scheduling (dispatcher) | Deciding which process shall be executed next by the processor | |||
| Mid-level scheduling | Swapping processes | |||
| I/O scheduling | Deciding which process’s pending I/O request shall be handled by an available I/O device |
