System Programming & Operating System TE Computer Engineering

UNIT – V
MEMORY MANAGEMENT
Memory management: Contiguous and non-contiguous, Swapping, Paging, Segmentation,
Segmentation with Paging. Virtual Memory: Background, Demand paging, Page replacement
scheme- FIFO, LRU, Optimal, Thrashing.
.

INTRODUCTION :
Memory management is the functionality of an operating system which handles or manages
primary memory and moves processes back and forth between main memory and disk during
execution. Memory management keeps track of each and every memory location, regardless of
either it is allocated to some process or it is free. It checks how much memory is to be allocated
to processes. It decides which process will get memory at what time. It tracks whenever some
memory gets freed or unallocated and correspondingly it updates the status.

 80386 Register

The 80386 contains a total of sixteen registers that are of interest to the applications programmer.
As Figure 2-5 shows, these registers may be grouped into these basic categories:

1. General registers. These eight 32-bit general-purpose registers are used primarily to
contain operands for arithmetic and logical operations.
2. Segment registers. These special-purpose registers permit systems software designers to
choose either a flat or segmented model of memory organization. These six registers
determine, at any given time, which segments of memory are currently addressable.
3. Status and instruction registers. These special-purpose registers are used to record and
alter certain aspects of the 80386 processor state.

2.3.1 General Registers

The general registers of the 80386 are the 32-bit registers EAX, EBX, ECX, EDX, EBP, ESP,
ESI, and EDI. These registers are used interchangeably to contain the operands of logical and
arithmetic operations. They may also be used interchangeably for operands of address
computations (except that ESP cannot be used as an index operand).

As Figure 2-5 shows, the low-order word of each of these eight registers has a separate name and
can be treated as a unit. This feature is useful for handling 16-bit data items and for compatibility
with the 8086 and 80286 processors. The word registers are named AX, BX, CX, DX, BP, SP,
SI, and DI.

Figure 2-5 also illustrates that each byte of the 16-bit registers AX, BX, CX, and DX has a
separate name and can be treated as a unit. This feature is useful for handling characters and

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 1

System Programming & Operating System TE Computer Engineering

other 8-bit data items. The byte registers are named AH, BH, CH, and DH (high bytes); and AL,
BL, CL, and DL (low bytes).

All of the general-purpose registers are available for addressing calculations and for the results of
most arithmetic and logical calculations; however, a few functions are dedicated to certain
registers. By implicitly choosing registers for these functions, the 80386 architecture can encode
instructions more compactly. The instructions that use specific registers include: double-
precision multiply and divide, I/O, string instructions, translate, loop, variable shift and rotate,
and stack operations.

2.3.2 Segment Registers

The segment registers of the 80386 give systems software designers the flexibility to choose
among various models of memory organization. Implementation of memory models is the
subject of Part II -- Systems Programming. Designers may choose a model in which applications
programs do not need to modify segment registers, in which case applications programmers may
skip this section.

Complete programs generally consist of many different modules, each consisting of instructions
and data. However, at any given time during program execution, only a small subset of a
program's modules are actually in use. The 80386 architecture takes advantage of this by
providing mechanisms to support direct access to the instructions and data of the current
module's environment, with access to additional segments on demand.

At any given instant, six segments of memory may be immediately accessible to an executing
80386 program. The segment registers CS, DS, SS, ES, FS, and GS are used to identify these six
current segments. Each of these registers specifies a particular kind of segment, as characterized
by the associated mnemonics ("code," "data," or "stack") shown in Figure 2-6 . Each register
uniquely determines one particular segment, from among the segments that make up the
program, that is to be immediately accessible at highest speed.

The segment containing the currently executing sequence of instructions is known as the current
code segment; it is specified by means of the CS register. The 80386 fetches all instructions from
this code segment, using as an offset the contents of the instruction pointer. CS is changed
implicitly as the result of intersegment control-transfer instructions (for
example, CALL and JMP), interrupts, and exceptions.

Subroutine calls, parameters, and procedure activation records usually require that a region of
memory be allocated for a stack. All stack operations use the SS register to locate the stack.
Unlike CS, the SS register can be loaded explicitly, thereby permitting programmers to define
stacks dynamically.

The DS, ES, FS, and GS registers allow the specification of four data segments, each addressable
by the currently executing program. Accessibility to four separate data areas helps programs
efficiently access different types of data structures; for example, one data segment register can
point to the data structures of the current module, another to the exported data of a higher-level
module, another to a dynamically created data structure, and another to data shared with another
task. An operand within a data segment is addressed by specifying its offset either directly in an
instruction or indirectly via general registers.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 2

System Programming & Operating System TE Computer Engineering

Depending on the structure of data (e.g., the way data is parceled into one or more segments), a
program may require access to more than four data segments. To access additional segments, the
DS, ES, FS, and GS registers can be changed under program control during the course of a
program's execution. This simply requires that the program execute an instruction to load the
appropriate segment register prior to executing instructions that access the data.

The processor associates a base address with each segment selected by a segment register. To
address an element within a segment, a 32-bit offset is added to the segment's base address. Once
a segment is selected (by loading the segment selector into a segment register), a data
manipulation instruction only needs to specify the offset. Simple rules define which segment
register is used to form an address when only an offset is specified.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 3

System Programming & Operating System TE Computer Engineering

