Partitions are created dynamically and each process is loaded into a partition of exactly the same size as the process.
Periodic compaction of memory space needed
Placement algorithms: Best-fit, First-fit and Next-fit
The Effects of dynamic partitioning
Because of the overheads involved in compaction, the OP system must be clever in deciding how to assign processes to memory.
Best –fit: Allocated the smallest hole that is big enough.
First-fit:Allocates the first hole that is big enough, starting from the beginning of memory.
Next-fit:Starts scan fromlast allocation and allocates the next hole big enough.
Deciding which placement algorithm is the best depends on the size of the processes and the exact sequence of process swapping that takes place. In general , the First-fit usually results in the best and fastest allocation. Next-fit usually results in the last block being allocated and is in general large in size. Best-fit results in compaction having to be carried out more frequently than the others – because it results in lots of small fragments scattered throughout memory.
The above diagram shows an example of memory configuration after a number of placement and swapping-out operations. The last operation was allocating a 14 Mb process to an used 22 Mb block. The left side shows how a 16 Mb request might be satisfied.
Introduced to alleviate problem of fragmentation.
Memory is divided into page frames all of equal size.
The logical address space divided into pagesof equal size.
The memory manager determines
1. The number of pages in the program
2. Locates enough empty page frames to facilitate
3. Loads all of the pages into memory, pages need not be contiguous.
A number of tables need to be maintained for this system to operate:
1. Job Table- for each job holds the size of the job, the memory location of the Page table.
2. Page Table – For each active job the Page , page Frame memory address
3. Memory Map table – for each page Frame its location and whether free or busy.
Logical AddressIs a reference to a memory location independent of the current assignment of data to memory – a translation must be made to a physical address before memory access can be achieved. ( Mov Reg,8192)
Physical AddressIs an actual location in main memory
Memory address translation takes place at run time. Reading a word from memory involves translating a virtual or logical address, consisting of a page number and offset, into an actual physical address, consisting of a frame number and offset. This process will make use of the Page Table entries.
Logical address Physical address
If the system used 16 bits then it could utilise memory in this fashion:
Page no Displacement
with this set up the system would have 32 pages (25 ) each with 2048 bytes (2 11)
Example If a logical address of 0010100000101010 was encountered this will represent offset 42 on page 5. The Page table would be accessed to see the Mapping of page 5.
· No external fragmentation
· Fixed size pages
· Internal fragmentation – only on last page
· Non- contiguous memory (page table)
Lets say memory is only 1024 bytes = 210 address locations.
A page frame size is 256 byte 28 .
Logical address 00,0000,0000
The concept of segmentation is based on the common practice by programmers of structuring their programs in modules-logical groupings of code. With segmented memory allocation, each job is divided into several segments of different sizes, one for each module which contains pieces that perform related functions. A subroutine is an example of one such logical group. This is fundamentally different from a paging scheme, which divides the job into several pages all of the same size each of which often contains pieces from more than one program module.
A second important difference is that main memory is no longer divided into page
frames because the size of each segment is different - some are large and some are small. Therefore, as with the dynamic partitions , memory is allocated in a dynamic manner.
When a program is compiled or assembled, the segments are set up according to the program's structural modules. Each segment is numbered and a Segment Map Table (SMT) is generated for each job - it contains the segment numbers, their lengths, and (when each is loaded into memory) its location in memory.
The system maintains three tables:
1.The job table (as with static paging)
2.The segment Map table list details about each job (one for each job)
3.Memory Map Table (as before).
Like paging, the instructions within each segment are ordered sequentially, but the segments need not be contiguous in memory. We only need to know where each segment is stored. The contents of the segments themselves are contiguous (in this scheme). To access a specific location within a segment we can perform an operation similar to the one used with paged memory management. The only difference is that we work with segments instead of pages.
The addressing scheme requires the segment number and the displacement within that segment, and, because the segments are of different sizes, the displacement must be verified to make sure it isn't outside of the segment's range.
A segmented address reference requires the following steps:
1. extract the segment number and the displacement from the logical address
2. use the segment number to index the segment table, to obtain the segment base address and length.
3. check that the offset is not greater than the given length; if so an invalid address is signaled.
4. generate the required physical address by adding the offset to the base address.
The benefits of segmentation include modularity of programs and sharing and protection.
There is a maximum segment size that the programmer must be aware of.
No internal fragmentation
Unequal sized segments
Non –contiguous memory.
Some external fragmentation.
Segmentation greatly facilitates the sharing of procedures or data between a number of processes. Because a segment normally has either program code or data within them different segments within the same process can have different protections set for them. While protection is possible in a paging environment it is far more difficult to implement, the programmer is unaware of what pages hold a procedure or data area that he may wish to share, to do this the programmer would have to keep track of the exact pages that held a procedure and then assign the necessary protection to those pages.