Transcript Operating Systems - UIIT-UIMS University of Arid

Advanced Operating
Systems
Dr. Anwar Majid Mirza
[email protected]
Lecture No. 1 (ii)
August 07, 2007
National University of Computer & Emerging Sciences
NUCES-FAST, A. K. Brohi Rd., H11, Islamabad, Pakistan
What is an Operating System?





A computer fresh off the assembly line, with no software in
place, can do absolutely nothing.
It cannot accept characters from the keyboard or display
characters on screen.
Faced with the raw “iron”, even experienced programmers
find it difficult to accomplish much, and non-technical
people are completely lost.
Pure hardware presents a most unfriendly interface. Thus,
people rarely communicate directly with the hardware.
Instead, users and application programmers deal with the
hardware through a system program called the Operating
System.
Layers and Views of a Computer System
End User
Programmer
Application Programs
Utilities
Operating System
Computer Hardware
Operating
System
Designer
Operating System Objectives and Functions

An operating system is a program that controls the execution of
application programs and acts as an interface between the user of a
computer and the computer hardware. Its three main objectives
are:
 Convenience: An operating system makes a computer more
convenient to use.
 Efficiency: An operating system allows the computer system
resources to be used in an efficient manner.
 Ability to Evolve: An operating system should be constructed
in such a way as to permit the effective development, testing
and introduction of new system functions without interfering
with service.
The Operating System as a
User/Computer Interface
The operating system typically provides the following services:
1.
Program Creation: The operating system provides a variety of
facilities and services, such as editors and debuggers, to assist the
programmer in creating programs. Typically these services are in
the form of utility programs that are not actually part of the
operating system but are accessible through the operating
system.
2.
Program Execution: A number of tasks need to be performed
to execute a program. Instructions and data must be loaded into
main memory, input/output devices and files must be initialized,
and other resources must be prepared. The OS handles all of this
for the user.
3.
Access to I/O Devices: Each I/O device requires its own
peculiar set of instructions or control signals for operation. The
operating system takes care of the details so that the programmer
can think in terms of simple reads and writes.
The Operating System as a
User/Computer Interface (continued…)
4.
5.
Controlled Access to Files: In the case of files, control
must include an understanding of not only the nature of the
I/O device (disk drive, CD ROM drive, tape drive) but also
the file format on the storage medium. Again, the OS
worries about the details. Further, in the case of a system
with multiple simultaneous users, the OS can provide
protection mechanisms to control access to the files.
System Access: In the case of a shared or public system,
the OS controls access to the system as a whole and to
specific system resources. The access function must provide
protection of resources and data from unauthorized users
and must resolve conflicts for resource contention.
The Operating System as a
User/Computer Interface (continued…)
6.
7.
Error Detection and Response: A variety of errors can occur
when a computer system is running. These include internal and
external hardware errors, such as a memory error or a device
failure or malfunction; and various software errors, such as
arithmetic overflow, attempt to access forbidden memory
location etc. In each case the OS must make the response that
clears the error condition with the least impact on running
applications. The response may range from ending the program
that caused the error, to retrying the operation, to simple
reporting the error to the application
Accounting: A good operating system will collect usage
statistics for various resources and monitor performance
parameters such as response time. On any system, this
information is useful in anticipating the need for future
enhancements and in tuning the system to improve performance.
On a multi-user system, the information can be used for billing
purposes.
The Operating System as a Resource Manager








