chapter 6 Operating System in computer architecture support.ppt

describes the operating system architecture

1. OPERATING SYSTEM SUPPORT

2. Introduction
•The operating system (OS) is the software that controls
the execution of programs on a processor and that
manages the processor’s resources.
•One of the most important functions of the OS is the
scheduling of processes. The OS determines which
process should run at any given time.

3. Operating System Overview
•Another important OS function is memory management.
Most contemporary operating systems include a virtual
memory capability, which has two benefits:
a process can run in main memory without all of the
instructions and data for that program being present in
main memory at one time.
the total memory space available to a program may far
exceed the actual main memory on the system.
•OS can be thought of as having two objectives:
Convenience: An OS makes a computer more convenient
to use.
Efficiency: An OS allows the computer system resources
to be used in an efficient manner.

4. Operating System Overview
•The hardware and software used in providing applications to
a user can be viewed in a layered or hierarchical fashion, as
shown below.

5. Operating System Overview
•The end user, generally is not concerned with the
computer’s architecture. Thus the end user views a computer
system in terms of an application.
•To develop an application program as a set of processor
instructions and a set of systems programs named as utilities
can be used by a programmer.
•The most important system program is the OS. The OS
masks the details of the hardware from the programmer and
provides the programmer with a convenient interface for
using the system.

6. Operating System Overview
•OS typically provides services in the following areas:
Program creation: The OS provides a variety of facilities
and services to assist the programmer in creating programs.
Program execution: A number of tasks need to be
performed to execute a program. The OS handles this for the
user.
Access to I/O devices: Each I/O device requires its own
specific set of instructions or control signals for operation.
The OS takes care of the details.
Controlled access to files: In the case of a system with
multiple simultaneous users, the OS can provide protection
mechanisms to control access to the files.

7. Operating System Overview
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.

Error detection and response: A variety of errors such as
memory error or device failure, can occur while a computer
system is running. OS make response that clears error
condition with least impact on running application.
Accounting: A good OS will collect usage statistics for
various resources and monitor performance parameters
such as response time, to improve performance.

8. •A computer is a set of resources for the movement, storage,
and processing of data and for the control of these functions.
The OS is responsible for resource management.
•The OS functions in the same way as ordinary computer
software; that is, it is a program executed by the processor.
•Like other computer programs, it provides instructions for the
processor. The key difference is in the intent of the program.
•The OS frequently relinquishes control and must depend on
the processor to allow it to regain control.
•The OS directs the processor in the use of the other system
resources and in the timing of its execution of other programs.
Operating System Overview

9. •Following figure suggest main resources that are managed
by operating system.
Operating System Overview

10. Operating System Overview
•A portion of the OS is in main memory. This includes the
kernel, or nucleus, which contains the most frequently used
functions in the OS and, at a given time, other portions of the
OS currently in use.
•The remainder of main memory contains user programs and
data.
•The OS decides when an I/O device can be used by a
program in execution, and controls access to and use of files.
•The processor itself is a resource, and the OS must determine
how much processor time is to be devoted to the execution of
a particular user program.

11. •Certain key characteristics serve to differentiate various
types of operating systems. The characteristics fall along
two independent dimensions.
•The first dimension specifies whether the system is batch or
interactive.
Interactive: User/programmer interacts directly with
computer to request execution of a job or to perform a
transaction.
Batch: The user’s program is batched together with
programs from other users and submitted by a computer
operator.
Types of Operating System

12. •An independent dimension specifies whether the system
employs multiprogramming or not.
Multiprogramming: More than one program work at a
time (the attempt is made to keep the processor as busy
as possible).
Uniprogramming: Only one program works at a time.
Types of Operating System

13. •From late 1940s to mid 1950s, programmer interacted directly
with computer hardware, there was no operating system.
•These processors were run from a console, consisting of
display lights, toggle switches, some form of input device,
and a printer.
•Early systems presented two main problems:
Scheduling: It was hard to reserve processor time.
Setup time: A considerable amount of time was spent just
in setting up program to run.
•The wasted time due to scheduling and setup time was
unacceptable.
Early Systems

