|
Waiting time of each process is as follows −
Average Wait Time: (0 + 10 + 12 + 2)/4 = 24 / 4 = 6
Shortest Remaining Time
- Shortest remaining time (SRT) is the preemptive version of the SJN algorithm.
- The processor is allocated to the job closest to completion but
it can be preempted by a newer ready job with shorter time to
completion.
- Impossible to implement in interactive systems where required CPU time is not known.
- It is often used in batch environments where short jobs need to give preference.
Round Robin Scheduling
- Round Robin is the preemptive process scheduling algorithm.
- Each process is provided a fix time to execute, it is called a quantum.
- Once a process is executed for a given time period, it is preempted and other process executes for a given time period.
- Context switching is used to save states of preempted processes.
Wait time of each process is as follows −
Average Wait Time: (9+2+12+11) / 4 = 8.5
Multiple-Level Queues Scheduling
Multiple-level queues are not an independent scheduling algorithm.
They make use of other existing algorithms to group and schedule jobs
with common characteristics.
- Multiple queues are maintained for processes with common characteristics.
- Each queue can have its own scheduling algorithms.
- Priorities are assigned to each queue.
For example, CPU-bound jobs can be scheduled in one queue and all
I/O-bound jobs in another queue. The Process Scheduler then alternately
selects jobs from each queue and assigns them to the CPU based on the
algorithm assigned to the queue.
What is Thread?
A thread is a flow of execution through the process code, with its
own program counter that keeps track of which instruction to execute
next, system registers which hold its current working variables, and a
stack which contains the execution history.
A thread shares with its peer threads few information like code
segment, data segment and open files. When one thread alters a code
segment memory item, all other threads see that.
A thread is also called a lightweight process. Threads provide
a way to improve application performance through parallelism. Threads
represent a software approach to improving performance of operating
system by reducing the overhead thread is equivalent to a classical
process.
Each thread belongs to exactly one process and no thread can exist
outside a process. Each thread represents a separate flow of control.
Threads have been successfully used in implementing network servers and
web server. They also provide a suitable foundation for parallel
execution of applications on shared memory multiprocessors. The
following figure shows the working of a single-threaded and a
multithreaded process.
Difference between Process and Thread
Advantages of Thread
- Threads minimize the context switching time.
- Use of threads provides concurrency within a process.
- Efficient communication.
- It is more economical to create and context switch threads.
- Threads allow utilization of multiprocessor architectures to a greater scale and efficiency.
Types of Thread
Threads are implemented in following two ways −
- User Level Threads − User managed threads.
- Kernel Level Threads − Operating System managed threads acting on kernel, an operating system core.
User Level Threads
In this case, the thread management kernel is not aware of the
existence of threads. The thread library contains code for creating and
destroying threads, for passing message and data between threads, for
scheduling thread execution and for saving and restoring thread
contexts. The application starts with a single thread.
Advantages
- Thread switching does not require Kernel mode privileges.
- User level thread can run on any operating system.
- Scheduling can be application specific in the user level thread.
- User level threads are fast to create and manage.
Disadvantages
- In a typical operating system, most system calls are blocking.
- Multithreaded application cannot take advantage of multiprocessing.
Kernel Level Threads
In this case, thread management is done by the Kernel. There is no
thread management code in the application area. Kernel threads are
supported directly by the operating system. Any application can be
programmed to be multithreaded. All of the threads within an application
are supported within a single process.
The Kernel maintains context information for the process as a whole
and for individuals threads within the process. Scheduling by the Kernel
is done on a thread basis. The Kernel performs thread creation,
scheduling and management in Kernel space. Kernel threads are generally
slower to create and manage than the user threads.
Advantages
- Kernel can simultaneously schedule multiple threads from the same process on multiple processes.
- If one thread in a process is blocked, the Kernel can schedule another thread of the same process.
- Kernel routines themselves can be multithreaded.
Disadvantages
- Kernel threads are generally slower to create and manage than the user threads.
- Transfer of control from one thread to another within the same process requires a mode switch to the Kernel.
Multithreading Models
Some operating system provide a combined user level thread and Kernel
level thread facility. Solaris is a good example of this combined
approach. In a combined system, multiple threads within the same
application can run in parallel on multiple processors and a blocking
system call need not block the entire process. Multithreading models are
three types
- Many to many relationship.
- Many to one relationship.
- One to one relationship.
Many to Many Model
The many-to-many model multiplexes any number of user threads onto an equal or smaller number of kernel threads.
The following diagram shows the many-to-many threading model where 6
user level threads are multiplexing with 6 kernel level threads. In this
model, developers can create as many user threads as necessary and the
corresponding Kernel threads can run in parallel on a multiprocessor
machine. This model provides the best accuracy on concurrency and when a
thread performs a blocking system call, the kernel can schedule another
thread for execution.
Many to One Model
Many-to-one model maps many user level threads to one Kernel-level
thread. Thread management is done in user space by the thread library.
When thread makes a blocking system call, the entire process will be
blocked. Only one thread can access the Kernel at a time, so multiple
threads are unable to run in parallel on multiprocessors.
If the user-level thread libraries are implemented in the operating
system in such a way that the system does not support them, then the
Kernel threads use the many-to-one relationship modes.
One to One Model
There is one-to-one relationship of user-level thread to the
kernel-level thread. This model provides more concurrency than the
many-to-one model. It also allows another thread to run when a thread
makes a blocking system call. It supports multiple threads to execute in
parallel on microprocessors.
Disadvantage of this model is that creating user thread requires the
corresponding Kernel thread. OS/2, windows NT and windows 2000 use one
to one relationship model.
Difference between User-Level & Kernel-Level Thread
Process Creation
A process may be created in the system for
different operations. Some of the events that lead to process creation
are as follows −
- User request for process creation
- System Initialization
- Batch job initialization
- Execution of a process creation system call by a running process
A
process may be created by another process using fork(). The creating
process is called the parent process and the created process is the
child process. A child process can have only one parent but a parent
process may have many children. Both the parent and child processes have
the same memory image, open files and environment strings. However,
they have distinct address spaces.
A diagram that demonstrates process creation using fork() is as follows:
.PNG)
Process Termination
Process
termination occurs when the process is terminated The exit() system
call is used by most operating systems for process termination.
Some of the causes of process termination are as follows −
- A
process may be terminated after its execution is naturally completed.
This process leaves the processor and releases all its resources.
- A child process may be terminated if its parent process requests for its termination.
- A
process can be terminated if it tries to use a resource that it is not
allowed to. For example - A process can be terminated for trying to
write into a read only file.
- If an I/O failure occurs for a
process, it can be terminated. For example - If a process requires the
printer and it is not working, then the process will be terminated.
- In
most cases, if a parent process is terminated then its child processes
are also terminated. This is done because the child process cannot exist
without the parent process.
- If a process requires more memory than is currently available in the system, then it is terminated because of memory scarcity.
Process Synchronization
Process Synchronization means sharing system resources by processes
in a such a way that, Concurrent access to shared data is handled
thereby minimizing the chance of inconsistent data. Maintaining data
consistency demands mechanisms to ensure synchronized execution of
cooperating processes.
Process Synchronization was introduced to handle problems that arose
while multiple process executions. Some of the problems are discussed
below.
Critical Section Problem
A Critical Section is a code segment that accesses shared variables
and has to be executed as an atomic action. It means that in a group of
cooperating processes, at a given point of time, only one process must
be executing its critical section. If any other process also wants to
execute its critical section, it must wait until the first one finishes.
Solution to Critical Section Problem
A solution to the critical section problem must satisfy the following three conditions:
1. Mutual Exclusion
Out of a group of cooperating processes, only one process can be in its critical section at a given point of time.
2. Progress
If no process is in its critical section, and if one or more threads
want to execute their critical section then any one of these threads
must be allowed to get into its critical section.
3. Bounded Waiting
After a process makes a request for getting into its critical
section, there is a limit for how many other processes can get into
their critical section, before this process's request is granted. So
after the limit is reached, system must grant the process permission to
get into its critical section.
Synchronization Hardware
Many systems provide hardware support for critical section code. The
critical section problem could be solved easily in a single-processor
environment if we could disallow interrupts to occur while a shared
variable or resource is being modified.
In this manner, we could be sure that the current sequence of
instructions would be allowed to execute in order without pre-emption.
Unfortunately, this solution is not feasible in a multiprocessor
environment.
Disabling interrupt on a multiprocessor environment can be time consuming as the message is passed to all the processors.
This message transmission lag, delays entry of threads into critical section and the system efficiency decreases.
Mutex Locks
As the synchronization hardware solution is not easy to implement for
everyone, a strict software approach called Mutex Locks was introduced.
In this approach, in the entry section of code, a LOCK is acquired over
the critical resources modified and used inside critical section, and
in the exit section that LOCK is released.
As the resource is locked while a process executes its critical section hence no other process can access it.
Introduction to Semaphores
In 1965, Dijkstra proposed a new and very significant technique for
managing concurrent processes by using the value of a simple integer
variable to synchronize the progress of interacting processes. This
integer variable is called semaphore. So it is basically a synchronizing tool and is accessed only through two low standard atomic operations, wait and signal designated by P(S) and V(S) respectively.
In very simple words, semaphore is a variable which can hold only a non-negative Integer value, shared between all the threads, with operations wait and signal, which work as follow:
P(S): if S ≥ 1 then S := S - 1
else <block and enqueue the process>;
V(S): if <some process is blocked on the queue>
then <unblock a process>
else S := S + 1;
The classical definitions of wait and signal are:
- Wait: Decrements the value of its argument
S, as soon as it would become non-negative(greater than or equal to 1).
- Signal: Increments the value of its argument
S, as there is no more process blocked on the queue.
Properties of Semaphores
- It's simple and always have a non-negative Integer value.
- Works with many processes.
- Can have many different critical sections with different semaphores.
- Each critical section has unique access semaphores.
- Can permit multiple processes into the critical section at once, if desirable.
Types of Semaphores
Semaphores are mainly of two types:
- Binary Semaphore:
It is a special form of semaphore used for implementing mutual exclusion, hence it is often called a Mutex. A binary semaphore is initialized to
1 and only takes the values 0 and 1 during execution of a program.
- Counting Semaphores:
These are used to implement bounded concurrency.
Example of Use
Here is a simple step wise implementation involving declaration and usage of semaphore.
Shared var mutex: semaphore = 1;
Process i
begin
.
.
P(mutex);
execute CS;
V(mutex);
.
.
End;
Limitations of Semaphores
- Priority Inversion is a big limitation of semaphores.
- Their use is not enforced, but is by convention only.
- With improper use, a process may block indefinitely. Such a situation is called Deadlock. We will be studying deadlocks in details in coming lessons.
Classical Problems of Synchronization
In this tutorial we will discuss about various classic problem of synchronization.
Semaphore can be used in other synchronization problems besides Mutual Exclusion.
Below are some of the classical problem depicting flaws of process
synchronaization in systems where cooperating processes are present.
We will discuss the following three problems:
- Bounded Buffer (Producer-Consumer) Problem
- Dining Philosophers Problem
- The Readers Writers Problem
- This problem is generalised in terms of the Producer Consumer problem, where a finite buffer pool is used to exchange messages between producer and consumer processes.
Because the buffer pool has a maximum size, this problem is often called the Bounded buffer problem.
- Solution to this problem is, creating two counting semaphores "full"
and "empty" to keep track of the current number of full and empty
buffers respectively.
- The dining philosopher's problem involves the allocation of limited
resources to a group of processes in a deadlock-free and starvation-free
manner.
- There are five philosophers sitting around a table, in which there
are five chopsticks/forks kept beside them and a bowl of rice in the
centre, When a philosopher wants to eat, he uses two chopsticks - one
from their left and one from their right. When a philosopher wants to
think, he keeps down both chopsticks at their original place.
- In this problem there are some processes(called readers) that only read the shared data, and never change it, and there are other processes(called writers) who may change the data in addition to reading, or instead of reading it.
- There are various type of readers-writers problem, most centred on relative priorities of readers and writers.
Bounded Buffer Problem
Bounded buffer problem, which is also called producer consumer problem,
is one of the classic problems of synchronization. Let's start by
understanding the problem here, before moving on to the solution and
program code.
What is the Problem Statement?
There is a buffer of n slots and each slot is capable of storing one unit of data. There are two processes running, namely, producer and consumer, which are operating on the buffer.
Bounded Buffer Problem
A producer tries to insert data into an empty slot of the buffer. A
consumer tries to remove data from a filled slot in the buffer. As you
might have guessed by now, those two processes won't produce the
expected output if they are being executed concurrently.
There needs to be a way to make the producer and consumer work in an independent manner.
Here's a Solution
One solution of this problem is to use semaphores. The semaphores which will be used here are:
m, a binary semaphore which is used to acquire and release the lock.empty, a counting semaphore whose initial value is the number of slots in the buffer, since, initially all slots are empty.full, a counting semaphore whose initial value is 0.
At any instant, the current value of empty represents the number of
empty slots in the buffer and full represents the number of occupied
slots in the buffer.
The Producer Operation
The pseudocode of the producer function looks like this:
do
{
wait(empty);
wait(mutex);
signal(mutex);
signal(full);
}
while(TRUE)
- Looking at the above code for a producer, we can see that a producer first waits until there is atleast one empty slot.
- Then it decrements the empty semaphore because, there will now be one less empty slot, since the producer is going to insert data in one of those slots.
- Then, it acquires lock on the buffer, so that the consumer cannot access the buffer until producer completes its operation.
- After performing the insert operation, the lock is released and the value of full is incremented because the producer has just filled a slot in the buffer.
The Consumer Operation
The pseudocode for the consumer function looks like this:
do
{
wait(full);
wait(mutex);
signal(mutex);
signal(empty);
}
while(TRUE);
- The consumer waits until there is atleast one full slot in the buffer.
- Then it decrements the full semaphore because the number of occupied slots will be decreased by one, after the consumer completes its operation.
- After that, the consumer acquires lock on the buffer.
- Following that, the consumer completes the removal operation so that the data from one of the full slots is removed.
- Then, the consumer releases the lock.
- Finally, the empty semaphore is incremented by 1, because the consumer has just removed data from an occupied slot, thus making it empty.
Dining Philosophers Problem
The dining philosophers problem is another classic synchronization
problem which is used to evaluate situations where there is a need of
allocating multiple resources to multiple processes.
What is the Problem Statement?
Consider there are five philosophers sitting around a circular dining
table. The dining table has five chopsticks and a bowl of rice in the
middle as shown in the below figure.
Dining Philosophers Problem
At any instant, a philosopher is either eating or thinking. When a
philosopher wants to eat, he uses two chopsticks - one from their left
and one from their right. When a philosopher wants to think, he keeps
down both chopsticks at their original place.
Here's the Solution
From the problem statement, it is clear that a philosopher can think
for an indefinite amount of time. But when a philosopher starts eating,
he has to stop at some point of time. The philosopher is in an endless
cycle of thinking and eating.
An array of five semaphores, stick[5], for each of the five chopsticks.
The code for each philosopher looks like:
while(TRUE)
{
wait(stick[i]);
wait(stick[(i+1) % 5]);
signal(stick[i]);
signal(stick[(i+1) % 5]);
}
When a philosopher wants to eat the rice, he will wait for the
chopstick at his left and picks up that chopstick. Then he waits for the
right chopstick to be available, and then picks it too. After eating,
he puts both the chopsticks down.
But if all five philosophers are hungry simultaneously, and each of
them pickup one chopstick, then a deadlock situation occurs because they
will be waiting for another chopstick forever. The possible solutions
for this are:
- A philosopher must be allowed to pick up the chopsticks only if both the left and right chopsticks are available.
- Allow only four philosophers to sit at the table. That way, if all
the four philosophers pick up four chopsticks, there will be one
chopstick left on the table. So, one philosopher can start eating and
eventually, two chopsticks will be available. In this way, deadlocks can
be avoided.
What is Readers Writer Problem?
Readers writer problem is another example of a classic
synchronization problem. There are many variants of this problem, one of
which is examined below.
The Problem Statement
There is a shared resource which should be accessed by multiple
processes. There are two types of processes in this context. They are reader and writer. Any number of readers can read from the shared resource simultaneously, but only one writer can write to the shared resource. When a writer is writing data to the resource, no other process can access the resource. A writer cannot write to the resource if there are non zero number of readers accessing the resource at that time.
The Solution
From the above problem statement, it is evident that readers have
higher priority than writer. If a writer wants to write to the resource,
it must wait until there are no readers currently accessing that
resource.
Here, we use one mutex m and a semaphore w. An integer variable read_count is used to maintain the number of readers currently accessing the resource. The variable read_count is initialized to 0. A value of 1 is given initially to m and w.
Instead of having the process to acquire lock on the shared resource, we use the mutex m to make the process to acquire and release lock whenever it is updating the read_count variable.
The code for the writer process looks like this:
while(TRUE)
{
wait(w);
signal(w);
}
And, the code for the reader process looks like this:
while(TRUE)
{
wait(m);
read_count++;
if(read_count == 1)
wait(w);
signal(m);
wait(m);
read_count--;
if(read_count == 0)
signal(w);
signal(m);
}
Here is the Code uncoded(explained)
- As seen above in the code for the writer, the writer just waits on the w semaphore until it gets a chance to write to the resource.
- After performing the write operation, it increments w so that the next writer can access the resource.
- On the other hand, in the code for the reader, the lock is acquired whenever the read_count is updated by a process.
- When a reader wants to access the resource, first it increments the read_count value, then accesses the resource and then decrements the read_count value.
- The semaphore w is used by the first reader which enters the critical section and the last reader which exits the critical section.
- The reason for this is, when the first readers enters the critical
section, the writer is blocked from the resource. Only new readers can
access the resource now.
- Similarly, when the last reader exits the critical section, it signals the writer using the w semaphore because there are zero readers now and a writer can have the chance to access the resource.
|
The PCB is maintained for a process throughout its lifetime, and is deleted once the process terminates.
The OS can use different policies to manage each queue (FIFO, Round
Robin, Priority, etc.). The OS scheduler determines how to move
processes between the ready and run queues which can only have one entry
per processor core on the system; in the above diagram, it has been
merged with the CPU.
Context switches are computationally intensive since register and
memory state must be saved and restored. To avoid the amount of context
switching time, some hardware systems employ two or more sets of
processor registers. When the process is switched, the following
information is stored for later use.
Wait time of each process is as follows −
0 Comments