A computer is a set of resources, for the movement, storage and
processing of data and for the control of these functions.
By managing the computer’s resources, the operating system is in
control of the computer’s basic functions. But this control is
exercised in a curious way!
The operating system is nothing more than a computer program.
Like other programs it provides instructions for the processor.
The key difference is in the intent of the program.
The operating system directs the processor in the use of other
system resources and in the timing of its execution of other
programs.
But in order for the processor to do any of these things, it must
cease executing the OS program and execute other programs.
Thus the OS relinquishes control for the processor to do some
“useful” work and then resumes control long enough to prepare
the processor to do the next piece of work.
Ease of Evolution of an Operating System
A major operating system will evolve over time for a number of
reasons:
1.
Hardware upgrades and new types of hardware: For
example, early versions of UNIX and OS/2 did not employ a
paging mechanism because they were run on machines without
paging hardware. More recent versions have been modified to
exploit paging capabilities. Also, the use of graphics terminals
and page-mode terminals instead of line-at-a-time scroll mode
terminals have affected the operating system design.
2.
New Services: In response to user demand or in response to
the needs of the system managers, the operating system will
expand to offer new services. For example, if it is found to be
difficult to maintain good performance for users with existing
tools, new measurements and control tools may be added to the
operating system.
3.
Fixes: Any operating system has faults. These are discovered
over the course of time, and fixes are made. Of course, the fixes
may introduce new faults.
Processes


The concept of process is fundamental to the structure
of operating systems.
Many definitions have been given for the term process,
including:
A
program in execution.
 The “animated spirit” of a program.
 The entity that can be assigned to and
executed on a processor.

All multiprogramming operating systems, from singleuser systems such as Windows NT to mainframe
systems such as MVS (Multiple Virtual Storage) that
can support thousands of users, are built around the
concept of the process.
Processes

1.
2.
3.
Many requirements that the operating system must
meet can all be expressed with reference to process:
The operating system must interleave the execution
of a number of processes to maximize processor use
while providing reasonable response time.
The operating system must allocate resources to a
process in conforming to a specific policy (e.g. certain
functions or applications are of higher priority) while
at the same time avoiding deadlocks.
The operating system may be required to support
inter-process communication and user creation of
processes, both of which may aid in the structuring of
applications.
Process States





The principle function of a processor is to execute machine
instructions residing in main memory.
From the processor point of view, it will execute
instructions from its collection of instructions in some
sequence dictated by the changing values in the register
known as the program counter (PC) or instruction
pointer.
Over time that pointer may refer to code in different
programs that are part of different applications.
The behavior of an individual process can be characterized
by listing the sequence of instructions that execute for that
process. Such a listing is called a trace of the process.
The behavior of the processor can be characterized by
showing the way in which the trace of the various processes
are interleaved!
Process States



Figure 1 shows a
memory layout of
three processes.
We assume no use
of “virtual memory”
i.e. all three
processes are
represented by
programs that are
fully loaded in main
memory.
There is a small
dispatcher program
that moves the
processor from one
process to another.
Main Memory
0K
Program
Counter
20K
35K
50K
80K
90K
140K
190K
Dispatcher
Process A
Process B
Process C
Fig.1: Snapshot of example execution
Process States



a+0
g+0
Figure 2 shows the
a+1
g+1
traces of the three
a+2
g+2
individual processes
a+3
g+3
during the early part
a+4
b+0
g+4
of their execution.
a+5
b+1
g+5
The first 12
a+6
b+2
g+6
instructions
a+7
b+3
g+7
executed in
a+8
g+8
processes A and C
a+9
g+9
are shown.
a+10
g+10
Process B executes 4
a+11
g+11
instructions and it is
assumed that the
(a) Trace of (b) Trace of (c) Trace of
fourth instruction is
Process A
Process B
Process C
an I/O operation
a, b and g are the starting addresses of the
for which the
process must wait. programs of processes A, B and C respectively.
Fig.2: Trace of Processes
Process States


Figure 3 shows the
traces from the
processor’s point
of view.
We have assumed
that the OS allows
a process to
continue execution
for a maximum of
only six
instructions cycles
after which it is
interrupted; this
prevents any single
process from
monopolizing
processor time!
1 a+0
2 a+1
3 a+2
4 a+3
5 a+4
6 a+5
…Time Out
7 d+0
8 d+1
9 d+2
10 d+3
11 d+4
12 d+5
13 b+0
14 b+1
15 b+2
16 b+3
…Time Out
17 d+0
18 d+1
19 d+2
20 d+3
21 d+4
22 d+5
23 g+0
24 g+1
25 g+2
26 g+3
27 g+4
28 g+5
…Time Out
29 d+0
30 d+1
31 d+2
32 d+3
33 d+4
34 d+5
35 a+6
36 a+7
37 a+8
38 a+9
39 a+10
40 a+11
…Time Out
41 d+0
42 d+1
43 d+2
44 d+3
45 d+4
46 d+5
47 g+6
48 g+7
49 g+8
50 g+9
51 g+10
52 g+11
…Time Out
Fig.3: Combined Trace of Processes
A Two-State Process Model




