Transcript No Slide Title

Chapter 8: Memory
Management Strategies
Operating System Concepts – 8th Edition
Silberschatz, Galvin and Gagne ©2009
Chapter 8: Memory Management Strategies
 Background
 Swapping
 Contiguous Memory Allocation
 Paging
 Structure of the Page Table
 Segmentation
Operating System Concepts – 8th Edition
7.2
Silberschatz, Galvin and Gagne ©2009
Objectives
 To provide a detailed description of various ways of
organizing memory hardware
 To discuss various memory-management techniques,
including paging and segmentation
Operating System Concepts – 8th Edition
7.3
Silberschatz, Galvin and Gagne ©2009
Operating System Concepts – 8th Edition
7.4
Silberschatz, Galvin and Gagne ©2009
Background

Memory is central to the operation of a modern computer system.

Memory consists of a large array of words or bytes, each with its
own address

Selection of a memory-management method for a specific system
depends on many factors, especially on the hardware design of the
system.
Operating System Concepts – 8th Edition
7.5
Silberschatz, Galvin and Gagne ©2009
Basic Hardware

Main memory , registers and cash are ONLY storage CPU can access
directly

Program must be brought (from disk) into memory and placed within a
process for it to be run

Direct storage access time:
Huge problem… because
of the frequency of
memory accesses.
 Register access in one CPU clock (or less)
 Main memory can take many cycles (i.e. slowly)
 Solution: Cache (fast memory) sits between main memory and
CPU registers

Protection of memory:
 Protection of memory is necessary to ensure correct operation
 Protection from what (/possible risks)????
– protect the operating system from access by user processes
– protect user processes from one another.
 This protection must be provided by the hardware &can be
implemented in several ways.
Operating System Concepts – 8th Edition
7.6
Silberschatz, Galvin and Gagne ©2009
Basic Hardware (Cont.)
 One method to implement protection: use Base and Limit Registers
 We need to make sure that each process has a separate memory
space….How???
 Main idea: we need to determine the range of legal addresses
that can be accessed only by the process.
 We can provide this protection by using two registers (base
& limit)
– The base register>> holds the physical address of the
first byte in the legal range.
– The limit register >> holds the size of the range.
Operating System Concepts – 8th Edition
7.7
Silberschatz, Galvin and Gagne ©2009
Basic Hardware (Cont.)
– Example: If the base register holds
300040 and the limit register is
120900….what is the range of legal
addresses ??
»
The program can legally access all addresses from
300040 through 420939 (inclusive)
»
NOTE: Last physical address = base +limit -1
Operating System Concepts – 8th Edition
7.8
Silberschatz, Galvin and Gagne ©2009
Basic Hardware (Cont.)
 How base & limit registers help to provide memory
protection??
 By applying (2) procedures:
–
Procedure (1): The CPU hardware compare every address
generated in user mode with the registers.
– Procedure (2): restrict the ability to load base & limit registers
only to OS..
Operating System Concepts – 8th Edition
7.9
Silberschatz, Galvin and Gagne ©2009
Basic Hardware (Cont.)
 Procedure (1): The CPU hardware compare every address
generated in user mode with the registers.
 If (CPU generated address ≥ base) & (CPU generated address <
base +limit) …
– Then …..the CPU generated address is legal and allowed to
access the memory
– Else…… the CPU generated address is illegal and NOT
allowed to access the memory…..(causing a trap (/error) to OS)

This scheme prevents a user program from (accidentally or
deliberately) modifying the code or data structures of either the
operating system or other users…..(solution to protection problem)
Operating System Concepts – 8th Edition
7.10
Silberschatz, Galvin and Gagne ©2009
Basic Hardware (Cont.)
Fig. (8.2): Hardware address protection with base and limit registers
Operating System Concepts – 8th Edition
7.11
Silberschatz, Galvin and Gagne ©2009
Basic Hardware (Cont.)
 Procedure (2): restrict the ability to load base & limit registers
ONLY to OS.
 This restriction applied by using a special privileged instruction.
 Since privileged instructions can be executed only in kernel mode,
and since only the operating system executes in kernel mode…..So,
ONLY the operating system can load the base and limit registers.
 This scheme allows the operating system to change the value of the
registers but prevents user programs from changing the registers’
contents.
Operating System Concepts – 8th Edition
7.12
Silberschatz, Galvin and Gagne ©2009
Address Binding
 Address binding( or relocation): The process of associating program