2.3.3 Stack Implementation

Stack operations are facilitated by three registers:

1. The stack segment (SS) register. Stacks are implemented in memory. A system may have
a number of stacks that is limited only by the maximum number of segments. A stack
may be up to 4 gigabytes long, the maximum length of a segment. One stack is directly
addressable at a -- one located by SS. This is the current stack, often referred to simply as
"the" stack. SS is used automatically by the processor for all stack operations.
2. The stack pointer (ESP) register. ESP points to the top of the push-down stack (TOS). It
is referenced implicitly by PUSH and POP operations, subroutine calls and returns, and
interrupt operations. When an item is pushed onto the stack (see Figure 2-7 ), the
processor decrements ESP, then writes the item at the new TOS. When an item is popped
off the stack, the processor copies it from TOS, then increments ESP. In other words, the
stack grows down in memory toward lesser addresses.
3. The stack-frame base pointer (EBP) register. The EBP is the best choice of register for
accessing data structures, variables and dynamically allocated work space within the
stack. EBP is often used to access elements on the stack relative to a fixed point on the
stack rather than relative to the current TOS. It typically identifies the base address of the
current stack frame established for the current procedure. When EBP is used as the base
register in an offset calculation, the offset is calculated automatically in the current stack
segment (i.e., the segment currently selected by SS). Because SS does not have to be
explicitly specified, instruction encoding in such cases is more efficient. EBP can also be
used to index into segments addressable via other segment registers.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 4

System Programming & Operating System TE Computer Engineering

2.3.4 Flags Register

The flags register is a 32-bit register named EFLAGS. Figure 2-8 defines the bits within this
register. The flags control certain operations and indicate the status of the 80386.

The low-order 16 bits of EFLAGS is named FLAGS and can be treated as a unit. This feature is
useful when executing 8086 and 80286 code, because this part of EFLAGS is identical to the
FLAGS register of the 8086 and the 80286.

The flags may be considered in three groups: the status flags, the control flags, and the systems
flags. Discussion of the systems flags is delayed until Part II.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 5

System Programming & Operating System TE Computer Engineering

[Link] Status Flags

The status flags of the EFLAGS register allow the results of one instruction to influence later
instructions. The arithmetic instructions use OF, SF, ZF, AF, PF, and CF. The SCAS (Scan
String), CMPS(Compare String), and LOOP instructions use ZF to signal that their operations
are complete. There are instructions to set, clear, and complement CF before execution of an
arithmetic instruction. Refer to Appendix C for definition of each status flag.

[Link] Control Flag

The control flag DF of the EFLAGS register controls string instructions. DF (Direction Flag, bit
10) Setting DF causes string instructions to auto-decrement; that is, to process strings from high
addresses to low addresses. Clearing DF causes string instructions to auto-increment, or to
process strings from low addresses to high addresses.

[Link] Instruction Pointer

The instruction pointer register (EIP) contains the offset address, relative to the start of the
current code segment, of the next sequential instruction to be executed. The instruction pointer is
not directly visible to the programmer; it is controlled implicitly by control-transfer instructions,
interrupts, and exceptions.

As Figure 2-9 shows, the low-order 16 bits of EIP is named IP and can be used by the processor
as a unit. This feature is useful when executing instructions designed for the 8086 and 80286
processors.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 6

System Programming & Operating System TE Computer Engineering

 Basic Memory Management :

Main Memory Management Let us begin by examining the issues that prompt the main
memory management.
Allocation: First of all the processes that are scheduled to run must be resident in the
memory. These processes must be allocated space in main memory.

Swapping, fragmentation and compaction: If a program is moved out or terminates, it

creates a hole, (i.e. a contiguous unused area) in main memory. When a new process is to
be moved in, it may be allocated one of the available holes. It is quite possible that main
memory has far too many small holes at a certain time. In such a situation none of these
holes is really large enough to be allocated to a new process that may be moving in. The
main memory is too fragmented. It is, therefore, essential to attempt compaction.
Compaction means OS re-allocates the existing programs in contiguous regions and
creates a large enough free area for allocation to a new process.

Garbage collection: Some programs use dynamic data structures. These programs
dynamically use and discard memory space. Technically, the deleted data items (from a
dynamic data structure) release memory locations. However, in practice the OS does not
collect such free space immediately for allocation. as specialized files. Their buffers need
to be managed within main memory alongside the other processes. The considerations
stated above motivate the study of main memory managementSuch areas, therefore, are
called garbage. When such garbage exceeds a certain threshold, the OS would not have
enough memory available for any further allocation. This entails compaction (or garbage
collection), without severely affecting performance.

Protection: With many programs residing in main memory it can happen that due to a
programming error (or with malice) some process writes into data or instruction area of
some other process. The OS ensures that each process accesses only to its own allocated
area, i.e. each process is protected from other processes.

Virtual memory: Often a processor sees a large logical storage space (a virtual storage
space) though the actual main memory may not be that large. So some facility needs to be
provided to translate a logical address available to a processor into a physical address to
access the desired data or instruction.

IO support: Most of the block-oriented devices are recognized as specialized files. Their
buffers need to be managed within main memory alongside the other processes. The
considerations stated above motivate the study of main memory management.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 7

System Programming & Operating System TE Computer Engineering

 Memory allocation algorithms. :