To be able to “design” the operating system
effectively, we need to have a clear model of the
behavior of a process.
The first step in designing a program to control
processes is to describe the behavior that we would
like the processes to exhibit.
The simplest possible model can constructed by
observing that at any time, a process is either being
executed by a processor or not.
Thus a process may be in one of the two states:
Running and Not-Running
A Two-State Process Model
Dispatch
Enter
Not
Running
Running
Exit
Pause
(a) State transition diagram
Enter
Queue
Dispatch
Processor
Pause
(b) Queuing diagram
Exit
A Two-State Process Model
When the OS creates a new process, it enters that process into the
system in the Not-Running state.

Thus the process exists, is know to the OS, and is waiting for an
opportunity to execute.

From time to time, the currently running process will be interrupted,
and the dispatcher portion of the OS will select a new process and put
in the Running state.

The former process moves from the Running state to the NotRunning state, and one of the other processes moves to the running
state.
Design Issues / Points:

Each process must be represented in some way so that the OS can
keep track of it (e.g. its current state and location in memory).

Those processes that are in Not-Running state, are needed to be kept
in some sort of queue, waiting their turn.

The Creation and Termination of Processes
Regardless of the model of process behavior used,
the life of process is bounded by its creation and
termination.
Creation of Processes
 When a new process is to be added to those that are
currently being managed by the OS, the OS




Builds the data structures that are used to manage the
process and
Allocates the address space to be used by the process.
These actions constitute the creation of a new
process.
The Creation and Termination of Processes
Reasons for Process Creation
1.
2.
3.
4.


New Batch Job: In a batch environment, a process is created in
response to the submission of a job.
Interactive Log On: A user at a terminal logs onto the system
Created by OS to Provide a Service: The OS can create a process to
perform a function on behalf of a user program, without the user
having to wait e.g. printing.
Spawned by Existing Processes: For purposes of modularity or to
exploit parallelism, a user program can dictate the creation of a
number of processes. When a process is created by the OS at the
explicit request of another process, the action is referred as process
spawning.
When one process spawns another process, the spawning process is called the parent process
and the spawned process is called the child process.
Typically, the “related” processes need to “communicate” and “cooperate” with each other.
Achieving this cooperation is a difficult task for the programmers of the OS.
The Creation and Termination of Processes
Termination of Process



In any computer system, there must be a means for a process to
indicate its completion.
A batch job should indicate a “Halt” instruction, which generates an
interrupt to alert the operating system that a process has completed.
For an interactive application, the action of the user will indicate when
the process is completed.
Reasons for Process Termination
1.
Normal Termination: The process executes an OS service call to
indicate that it has completed running.
2.
Time Limit Exceeded: The process has run longer than the
specified total time limit. There are a number of possibilities for the
type of time that is measured. These include (i) total time elapsed, (ii)
amount of time spent executing, and (iii) in case of an interactive
process, the amount of time since the user last provided any input.
The Creation and Termination of Processes
Reasons for Process Termination (continued…)
3.
Memory Unavailable: The process requires more memory than
the system can provide.
4.
Bounds Violation: The process tries to access memory locations
that it is not allowed to access.
5.
Protection Error: The process attempts to use a resource or a file
that it is not allowed to use, or it tries to use it in an improper fashion,
such as writing to a read-only file.
6.
Arithmetic Error: The process tries a prohibited computation,
such as division by zero!
7.
Time Overrun: The process has waited longer than a specified
maximum for a certain event to occur.
The Creation and Termination of Processes
Reasons for Process Termination (continued…)
8.
An I/O Failure: An error occurs in input or output, such as
inability to find a file, failure to read or write after specified
number of tries (when, for example, a defective area is
encountered on a diskette), or invalid operation (such as reading
from the line printer).
9.
Invalid Instruction: The process attempts to execute a nonexistent instruction (often a result of branching into a data area
and attempting to execute the data).
10.
Privileged Instruction: The Process attempts to use an
instruction reserved for the operating system.
The Creation and Termination of Processes
Reasons for Process Termination (continued…)
11.
Data Misuse: A piece of data is of the wrong type or is not
initialized.
12.
OS or Operator Intervention: For some reason, the
operator or the operating system has terminated the process (e.g.
if a deadlock exists).
13.
Parent Termination: When a parent terminates, the operating
system may be designed to automatically terminate all the
offspring of that parent.
14.
Parent Request: A parent process typically has the authority to
terminate any of its offpring.
A Five-State Process Model





