Operating System Practical

Página 1

CPU scheduling -

is defined as a method which permits the process to use the CPU conveniently and an efficient way when another process execution is on hold or in a waiting state because of a lack of resources such as I/O, etc. The purpose of CPU scheduling is used to improve the efficiency of the system and make the system fast and fair.

First Come First Serve (FCFS) -

is an operating system scheduling algorithm that automatically executes queued requests and processes in order of their arrival. It is the easiest and simplest CPU scheduling algorithm. In this type of algorithm, processes which requests the CPU first get the CPU allocation first. This is managed with a FIFO queue.

Shortest job first (SJF) -

shortest job next, is a scheduling policy that selects the waiting process with the smallest execution time to execute next. SJN is a non-preemptive algorithm. or The processes are put into the ready queue based on their burst times. In this algorithm, the process with the least burst time is processed first.

Priority scheduling -

is a method of scheduling processes based on priority. In this method, the scheduler chooses the tasks to work as per the priority. It involves priority assignment to every process, and processes with higher priorities are carried out first, whereas tasks with equal priorities are carried out on a first-come-first-served (FCFS) or round robin basis. An example of a general-priority-scheduling algorithm is the shortest-job-first (SJF) algorithm.

Round robin scheduling (RRS) -

is a job-scheduling algorithm that is considered to be very fair, as it uses time slices that are assigned to each process in the queue or line. Each process is then allowed to use the CPU for a given amount of time, and if it does not finish within the allotted time, it is preempted and then moved at the back of the line so that the next process in line is able to use the CPU for the same amount of time.

Least Recently Used (LRU) page replacement policy-

replaces the page that has not been used for the longest period of time. It is one of the algorithms that were made to approximate if not better the efficiency of the optimal page replacement algorithm.

FIFO Page Replacement Algorithm-

As the name suggests, this algorithm works on the principle of “ First in First out “.It replaces the oldest page that has been present in the main memory for the longest time.It is implemented by keeping track of all the pages in a queue.

Optimal Page Replacement -

is an algorithm that works as follows: when a page needs to be swapped in, the operating system swaps out the page whose next use will occur farthest in the future.

Best-fit -

memory allocation makes the best use of memory space but slower in making allocation.

First-fit -

memory allocation is faster in making allocation but leads to memory waste.

Worst-fit -

memory allocation is opposite to best-fit. It allocates free available block to the new job and it is not the best choice for an actual system.

Banker's algorithm is a deadlock avoidance algorithm -

is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation for predetermined maximum possible amounts of all resources, then makes an “s-state” check to test for possible activities, before deciding whether allocation should be allowed to continue.

It is named so because this algorithm is used in banking systems to determine whether a loan can be granted or not.

Readers Writers Problem -

Readers - only read the data set they do not perform any updates.

Writers - can do both read and write. can perform updates.

Problems - One set of data is shared among a number of processes.

allow multiple readers to read at the same time

only one single writer can access the shared data at same time.

read - write and write - write crashes

If writer W1 has begun writing process then

No additional writer can perform write function

No reader is allowed to read

If 1 or more readers are reading then

Other readers may read as well

No writer may perform write function until all readers have finished reading

Página 2

1. New - A program which is going to be picked up by the OS into the main memory is called a new process.

2. Ready - Whenever a process is created, it directly enters in the ready state, in which, it waits for the CPU to be assigned. The OS picks the new processes from the secondary memory and put all of them in the main memory. The processes which are ready for the execution and reside in the main memory are called ready state processes. There can be many processes present in the ready state.

3. Running - One of the processes from the ready state will be chosen by the OS depending upon the scheduling algorithm. Hence, if we have only one CPU in our system, the number of running processes for a particular time will always be one. If we have n processors in the system then we can have n processes running simultaneously.

4. Block or wait - From the Running state, a process can make the transition to the block or wait state depending upon the scheduling algorithm or the intrinsic behavior of the process. When a process waits for a certain resource to be assigned or for the input from the user then the OS move this process to the block or wait state and assigns the CPU to the other processes.

5. Completion or termination - When a process finishes its execution, it comes in the termination state. All the context of the process (Process Control Block) will also be deleted the process will be terminated by the Operating system.

6. Suspend ready - A process in the ready state, which is moved to secondary memory from the main memory due to lack of the resources (mainly primary memory) is called in the suspend ready state.

If the main memory is full and a higher priority process comes for the execution then the OS have to make the room for the process in the main memory by throwing the lower priority process out into the secondary memory. The suspend ready processes remain in the secondary memory until the main memory gets available.

7. Suspend wait - Instead of removing the process from the ready queue, it's better to remove the blocked process which is waiting for some resources in the main memory. Since it is already waiting for some resource to get available hence it is better if it waits in the secondary memory and make room for the higher priority process. These processes complete their execution once the main memory gets available and their wait is finished.

Operations on the Process

1. Creation - Once the process is created, it will be ready and come into the ready queue (main memory) and will be ready for the execution.

2. Scheduling - Out of the many processes present in the ready queue, the Operating system chooses one process and start executing it. Selecting the process which is to be executed next, is known as scheduling.

