Operating system
Lecture nine
part2
Dr jamal altuwaijari
6. Paging Method
Anther possible solution to the external fragmentation problem in to
permit the logical address space of a process to be noncontiguous, thus
allowing a process to be allocated physical memory wherever is
available.
In paging scheme the physical memory is broken into filed- sized blocks
called frames. Logical memory is also broken into blocks of the same
size called pages. When a process is to be executed its pages are loaded
into any available memory frames from the backing store.
6. Paging Method
Figure 9.13: Paging Hordware.
6. Paging Method
Every address generaled by the CPU is divided into two parts a
page
.Number (p) and apage off set (d) p is used as an index to page table
The page table contains the base address of each page in physical
memory this base add- is combined with the page offset to define the
.physical memory address as in figure above
6. Paging Method
Example:
Consider a user program of logical address of size 4 pages and page size
4 bytes, use the physical address of 260 frames if the user program consists of
instruction a, b, c,... p, each instruction take 1 byte assume at that time the
free-frame list is 5, 6, 1, 2, 14 show how this program can be allocated in the
physical memory and draw the page table and the logical and physical maps.
Logical address 0 in page 0 offset 0 indexing into page table we find that
page 0 is in frame 5. Thus logical address 0 maps to physical address
(5x4) +0 = 20
Logical address 3 (page 0 offset 3) maps to physical add. 4 is page 1 offset 0
according to the page table page 1 is mapped to frame 6 —24 (=(6x4)+0 and
so on.
Note: if a process requires a pages there must be at least a frames available
In physical memory.
6.1 Structure of page table and H/W support
Each 0/S has its own methods for storing page tables. Most allocate a
P.T . for each process. A pointer to P.T is stored with the other register
value in PCB.. The P.T is kept in main memory and the page —table
base register (PTBR) points to page table.
To make the access to page — table —very fast is to us a special small
fast —look up HAY cache called associative registers, this set of
registers is built of especially high — speed memory.
The organization of page — table using this technique as in the figure
below.
Note:
1. The percentage of times that a page number is found in the
associative registers is called his ratio.
2. TLB translation look — a side buffers TLB.
6.2 Protection in Paging
One bit can be added to the page table to indicate a page to be read
and write or read —only.
Every reference to memory goes through the page table to find
the correct frame number, at the same time the protection bit can be
checked to verify that no writes are being made to a read only page.
Also we can add another bit to page table called valid and in -
valid bit if this bit set to valid means that page belong to process logical
address if set to invalid means illegal address space see the example
below.
6.3 Shared pages
Another advantage of paging is the possibility of sharing common
code.. This important in a time support to users. If the code reentrant it
can be shared
see the figure.
Here we see a three — page editor (each page size 50 k being
shared among three process. Each process has its one page an page
table.
6.3 Shared pages
Only one copy of editor needs to be kept in physical memory . page
table maps on to same physical copy of editor ,but data pages are
mapped on to different frames.
Thus to support 40 users we need only one copy of editor (150 k) plus
40 copies of 50 k .of data spare per user. The total space required is
now 8150 k
Instead of 8000 k.
[Link]
Segmentation is s memory – management scheme that support the
user view memory.
A logical address space is collection of segment has a name and a
length. The logical address of segment specify both the segment
number and the offset within the segment. Thus a logical address
.consists of tow part
The user refers to view memory as a collection of variable -sized
figure 9.15 user s view of program in segmentation
[Link]
The user can refer to objects in the program by a two dimensional
address therefore we require to map a two - dimensional address into
one - dimensional physical address . This mapping is effected by a
segment table where each entry of segment table has a segment limit .
The segment has a contains the starting physical address where the
segment resides in memory , where as segment limits specifies , the
length of the segment . The use of the segment table is illustrated in
the fig 9.16
Fig 9.16 segmentation H/W
An example: consider situation shown in the figure 9.16 therefore five segments 0 – 4 .
The segments are stored in physical memory the segment table has a separate entry for
each segment giving the beginning address of the segment in the physical memory
( the base ) and the length of the segment (the limit) . For example segment in 400
bytes long and begins at location 4300 thus reference to byte 1222 of segment 0 would
result in a trap O/S
7.2 Implementation of segment tables
Like the page table the segment table can be put either in fast registers
or in memory. In the case where a program may consist of a large
number of segment s it is not feasible to keep the segment table in
registers so we must keep it in memory .
A segment – table base registers (STRB) points to the segment table. A
segment –table-length –register (STLR)is used , for a logical address
(S,D) first check number S <STRL then add to STRB resulting in the
address (STRB+S) in memory of the segment – table entry and we
proceed as before.
As occurs in paging the mapping in segmentation requires two
memory references per logical address.
The normal solution is to use the associative registers to hold the most
recently used segment. Table entries , see the figure 9.17.
Figure 9.17 address translation in segmentation
7.3 protection and sharing in segmentation
One advantage of segmentation is the association of protection with
the segments such as the types of access read , write execute ,append
in addition to the segment secondary storage and residence of
segment bit. Therefore the segment map table entry can be explained
in the following.
7.3 protection and sharing in segmentation
Another advantage of segmentation is sharing segments are shared
when entries in the segment tables of two different processes points to
the same physical address see the fig 9.18 below.
7.4 fragmentation in segmentation
The I.T.S must find and allocate memory for all the segments of a user
program.
This situation similar to a paging expect that the segments are of
variable length. So memory allocation is a dynamic and the best – fit
or first – fit strategies can be used to allocate space for each segment .
Segmentation may then cause external fragmentation when all blocks
of free memory are too small to accommodate a segment.
Therefore segmentation has two types of fragment.
External and Internal.
7.4 fragmentation in segmentation
Example:
Consider a program consists of five segments so book B ,
S1=14KB ,S2=100KB , S3=580KB , S4=96KB.
Assume at the time the available free space partition of memory are
1200 - 1805 , 50 – 60 , 220 – 250 , 2500 – 3200 KB answer the
following :
1- Allocate space for each segment in the order given above .
2- Draw the logical physical maps and segment table.
3- Calculate the external fragmentation and the internal where if the
remainder of partition < 10 bytes leave it as internal fragmentation
and use the best fit- strategy to allocate space for each segment.
What are the address in physical memory for the following logical -4
address : a . 0.580 b.1.17 c. 2.96 d.4.112 e. 3.420
The solution of the example in page
1- logical and physical map before allocation as follows
The solution of the example in page
2- by using the best fit- strategy we can allocate space for each
segment .
3- After the allocation we can find the base address for each segment
and we can draw the segment table.
4- Because all segment able allocate and there is no waiting segment ,
therefore no external fragmentation .
5- The physical addresses are
i. S=0, d=580 base for S0=1200+580=1780.
ii. S=1, d=17 > limit so interior .
iii. S=2 , d= 96 base for S2=50+96=146.
iiii. S=4, d=112 > limit (96) so it addressing error .
iiiii. S=3,d=420 base for S2=2500+420=2920.
