Swapping

" A process must be loaded into memory in order to execute.

" If there is not enough memory available to keep all running processes in memory at the
same timne, then some processes that are not currently using the CPU may have their
memory swapped out to a fast local disk called the backing store.
" Swapping is the process of moving a process from memory to backing store and moving
another process from backing store to memory. Swapping is a very slow process
compared to other operations.
" A variant of swapping policy is used for priority-based scheduling algorithms. If a
higher-priority process arrives and wants service, the memory manager can swap out the
lower-priority process and then load and execute the higher-priority rprocess. When the
higher-priority process finishes, the lower-priority process can be swapped back in and
continued. This variant of swapping is called roll out, roll in.

Swapping depends upon address-binding:

" If binding is done at load-time, then process cannot be easily moved to a different
location.
" If binding is done at execution-time, then a process can be swapped into a different
memory-space, because the physical-addresses are computed during execution-time.

Major part of swap-time is transfer-time; i.e. total transfer-time is directly proportional to the
amount of memory swapped.

Disadvantages:
1. Context-switch time is fairly high.
2. If we want to swap a process, we must be sure that it is completely idle.
Two solutions:
i) Never swap a process with pending I/0.
ii) Execute VO operations only into OS buffers.

CRealicg

rocess P

prDoess P

Daocng store

ran meony

Figure: Swapping of two processes using a disk as a backing store

 ACCESS METHODS
" Files store information. When it is used, this information must be accessed and read
into computer memory. The information in the file can be accessed in several ways.
" Some of the common methods are:

Sequential access Direct access Other access

1. Sequential methods
The simplest access method is sequential methods. Information in the file is
processed in order., one record after the other.
" Reads and writes make up the bulk of the operations on a file.
"A read operation (next-reads) reads the next portion of the file and
automatically advances a file pointer, which tracks the I/O location
" The write operation (write next) appends to the end of the file and advances to the
end of the newly written material.
" A file can be reset to the beginning and on some systems, a program may able to
skip forward or backward n records for some integer n-perhaps only for n =1.

Operating SystemsBcS303

current position
beginning end

rewind:
read or write
Figure: Sequential-access file.
2. Direct Access
" A file is made up of fixed length logical records that allow programs to read and
write records rapidly in no particular order.
The direct-access method is based on a disk model of a file, since disks allow
random access to any file block. For direct access, the file is viewed as a numbered
sequence of blocks or records.
" Example: if wee may read block 14, then read block 53, and then write block 7. There
are no restrictions on the order of reading or writing for a direct-access file.
" Direct-access files are of great use for immediate access to large amounts of
information such as Databases, where searching becomes easy and fast.
" For the direct-access method, the file operations must be modified to include the
block number as a parameter. Thus, we have read n, where n is the block number,
rather than read next, and -write n rather than write next.
" An alternative approach is to retain read next and write next, as with sequential
access, and to add an operation position file to n, where n is the block number. Then,
to affect a read n, we would position ton and then read next.

sequential access implementation for direct access

rese cp=0;
read next read cp
cpcp+1;
write next Write cp.
cp= cp + 1;

Figure: Simulation of sequential access on a direct-access file.

O zepto
1o Minute Dativary
3. OtherAccess Methods:
" Other access methods can be built on top of a direct-access method. These methods
generally involve the construction of an index for the file.
" The Index, is like an index in the back of a book contains pointers to the various
blocks. To find a record in the file, we first search the index and then use the pointer
to access the file directly and to find the desired record.

Operating Systems Bcs303

logical record
last name number

Adams
Arthur
Asher smith, john social-securiy age

Smith

index file relative file

Figure: Example of index and relative files

Free Space Management
The space created after deleting the files can be reused. Another important aspect of disk
management is keeping track of free space in memory. The list which keeps track of free space in
memory is called the free-space list. To create a file, search the free-space list for the required
amount of space and allocate that space to the new file. This space is then removed from the free
space list. When a file is deleted, its disk space is added to the free-space list. The free-space list, is
implemented in different ways as explained below.
a) Bit Vector
Fast algorithms exist for quickly finding contiguous blocks of a given size
One simple approach is to use a bit vector, in which each bit represents a disk block,
set to 1 if free or 0 if allocated.

For example, consider a disk where blocks 2,3,4,5,8,9, 10,11, 12, 13, 17and 18 are free, and the
rest of the blocks are allocated. The free-space bit map would be
0011110011111100011
. Easy to implement and also very efficient in finding the first free block or 'n'
consecutive free blocks on the disk.

31

OperatingSystemsBCs303
. The down side is that a 40GB disk requires over SMB just to store the bitmap.

b) Linked List
a. A linked list can also be used to keep track of all free blocks.
b. Traversing the list and/or finding a contiguous block of a given size are not casy, but
fortunately are not frequently needed operations. Generally the system just adds and
removes single blocks from the beginning of the list.
c. The FAT table keeps track of the free list as just one more linked list on the table.
c) Grouping
a. A variation on linked list free lists. It stores the addresses of n free blocks in the first
free block. The fist n-I blocks are actually free. The last block contains the
addresses of another n free blocks, and so on.
b. The address ofa large number of free blocks can be found quickly.
d) Counting
a. When there are multiple contiguous blocks of free space then the system can keep
track of the starting address of the group and the number of contiguous free blocks.
b. Rather than keeping al list of n free disk addresses, we can keep the address of first
free block and the number of free contiguous blocks that follow the first block
c. Thus the overall space is shortened. It is similar to the extent method of allocating
blocks.
e) Space Maps
a. Sun's ZFS file system was designed for huge numbers and sizes of files, directories,
and even file systems.
b. The resulting data structures could be inefficient if not implemented carefully. For
example, freeing up a I GB file on a TB file system could involve updating
thousands of blocks of free list bit maps if the file was spread across the disk.
c. ZFS uses a combination of techniques, starting with dividing the disk up into
(hundreds of) Meta slabs of a manageable size, each having their own space map.
d. Free blocks are managed using the counting technique. but rather than write the
information to a table, it is recorded in a log-structured transaction record. Adjacent
free blocks are also coalesced into a larger single free block.
e. An in-memory space map is constructed using a balanced tree data structure,
constructed from the log data.
f. The combination of the in-memory tree and the on-disk log provide for very fast and
efficient management of these very large files and free blocks.
 3. Tree Structured Directories
