2. To provide a satisfactory level of performance for system users.
3. To protect each process from each others.
4. To make the addressing of memory space as transparent as possible for the programmers.
i. Single Contiguous Allocation:-
Advantage:-
1. Easy to understand and use the system (simplicity).
Disadvantage:-
1. Poor utilization of memory.
2. User's job is limited to the size of
the available main memory.
ii. Partitioned Memory Management:-
Memory is divided into regions or partitions each of which can hold one process. It facilitates multiprogramming environment.
Advantage:-
1. Supports multiprogramming.
ii. a. Fixed Partition Scheme:-
Fixed-sized partitions are usually created at the time of installation of O.S. Partition sizes are chosen by system admin. The partition table is maintained by O.S.
Advantage:-
It facilitates multiprogramming.
Drawbacks:-
1. Internal fragmentation, which collectively accommodates another process.
2. Fixed partition size can prevent a
process being run due to non-availability of a partition of sufficient size
even though there is the total amount of available memory is greater than job
requirement.
3. Internal
fragmentation: - The unused space in between 2 partitions, the occurrence
of wasted space in this way is called internal fragmentation. (Wasted within
space allocated to a process).
ii . b.Dynamic partition scheme:
Memory
is allocated to a process at the time of loading the exact amount it requires
i.e. at runtime. Processes are loaded into conductive area until memory is
filled or more likely, remaining space is too small to accommodate another process.
External Fragmentation:
The terms external refers to space
outside any process allocation.
Coalescing of Holes:
It may
frequently happen that a process adjacent to one more hole/slots may terminate
and free its space allocation. This results in two or three adjacent holes
which can then be viewed and utilized as a single hole. It is a significant
factor in maintaining fragmentation within useable limit.
Selection of free slot:
1.
First fit algorithm.
2.
Best fit algorithm.
3.
Worst fit algorithm.
Best fit policy:-
An incoming process is placed in a hole/slot in which it fits mostly. Free table is kept sorted by size in ascending order. So, the free area closest in size but >= the desired partition is allocated (Unused space is minimum).
Advantage:-
1. Searching time for the best fit is usually smaller.
2. If there exists a free area of exactly the desired size, it will be selected.
3. Desired partition will be taken from the smallest possible free area. Therefore larger free areas are left untouched for further use.
Limitation:-
1. Free area is usually not exactly the right size and must be split into 2 pieces (1. Where it’s tightly fitted | 2. Rest area). Therefore resulting free/rest areas are often quite small – so small that it may be almost worthless.
First fit policy:-
An incoming process is placed in the first available hole/slot which can accommodate it.
Disadvantage:-
1. Each time a partition is released the free area table has to be sorted. This consumes some time.
2. As this algorithm chooses the first free area available, there is the least possibility of leaving a large free area, i.e. more small free areas are possible to generate (i.e. generation of small free areas are highly probable rather than large ones). This causes inconvenience to run jobs that require large memory areas.
Worst fit policy:-
An incoming process is placed in the hole/slot which leaves the maximum amount of unused space (Current largest hole is selected).
Advantages of Partitioned Memory Management:-
1. It facilitates multiprogramming and efficient utilization of processes and I/O devices.
2. It requires no special hardware.
3. Algorithms used are simple and easy to implement.
Disadvantages of Partitioned Memory Management:-
1. Fragmentation can be a significant problem.
2. If not fragmented a single free area may not be large enough for a partition.
3. Jobs partition size is limited to the size of physical memory.
iii. Relocatable memory management:-
Scheme – This scheme periodically combines all free areas into one contiguous area by making the contents of all allocated partition, so that they can be contiguous. This process is called compaction.
iv. Paged memory management (Paging):-
Scheme – It actually facilitates non-contiguous
allocation. Fragmentation problem can be avoided if non-contiguous allocation
of physical memory can be made.
Non-contiguous allocation means parts of address space of a
job is placed in different parts of memory. This suggests translation of address reference during
execution of jobs.
Paging – Paging means a memory management scheme that
facilitates non-contiguous allocation of physical memory to a process.
Pages – Each process address space is notionally
divided into a number of fixed-sized equal chunks called pages.
Block - Physical memory is also conceptually divided
into pieces of the same size of pages is called block or page frame.
Address mapping - Maintain the illusion of the continuity of the virtual address space of a process, despite its non-contiguous allocation in physical memory.
Page block mapping –
Placement of any
page into any block is made possible by using a suitable hardware mapping facility,
is called PMT (Page Map Table). A separate register for each space is desired.
This may either be special hardware register or reserve section of memory.
Page size: - Large page is equivalent to a partition, so,
the scheme will be essentially relocatable partition memory management. Too
small page size requires many page map registers. The optimum page size is 1k
to 4k.
Paging doesn’t guarantee 100% utilization of memory because a job can’t be loaded into the memory if its total address space cannot be accommodated – Thus there is always a chance of leaving a few pages of memory unutilized.
Implementation of Paging:-
1. This
requires substantial relocation in address space of the process.
2. An address is of the form (p, d) where p is the page no. containing the location and d is the offset of the location from the start of the page.
For simplicity it is assumed a 16-bit address with displacement 11 bit and page no. containing 5 bits.
Advantage of Paging:-
1. Fragmentation problem is removed and memory utilization is improved.
Disadvantage:-
1. Complexity in software.
2. More hardware requirement (Because of Page Map Registers and Memory Protection Mechanism).
3. If at any instant the available memory is insufficient to hold the total address space of a process, then that available memory cannot be utilized in this scheme.
v. Demand paged memory management (Virtual
Memory Scheme):-
2. The total address space of processes is conceptually divided into pages of typical sizes, a portion of the disk is used as virtual memory and address spaces of processes are kept in virtual memory.
Page replacement policy:-
It is the algorithm to decide which page is to be replaced. There are 3 algorithms:-
1. First In First
Out (FIFO)
2. Least Recently
Used (LRU)
3. Optimal
FIFO:- This method selects the page which hase be resident in memory for the longest time, this is with the idea that such a page may not be needed anymore.
Advantage:-
1. Algorithm is very simple to understand and easy to implement.
Disadvantage:-
1. The page that is selected for removal may be referenced in the next moment, this is because the longest time in memory does not necessarily mean least in use. FIFO algorithm does not check references of pages.
2. Increase in memory does not necessarily increase the performance of the system – called FIFO anomaly (Belady’s Anomaly).
2. LRU :- The page not referred for the longest time is selected for removal. This could notionally require that a timestamp recording is made for a page block at the time of each page reference. A page with the oldest timestamp would then be selected.
Disadvantage:-
Implementing LRU requires software and hardware overhead and also time-consuming.
3. Optimal:- It’s easy to describe but difficult to implement. This algorithm has the lowest page fault rate of all algorithms, the optimal page algorithms simply says that the page with the highest level should be removed (The page which will be referred after longest time).
Belady’s Anomaly:-
1. The general principle is if the
number of page frame is increased, the page fault rate will be decreased.
2. Consider the reference string “123412512345”.
3. Consider 4 page frames. There
would be 10 page faults.
4. With 3 page frames, there would be
9 page faults.
5. This result is most unexpected and
is known as Belady’s Anomaly. It’s not always true and is applicable only for
FIFO algorithm.
vi. Segmentation:-
1. A segment can be defined as a logical grouping of instructions such as subroutines, functions, array or data area.
2. Every program is a collection of these segments. Segmentation is the technique for managing these segments.
3. Each segment has a name and a length.
4. The address of a segment specifies both segment name and the offset within the segment.
5. The Segment table is a table where each entry of the segment table has a segment base and a segment limit.
6. The logical address consists of 2 parts :
6.1. Segment number (s).
6.2. An offset into that segment (d).
Advantages:-
1. It eliminates fragmentation – by moving segments around, fragmented memory space can be combined into a single free area.
2. Segmentation supports virtual memory.
3. It allows dynamically growing segment.
4. Dynamic linking and loading of segments.
vii. Page DE segments.
1. Both paging and segmentation has their advantages and disadvantages. It’s better possible to combine these 2 schemes to improve on each – The combined scheme is page DE segments.
2. Each segment in this scheme is divided into pages. And each segment maintains a PMT.
3. The logical address is divided into 3 parts (s, p, d).
Advantage:-
1. The main advantage of this scheme is to avoid fragmentation and it supports user view of memory.
Translation look aside buffer:-
1. Whenever the processor needs to access a particular page, first of all it searches the Translation Look aside Buffer (TLB).
2. The TLB acts like a Cache and contains page table entries that entries must have been recently/frequently used.
3. If the desired page table entry is present in TLB it is called TLB Hit and then the frame number is retrieved and the real address is accessed.
4. If the desired page table entry is not present in TLB (TLB Miss) then the processor searches the PMT for corresponding page table entry.
5. The Valid Bit shows page is in main memory and the processor can retrieve the frame number from the page table entry to form the real address.
6. If the bit shows ‘invalid’ then the desired page is not in main memory and page fault happens. Then the OS loads the desired page into main memory from secondary memory.
Question 1: - What do you mean by logical
address and physical address?
Answer: - An address generated by CPU is called physical address.An address generated by MMU is called logical address.Physical address = Logical address + contents of the base register
Question 2: - What is dynamic Loading?
Answer: - Loading the routines at runtime is called dynamic loading. In dynamic loading a routine is not loaded unless it is called.
Question 3: - What do you mean by Swapping?
Answer: - Combined effect of swap in and swap out.
Moving of a process from main memory to back in store and moving of a process
from store to main memory is called Swapping.
Problems:-
1. For variable memory system, find the selection of free slot of a incoming process of size 25k among the free slots:-
20k, 15k, 40k, 60k, 10k, 26k using
best fit, worst fit and first-fit policy.
Answer: Best fit: 26k
First fit: 40k
Worst fit: 60k
Allocation algorithm:
Step 1:Search for free area >= partition desire
Step 2:If free area> the partition desired
A. Split the free part into two parts:-
1. Equal to the desire partition.
2. Rest area.
B. Allocate one part to the desired partition.
C. Leave the rest part of the free area.
D. Update the tables of allocated partition and free area.
Step 3:Else inform inability to allocate desired partition at this time, this means there's not enough space in memory
Step 4:Stop
Deallocation algorithm:
Step 1:Search for free area adjacent to the partition deleted.
Step 2:If found, Merge the deallocated partition to the adjacent free area.
Step 3:Update the entries in the both tables of allocation partition and free area.
Step 4:Stop
Comments
Post a Comment