instructions and data to physical memory addresses
 A user program will go through several steps -some of which may be
optional-before being executed ….. ( steps are: compiling>>>
linking>>>execution)
 Addresses may be represented in different ways during these steps.

Addresses in the source program are generally symbolic (such as
count, sum).

A compiler will typically bind these symbolic addresses to relocatable
addresses (such as "14 bytes from the beginning of this module").

The linkage editor or loader will in turn bind the relocatable addresses
to absolute addresses (physical address) (such as 74014).
 Each binding is a mapping from one address space to another.
Operating System Concepts – 8th Edition
7.13
Silberschatz, Galvin and Gagne ©2009
Address Binding (cont.)
Figure 8.3: Multistep processing of a user program.
Operating System Concepts – 8th Edition
7.14
Silberschatz, Galvin and Gagne ©2009
Address Binding (cont.)
 The binding of instructions and data to memory addresses can be
done at any step along the way:

Compile time. The compiler translates symbolic addresses to absolute
addresses. If you know at compile time where the process will reside in
memory, then absolute code can be generated (Static).

Load time : When it is not known at compile time where the process
will reside in memory, then The compiler translates symbolic addresses
to relative (relocatable) addresses. The loader translates these to
absolute addresses (Static).

Execution time. If the process can be moved during its execution from
one memory segment to another, then binding must be delayed until run
time. The absolute addresses are generated by specialhardware
(e.g.MMU)

Most general-purpose OSs use this method (Dynamic).
 Static-new locations are determined before execution.
 Dynamic-new locations are determined during execution.
Operating System Concepts – 8th Edition
7.15
Silberschatz, Galvin and Gagne ©2009
Logical vs. Physical Address Space
 Logical/virtual address: address generated by CPU
 Physical address: address seen by memory hardware
 Compile-time / load-time binding >>> logical address = physical address
 Run-time binding >>> logical address≠ physical address

Logical address space: is the set of all logical addresses generated by a
program

Physical address space: is the set of all physical addresses corresponding to
these logical addresses.

MMU (Memory-Management Unit ): h/w device that maps virtual addresses to
physical addresses at run time

Different methods of address mapping (/memory management strategies):

Continuous memory allocation

Paging

segmentation
Operating System Concepts – 8th Edition
7.16
Silberschatz, Galvin and Gagne ©2009
Simple Address Mapping Method
 For NOW, we illustrate address mapping with a simple MMU scheme:

The base register is now called a relocation register.

Basic methodology>>>> Physical address= logical address + relocation register

For example:

Base register contains 14000

If logical address =0 >>>> Physical address= 0+14000=14000

If logical address =346 >>>> Physical address= 346+14000=14346
 The user program never sees the real physical addresses. The user
program deals with logical addresses. MMU converts logical addresses into
physical addresses.
Operating System Concepts – 8th Edition
7.17
Silberschatz, Galvin and Gagne ©2009
Example of Simple Address Mapping Method
Operating System Concepts – 8th Edition
7.18
Silberschatz, Galvin and Gagne ©2009
Operating System Concepts – 8th Edition
7.19
Silberschatz, Galvin and Gagne ©2009
Swapping
 Swapping is a mechanism in which a process can be swapped temporarily
out of main memory to a backing store , and then brought back into memory
for continued execution.
 Backing store is a usually a hard disk drive or any other secondary storage
which fast in access and large .
Operating System Concepts – 8th Edition
7.20
Silberschatz, Galvin and Gagne ©2009
Swapping (Cont.)
 How swapping performed???

The system maintains a ready queue consisting of all processes whose memory
images are on the backing store or in memory and are ready to run.

Whenever the CPU scheduler decides to execute a process, it calls the
dispatcher.

The dispatcher checks to see whether the next process in the queue is in
memory.

If it is not, and if there is no free memory region, the dispatcher swaps out a
process currently in memory and swaps in the desired process.

Then, Dispatcher reloads registers and transfers control to the selected process.


Major time consuming part of swapping is transfer time
Total transfer time ∝ amount of memory swapped.

Context-switch time in such a swapping system is high.

Swapping is normally disabled but will start if many processes are running and are
using a threshold amount of memory.