14. •To improve utilization, simple batch operating systems,
also called a monitor, were developed.
•With this system, the user no longer has direct access to the
processor.
•Rather, the user submits the job on cards or tape to a
computer operator, who batches the jobs together
sequentially and places the entire batch on an input device,
for use by the monitor.
•The monitor controls the sequence of events. Much of the
monitor must always be in main memory and available for
execution.
•That portion is referred to as the resident monitor.
Simple Batch Systems

15. •The monitor reads in jobs one at a time from the input device
(typically a card reader or magnetic tape drive). As it is read
in, the current job is placed in the user program area, and
control is passed to this job.
•When the job is completed, it returns control to the monitor,
which immediately reads in the next job. The results of each
job are printed out for delivery to the user.
•Monitor handles the scheduling problem. A batch of jobs is
queued up, and jobs are executed as rapidly as possible, with
no intervening idle time.
•The monitor also handles setup time. With each job,
instructions are provided to the monitor, by a special type of
programming language.
Simple Batch Systems

16. •Even with the automatic job sequencing provided by a simple
batch OS, the processor is often idle.
•The problem is that I/O devices are slow compared to the
processor.
•We know that there must be enough memory to hold the OS
(resident monitor) and one user program. Suppose that there is
room for the OS and two user programs. Now, when one job
needs to wait for I/O, the processor can switch to the other job,
which likely is not waiting for I/O.
•Furthermore, we might expand memory to hold three, four, or
more programs and switch among all of them.
•This technique is known as multiprogramming, or multitasking.
Multiprogramed Batch Systems

17. Uni-programming vs. Multiprogramming

18. Uni-programming vs. Multiprogramming

19. •To have several jobs ready to run, the jobs must be kept in
main memory, requiring some form of memory management.
•In addition, if several jobs are ready to run, the processor
must decide which one to run, which requires some algorithm
for scheduling.
•A better term than a job is process.
Scheduling

20. Scheduling
•There are four types of scheduling:
Long-term scheduling
Medium-term scheduling
Short-term scheduling
I/O scheduling

21. •Long-term scheduling
Determines which programs are admitted to system for
processing.
Controls degree of multiprogramming (number of
processes in memory).
Once admitted, a job or program becomes a process and
is added to a queue for short-term scheduler.
•Medium-term scheduling
Is part of swapping function.
Usually based on need to manage multiprogramming.
If there is no virtual memory, memory management is
also an issue.
Scheduling

22. •Short-term scheduler
•Also known as the dispatcher, executes frequently and
makes the fine-grained decision of which job to execute
next.
•Determines which process (of those permitted by high-
level scheduler) gets to execute next
Scheduling

23. •During lifetime of a process, its status change a number
of times. Its status at any time is referred as a state.
Scheduling

24. •There are five defined states for a process:
New: A program is admitted by high-level scheduler
but is not yet ready to execute.
Ready: Process is ready to execute and is awaiting
access to processor.
Running: Process is being executed by processor.
Blocked: Process is suspended from execution
waiting for some system resource such as I/O.
Exit: Process has terminated and will be destroyed by
operating system.
Scheduling

25. •For each process in the system, the OS
must maintain information indicating
the state of the process and other
information necessary for process
execution.
•For this purpose, each process is
represented in the OS by a process
control block (PCB).
Scheduling

26. •A process control block contains:
Identifier: Each current process has a unique identifier.
State: Current state of process (new, ready and so on).
Priority: Relative priority level.
Program counter: Address of next instruction in program to be
executed.
Memory pointers: Starting and ending locations of process in
memory.
Context data: These are data that are present in registers in
processor while process is executing.
I/O status information: Includes outstanding I/O requests, I/O
devices assigned to this process, a list of files assigned to process
and so on.
Accounting information: May include amount of processor time
and clock time used, time limits, account numbers and so on.
Scheduling