1. First Fit
2. Best fit
3. Worst fit
4. Best fit: The allocator places a process in the smallest block of unallocated memory in
which it will fit. For example, suppose a process requests 12KB of memory and the
memory manager currently has a list of unallocated blocks of 6KB, 14KB, 19KB, 11KB,
and 13KB blocks. The best-fit strategy will allocate 12KB of the 13KB block to the
process.

5. Worst fit: The memory manager places a process in the largest block of unallocated
memory available. The idea is that this placement will create the largest hold after the
allocations, thus increasing the possibility that, compared to best fit, another process can
use the remaining space. Using the same example as above, worst fit will allocate 12KB
of the 19KB block to the process, leaving a 7KB block for future use.

6. First fit: There may be many holes in the memory, so the operating system, to reduce the
amount of time it spends analyzing the available spaces, begins at the start of primary
memory and allocates memory from the first hole it encounters large enough to satisfy
the request. Using the same example as above, first fit will allocate 12KB of the 14KB
block to the process.

Primary
Best fit Worst fit First fit
Memory

Notice in the diagram above that the Best fit and First fit strategies both leave a tiny segment of
memory unallocated just beyond the new process. Since the amount of memory is small, it is not
likely that any new processes can be loaded here. This condition of splitting primary memory
into segments as the memory is allocated and deallocated is known as fragmentation. The Worst
fit strategy attempts to reduce the problem of fragmentation by allocating the largest fragments to
new processes. Thus, a larger amount of space will be left as seen in the diagram above.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 8

System Programming & Operating System TE Computer Engineering

Basic Hardware(basic memory concepts) :

 It should be noted that from the memory chips point of view, all memory accesses are
equivalent. The memory hardware doesn't know what a particular part of memory is
being used for, nor does it care. This is almost true of the OS as well, although not
entirely.
 The CPU can only access its registers and main memory. It cannot, for example, make
direct access to the hard drive, so any data stored there must first be transferred into the
main memory chips before the CPU can work with it. ( Device drivers communicate with
their hardware via interrupts and "memory" accesses, sending short instructions for
example to transfer data from the hard drive to a specified location in main memory. The
disk controller monitors the bus for such instructions, transfers the data, and then notifies
the CPU that the data is there with another interrupt, but the CPU never gets direct access
to the disk. )
 Memory accesses to registers are very fast, generally one clock tick, and a CPU may be
able to execute more than one machine instruction per clock tick.
 Memory accesses to main memory are comparatively slow, and may take a number of
clock ticks to complete. This would require intolerable waiting by the CPU if it were not
for an intermediary fast memory cache built into most modern CPUs. The basic idea of
the cache is to transfer chunks of memory at a time from the main memory to the cache,
and then to access individual memory locations one at a time from the cache.
 User processes must be restricted so that they only access memory locations that
"belong" to that particular process. This is usually implemented using a base register and
a limit register for each process, as shown in Figures 8.1 and 8.2 below. Every memory
access made by a user process is checked against these two registers, and if a memory
access is attempted outside the valid range, then a fatal error is generated. The OS
obviously has access to all existing memory locations, as this is necessary to swap users'
code and data in and out of memory. It should also be obvious that changing the contents
of the base and limit registers is a privileged activity, allowed only to the OS kernel.

Figure 8.1 - A base and a limit register define a logical addresss space

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 9

System Programming & Operating System TE Computer Engineering

Figure 8.2 - Hardware address protection with base and limit registers

8.1.2 Address Binding

 User programs typically refer to memory addresses with symbolic names such as "i",
"count", and "averageTemperature". These symbolic names must be mapped or bound to
physical memory addresses, which typically occurs in several stages:
o Compile Time - If it is known at compile time where a program will reside in
physical memory, then absolute code can be generated by the compiler,
containing actual physical addresses. However if the load address changes at
some later time, then the program will have to be recompiled. DOS .COM
programs use compile time binding.
o Load Time - If the location at which a program will be loaded is not known at
compile time, then the compiler must generate relocatable code, which references
addresses relative to the start of the program. If that starting address changes, then
the program must be reloaded but not recompiled.
o Execution Time - If a program can be moved around in memory during the
course of its execution, then binding must be delayed until execution time. This
requires special hardware, and is the method implemented by most modern OSes.
 Figure 8.3 shows the various stages of the binding processes and the units involved in
each stage:

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 10

System Programming & Operating System TE Computer Engineering

Figure 8.3 - Multistep processing of a user program

8.1.3 Logical Versus Physical Address Space

 The address generated by the CPU is a logical address, whereas the address actually seen
by the memory hardware is a physical address.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 11

System Programming & Operating System TE Computer Engineering

 Addresses bound at compile time or load time have identical logical and physical
addresses.
 Addresses created at execution time, however, have different logical and physical
addresses.
o In this case the logical address is also known as a virtual address, and the two
terms are used interchangeably by our text.
o The set of all logical addresses used by a program composes the logical address
space, and the set of all corresponding physical addresses composes the physical
address space.
 The run time mapping of logical to physical addresses is handled by the memory-
management unit, MMU.
o The MMU can take on many forms. One of the simplest is a modification of the
base-register scheme described earlier.
o The base register is now termed a relocation register, whose value is added to
every memory request at the hardware level.
 Note that user programs never see physical addresses. User programs work entirely in