The queue in the two state process model, is a first-in-firstout (FIFO) list, and the processor operates in round-robin
fashion on the available processes (each process in the
queue is given a certain amount of time to execute and then
returned to the queue unless blocked).
It must be noticed that some processes in the Not-Running
state are “ready to execute”, whereas others are
“blocked”, waiting an I/O operation to complete.
Thus, using a single queue, the dispatcher could not just
select the process at the oldest end of the queue.
Rather, the dispatcher would have to scan the list looking
for the process that is not blocked that has been in the
queue the longest.
A more natural way is to split the Not-Running state into
two states: Ready and Blocked.
Five-State Process Model
New
Release
Dispatch
Enter
Running
Ready
Time-out
Event
Occurs
Blocked
Event
Wait
State Transition Diagram
Exit
A Five-State Process Model
The five states in this model are

Running: The process is currently being executed.

Ready: Processes that prepared to execute when given
opportunity.

Blocked: A process that cannot execute until some event
occurs, such as completion of an I/O operation.

New: A process that has just been created but has not yet
been admitted to the pool of executable processes by the
operating system.

Exit: A process that has been released from the pool of
executable processes by the OS, either because it halted or
because it aborted for some reason.
Five State Process Model
Admit
Ready Queue
Dispatch
Processor
Time-out
Event-wait
Event
Occur
Block Queue
Queuing diagram with single blocked queue
Release
A Five-State Process Model








In the queuing diagram, now there are two queues: a Ready-Queue
and a Blocked-Queue.
When it is time for the operating system to choose another process to
run, it selects one from the Ready queue. In the absence of any
priority scheme, this can be a simple FIFO queue.
When a running program is removed from execution, it is either
terminated or placed in the Ready or Blocked queue, depending on the
circumstances.
Finally when an event occurs, all processes in the Blocked queue that
waiting on that event are moved to the Ready queue.
This latter arrangement means that, when an event occurs, the
operating system must scan the entire Blocked queue, searching for
those processes waiting on that event.
In a large operating system, there could be hundreds or even
thousands of processes in that queue.
Therefore it would more efficient to have a number of queues, one for
each event.
Then, when the event occurs, the entire list of processes in the
appropriate queue can be moved to the Ready queue.
Admit
Ready Queue
Dispatch
Processor
Release
Time-out
Event 1 - wait
Event 1
Occur
Block Queue 1
Event 2
Occur
Event 2 - wait
Block Queue 2
Event n - wait
Event n
Occur
Block Queue n
Queuing diagram with multiple blocked queue
A Five-State Process Model


Finally: if the dispatching of processes is dictated by
a priority scheme, then it is convenient to have a
number of Ready queues, one for each priority
level.
The operating system can then readily determine
which is the highest priority Ready process that has
been waiting the longest.
Suspended Processes
The Need for Swapping

The three principal states that have been described (Ready, Running,
Blocked) provide a systematic way of modeling the behavior of
processes and guide the implementation of the OS.

Many operating systems are constructed using only these three states.

However, there is good justification for adding additional states to the
model.
Even with multi-programming, a processor could be idle most of the
time.