Swapping is again halted when the load on the system is reduced.
Operating System Concepts – 8th Edition
7.21
Silberschatz, Galvin and Gagne ©2009
Operating System Concepts – 8th Edition
7.22
Silberschatz, Galvin and Gagne ©2009
Basic Memory Management schemes
Mem. Manegment schems
(/strategies)
Paging
Continuous
Allocation
Multiple-partition
method
(Fixed-partition
allocation)
variable size
method
Conventional
paging
(basic method)
Hierarchical
Page
Segmentation
Hashed Page
Inverted Page
>>>>These strategies can also be combined.
Operating System Concepts – 8th Edition
7.23
Silberschatz, Galvin and Gagne ©2009
Operating System Concepts – 8th Edition
7.24
Silberschatz, Galvin and Gagne ©2009
Contiguous Memory Allocation (CMA)
 The memory is usually divided into two partitions:

One for the resident OS

One for the user processes.
 We can place the OS in either low memory or high memory .
 Basic methodology:

Each process is contained in a single contiguous section of memory.
 CMA strategy can be applied in (2) methods:

Multiple-partition method/(Fixed-partition allocation) method

variable-partition allocation method
Operating System Concepts – 8th Edition
7.25
Silberschatz, Galvin and Gagne ©2009
Memory Allocation
 Method #(1): Multiple-partition method (/Fixed-partition method)

Main idea: divide memory into several fixed-sized partitions. Each
partition may contain exactly one process.

. In this multiple-partition method:

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.

The degree of multiprogramming is bound by the number of partitions

One of the simplest methods for allocating memory

This method is called (Multiprogramming with a Fixed number of
Tasks/ MFT)

This method is no longer in use
Operating System Concepts – 8th Edition
7.26
Silberschatz, Galvin and Gagne ©2009
Memory Allocation (cont.)
 Method #(2): variable-partition method:

Memory is divided into variable-sized partitions

OS maintains a list of allocated / free partitions (holes)

When a process arrives, it is allocated memory from a hole large
enough to accommodate it

Memory is allocated to processes until requirements of next process in
queue cannot be met

OS may skip down the queue to allocate memory to a smaller process
that fits in available memory

When process exits, memory is returned to the set of holes and merged
with adjacent holes, if any

The method is a generalization of the fixed-partition scheme (called
Multiprogramming with a Variable number of Tasks (MVT))
Operating System Concepts – 8th Edition
7.27
Silberschatz, Galvin and Gagne ©2009
Memory Allocation (cont.)
 Example:
Operating System Concepts – 8th Edition
7.28
Silberschatz, Galvin and Gagne ©2009
Memory Allocation (cont.)
 New problem appear in variable-partition method…(how to satisfy a
request of size (n) from a list of free holes??? )
 There are many solutions to this problem:


First fit.

Allocate the first hole that is big enough.

Searching can start either at the beginning of the set of holes or where the previous
first-fit search ended. We can stop searching as soon as we find a free hole that is large
enough.
Best fit




Allocate the smallest hole that is big enough.
We must search the entire list, unless the list is ordered by size.
This strategy produces the smallest leftover hole.
Worst fit.

Allocate the largest hole.

we must search the entire list, unless it is sorted by size.

This strategy produces the largest leftover hole, which may be more useful than the
smaller leftover hole from a best-fit approach.
Operating System Concepts – 8th Edition
7.29
Silberschatz, Galvin and Gagne ©2009
Memory Allocation (cont.)

Exercise (8.16): Given five memory partitions of 100 KB, 500 KB, 200 KB, 300
KB, and 600 KB (in order), how would each of the first-fit, best-fit, and worst-fit
algorithms place processes of 212 KB, 417 KB, 112 KB, and 426 KB (in
order)?Which algorithm makes the most efficient use of memory?
>>> Let p1, p2, p3 & p4 are the names of the processes
Best-fit:
First-fit:
P1>>> 100, 500, 200, 300, 600
P2>>> 100, 288, 200, 300, 600
P3>>> 100, 288, 200, 300, 183
100, 116, 200, 300, 183
P4 (426K) must wait
final set
of holes
P1>>> 100, 500, 200, 300, 600
P2>>> 100, 500, 200, 88, 600
P3>>> 100, 83, 200, 88, 600
P4>>> 100, 83, 88, 88, 600
100, 83, 88, 88, 174
Worst-fit:
P1>>> 100, 500, 200, 300, 600
P2>>> 100, 500, 200, 300, 388
P3>>> 100, 83, 200, 300, 388
100, 83, 200, 300, 276 << final set of hole
P4 (426K) must wait
>>> In this example, Best-fit turns out to be the best because there is no wait processes.
Operating System Concepts – 8th Edition
7.30
Silberschatz, Galvin and Gagne ©2009
Memory Allocation (cont.)
 In general witch algorithm (first-fit, best-fit, or worst-fit) is