A tree is the most common directory structure.
The tree has a root directory, and every file in the system has a unique path name.
A directory contains a set of files or subdirectories. A directory is simply another file, but
it is treated in a special way.
All directories have the same internal format. One bit in each directory entry defines the
entry as a file (0) or as a subdirectory (1). Special system calls are used to create and

Operating SystemsBCS303

delete directories.
Two types of path-names:
1. Absolute path-name: begins at the root.
2. Relative path-name: defines a path from the current directory.
roo pel bin programs

statmat dt find ount hex eorder P m a l

reorder i s n d hex count

ist obË spell last Brst

How to delete directory?

I. To delete an empty directory: Just delete the directory.
2. To delete a non-empty directory:
First, delete all files in the directory.
. If any subdirectories exist, this procedure must be applied recursively to them.
Advantage:
.Users can be allowed to access the files of other users.
Disadvantages:
A path toa file can be longer than a path in a two-level directory.
"Prohibits the sharing of files (or directories).
4. Acyclic Graph Directories
The common subdirectory should be shared. A shared directory or file will exist in the
file system in two or more places at once. A tree structure prohibits the sharing of files
or directories.
An acyclic graph is a graph with no cycles. It allows directories to share subdirectories
and files.
 root dicspel

ist al W count COunt Words ist

om

ist rade w7

" The same file or subdirectory may be in two different directories. The acyclic graph
is a natural generalization of the tree-structured directory scheme.

Two methods to implement shared-files (or subdirectories):

1. Create a new directory-entry called a link. A link is a pointer to another file (or
subdirectory).
2. Duplicate all information about shared-files in both sharing directories.

Two problems:
1. A file may have multiple absolute path-names.
2. Deletion may leave dangling-pointers to the non-existent file.

Solution to deletion problem:

1. Use back-pointers: Preserve the file until all references to it are deleted.
2. With symbolic links, remove only the link, not the file. If the file itself is
deleted, the link can be removed.
 Process 07
needs 50KB
40 KB memory space
Fragment
Assigned‘
Space
Fragment | | 10 KB
Assigned
Space
Fragment 5 KB
Assigned Fragment
Space
Used
Space

Fragment
Assigned Used
Space
Space

Internal Fragmentation
Hashed Page Table:
Acommon approach for handling address spaces larger than 32 bits is to use a hashed page table,
with the hash valuc being the virtual page number. Each cntry in the hash table contains a linked list
of clements that has to the same location. Each clement consists of three ficlds: (a) the virtual page
number, (b) the value of the mapped page frame, and (c) a pointer to the next edement in the linked
list. The algorithm works as follows: The virtual page number in the virtual address is hashed into
the hash table. The irtual page number is compared to field (a) in the first element in the linked list.
If there is a match, the corresponding page frame (ficld (b) is uscd to form the desired physical
address. If there is no match, subscquent entrics in the linked list are searched for a matching virtual
page number. The scheme is shown in below figure.

65 | Page

physical
ogcaaddre

hash phyNca
function menory

hash tabie
Inverted Page Table:
Onc cntry for cach real page (frame) of mnemory.
Entry consists of the virtual address of the page storcd in that real memory location, with
information abour the process that owns that page.
" There is only one page table in the system. Not per process.
" Decreases memory needed to store each page table, but increases time needed to search the table
when a page reference occurs.
Use hash table to limit the scarch to oneor at most afewpage-table entries.

CPU

searc

e tabie

Each virtual address in the system consists of a triple <process-id, page-number, offset>. ach
inverted page table entry is a pair <process-id, page-number> where the process-id assumes the role
of the address space identifier. When a memory reference occurs, part of the virtual address,
consisting of <process-id, page-number>, is presented to the memory subsystem. The inverted page
table is then searched for a match. If a match is found say at entry i, then the physical address <i,
offset> is gencrated If no match is found, then an illegal address access has been attempted.
7. (a). What is TLB? TLB in detail with a paging system with a neat
diagram. 6 Marks
Answer:
U The standard soution to this problem is to use a special, small, fast lookup
hardwate cache, called a translation look-aside buffer (TLB).
O The TLB 1s associative, high-speed memory. Each entry in the TLB consists of two
parts: a key (or tag) and a value.
O When the associative memory is presented with an item, the item is compared with
Kall keys simultaneously.
O The TLB is used with page tables in the following way. The TLB contains only a few
of the page-table entries. When a logical address is generated by the CPU, its page
number is presented to the TLB.
O If the page number is found, its frame number is immediately available and is used
to access memory.
O The whole task may take less than 10 percent longer than it would if an unmapped
memory reference were used.

O If the page number is not in the TLB (known as a TLB miss), a memory reference to
the page table must be made. When the frame number is obtained, we can use it to
access memory (Figure below).
logical
addressr
CPU p d
page frame
number number

TLB hit
physical
address
d
TLB

TLB miss

physical
memory

page table
Solution