logical address space, and any memory references or manipulations are done using purely
logical addresses. Only when the address gets sent to the physical memory chips is the
physical memory address generated.

Figure 8.4 - Dynamic relocation using a relocation register

8.1.4 Dynamic Loading

 Rather than loading an entire program into memory at once, dynamic loading loads up
each routine as it is called. The advantage is that unused routines need never be loaded,
reducing total memory usage and generating faster program startup times. The downside

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 12

System Programming & Operating System TE Computer Engineering

is the added complexity and overhead of checking to see if a routine is loaded every time
it is called and then then loading it up if it is not already loaded.

8.1.5 Dynamic Linking and Shared Libraries

 With static linking library modules get fully included in executable modules, wasting
both disk space and main memory usage, because every program that included a certain
routine from the library would have to have their own copy of that routine linked into
their executable code.
 With dynamic linking, however, only a stub is linked into the executable module,
containing references to the actual library module linked in at run time.
o This method saves disk space, because the library routines do not need to be fully
included in the executable modules, only the stubs.
o We will also learn that if the code section of the library routines is reentrant,
( meaning it does not modify the code while it runs, making it safe to re-enter it ),
then main memory can be saved by loading only one copy of dynamically linked
routines into memory and sharing the code amongst all processes that are
concurrently using it. ( Each process would have their own copy of
the data section of the routines, but that may be small relative to the code
segments. ) Obviously the OS must manage shared routines in memory.
o An added benefit of dynamically linked libraries ( DLLs, also known as shared
libraries or shared objects on UNIX systems ) involves easy upgrades and
updates. When a program uses a routine from a standard library and the routine
changes, then the program must be re-built ( re-linked ) in order to incorporate the
changes. However if DLLs are used, then as long as the stub doesn't change, the
program can be updated merely by loading new versions of the DLLs onto the
system. Version information is maintained in both the program and the DLLs, so
that a program can specify a particular version of the DLL if necessary.
o In practice, the first time a program calls a DLL routine, the stub will recognize
the fact and will replace itself with the actual routine from the DLL library.
Further calls to the same routine will access the routine directly and not incur the
overhead of the stub access. ( Following the UML Proxy Pattern. )
o ( Additional information regarding dynamic linking is available
at [Link] )

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 13

System Programming & Operating System TE Computer Engineering

Swapping
Swapping is a mechanism in which a process can be swapped temporarily out of main memory
(or move) to secondary storage (disk) and make that memory available to other processes. At
some later time, the system swaps back the process from the secondary storage to main
memory.
Though performance is usually affected by swapping process but it helps in running multiple
and big processes in parallel and that's the reason Swapping is also known as a technique for
memory compaction.

The total time taken by swapping process includes the time it takes to move the entire process to
a secondary disk and then to copy the process back to memory, as well as the time the process
takes to regain main memory.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 14

System Programming & Operating System TE Computer Engineering

Let us assume that the user process is of size 2048KB and on a standard hard disk where
swapping will take place has a data transfer rate around 1 MB per second. The actual transfer of
the 1000K process to or from memory will take

2048KB / 1024KB per second

= 2 seconds
= 2000 milliseconds
Now considering in and out time, it will take complete 4000 milliseconds plus other overhead
where the process competes to regain main memory.
Memory Allocation
Main memory usually has two partitions −
 Low Memory − Operating system resides in this memory.
 High Memory − User processes are held in high memory.
Operating system uses the following memory allocation mechanism.

S.N. Memory Allocation & Description

1 Single-partition allocation
In this type of allocation, relocation-register scheme is used to protect user
processes from each other, and from changing operating-system code and data.
Relocation register contains value of smallest physical address whereas limit
register contains range of logical addresses. Each logical address must be less than
the limit register.

2 Multiple-partition allocation
In this type of allocation, main memory is divided into a number of fixed-sized
partitions where each partition should contain only one process. When a partition is
free, a process is selected from the input queue and is loaded into the free partition.
When the process terminates, the partition becomes available for another process.

Fragmentation
As processes are loaded and removed from memory, the free memory space is broken into little
pieces. It happens after sometimes that processes cannot be allocated to memory blocks
considering their small size and memory blocks remains unused. This problem is known as
Fragmentation.
Fragmentation is of two types −

S.N. Fragmentation & Description

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 15

System Programming & Operating System TE Computer Engineering

1 External fragmentation
Total memory space is enough to satisfy a request or to reside a process in it, but it
is not contiguous, so it cannot be used.

2 Internal fragmentation
Memory block assigned to process is bigger. Some portion of memory is left
unused, as it cannot be used by another process.

The following diagram shows how fragmentation can cause waste of memory and a compaction
technique can be used to create more free memory out of fragmented memory −

External fragmentation can be reduced by compaction or shuffle memory contents to place all
free memory together in one large block. To make compaction feasible, relocation should be
dynamic.
The internal fragmentation can be reduced by effectively assigning the smallest partition but
large enough for the process.
Paging
A computer can address more memory than the amount physically installed on the system. This
extra memory is actually called virtual memory and it is a section of a hard that's set up to
emulate the computer's RAM. Paging technique plays an important role in implementing virtual
memory.
Paging is a memory management technique in which process address space is broken into
blocks of the same size called pages (size is power of 2, between 512 bytes and 8192 bytes).
The size of the process is measured in the number of pages.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 16