3. Execution - Once the process is scheduled for the execution, the processor starts executing it. Process may come to the blocked or wait state during the execution then in that case the processor starts executing the other processes.

4. Deletion/killing - Once the purpose of the process gets over then the OS will kill the process. The Context of the process (PCB) will be deleted and the process gets terminated by the Operating system.

Process Schedulers

1.Long Term - selects a process from the job queue and brings that process to the ready queue while the short term scheduler selects which process to execute next from the ready queue.

2.Short Term - It selects a process from the ready queue to be executed by the CPU. When the short term scheduler chooses a process from the ready queue, the currently executing process goes to the waiting state.

3.Medium Term - When the main memory is full, it swaps out the processes from the main memory to secondary memory. When the main memory is free again, it swaps in that previously swapped out process back to the main memory for execution. Then the process is executed from where it was paused.

Página 3

The Purpose of a Scheduling algorithm

Maximum CPU utilization

Fare allocation of CPU

Maximum throughput

Minimum turnaround time

Minimum waiting time

Minimum response time

There are the following algorithms which can be used to schedule the jobs.

1. First Come First Serve

It is the simplest algorithm to implement. The process with the minimal arrival time will get the CPU first. The lesser the arrival time, the sooner will the process gets the CPU. It is the non-preemptive type of scheduling.

2. Round Robin

In the Round Robin scheduling algorithm, the OS defines a time quantum (slice). All the processes will get executed in the cyclic way. Each of the process will get the CPU for a small amount of time (called time quantum) and then get back to the ready queue to wait for its next turn. It is a preemptive type of scheduling.

3. Shortest Job First

The job with the shortest burst time will get the CPU first. The lesser the burst time, the sooner will the process get the CPU. It is the non-preemptive type of scheduling.

4. Shortest remaining time first

It is the preemptive form of SJF. In this algorithm, the OS schedules the Job according to the remaining time of the execution.

5. Priority based scheduling

In this algorithm, the priority will be assigned to each of the processes. The higher the priority, the sooner will the process get the CPU. If the priority of the two processes is same then they will be scheduled according to their arrival time.

6. Highest Response Ratio Next

In this scheduling Algorithm, the process with highest response ratio will be scheduled next. This reduces the starvation in the system.

CPU utilisation –

The main objective of any CPU scheduling algorithm is to keep the CPU as busy as possible. Theoretically, CPU utilisation can range from 0 to 100 but in a real-time system, it varies from 40 to 90 percent depending on the load upon the system.

Throughput –

A measure of the work done by CPU is the number of processes being executed and completed per unit time. This is called throughput. The throughput may vary depending upon the length or duration of processes.

Turnaround time –

For a particular process, an important criteria is how long it takes to execute that process. The time elapsed from the time of submission of a process to the time of completion is known as the turnaround time. Turn-around time is the sum of times spent waiting to get into memory, waiting in ready queue, executing in CPU, and waiting for I/O.

Waiting time –

A scheduling algorithm does not affect the time required to complete the process once it starts execution. It only affects the waiting time of a process i.e. time spent by a process waiting in the ready queue.

Response time –

In an interactive system, turn-around time is not the best criteria. A process may produce some output fairly early and continue computing new results while previous results are being output to the user. Thus another criteria is the time taken from submission of the process of request until the first response is produced. This measure is called response time.

Página 4

Concurrency is the execution of the multiple instruction sequences at the same time. It happens in the operating system when there are several process threads running in parallel. The running process threads always communicate with each other through shared memory or message passing. Concurrency results in sharing of resources result in problems like deadlocks and resources starvation.

It helps in techniques like coordinating execution of processes, memory allocation and execution scheduling for maximizing throughput.

Principles of Concurrency :

Both interleaved and overlapped processes can be viewed as examples of concurrent processes, they both present the same problems.

The relative speed of execution cannot be predicted. It depends on the following:

The activities of other processes

The way operating system handles interrupts

The scheduling policies of the operating system

Concurrency arises in Multiprogramming Multiple applications Multiprocessing Structured applications Distributed processing Operating system structures Principles of Concurrency relative speed of execution of processes is not predictable.

A mutual exclusion (mutex) is a program object that prevents simultaneous access to a shared resource. This concept is used in concurrent programming with a critical section, a piece of code in which processes or threads access a shared resource.

integer variables that are used to solve the critical section problem by using two atomic operations, wait and signal that are used for process synchronization.

Wait

The wait operation decrements the value of its argument S, if it is positive. If S is negative or zero, then no operation is performed.

Signal

The signal operation increments the value of its argument S

counting semaphore can be used when we need to have more than one process in the critical section at the same time

The value of counting semaphore at any point of time indicates the maximum number of processes that can enter in the critical section at the same time. A process which wants to enter in the critical section

Binary Semaphore or Mutex

In counting semaphore, Mutual exclusion was not provided because we has the set of processes which required to execute in the critical section simultaneously.

However, Binary Semaphore strictly provides mutual exclusion. Here, instead of having more than 1 slots available in the critical section, we can only have at most 1 process in the critical section. The semaphore can have only two values, 0 or 1.

first decrease the semaphore value by 1 and then check whether it gets negative or not.