27. •When scheduler accepts a new job or user request for
execution it creates a blank process control block.
•It places associated process in new state.
•After system has properly filled in process control block,
process is transferred to ready state.
Scheduling

28. •To understand how the OS manages the scheduling of the
various jobs in memory, consider the example shown below.
Scheduling

29. •The figure shows how main memory is partitioned at a given point
in time. The kernel of the OS is, of course, always resident.
•In addition, there are a number of active processes, including A
and B, each of which is allocated a portion of memory.
•We begin at a point in time when process A is running. At some
later point in time, the processor ceases to execute instructions in
A and begins executing instructions in the OS area.
•This will happen for one of three reasons:
Process A issues a service call (e.g. an I/O request) to the OS.
Execution of A is suspended until this call is satisfied by the
OS.
Process A causes an interrupt (e.g. error, timeout).
Some event unrelated to process A that requires attention causes
an interrupt. An example is the completion of an I/O operation.
Scheduling

30. •The processor saves the current context data and the program
counter for A in A’s process control block and then begins
executing in the OS.
•The OS may perform some work, such as initiating an I/O
operation.
•Then the short-term-scheduler portion of the OS decides
which process should be executed next.
•In this example, B is chosen. The OS instructs the processor to
restore B’s context data and proceed with the execution of B
where it left off.
Scheduling

31. •Figure shows major elements of operating system involved in
multiprogramming and scheduling of processes.
•The OS receives control of the processor if an interrupt and a
service call occurs. Once the interrupt or service call is handled,
the short-term scheduler selects a process for execution.
Scheduling

32. •The OS maintains a number of queues. Each queue is simply a
waiting list of processes waiting for some resource.
•The long-term queue is a list of jobs waiting to use the
system. As conditions permit, the high-level scheduler will
allocate memory and create a process for one of the waiting
items.
•The short-term queue consists of all processes in the ready
state. Short-term scheduler picks one of these processes to use
the processor next.
•Finally, there is an I/O queue for each I/O device. More than
one process may request the use of the same I/O device. All
processes waiting to use each device are lined up in that
device’s queue.
Scheduling

33. •Figure suggest how processes progress through computer under
control of operating system.
Scheduling

34. Scheduling
•Each process request is placed in the long-term queue.
•As resources become available, a process request becomes a
process and is then placed in the ready state and put in the short-
term queue.
•The processor alternates between executing OS instructions and
executing user processes.
•While the OS is in control, it decides which process in the short-
term queue should be executed next.
•When the OS has finished its immediate tasks, it turns the
processor over to the chosen process.

35. Scheduling
•If a process requests I/O, it may be suspended and placed in
the appropriate I/O queue.
•If a timeout occurs for a process, then it may be suspended,
placed in the ready state and put into the short-term queue.
•When an I/O operation is completed, the OS removes the
satisfied process from that I/O queue and places it in the short-
term queue.
•It then selects another waiting process (if any) and signals for
the I/O device to satisfy that process’s request.

36. OPERATING SYSTEM
SUPPORT(cont.)

37. •In a uni-programming system, main memory is divided
into two parts; one part for operating system and one part
for program currently being executed.
•In a multiprogramming system, user part of memory is
subdivided to accommodate multiple processes. Task of
subdivision is carried out dynamically by operating system
and is known as memory management.
Memory Management

38. •Effective memory management is important in a
multiprogramming system.
•If only a few processes are in memory, then for much of
the time all of the processes will be waiting for I/O and the
processor will be idle.
•Thus, memory needs to be allocated efficiently to pack as
many processes into memory as possible.
•Several techniques are used for this purpose:
Swapping
Partitioning
Paging
Virtual Memory
Translation Lookaside Buffer
Segmentation
Memory Management

