Info-Grade

FCFS Job Scheduling Algorithm in OS (Operating System)

A process scheduler schedules different process to be assigned to the CPU based on particular scheduling algorithms. In this section we will discuss about FCFS (First come First Server) Scheduling algorithm.

First Come First Serve (FCFS)
In this algorithm jobs are executed on first come, first serve basis. It is a non preemptive, preemptive scheduling algorithm. This algorithm is easy to understand and implement. Its implementation is based on FIFO queue. It is poor in performance as average wait time is high.

Example :
Consider following process and calculate average turnover FCFS algorithm.

= Solution
Gaint Chart

Average Waiting Time = Finished time - Arrival time - Brush time
= (0+25+32)/3
= 19
Average Turnaround Time = Finished time - Arrival time
= (27+34+34)/3
= 31.67

Device Driver (Operating System)

Device driver is the software that is responsible for communicating with device controller and reset of the operating system. Device drivers are vendor specific software and are provided by I/O device manufactures. It place vital role in making operating systems independent of I/O devices. Device manufactures are responsible for providing different drivers for different operating systems. This means separate device driver is needed for Windows, Linux, Sun Solaries, Unix etc.

Fragmentation (Operating System)

Fragmentation refers to the condition of disk in which files are divided into pieces scattered around the disk. Fragmentation occurs naturally when we use a disk frequently, creating, deleting and modifying files.
There are two types of fragmentation

1. Internal Fragmentation

It occurs with all memory allocation strategies. This is caused by the fact that memory is allocated in blocks of a fixed size, wheres the actual memory needed will rarely be that exact size. For a random distribution of memory requests, on the average 1/2 block will be wasted per memory request, because on the average the last allocated block will be only half null.
Note that the same effect happens with hard drives, and that modern hardware gives us increasingly larger drives and memory at the expense of ever larger block size, which translate to more memory lost to internal fragmentation.
Some system use variable size blocks to minimize losses due to internal fragmentation.

2. External Fragmentation

External fragmentation means that the available memory is broken up into lots of little pieces, none of which is big enough to satisfy the next memory requirement, although the same total could.
All the memory allocation strategies suffer from external fragmentation, though first and best fits experience the problems more so than worst fit. The amount of memory lost to fragmentation may very with algorithm, usage patterns, and some design decision such as which end of a hole to allocate and which end to save on the free list.
Statistical analysis of first fit, for example, shows that for N blocks of allocated memory, another 0.5 N will be lost to fragmentation.
If the program in memory are relocatable, then the external fragmentation problem can be reduced via compaction, i.e. moving all processes down to one end of physical memory. This only involves updating the relocation register for each process, as all internal work is done using logical addresses.

Virtual Memory in Computer

virtual memory is a section of a hard disk that's set up to emulate the computer's RAM.

A computer can address more memory than the amount physically installed on the system. This extra memory is actually called virtual memory and it is a section of a hard disk that's set up to emulate the computer's RAM.

Virtual Memory is a storage allocation scheme in which secondary memory can be addressed as thought it were part of main memory. Virtual memory is a memory management technique that is implemented using both hardware and software. It maps memory addresses used by a program, called virtual address, into physical addresses in computer memory. It gives an illusion to the programmer that programs which are larger in size than actual memory can be executed. Virtual memory can be implemented with demand paging.
The main visible advantage of this scheme is that programs can be larger than physical memory. Virtual memory serves two purposes. First, it allows us to extend the use of physical memory by using disk. Second, it allows us to have memory protection, because each virtual address is translated to a physical address.

Modern microprocessors intended for general-purpose unit, or MMU, is built into the hardware. The MMU's job is to translate virtual addresses into physical addresses.

Virtual memory also allows the sharing of files and memory by multiple processes with several benefits:

System libraries can be shared by mapping them into the virtual address space of more than one process.
Processes can also share virtual memory by mapping the same block of memory to more than one process.
Process pages can be shared during fork() system call, eliminating the need to copy all of the page of the original (parent) process.

Semaphore Concept (Operating System)

Concept of semaphore was devised by Dijkastra in 1965. Semaphore is an integer variable that is used to record number of weakups and had been saved. If it is equal to zero it indicates that no wakeup's are saved. A positive value shows that one or more wakeup's are pending. The DOWN operation (sleep) checks the semaphore to see if it is greater than zero. If it is, it decrements the value (UP) and continues. If the semaphore is zero the process sleeps. The UP operation (weakup) increments the value of the semaphore. If one or more proces were sleeping on that semaphore then one of the process is chosen and allowed to compute its DOWN. Checking and updating the semaphore must be done as an atomic action to avoid race conditions. Product Customer problem can be solved using semaphore as below.

 
#define N 100 /* number of slots in the buffer */
typedef int semaphore; /* semaphores are a special kind of int */
semaphore mutex = 1; /* controls access to critical region */
semaphore empty = N; /* counts empty buffer slots */
semaphore null = 0; /* counts full buffer slots */
void producer(void){
    int item; 
    message m;      // message buffer. 
    while(TRUE){
        item = produce_item(); // generate something to put in buffer 
        receive(consumer, &m); // Receive an empty message, if any 
        build_message(&m, item); // construct a message to send 
        send(consumer, &m);  // send item to consumer 
    }
} 
void consumer(void){
    int item, i; 
    message m; 
    for(i=0; i<N; i++)
        send(producer, &m);  // send N empty messages 
    while(TRUE){
        receive(produce, &m);  // get message containing item   
        item = extract_item(&m); // extract item from message
        send(producer, &m); //send back empty replay 
        consumer_item(term); //do something with the item
    }
}

The Shell (Operating System)

The shell is an interface between user and the operating system

The operating system shell is the mechanism that carries out the system calls requested by the various parts of the system.
Shell is not part of the operating system kernel. The shell is the part of operating systems such as UNIX and MS-DOS where we can type commands to the operating system and receive a response.
Shell is also called the Command Line Interpreter (CLI) or the “C” prompt. Shell is the primary interface between a user sitting at his terminal and the operating system. Many shells exist, including sh, csh, ksh, and bash.
It starts out by typing the prompt, which tells the user that the shell is waiting to accept a command. If the user now types “date” command, the shell creates a child process and runs the date program as the child.

While the child process is running, the shell waits for it to terminate. When the child finishes, the shell types the prompt again and tries to read the next input line.
A more complicated command is:

cat file1 file2 file3 | sort > /dev/lp &

This command concatenates three files and pipes them to the sort program. It then redirects the sorted file to a line printer. The ampersand “&” at the end of the command instructs UNIX to issue the command as a background job. This results in the command prompt being returned immediately, whilst another process carries out the requested work.
Above command makes a series of system calls to the operating system in order to satisfy the whole request.