Consider a system that does not employ virtual memory. Then each
process to be executed must be loaded fully into main memory.

Thus, in the multiple blocked queuing model, all the processes in all
the queues must be resident in main memory.

Recall, that the reason for all this elaborate machinery is that I/O
activities are much slower than computation, and therefore, the
processor in a “uni-programming” system is idle most of the time.
Suspended Processes
The Need for Swapping
 But the above arrangement does not entirely solve
the problem.
 It is true that in this case memory holds multiple
processes and that the processor can move to
another process when one process is waiting.
 But the processor is so much faster than I/O that it
will be common for all the processes in the memory
for waiting for an I/O.
 Thus even with multi-programming, a processor
could be idle most of the time.
Solutions:
Suspended
1.
Expand the main memory

There are two flaws in this approach:


1.





Processes
There is a cost associated with memory.
Appetite of programs for memory has grown as fast as the cost of memory has
dropped. So larger main memory results in “larges processes” not “more
processes”
Swapping
Moving part or all of a process from main memory to disk.
When none of the processes in main memory is in the “Ready state”,
the OS swaps one of the “blocked processes” out onto disk, into a
“suspend queue”.
Suspend queue is a queue of existing processes that have been
temporarily kicked out of the main memory or suspended.
The OS then brings another process from the suspend queue, or it
honors a new-process request. Execution then continues with the
newly arrived process.
Swapping, however, is an I/O operation, and therefore, there is the
potential for making the problem worse, not better. But because, disk
I/O is generally the fastest I/O on a system (e.g. compared with a
printer I/O) swapping will usually enhance performance.
Need for including more states in the process model
One additional state must be added in the process model to take into
account the swapping.
New
Activate
Suspend
Release
Dispatch
Enter
Ready
Running
Exit
Time-out
Event
Occurs
Event
Wait
Blocked
Suspend
Process state model with
one suspend state
• When all the processes in main memory are in the “Blocked state”, the OS can suspend
one process by putting it in the “Suspend state” and transferring it to the disk.
•The space that is freed up in main memory can then be used to bring another process.
Suspended Processes
When the OS has performed a swapping-out operation, it has two
choices for selecting a process to bring it into main memory:
1.
It can admit a newly created process or
2.
It can bring in a previously suspended process.

It would appear that the preference should be given to bring a
previously suspended process to provide it with service, rather than
increasing the total load on the system.
Difficulty
The above line of reasoning presents a difficulty.

All the processes that have been suspended were in the Blocked state
at the time of suspension.

It clearly, would not do any good to bring a Blocked process back into
main memory, because it is still not ready for execution.

Recall, that each process in the suspend state was originally blocked on
particular event. When that event occurs, the process is not blocked
and is potentially available for execution.

Suspended Processes
Thus we need the following four states:
 Ready: The process is in main memory and
available for execution.
 Blocked: The process is in main memory and
awaiting an event.
 Blocked, Suspend: The process is in secondary
memory and awaiting an event.
 Ready, Suspend: The process is in secondary
memory but is available for execution as soon as it is
loaded into main memory.
Suspended Processes
New
Enter
Ready
Suspend
Suspend
Enter
Activate
Release
Dispatch
Ready
Running
Suspend
Time-out
Event
Event
Occurs
Occurs
Event
Activate
Wait
Blocked
Blocked
Suspend
Suspend
Process state model with two suspend states
Exit
Reasons for Process Suspension





Swapping: The OS need to release sufficient main memory
to bring in a process that is ready to execute,
Interactive user request: A user may wish to suspend
execution of a program for purposes of debugging or in
connection with the use of a resource.
Timing: A process may be executed periodically (e.g. an
accounting or system monitoring process) and may be
suspended while waiting for the next time interval.
Parent process request: A parent process may wish to
suspend execution of a descendent to examine or modify
the suspended process, or to coordinate the activity of
various descendants.
Other OS reason: The OS may suspend a background or
utility process or a process that is suspected of causing a
problem.