39. Memory Management
•Swapping
Even in multiprogramming system, CPU can be idle most
of time since I/O is so slow compared with CPU.
At some point, none of the processes in memory may be
in the ready state. Rather than remain idle, the processor
swaps one of these processes back out to disk into an
intermediate queue.
The OS then brings in another process from the
intermediate queue, or it selects new process request from
the long-term queue.
This process is known as swapping.

40. Memory Management
Swapping is represented in the following figure.

41. •Partitioning
Operating system occupies a fixed portion of main
memory. Remaining memory is partitioned among other
processes.
The simplest scheme for partitioning available memory is
to use fixed-size partitions.
Note that, although the partitions are of fixed size, they
need not be of equal size.
When a process is brought into memory, it is placed in the
smallest available partition that will hold it.
A more efficient approach is to use dynamic (variable-
size) partitions. When a process is brought into memory, it
is allocated exactly as much memory as it requires.
Memory Management

42. An example for fixed
size partitioning of a
64Mbyte memory is
shown in the figure.
Memory Management

43. •An example of dynamic partitioning using 64Mbyte memory is shown
below. Assume that 4 processes will be loaded into the memory that have
sizes 20Mb, 14Mb, 18Mb and 8Mb.
a)Initially main memory is empty except OS.
b)Process 1 is loaded into the memory.
c)Process 2 is loaded into the memory.
d)Process 3 is loaded and leaves a hole at end of memory that is too
small for fourth process.
Memory Management

44. e)Assume that at some point none of processes in memory is ready. OS
swaps out process 2 which leaves enough room to load process 4.
f)Since process 4 is smaller than process 2, another small hole is created.
g)Assume that none of processes in memory is ready but process 2 that is
swapped out is now ready to execute. OS swaps process 1 out.
h)Then, process 2 swapped back in result in creating another small hole.
Eventually there are a lot of small holes in memory.
Memory Management

45. •One technique to overcome this problem is compaction.
•From time to time, operating system shifts processes in
memory to place all free memory together in one block.
•This is a time consuming procedure and wasteful of processor
time.
•It is obvious that a process is not likely to be loaded into same
place in main memory each time it is swapped in.
•Furthermore, if compaction is used, a process may be shifted
while in the memory.
•A process in memory consists of instructions plus data.
•Instructions will contain addresses for memory locations.
•These addresses are not fixed. They will change each time a
process is swapped in.
Memory Management

46. •To solve this problem, a distinction is made between logical
addresses and physical addresses.
A logical address is expressed as a location relative to
beginning of program. Instructions in the program contain
only logical addresses.
A physical address is an actual location in main memory.
•When the processor executes a process, it automatically
converts from logical to physical address by adding the
current starting location of the process, called its base
address, to each logical address.
Memory Management

47. •Paging
Both unequal fixed-size and dynamic partitions are
inefficient in use of memory.
Suppose, memory is partitioned into equal fixed-size
chunks, called frames, and that each process is also
divided into small fixed-size chunks of same size, called
pages.
Then, pages could be assigned to available frames.
A list of free frames that can be assigned to new pages, is
also maintained by the OS.
Memory Management

48. Memory Management
The figure shows an example
for the use of pages and
frames.
At a given point in time,
some of frames in memory
are in use and some are free.
Process A, stored on disk,
consists of 4 pages.
When it comes time to load
this process, OS finds 4
frames and loads 4 pages of
process A into 4 frames.

49. •If there are not sufficient unused neighbouring frames to hold
process, does this prevent operating system from loading
process?
Answer is no, because we can use concept of logical
address.
But in this case, a simple base address will no longer
suffice. Instead operating system maintains a page table
for each process.
•Page table shows frame location for each page of process.
•Each logical address consists of a (page number, relative
address (offset)) and the processor uses the page table to
produce a physical address (frame number, relative address
(offset)).
Memory Management

50. Memory Management
•An example for logical
to physical address
conversion is shown in
the figure.