System Programming & Operating System TE Computer Engineering

Similarly, main memory is divided into small fixed-sized blocks of (physical) memory
called frames and the size of a frame is kept the same as that of a page to have optimum
utilization of the main memory and to avoid external fragmentation.

Address Translation
Page address is called logical address and represented by page numberand the offset.

Logical Address = Page number + page offset

Frame address is called physical address and represented by a frame number and the offset.

Physical Address = Frame number + page offset

A data structure called page map table is used to keep track of the relation between a page of a
process to a frame in physical memory.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 17

System Programming & Operating System TE Computer Engineering

When the system allocates a frame to any page, it translates this logical address into a physical
address and create entry into the page table to be used throughout execution of the program.
When a process is to be executed, its corresponding pages are loaded into any available memory
frames. Suppose you have a program of 8Kb but your memory can accommodate only 5Kb at a
given point in time, then the paging concept will come into picture. When a computer runs out
of RAM, the operating system (OS) will move idle or unwanted pages of memory to secondary
memory to free up RAM for other processes and brings them back when needed by the
program.
This process continues during the whole execution of the program where the OS keeps
removing idle pages from the main memory and write them onto the secondary memory and
bring them back when required by the program.
Advantages and Disadvantages of Paging
Here is a list of advantages and disadvantages of paging −
 Paging reduces external fragmentation, but still suffer from internal fragmentation.
 Paging is simple to implement and assumed as an efficient memory management
technique.
 Due to equal size of the pages and frames, swapping becomes very easy.
 Page table requires extra memory space, so may not be good for a system having small
RAM.
Segmentation
Segmentation is a memory management technique in which each job is divided into several
segments of different sizes, one for each module that contains pieces that perform related
functions. Each segment is actually a different logical address space of the program.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 18

System Programming & Operating System TE Computer Engineering

When a process is to be executed, its corresponding segmentation are loaded into non-
contiguous memory though every segment is loaded into a contiguous block of available
memory.
Segmentation memory management works very similar to paging but here segments are of
variable-length where as in paging pages are of fixed size.
A program segment contains the program's main function, utility functions, data structures, and
so on. The operating system maintains a segment map table for every process and a list of free
memory blocks along with segment numbers, their size and corresponding memory locations in
main memory. For each segment, the table stores the starting address of the segment and the
length of the segment. A reference to a memory location includes a value that identifies a
segment and an offset.

Virtual memory :
computer can address more memory than the amount physically installed on the system. This
extra memory is actually called virtual memory and it is a section of a hard disk that's set up to
emulate the computer's RAM.
The main visible advantage of this scheme is that programs can be larger than physical memory.
Virtual memory serves two purposes. First, it allows us to extend the use of physical memory
by using disk. Second, it allows us to have memory protection, because each virtual address is
translated to a physical address.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 19

System Programming & Operating System TE Computer Engineering

Following are the situations, when entire program is not required to be loaded fully in main
memory.
 User written error handling routines are used only when an error occurred in the data or
computation.
 Certain options and features of a program may be used rarely.
 Many tables are assigned a fixed amount of address space even though only a small
amount of the table is actually used.
 The ability to execute a program that is only partially in memory would counter many
benefits.
 Less number of I/O would be needed to load or swap each user program into memory.
 A program would no longer be constrained by the amount of physical memory that is
available.
 Each user program could take less physical memory, more programs could be run the
same time, with a corresponding increase in CPU utilization and throughput.
Modern microprocessors intended for general-purpose use, a memory management unit, or
MMU, is built into the hardware. The MMU's job is to translate virtual addresses into physical
addresses. A basic example is given below −

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 20

System Programming & Operating System TE Computer Engineering

Virtual memory is commonly implemented by demand paging. It can also be implemented in a

segmentation system. Demand segmentation can also be used to provide virtual memory.

Demand Paging
A demand paging system is quite similar to a paging system with swapping where processes
reside in secondary memory and pages are loaded only on demand, not in advance. When a
context switch occurs, the operating system does not copy any of the old program’s pages out to
the disk or any of the new program’s pages into the main memory Instead, it just begins
executing the new program after loading the first page and fetches that program’s pages as they
are referenced.

While executing a program, if the program references a page which is not available in the main
memory because it was swapped out a little ago, the processor treats this invalid memory
reference as a page fault and transfers control from the program to the operating system to
demand the page back into the memory.
Advantages
Following are the advantages of Demand Paging −

 Large virtual memory.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 21

System Programming & Operating System TE Computer Engineering

 More efficient use of memory.

 There is no limit on degree of multiprogramming.
Disadvantages
 Number of tables and the amount of processor overhead for handling page interrupts are
greater than in the case of the simple paged management techniques.

Page Replacement Algorithm

Page replacement algorithms are the techniques using which an Operating System decides
which memory pages to swap out, write to disk when a page of memory needs to be allocated.
Paging happens whenever a page fault occurs and a free page cannot be used for allocation
purpose accounting to reason that pages are not available or the number of free pages is lower
than required pages.
When the page that was selected for replacement and was paged out, is referenced again, it has
to read in from disk, and this requires for I/O completion. This process determines the quality of
the page replacement algorithm: the lesser the time waiting for page-ins, the better is the
algorithm.
A page replacement algorithm looks at the limited information about accessing the pages
provided by hardware, and tries to select which pages should be replaced to minimize the total
number of page misses, while balancing it with the costs of primary storage and processor time
of the algorithm itself. There are many different page replacement algorithms. We evaluate an
algorithm by running it on a particular string of memory reference and computing the number of
page faults,
Reference String
The string of memory references is called reference string. Reference strings are generated
artificially or by tracing a given system and recording the address of each memory reference.
The latter choice produces a large number of data, where we note two things.
 For a given page size, we need to consider only the page number, not the entire address.
 If we have a reference to a page p, then any immediately following references to
