MOSES NJUGUNA KIMANI
BIT/0430/2017
OPERATING SYSTEMS
CAT 2
1.File are allocated disk space by the operating systems. Explain the three ways of allocating disk space.
There are three types of allocation:
a) contiguous allocation
Each file occupies a contiguous set of blocks on the disk. The location of a file is defined by the disk address of the first block and its length. For example, if a file requires n blocks and is given a block b as the starting location, then the blocks assigned to the file will be: b, b+1, b+2,……b+n-1. This means that given the starting block address and the length of the file we can determine the blocks occupied by the file.
The directory entry for a file with contiguous allocation contains
· Address of starting block
· Length of the allocated portion.
Advantages:
· Both the Sequential and Direct Accesses are supported by this. For direct access, the address of the kth block of the file which starts at block b can easily be obtained as (b+k).
· This is extremely fast since the number of seeks are minimal because of contiguous allocation of file blocks.
Disadvantages:
· Because the file blocks are distributed randomly on the disk, a large number of seeks are needed to access every block individually. This makes linked allocation slower.
b) linked allocation
In this case each file is a linked list of disk blocks which need not be contiguous. The disk blocks can be scattered anywhere on the disk.
The directory entry contains a pointer to the starting and the ending file block. Each block contains a pointer to the next block occupied by the file.
Advantages:
· This is very flexible in terms of file size. File size can be increased easily since the system does not have to look for a contiguous chunk of memory.
· This method does not suffer from external fragmentation. This makes it relatively better in terms of memory utilization.
Disadvantage
· Pointers required in the linked allocation incur some extra overhead.
c) indexed allocation
In this scheme, a special block known as the Index block contains the pointers to all the blocks occupied by a file. Each file has its own index block. The ith entry in the index block contains the disk address of the itch file block. The directory entry contains the address of the index block.
Advantages:
· This supports direct access to the blocks occupied by the file and therefore provides fast access to the file blocks.
· It overcomes the problem of external fragmentation.
Disadvantages:
· The pointer overhead for indexed allocation is greater than linked allocation.
2. Describe the following
a) SYSTEM CALLS
A system call is a way for programs to interact with the operating system. or A computer program makes a system call when it makes a request to the operating system’s kernel. System call provides the services of the operating system to the user programs via Application Program Interface(API). It provides an interface between a process and operating system to allow user-level processes to request services of the operating system. System calls are the only entry points into the kernel system. All programs needing resources must use system calls. When a program in user mode requires access to RAM or a hardware resource, it must ask the kernel to provide access to that resource. This is done via something called a system call. System calls provide an interface between the process and the operating system.
The following Services Provided by System Calls:
Process creation and management
Main memory management
File Access, Directory and File system management
Device handling (I/O)
Protection
There are 5 different categories of system calls
b) HARDWERE INTERRUPTS
Hardware interrupts is a signal which has highest priority from hardware that are used by devices to communicate that they require attention from the operating system. They are sent to the processor from an external device, which is either a part of the computer itself, such as a disk controller, or an external peripheral.
These hardware interrupts can be classified into two categories;
1. Periodic Interrupt
If the interrupts occurred at fixed interval in timeline then that interrupts are called periodic interrupts
2. Aperiodic Interrupt
If the occurrence of interrupt cannot be predicted then that interrupt is called aperiodic interrupt
C) DIRECT MEMORY ADDRESs
(DMA) is a feature of computer systems that allows certain hardware subsystems to access main system memory (Random-access memory), independent of the central processing unit (CPU). Also is a capability provided by some computer bus architectures that allows data to be sent directly from an attached device (such as a disk drive) to the memory on the computer's motherboard? The microprocessor is freed from involvement with the data transfer, thus speeding up overall computer operation.
3. Explain replacement algorithms for paged system.
Page replacement algorithms decide which memory pages to page out, sometimes called swap out, or write to disk, when a page of memory needs to be allocated. Page replacement happens when a requested page is not in memory (page fault) and a free page cannot be used to satisfy the allocation, either because there are none, or because the number of free pages is lower than some threshold.
Each operating system uses different page replacement algorithms. To select the particular algorithm,
The algorithm with lowest page fault rate is considered.
A.Optimal page replacement algorithm
This algorithm state that: Replace the page which will not be used for longest period of time i.e. future knowledge of reference string is required.
•Often called Balady's Min Basic idea: Replace the page that will not be referenced for the longest time.
•Impossible to implement
B.First in First out (FIFO)
This is the simplest page replacement algorithm. In this algorithm, operating system keeps track of all pages in the memory in a queue, oldest page is in the front of the queue. When a page needs to be replaced page in the front of the queue is selected for removal.
C.Second chance page replacement
A simple modification to FIFO that avoids the problem of heavily used page. It inspects the R
Bit if it is 0, the page is both old and unused, so it is replaced immediately. If the R bit is
1, the bit is cleared, the page is put onto the end of the list of pages, and its load time is
Updated as though it had just arrived in memory. Then the search continues.
D. Least recently used page replacement
In this algorithm, the page that has not been used for longest period of time is selected for replacement.
Although LRU is theoretically realizable, it is not cheap. To fully implement LRU, it is necessary to
Maintain a linked list of all pages in memory, with the most recently used page at the front and the least recently used page at the rear. The difficulty is that the list must be updated on every memory
Reference. Finding a page in the list, deleting it, and then moving it to the front is a very time-consuming
Operation, even in hardware.