Thursday, September 25, 2008

Paging and Segmentation

Paging:
In computer operating systems that have their main memory divided into pages, paging (sometimes called swapping) is a transfer of pages between main memory and an auxiliary store, such as hard disk drive.[1] Paging is an important part of virtual memory implementation in most contemporary general-purpose operating systems, allowing them to use disk storage for data that does not fit into physical RAM. Paging is usually implemented as architecture-specific code built into the kernel of the operating system.

Segmentation:
Segmentation is one approach to memory management and protection in the operating system. It has been superseded by paging for most purposes, but much of the terminology of segmentation is still used, "segmentation fault" being an example. Some operating systems still have segmentation at some logical level although paging is used as the main memory management policy.

Wednesday, September 10, 2008

LINKED ALLOCATION

The problems in contiguous allocation can be traced directly to the requirement that the spaces be allocated contiguously and that the files that need these spaces are of different sizes. These requirements can be avoided by using linked allocation.

In linked allocation, each file is a linked list of disk blocks. The directory contains a pointer to the first and (optionally the last) block of the file. For example, a file of 5 blocks which starts at block 4, might continue at block 7, then block 16, block 10, and finally block 27. Each block contains a pointer to the next block and the last block contains a NIL pointer. The value -1 may be used for NIL to differentiate it from block 0.


With linked allocation, each directory entry has a pointer to the first disk block of the file. This pointer is initialized to nil (the end-of-list pointer value) to signify an empty file. A write to a file removes the first free block and writes to that block. This new block is then linked to the end of the file. To read a file, the pointers are just followed from block to block.

There is no external fragmentation with linked allocation. Any free block can be used to satisfy a request. Notice also that there is no need to declare the size of a file when that file is created. A file can continue to grow as long as there are free blocks. Linked allocation, does have disadvantages, however. The major problem is that it is inefficient to support direct-access; it is effective only for sequential-access files. To find the ith block of a file, it must start at the beginning of that file and follow the pointers until the ith block is reached. Note that each access to a pointer requires a disk read.


Another severe problem is reliability. A bug in OS or disk hardware failure might result in pointers being lost and damaged. The effect of which could be picking up a wrong pointer and linking it to a free block or into another file.

File Allocation Methods

One main problem in file management is how to allocate space for files so that disk space is utilized effectively and files can be accessed quickly. Three major methods of allocating disk space are:
* Contiguous Allocation
* Linked Allocation
* Indexed Allocation.
Each method has its advantages and disadvantages. Accordingly, some systems support all three (e.g. Data General's RDOS). More commonly, a system will use one particular method for all files.

Contiguous File Allocation
  • Each file occupies a set of contiguous block on the disk
  • Allocation using first fit/best fit.
  • A need for compaction
  • Only starting block and length of file in blocks are needed to work with the file
  • Allows random access
  • Problems with files that grow.

Linked File Allocation

  • Each file is a linked list of blocks
  • NO external fragmentations
  • Effective for sequential access.
  • Problematic for direct access

File Allocation Table (FAT)

  • Variation of the link list(MS/DOS and OS/2)

- A section of the disk at the beginning of each partition (Volume) is set aside to contain a FAT
- FAT has one entry for each disk block, pointing to the next block in the file.
- The link list is implemented in that section
- Actual file blocks contain no links

Indexed File Allocation

  • Indexed allocation is bringing all the pointers together
  • Much more effective for direct access
  • Inefficient for small files