page p will never cause a page fault. Page p will be in memory after the first reference;
the immediately following references will not fault.
 For example, consider the following sequence of addresses − 123,215,600,1234,76,96
 If page size is 100, then the reference string is 1,2,6,12,0,0
First In First Out (FIFO) algorithm
 Oldest page in main memory is the one which will be selected for replacement.

 Easy to implement, keep a list, replace pages from the tail and add new pages at the
head.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 22

System Programming & Operating System TE Computer Engineering

Optimal Page algorithm

 An optimal page-replacement algorithm has the lowest page-fault rate of all algorithms.
An optimal page-replacement algorithm exists, and has been called OPT or MIN.
 Replace the page that will not be used for the longest period of time. Use the time when a
page is to be used.

Least Recently Used (LRU) algorithm

 Page which has not been used for the longest time in main memory is the one which will
be selected for replacement.
 Easy to implement, keep a list, replace pages by looking back into time.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 23

System Programming & Operating System TE Computer Engineering

Example of Page Replacement Algorithms :

On a page fault, the frame that has been in memory the longest is replaced.

FIFO is not a stack algorithm. In certain cases, the number of page faults can actually increase
when more frames are allocated to the process. In the example below, there are 9 page faults for
3 frames and 10 page faults for 4 frames.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 24

 System Programming & Operating System TE Computer Engineering

Optimal Replacement

The Belady’s optimal algorithm cheats. It looks forward in time to see which frame to replace on
a page fault. Thus it is not a real replacement algorithm. It gives us a frame of reference for a
given static frame access sequence.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 25

System Programming & Operating System TE Computer Engineering

Page Buffering algorithm

 To get a process start quickly, keep a pool of free frames.

 On page fault, select a page to be replaced.
 Write the new page in the frame of free pool, mark the page table and restart the process.
 Now write the dirty page out of disk and place the frame holding replaced page in free
pool.
Least frequently Used(LFU) algorithm
 The page with the smallest count is the one which will be selected for replacement.
 This algorithm suffers from the situation in which a page is used heavily during the
initial phase of a process, but then is never used again.
Most frequently Used(MFU) algorithm
 This algorithm is based on the argument that the page with the smallest count was
probably just brought in and has yet to be used.
One of the important jobs of an Operating System is to manage various I/O devices including
mouse, keyboards, touch pad, disk drives, display adapters, USB devices, Bit-mapped screen,
LED, Analog-to-digital converter, On/off switch, network connections, audio I/O, printers etc.
An I/O system is required to take an application I/O request and send it to the physical device,
then take whatever response comes back from the device and send it to the application. I/O
devices can be divided into two categories −
 Block devices − A block device is one with which the driver communicates by sending
entire blocks of data. For example, Hard disks, USB cameras, Disk-On-Key etc.
 Character devices − A character device is one with which the driver communicates by
sending and receiving single characters (bytes, octets). For example, serial ports, parallel
ports, sounds cards etc
Device Controllers
Device drivers are software modules that can be plugged into an OS to handle a particular
device. Operating System takes help from device drivers to handle all I/O devices.
The Device Controller works like an interface between a device and a device driver. I/O units
(Keyboard, mouse, printer, etc.) typically consist of a mechanical component and an electronic
component where electronic component is called the device controller.
There is always a device controller and a device driver for each device to communicate with the
Operating Systems. A device controller may be able to handle multiple devices. As an interface
its main task is to convert serial bit stream to block of bytes, perform error correction as
necessary.
Any device connected to the computer is connected by a plug and socket, and the socket is
connected to a device controller. Following is a model for connecting the CPU, memory,
controllers, and I/O devices where CPU and device controllers all use a common bus for
communication.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 26

System Programming & Operating System TE Computer Engineering

Synchronous vs asynchronous I/O

 Synchronous I/O − In this scheme CPU execution waits while I/O proceeds
 Asynchronous I/O − I/O proceeds concurrently with CPU execution
Communication to I/O Devices
The CPU must have a way to pass information to and from an I/O device. There are three
approaches available to communicate with the CPU and Device.

 Special Instruction I/O

 Memory-mapped I/O
 Direct memory access (DMA)
Special Instruction I/O
This uses CPU instructions that are specifically made for controlling I/O devices. These
instructions typically allow data to be sent to an I/O device or read from an I/O device.
Memory-mapped I/O
When using memory-mapped I/O, the same address space is shared by memory and I/O devices.
The device is connected directly to certain main memory locations so that I/O device can
transfer block of data to/from memory without going through CPU.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 27

System Programming & Operating System TE Computer Engineering