51. •Virtual Memory
Breaking a process into pages led to development of
another important concept known as virtual memory.
Virtual memory uses demand paging, which means each
page of a process is brought in only when it is needed, that
is, on demand.
It would clearly be wasteful to load in dozens of pages for
that process when only a few pages will be used before the
program is suspended.
If the program branches to an instruction on a page not in
main memory, or if the program references data on a page
not in memory, a page fault is triggered.
This tells the OS to bring in the desired page.
Memory Management

52. Thus, at any one time, only a few pages of any given process
are in memory, and therefore more processes can be
maintained in memory.
Furthermore, time is saved because unused pages are not
swapped in and out of memory.
When it brings one page in, it must throw another page out;
this is known as page replacement.
If it throws out a page just before it is about to be used, then it
will just have to go get that page again almost immediately.
Too much of this leads to a condition known as thrashing.
The processor spends most of its time swapping pages rather
than executing instructions.
The OS tries to guess, based on recent history, which pages
are least likely to be used in the near future.
Memory Management

53. Because of demand paging, it is possible for a process to be
larger than all of main memory.
A process executes only in main memory and that memory is
referred to as real memory.
A programmer or user perceives a much larger memory which
is allocated on the disk and it is referred to as virtual memory.
Memory Management

54. The basic mechanism for reading a word from memory
involves the translation of a virtual or logical address into a
physical address, using a page table.
Because the page table is of variable length, depending on the
size of the process, it must be stored in main memory to be
accessed.
The amount of memory devoted to page tables alone could be
unacceptably high. To overcome this problem, most virtual
memory schemes store page tables in virtual memory rather
than real memory.
Memory Management

55. Memory Management
An alternative approach for the use of page tables is the use of
an inverted page table structure.
Instead of having a page table for each process, a single inverted
page table that maps virtual addresses to physical addresses can
be used.
The table entries maps physical frames to (process ID, virtual
page number) pairs.

56. •Translation Lookaside Buffer (TLB)
Every virtual memory reference can cause two physical
memory accesses: one to fetch appropriate page table entry
and one to fetch desired data.
Thus a straightforward virtual memory scheme would
have the effect of doubling the memory access time.
To overcome this problem, most virtual memory schemes
make use of a special cache for page table entries usually
called translation lookaside buffer (TLB).
Memory Management

57. Memory Management
Operation of paging
and TLB is shown in
the figure.

58. Memory Management
Note that the virtual memory mechanism must interact with
the cache system.

59. Memory Management
The memory system consults the TLB to see if the matching
page table entry is present.
If it is, the real (physical) address is generated by combining
the frame number with the offset.
If not, the entry is accessed from a page table.
Once the real address is generated, which is in the form of a tag
and a remainder, the cache is consulted to see if the block
containing that word is present.
If so, it is returned to the processor.
If not, the word is retrieved from main memory.

60. •Segmentation
Segmentation allows programmer to view memory as
multiple address spaces or segments.
Elements are identified within a segment by their offset
from the beginning of the segment.
Logical address contains (segment number, offset).
Memory Management

61. To convert it to physical address, like page tables, segment
table is used.
An entry in this table contains (segment no, base address
of segment, length of segment).
Memory Management

62. •For example, consider the segment table shown below.
•Find the physical addresses for the following logical addresses
(segment no, offset):
a)(0, 198)
b)(2, 156)
c)(1, 530)
d)(3, 455)
e)(0, 252)
Memory Management
Segment noBase Address Length
0 660 248
1 1752 422
2 222 198
3 996 604

63. Logical address Physical address
a) (0, 198) 198 < 248 660 + 198 = 858
b) (2, 156) 156 < 198 222 + 156 = 378
c) (1, 530) Segment fault
d) (3, 455) 455 < 604 996 + 455 = 1451
e) (0, 252) Segment fault
•First of all, the offset value should be compared with the
corresponding segment length.
•If it is smaller, then the physical address can be calculated by
adding the offset to the base address of the segment.
•Otherwise, a segment fault should be triggered
Segment no Base Address Length
0 660 248
1 1752 422
2 222 198
3 996 604
Memory Management