better?

Both first fit and best fit are better than worst fit in terms of
decreasing time and storage utilization.

Neither first fit nor best fit is clearly better than the other in terms
of storage utilization, but first fit is generally faster (because it
doesn’t require full list search or sorting)
Operating System Concepts – 8th Edition
7.31
Silberschatz, Galvin and Gagne ©2009
Fragmentation
 Fragmentation is a problem appears in memory allocation censers
about unusable memory space.
 Fragmentation types:


External fragmentation: memory space to satisfy a request is available, but
is not contiguous…(i.e. storage is fragmented into a large number of small
holes)

Both the first-fit and best-fit strategies for memory allocation suffer from external
fragmentation.

(1/3) of memory may be unusable!!!
Internal Fragmentation: allocated memory may be larger than requested
memory….(i.e. some memory within partition may be left unused)
Operating System Concepts – 8th Edition
7.32
Silberschatz, Galvin and Gagne ©2009
Fragmentation (Cont.)
 External fragmentation solution:


Compaction: Memory contents shuffled to place all free memory
together in one large block

Dynamic relocation (run-time binding) needed

Compaction is expensive (high overhead)
Permit the logical address space of the processes to be noncontiguous, thus allowing a process to be allocated physical memory
wherever it is available.

Two techniques achieve this solution:
–
Paging
–
Segmentation
Operating System Concepts – 8th Edition
7.33
Silberschatz, Galvin and Gagne ©2009
Fragmentation in
Continuous memory allocation scheme
 fixed-partition method suffer from internal fragmentation
 variable-partition method suffer from external fragmentation
Operating System Concepts – 8th Edition
7.34
Silberschatz, Galvin and Gagne ©2009
Operating System Concepts – 8th Edition
7.35
Silberschatz, Galvin and Gagne ©2009
Paging
 Paging is a memory-management scheme that permits the physical
address space of a process to be non-contiguous.
 Because of its advantages, paging in its various forms is commonly used in
most OSs.
 Recent designs have implemented paging by closely integrating the
hardware and OS, especially on 64-bit microprocessors.
 Paging method also used to manage backing store (e.g. hard disk)
.
Operating System Concepts – 8th Edition
7.36
Silberschatz, Galvin and Gagne ©2009
Paging: Basic Method
 The basic methodology:

Breaking physical memory into fixed-sized blocks called frames

Breaking logical memory into blocks called pages… Where (frame size=
page size)
 When a process is to be executed, its pages are loaded into any
available memory frames from the backing store.
 The backing store is divided into fixed-sized blocks that are of the
same size as the memory frames.
 OS keeps track of free frames.
 Page table translates logical page to physical frame addresses
 Frame size:

Defined by hardware

Should be power of 2

Usually between 512 byte- 16MB
Operating System Concepts – 8th Edition
7.37
Silberschatz, Galvin and Gagne ©2009
Paging: Basic Method (cont.)
Figure 8.8 Paging model of logical and physical memory.
Operating System Concepts – 8th Edition
7.38
Silberschatz, Galvin and Gagne ©2009
Paging: Basic Method (cont.)
 Address generated by CPU is divided into:

Page number (p) – used as an index into a page table which contains the
corresponding frame number

Page offset (d) – is the displacement within the page.

Where:

m= number of bits in logical address

n= number of bits in offset part

m-n= number of bits in page number part
Operating System Concepts – 8th Edition
7.39
Silberschatz, Galvin and Gagne ©2009
Paging: Basic Method (cont.)
 Example:
Page# 0
Frame #0
Page# 1
Frame #1
Given:
n=2 bits
m=4 bits
Page# 2
Frame #2
Page# 3
Frame #3
Page size=4 B
Physical mem. Size=32 B
# of pages= 8 pages
>> Convert the logical address
(13) to physical address.
Base address is the physical
address of first byte in
the target frame
>>How to convert from logical address to physical address
in paging???
Physical address = base address+ offset
= (frame # * frame size) + offset
Operating System Concepts – 8th Edition
7.40
.
.
.
.
.
.
.
.
.
Frame #7
Silberschatz, Galvin and Gagne ©2009
Paging: Basic Method (cont.)
 Example. (Cont.):
Given:
n= 2 bits
m= 4 bits
Page size=4 B
Physical mem. Size=32 B
# of pages= 8 pages
>> Convert the logical address (13) to physical address.
Physical address = base address+ offset
= (frame # * frame size) + offset
Logical address= 13 (in decimal) = (1101) in binary
Page # = (11) = 3
Offset= (01)= 1
By using the page table>>> frame # = 2
>>> Physical address of logical address (13) =(2* 4) + 1=9
Exercise: Convert the following logical addresses (given in decimal) to physical for the same
example: (0, 4,10,15)
Operating System Concepts – 8th Edition
7.41
Silberschatz, Galvin and Gagne ©2009
Paging Arithmetic Laws
>>How to convert from logical address to physical address in paging???
Physical address = base address+ offset
= (frame # * frame size) + offset

Page size = frame size

Logical address space (/size) = 2m

Physical address space (/size) = 2x (where x is the number of bits in physical
address)

Logical address space (/size) = # of pages × page size

Physical address space (/size) = # of frames × frame size

Page size= frame size= 2n

# of pages= 2m-n

# of entries (records)in page table = # of pages

Required number of pages for a process = process size/ page size (Rounded up)
Operating System Concepts – 8th Edition
7.42
Silberschatz, Galvin and Gagne ©2009
Paging: Basic method(Cont.)
Frame allocation procedure:
 When a process arrives in the
system to be executed:

Process size ( expressed in
pages) is examined. …(i.e. if
the process requires (n)
pages, at least (n) frames
must be available in memory)

If (n) frames are available>>>
they are allocated …then,
when a page is loaded into a
frame, its frame number is
put into the page table for
this process…. and so on.
Figure 8.10 Free frames (a) before allocation and (b) after allocation
Operating System Concepts – 8th Edition
7.43
Silberschatz, Galvin and Gagne ©2009
Paging: Basic Method (cont.)
 Paging scheme has NO external fragmentation..but it has an internal
fragmentation
 Example:
If process (p1) size= 1030 B , page size= 512 B..How many pages P1
will occupied??

Required # of pages= 1030/512≈ 2.01 3 pages

Notice that the last page is almost empty…. (506 bytes are allocated and
unused)……. (Internal fragmentation)….what is the solution??

Make page size small to reduce the internal fragmentation<<<<<Unsuitable
solution because:

Page table size will increased…(more memory consumption & moreover
head)

Disk I/O is more efficient when the amount data being transferred is larger
 Generally, page sizes have grown over time as processes, datasets, and
main memory have become larger.
Operating System Concepts – 8th Edition
7.44
Silberschatz, Galvin and Gagne ©2009
Paging: Basic Method (cont.)
 Page table:

Part of process control block (PCB)

Each process has one page table

Contains 1 entry per logical page

Used to translate logical addresses to physical addresses in software
 OS keep track of physical memory allocation by using a frame table
 Frame table:

Maintained by OS

Contains 1 entry per physical frame

Whether free or allocated

If allocated>>> it contains allocation information (Process ID, page#)
Operating System Concepts – 8th Edition
7.45
Silberschatz, Galvin and Gagne ©2009
Paging hardware
 The hardware implementation of the page table can be done in several
ways.
 Different methods to implement (/store) the page table(PT):


Method (1): Storing PT in dedicated registers:

The simplest case

Page table is stored in a set of dedicated, high-speed registers

Instructions to load/modify PT registers are privileged

Acceptable solution if page table is small
Method (2): Storing whole PT in RAM :

This method is used if PT is large (common)

PT stored in main memory

Base address of PT is stored in page table base register (PTBR)

Context switch involves changing (1) register only (i.e. fast)

Two physical memory accesses are needed per user memory access (one for the
page-table entry, one for the byte).
–
memory access is slowed by factor of 2>>> this delay is unacceptable!!
Operating System Concepts – 8th Edition
7.46
Silberschatz, Galvin and Gagne ©2009
Paging hardware (Cont.)

Method (3): Use a cash (TLB):

Use a special, small, fast cache, called a Translation Look-aside Buffer
(TLB).

The search is fast but the hardware is expensive.

TLB holds subset of page table entries

Each entry in the TLB consists of two parts: a key (page #) and a value
(frame #)

Input value (logical address(L.A.)) is compared simultaneously with all keys
simultaneously.
–
If L.A is found (/ TLB hit ) >> corresponding value (frame #) is
returned to calculate physical address (P.A.)
–
If L.A is NOT found (/ TLB miss )>>
»
Access PT in RAM to get the frame# and then access RAM
»
The page # and frame # is added to TLB, so that they will be found
quickly on the next reference.
Operating System Concepts – 8th Edition
7.47
Silberschatz, Galvin and Gagne ©2009
Paging hardware (cont.)
Figure 8.11 :Paging hardware with TLB.
Operating System Concepts – 8th Edition
7.48
Silberschatz, Galvin and Gagne ©2009
Paging Hardware (Cont.)
 Hit ratio: percentage of times that a page# is found in TLB
 Effective memory access time :average time for a memory access
(including TLB lookup)
 Example:

IF [ TLB lookup: 20ns, Memory access time: 100ns, Hit ratio:
80%]…Calculate the effective memory access time

If TLB hit >>> it takes (1) TLB access & (1) memory access
Memory access time if TLB hit = 20+ 100 = 120 ns

If TLB miss >>> it takes (1) TLB access & (1) memory access to read PT &
(1) memory access to access the desired byte
Memory access time if TLB miss= 20+ 100 +100 = 220 ns

Hit ratio =80% >>> So, miss ratio= 20 %
Effective access time = (0.8 × 120) + (0.2 × 220) = 140ns
Operating System Concepts – 8th Edition
7.49
Silberschatz, Galvin and Gagne ©2009
Protection in Paging
 Memory protection in a paged environment is accomplished by protection
bits associated with each frame. Normally, these bits are kept in the page
table.
 One bit can define a page to be read-write or read-only.

Every reference to memory goes through the page table to find the correct frame
number. At the same time that the physical address is being computed, the
protection bits is checked to verify that no writes are being made to a readonly page.

An attempt to write to a read-only page causes a hardware trap to the operating
system
 One additional bit is generally attached to each entry in the page table: a
valid-invalid bit.

When this bit is set to ``valid''>>>the page is in the process's logical address
space and is thus a legal (/ valid) page.

When the bit is set to ``invalid'‘>>> the page is not in the process's logical
address space.

Illegal addresses are trapped by use of the valid-invalid bit.

The OS sets this bit for each page to allow or disallow access to the page.
Operating System Concepts – 8th Edition
7.50
Silberschatz, Galvin and Gagne ©2009
Protection in Paging (Cont.)
 Example:
Consider a system with a 14-bit address space , we
have a program that should use only addresses 0 to
10468. the page size is 2 KB. What are the valid
pages for this program??
m = 14 ,, page size =2 KB= 2 11 B
Logical address space = 2 m = 214 =16384 B
Logical addresses range (0- 16383)
# of required pages I for this program=
program size / page size
= 10469 / 2 11 = 5.11 ≈ 6 pages
Valid pages for this program: pages # 0,1,2,3,4,5.

Addresses in pages 0, 1, 2, 3, 4, and 5 are mapped normally through PT.

Any attempt to generate an address in pages 6 or 7>>> the computer will
trap to the OS
Operating System Concepts – 8th Edition
7.51
Silberschatz, Galvin and Gagne ©2009
Shared Pages

An advantage of paging is the possibility of sharing common code. This
consideration is particularly important in a time-sharing environment.

Example:

Consider a system that supports 40 users, each of whom executes a text
editor

If the text editor consists of 150 KB of code and 50 KB of data space,>>> we need 8,000 KB to
support the 40 users .

If the code shared>>> the required memory space =2,150 KB
 Only one copy of the editor need be kept in RAM. Each user's page table
maps onto the same physical copy of the editor, but data pages are mapped
onto different frames.
 The code must be reentrant to be shareable …(Reentrant code is non-self-
modifying code; it never changes during execution)
Operating System Concepts – 8th Edition
7.52
Silberschatz, Galvin and Gagne ©2009
Shared Pages (Cont.)
Figure 8.13 : Sharing of code in a paging environment.
Operating System Concepts – 8th Edition
7.53
Silberschatz, Galvin and Gagne ©2009
Operating System Concepts – 8th Edition
7.54
Silberschatz, Galvin and Gagne ©2009
Segmentation
 Users prefer to view memory as a
collection of variable-sized
segments, with no necessary ordering
among segments.
 Address space is made up of variable-
sized logical segments e.g. main
function, subroutines, some data
structures (list, array, stack, etc.), . . .
 Segmentation is a memory-
management scheme that supports the
user view of memory. A logical address
space is a collection of segments.
Operating System Concepts – 8th Edition
7.55
Silberschatz, Galvin and Gagne ©2009
Segmentation (cont.)
 Each segment has a name and a length. The addresses specify both the
segment name and the offset within the segment.
 The user therefore specifies each address by two quantities:

a segment name ….(replaced by segment # for simplicity)

an offset
 Logical addresses specify < segment identifier, offset >
Operating System Concepts – 8th Edition
7.56
Silberschatz, Galvin and Gagne ©2009
Segmentation: Hardware
 Segment Table

Segment Table used to convert from logical to physical
addresses

Segment table entry = ( segment base, segment limit )

Base = starting physical address of segment in memory

Limit = size of segment
 Logical address consist of :

Segment number (s) -- segment number is used as an index into a
segment table .

Segment offset (d)- segment offset is first checked against limit and
then is combined with base address to define the physical memory
address

The offset of the logical address must be between 0 and the
segment limit. If it is not, we trap to the OS (logical addressing
attempt beyond end of segment).
.
Operating System Concepts – 8th Edition
7.57
Silberschatz, Galvin and Gagne ©2009
Segmentation: Hardware (Cont.)
>>How to convert from logical address to physical address in
segmentation???
IF (offset < limit) then
Physical address=
base
address+
offset
Figure
8.19:
Segmentation
hardware
Else
Trap (address error)
Operating System Concepts – 8th Edition
7.58
Silberschatz, Galvin and Gagne ©2009
Segmentation: Hardware (Cont.)
 Example:
Consider the segmentation system
shown in the figure..Convert the
following logical addresses (given
in decimal) to physical addresses.
case(1):
L.A.= 2,53
IF (offset < limit) then
Physical address= base address+ offset
Else
Trap (address error)
Segment # =2
Offset= 53
Base= 4300
P.A. = 4300+53=4353
Operating System Concepts – 8th Edition
7.59
Silberschatz, Galvin and Gagne ©2009
Segmentation: Hardware (Cont.)
 Example. (Cont.):
case(2):
L.A.= 0, 1222
IF (offset < limit) then
Physical address= base address+ offset
Else
Trap (address error)
Segment # = 0
Offset= 1222
Offset (1222) is not less than limit
(1000) …
So, it is illegal reference, trap
to operating system
Operating System Concepts – 8th Edition
7.60
Silberschatz, Galvin and Gagne ©2009
Segmentation
 Segmentation suffer from external
fragmentation
Operating System Concepts – 8th Edition
7.61
Silberschatz, Galvin and Gagne ©2009
End of Chapter 8
Operating System Concepts – 8th Edition
Silberschatz, Galvin and Gagne ©2009
Helpful Information
 The computer system has two modes of operation :


User mode

Kernel mode (also called supervisor mode/ system mode/ privileged mode).
There is a bit (mode bit) indicate the current mode: kernel (0) or user (1).
 When the computer system is executing on behalf of a user application, the
system is in user mode.
 Whenever the operating system gains control of the computer, it is in kernel
mode.
 Only the operating system executes in kernel mode
 Privileged instructions: are a machine code instructions that may only be
executed when the processor is running in kernel mode.
• Example of privileged instructions: I/O operations and interrupt management.
•If
an attempt is made to execute a privileged instruction in user mode>>> the
hardware does not execute the instruction & traps it to the operating system.
Operating System Concepts – 8th Edition
7.63
Silberschatz, Galvin and Gagne ©2009
Helpful Information
 Fragmentation is a problem about unusable memory space.
…..(i.e. waste in memory)

Fragmentation types:

External fragmentation: memory space is NOT allocated and unused

Internal Fragmentation: memory space is allocated and unused
Operating System Concepts – 8th Edition
7.64
Silberschatz, Galvin and Gagne ©2009