While using memory mapped IO, OS allocates buffer in memory and informs I/O device to use
that buffer to send data to the CPU. I/O device operates asynchronously with CPU, interrupts
CPU when finished.
The advantage to this method is that every instruction which can access memory can be used to
manipulate an I/O device. Memory mapped IO is used for most high-speed I/O devices like
disks, communication interfaces.
Direct Memory Access (DMA)
Slow devices like keyboards will generate an interrupt to the main CPU after each byte is
transferred. If a fast device such as a disk generated an interrupt for each byte, the operating
system would spend most of its time handling these interrupts. So a typical computer uses direct
memory access (DMA) hardware to reduce this overhead.
Direct Memory Access (DMA) means CPU grants I/O module authority to read from or write to
memory without involvement. DMA module itself controls exchange of data between main
memory and the I/O device. CPU is only involved at the beginning and end of the transfer and
interrupted only after entire block has been transferred.
Direct Memory Access needs a special hardware called DMA controller (DMAC) that manages
the data transfers and arbitrates access to the system bus. The controllers are programmed with
source and destination pointers (where to read/write the data), counters to track the number of
transferred bytes, and settings, which includes I/O and memory types, interrupts and states for
the CPU cycles.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 28

System Programming & Operating System TE Computer Engineering

The operating system uses the DMA hardware as follows −

Step Description

1 Device driver is instructed to transfer disk data to a buffer address X.

2 Device driver then instruct disk controller to transfer data to buffer.

3 Disk controller starts DMA transfer.

4 Disk controller sends each byte to DMA controller.

5 DMA controller transfers bytes to buffer, increases the memory address, decreases
the counter C until C becomes zero.

6 When C becomes zero, DMA interrupts CPU to signal transfer completion.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 29

System Programming & Operating System TE Computer Engineering

Polling vs Interrupts I/O

A computer must have a way of detecting the arrival of any type of input. There are two ways
that this can happen, known as polling and interrupts. Both of these techniques allow the
processor to deal with events that can happen at any time and that are not related to the process
it is currently running.
Polling I/O
Polling is the simplest way for an I/O device to communicate with the processor. The process of
periodically checking status of the device to see if it is time for the next I/O operation, is called
polling. The I/O device simply puts the information in a Status register, and the processor must
come and get the information.
Most of the time, devices will not require attention and when one does it will have to wait until
it is next interrogated by the polling program. This is an inefficient method and much of the
processors time is wasted on unnecessary polls.
Compare this method to a teacher continually asking every student in a class, one after another,
if they need help. Obviously the more efficient method would be for a student to inform the
teacher whenever they require assistance.
Interrupts I/O
An alternative scheme for dealing with I/O is the interrupt-driven method. An interrupt is a
signal to the microprocessor from a device that requires attention.
A device controller puts an interrupt signal on the bus when it needs CPU’s attention when CPU
receives an interrupt, It saves its current state and invokes the appropriate interrupt handler
using the interrupt vector (addresses of OS routines to handle various events). When the
interrupting device has been dealt with, the CPU continues with its original task as if it had
never been interrupted.
I/O software is often organized in the following layers −
 User Level Libraries − This provides simple interface to the user program to perform
input and output. For example, stdio is a library provided by C and C++ programming
languages.
 Kernel Level Modules − This provides device driver to interact with the device
controller and device independent I/O modules used by the device drivers.
 Hardware − This layer includes actual hardware and hardware controller which interact
with the device drivers and makes hardware alive.
A key concept in the design of I/O software is that it should be device independent where it
should be possible to write programs that can access any I/O device without having to specify
the device in advance. For example, a program that reads a file as input should be able to read a
file on a floppy disk, on a hard disk, or on a CD-ROM, without having to modify the program
for each different device.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 30

System Programming & Operating System TE Computer Engineering

Device Drivers
Device drivers are software modules that can be plugged into an OS to handle a particular
device. Operating System takes help from device drivers to handle all I/O devices. Device
drivers encapsulate device-dependent code and implement a standard interface in such a way
that code contains device-specific register reads/writes. Device driver, is generally written by
the device's manufacturer and delivered along with the device on a CD-ROM.
A device driver performs the following jobs −

 To accept request from the device independent software above to it.

 Interact with the device controller to take and give I/O and perform required error
handling
 Making sure that the request is executed successfully
How a device driver handles a request is as follows: Suppose a request comes to read a block N.
If the driver is idle at the time a request arrives, it starts carrying out the request immediately.
Otherwise, if the driver is already busy with some other request, it places the new request in the
queue of pending requests.
Interrupt handlers
An interrupt handler, also known as an interrupt service routine or ISR, is a piece of software or
more specifically a callback function in an operating system or more specifically in a device
driver, whose execution is triggered by the reception of an interrupt.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 31

System Programming & Operating System TE Computer Engineering

When the interrupt happens, the interrupt procedure does whatever it has to in order to handle
the interrupt, updates data structures and wakes up process that was waiting for an interrupt to
happen.
The interrupt mechanism accepts an address ─ a number that selects a specific interrupt
handling routine/function from a small set. In most architectures, this address is an offset stored
in a table called the interrupt vector table. This vector contains the memory addresses of
specialized interrupt handlers.
Device-Independent I/O Software
The basic function of the device-independent software is to perform the I/O functions that are
common to all devices and to provide a uniform interface to the user-level software. Though it
is difficult to write completely device independent software but we can write some modules
which are common among all the devices. Following is a list of functions of device-independent
I/O Software −

 Uniform interfacing for device drivers

 Device naming - Mnemonic names mapped to Major and Minor device numbers
 Device protection
 Providing a device-independent block size
 Buffering because data coming off a device cannot be stored in final destination.
 Storage allocation on block devices
 Allocation and releasing dedicated devices
 Error Reporting
User-Space I/O Software
These are the libraries which provide richer and simplified interface to access the functionality
of the kernel or ultimately interactive with the device drivers. Most of the user-level I/O
software consists of library procedures with some exception like spooling system which is a
way of dealing with dedicated I/O devices in a multiprogramming system.
I/O Libraries (e.g., stdio) are in user-space to provide an interface to the OS resident device-
independent I/O SW. For example putchar(), getchar(), printf() and scanf() are example of user
level I/O library stdio available in C programming.
Kernel I/O Subsystem
Kernel I/O Subsystem is responsible to provide many services related to I/O. Following are
some of the services provided.
 Scheduling − Kernel schedules a set of I/O requests to determine a good order in which
to execute them. When an application issues a blocking I/O system call, the request is
placed on the queue for that device. The Kernel I/O scheduler rearranges the order of the
queue to improve the overall system efficiency and the average response time
experienced by the applications.
 Buffering − Kernel I/O Subsystem maintains a memory area known as buffer that stores
data while they are transferred between two devices or between a device with an

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 32

System Programming & Operating System TE Computer Engineering

application operation. Buffering is done to cope with a speed mismatch between the
producer and consumer of a data stream or to adapt between devices that have different
data transfer sizes.
 Caching − Kernel maintains cache memory which is region of fast memory that holds
copies of data. Access to the cached copy is more efficient than access to the original.
 Spooling and Device Reservation − A spool is a buffer that holds output for a device,
such as a printer, that cannot accept interleaved data streams. The spooling system
copies the queued spool files to the printer one at a time. In some operating systems,
spooling is managed by a system daemon process. In other operating systems, it is
handled by an in kernel thread.
 Error Handling − An operating system that uses protected memory can guard against
many kinds of hardware and application errors.

Segmentation
In Operating Systems, Segmentation is a memory management technique in which, the memory
is divided into the variable size parts. Each part is known as segment which can be allocated to a
process.

The details about each segment are stored in a table called as segment table. Segment table is
stored in one (or many) of the segments.

Segment table contains mainly two information about segment:

1. Base: It is the base address of the segment

2. Limit: It is the length of the segment.

Why Segmentation is required?

Till now, we were using Paging as our main memory management technique. Paging is more
close to Operating system rather than the User. It divides all the process into the form of pages
regardless of the fact that a process can have some relative parts of functions which needs to be
loaded in the same page.

Operating system doesn't care about the User's view of the process. It may divide the same
function into different pages and those pages may or may not be loaded at the same time into the
memory. It decreases the efficiency of the system.

It is better to have segmentation which divides the process into the segments. Each segment
contain same type of functions such as main function can be included in one segment and the
library functions can be included in the other segment,

Translation of Logical address into physical address by segment table

CPU generates a logical address which contains two parts:

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 33

System Programming & Operating System TE Computer Engineering

1. Segment Number
2. Offset

The Segment number is mapped to the segment table. The limit of the respective segment is
compared with the offset. If the offset is less than the limit then the address is valid otherwise it
throws an error as the address is invalid.

In the case of valid address, the base address of the segment is added to the offset to get the
physical address of actual word in the main memory.

Advantages of Segmentation

1. No internal fragmentation
2. Average Segment Size is larger than the actual page size.
3. Less overhead
4. It is easier to relocate segments than entire address space.
5. The segment table is of lesser size as compare to the page table in paging.

Disadvantages
1. It can have external fragmentation.
2. it is difficult to allocate contiguous memory to variable sized partition.
3. Costly memory management algorithms.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 34

System Programming & Operating System TE Computer Engineering

Compare Paging and Segmentation :

Paging VS Segmentation
Sr Paging Segmentation
No.

1 Non-Contiguous memory allocation Non-contiguous memory allocation

2 Paging divides program into fixed size Segmentation divides program into
pages. variable size segments.

3 OS is responsible Compiler is responsible.

4 Paging is faster than segmentation Segmentation is slower than paging

5 Paging is closer to Operating System Segmentation is closer to User

6 It suffers from internal fragmentation It suffers from external fragmentation

7 There is no external fragmentation There is no external fragmentation

8 Logical address is divided into page Logical address is divided into segment
number and page offset number and segment offset

9 Page table is used to maintain the Segment Table maintains the segment
page information. information

10 Page table entry has the frame Segment table entry has the base
number and some flag bits to address of the segment and some
represent details about pages. protection bits for the segments.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 35

System Programming & Operating System TE Computer Engineering

Thrashing :
Thrashing is computer activity that makes little or no progress, usually because memory or other
resources have become exhausted or too limited to perform needed operations. When this
happens, a pattern typically develops in which a request is made of the operating system by a
process or program, the operating system tries to find resources by taking them from some other
process, which in turn makes new requests that can't be satisfied. In a virtual storage system (an
operating system that manages its logical storage or memory in units called pages), thrashing is a
condition in which excessive paging operations are taking place.

A system that is thrashing can be perceived as either a very slow system or one that has come to
a halt.

Pune Vidyarthi Griha’s COLLEGE OF ENGINEERING, NASHIK-4. 36