Concurrency in Operating System
• Concurrency is the tendency for things to happen at the same time in a system.
Process that coexist on the memory at a given time are called concurrent
process. The concurrent process may either be independent or cooperating.
• Concurrency is when multiple tasks can run in overlapping periods. It’s an
illusion of multiple tasks running in parallel because of a very fast switching by
the CPU. Two tasks can’t run at the same time in a single-core CPU.
Parallelism is when tasks actually run in parallel in multiple CPUs.
• Concurrency needs only one CPU Core, while parallelism needs more than one.
• The independent process, as the name implies do not share any kind of
information or data with each other. They just compete with each other for
resources like CPU, I/O devices etc.
• In single processor multiprogramming systems, processors are interleaved in
the time to yield the appearances of simultaneous execution.
• Even though actual parallelism is not achieved, and even though there is a
certain amount of overhead in involved in switching back and forth
between processes, interleaved or concurrent execution provides major
benefits in processing efficiency.
• In multiprocessor system, it is possible not only to interleave the execution
of multiple process but also to overlap them.
• Concurrency refers to the execution of multiple instruction sequences at
the same time. It occurs in an operating system when multiple process
threads are executing concurrently. These threads can interact with one
another via shared memory or message passing. Concurrency results in
resource sharing, which causes issues like deadlocks and resource scarcity.
It aids with techniques such as process coordination, memory allocation,
and execution schedule to maximize throughput.
• Within a program, a Thread is a separate execution path. It is a lightweight
process that the operating system can schedule and run concurrently with other
threads. The operating system creates and manages threads, and they share the
same memory and resources as the program that created them. This enables
multiple threads to collaborate and work efficiently within a single program.
Inter-process communication (IPC)
• A process can be of two types: Independent process and Co-operating
process.
• An independent process is not affected by the execution of other
processes while a co-operating process can be affected by other
executing processes.
• Though one can think that those processes, which are running
independently, will execute very efficiently, in reality, there are many
situations when co-operative nature can be utilized for increasing
computational speed, convenience, and modularity.
• Inter-process communication (IPC) is a mechanism that allows
processes to communicate with each other and synchronize their
actions.
• The communication between these processes can be seen as a method
of co-operation between them. Processes can communicate with each
other through both:
• Shared Memory
• An operating system can implement both methods of communication.
• Communication between processes using shared memory requires
processes to share some variable, and it completely depends on how the
programmer will implement it.
• One way of communication using shared memory can be imagined like this:
Suppose process1 and process2 are executing simultaneously, and they
share some resources or use some information from another process.
• Process1 generates information about certain computations or resources
being used and keeps it as a record in shared memory. When process2
needs to use the shared information, it will check in the record stored in
shared memory and take note of the information generated by process1
and act accordingly.
• Processes can use shared memory for extracting information as a record
from another process as well as for delivering any specific information to
other processes.
• The following race condition occurs:
• App A reads the current balance, which is ₹1000
• App A adds ₹200 to ₹1000 and gets ₹1200 as the final balance
• Meanwhile, app B fetches the current balance, which is still ₹1000, as
app A has not executed step 3
• App B adds ₹500 to ₹1000 and gets ₹1500 as the final balance
• App B updates the account balance to ₹1500
• App A updates the account balance to ₹1200
• Thus the final balance is ₹1200 instead of ₹1700
Process Synchronization
Process Synchronization in OS
• Processes Synchronization or Synchronization is the way by which
processes that share the same memory space are managed in an
operating system. It helps maintain the consistency of data by using
variables or hardware so that only one process can make changes to
the shared memory at a time.
• An operating system is a software that manages all applications on a
device and basically helps in the smooth functioning of our computer.
Because of this reason, the operating system has to perform many
tasks, and sometimes simultaneously. This isn't usually a problem
unless these simultaneously occurring processes use a common
resource.
• Let us take a look at why exactly we need Process Synchronization.
For example, If a process1 is trying to read the data present in a
memory location while another process2 is trying to change the data
present at the same location, there is a high chance that the data read
by the process1 will be incorrect.
•
A race condition
• A race condition is an undesirable situation that occurs
when a device or system attempts to perform two or more
operations at the same time, but because of the nature of
the device or system, the operations must be done in the
proper sequence to be done correctly.
• Race conditions are most commonly associated with
computer science and programming. They occur when two
computer program processes, or threads, attempt to
access the same resource at the same time and cause
problems in the system.
• At a given point in time, many kernel-mode processes may be active in
the operating system. As a result, the code implementing an operating
system (kernel code) is subject to several possible race conditions.
Consider as an example a kernel data structure that maintains a list of
all open files in the system. This list must be modified when a new file is
opened or closed (adding the file to the list or removing it from the list).
If two processes were to open files simultaneously, the separate
updates to this list could result in a race condition.
• Other kernel data structures that are prone to possible race conditions
include structures for maintaining memory allocation, for maintaining
process lists, and for interrupt handling. It is up to kernel developers to
ensure that the operating system is free from such race conditions.
• Two general approaches are used to handle critical sections in
operating systems: (1) preemptive kernels and (2) nonpreemptive
kernels. A preemptive kernel allows a process to be preempted while it
is running in kernel mode.
• A nonpreemptive kernel does not allow a process running in kernel
mode to be preempted; a kernel-mode process will run until it exits
kernel mode, blocks, or voluntarily yields control of the CPU.
Obviously, a nonpreemptive kernel is essentially free from race
conditions on kernel data structures, as only one process is active in
the kernel at a time. We cannot say the same about preemptive
kernels, so they must be carefully designed to ensure that shared
kernel data are free from race conditions. Preemptive kernels are
especially difficult to design for SMP architectures, since in these
environments it is possible for two kernel-mode processes to run
simultaneously on different processors.
Why, then, would anyone favor a preemptive kernel over a nonpreemptive
one? A preemptive kernel is more suitable for real-time programming, as it will
allow a real-time process to preempt a process currently running in the kernel.
Furthermore, a preemptive kernel may be more responsive, since there is less
risk that a kernel-mode process will run for an arbitrarily long period before
relinquishing the processor to waiting processes. Of course, this effect can be
minimized by designing kernel code that does not behave in this way. Later in
this chapter, we explore how various operating systems manage preemption
within the kernel.
Critical Section
• Consider a system consisting of n processes {Po, P1 , ... , P11 _ I}. Each process has
a segment of code, called a critical section in which the process may be changing
common variables, updating a table, writing a file, and so on.
• The important feature of the system is that, when one process is executing in its
critical section, no other process is to be allowed to execute in its critical section.
• That is, no two processes are executing in their critical sections at the same time.
• The critical-section problem is to design a protocol that the processes can use to
cooperate. Each process must request permission to enter its critical section. The
section of code implementing this request is the entry section. The critical section
may be followed by an exit section.
• The remaining code is the is the part of a program which tries to access shared
resources.
• That resource may be any resource in a computer like a memory location, Data
structure, CPU or any IO device.
• The critical section problem is used to design a set of protocols which can ensure
that the Race condition among the processes will never arise.
Requirements of Synchronization
mechanisms
• do {
• I entry section I
• critical section
• I exit section I
• remainder section
• } while (TRUE);
General structure of a typical process A.
A solution to the critical-section problem :
• 1. Mutual exclusion. If process Pi is executing in its critical section,
then no other processes can be executing in their critical sections.
• 2. Progress. If no process is executing in its critical section and some
processes wish to enter their critical sections, then only those
processes that are not executing in their remainder sections can
participate in deciding which will enter its critical section next, and this
selection cannot be postponed indefinitely.
• [Link] waiting. There exists a bound, or limit, on the number of
times that other processes are allowed to enter their critical sections
after a process has made a request to enter its critical section and
before that request is granted.
• Mutual Exclusion
• Mutual exclusion is a concept in computer science and concurrent
programming that ensures that only one process or thread can access
a critical section of code (a resource or data structure) at a time. It is
essential for avoiding race conditions, where multiple processes or
threads concurrently access shared resources, which could lead to
inconsistent or incorrect results.
• Requirements for Mutual Exclusion
• For mutual exclusion to be effective, it must satisfy the following key
requirements:
1. Mutual Exclusion: At most one process can be in its critical section at any
given time. If one process is accessing the shared resource, other processes
must be blocked or prevented from entering the critical section.
2. Progress: If no process is currently in its critical section and more than one
process wants to enter, then one of the requesting processes must be
allowed to enter. It should not be stuck indefinitely if it wants to execute.
3. Bounded Waiting: There must be a limit on how long a process has to wait
before it is allowed to enter the critical section. No process should have to
wait forever if other processes are waiting too.
• Hardware Support for Mutual Exclusion (TSL)
• To implement mutual exclusion effectively in a system, hardware support
can play a crucial role. One widely used hardware mechanism for mutual
exclusion is the Test and Set Lock (TSL) instruction, which is typically
supported by the CPU.
• Test and Set Lock (TSL)
• TSL is an atomic instruction, meaning that it performs two operations in a
single, uninterruptible step:
• Test: It reads the value of a memory location (a lock variable, for example).
• Set: It sets the value of that memory location to 1 (or true), indicating that the
critical section is locked.
• The atomicity of the Test and Set instruction ensures that it operates
without being interrupted, so it prevents multiple processes from checking
and updating the lock variable simultaneously, which could lead to race
conditions.
Usage in Mutual Exclusion:
• A process attempting to enter the critical section will execute a TSL
instruction on a shared variable (often called a lock).
• If the lock is already set (i.e., another process is inside the critical
section), the process will keep trying (busy-waiting).
• If the lock is not set (indicating no other process is in the critical
section), the process will set the lock and enter the critical section.
How TSL Works:
• Suppose the lock variable lock is initially 0 (unlocked).
• When a process wants to enter the critical section:The process
executes the TSL instruction on lock.
• If lock is 0, TSL will set it to 1 and the process can enter the critical
section.
• If lock is already 1, the process will repeatedly check and attempt to
set it again until it can successfully acquire the lock.
Example of TSL Usage in a Pseudocode:
lock = 0 // shared lock variable
function enterCriticalSection():
while (TestAndSet(lock) == 1) // Wait if the lock is 1 (critical section
occupied)
// Busy wait (do nothing)
// Critical section code begins here
function exitCriticalSection():
lock = 0 // Release the lock so other processes can enter
Synchronization Hardware
• Generally any solution to the critical-section problem requires a simple
tool-a lock.
• Race conditions are prevented by requiring that critical regions be
protected by locks.
• That is, a process must acquire a lock before entering a critical section;
it releases the lock when it exits the critical section.
• some simple hardware instructions that are available on many systems
and showing how they can be used effectively in solving the
critical-section problem. Hardware features can make any
programming task easier and improve system efficiency.
Test and Set: the hardware approach of solving Process
Synchronization problem
• Here, the shared variable is lock which is initialized to false.
• TestAndSet(lock) algorithm works in this way – it always returns whatever value
is sent to it and sets lock to true.
• The first process will enter the critical section at once as TestAndSet(lock) will
return false and it’ll break out of the while loop.
• The other processes cannot enter now as lock is set to true and so the while loop
continues to be true.
• Mutual exclusion is ensured.
• Once the first process gets out of the critical section, lock is changed to false.
• So, now the other processes can enter one by one. Progress is also ensured.
• However, after the first process, any process can go in. There is no queue
maintained, so any new process that finds the lock to be false again can enter.
• So bounded waiting is not ensured.
Semaphore
•The hardware-based solutions to the critical-section problem are
complicated for application programmers to use. To overcome this
difficulty, we can use a synchronization tool called a semaphore.
•A semaphore S is an integer variable that, apart from initialization,
is accessed only through two standard atomic operations: wait ()
and signal ().
•The wait () operation was originally termed P (from the Dutch
proberen, "to test"); signal() was originally called V (from
verhogen, "to increment").
The definition of wait () is as follows:
wait(S) {
while S <= 0
;// no-operation
S--;
}
The definition of signal() is as follows:
signal(S) {
S++;
}
• All modifications to the integer value of the semaphore in the wait
() and signal() operations must be executed indivisibly.
• That is, when one process modifies the semaphore value, no other
process can simultaneously modify that same semaphore value.
• In addition, in the case of wait (S), the testing of the integer value of
S (S :S 0), as well as its possible modification (S--), must be executed
without interruption.
• Operating systems often distinguish between counting and binary
semaphores. The value of a counting semaphore can range over an
unrestricted domain. The value of a binary semaphore can range
only between 0 and 1. On some systems, binary semaphores are
known as mutex locks, as they are locks that provide mutual
exclusion.
• We can use binary semaphores to deal with the critical-section problem for
multiple processes. Processes share a semaphore, mutex, initialized to 1.
Each process Pi is organized as shown in Figure 6.9.
• do {
• wait (mutex) ;
// critical section
signal(mutex);
// remainder section
} while (TRUE);
• Figure 6.9 Mutual-exclusion implementation with semaphores.
•Counting semaphores can be used to control access to a given
resource consisting of a finite number of instances.
•The semaphore is initialized to the number of resources
available. Each process that wishes to use a resource performs
a wait() operation on the semaphore (thereby decrementing
the count).
•When a process releases a resource, it performs a signal()
operation (incrementing the count).
•When the count for the semaphore goes to 0, all resources are
being used.
•After that, processes that wish to use a resource will block
until the count becomes greater than 0.
• To implement semaphores under this definition, we define a semaphore as
a "C' struct:
typedef struct {
int value;
struct process *list;
} semaphore;
• Each semaphore has an integer value and a list of processes list.
• When a process must wait on a semaphore, it is added to the list of
processes.
• A signal() operation removes one process from the list of waiting processes
and awakens that process.
• The wait() semaphore operation can now be defined as
wait(semaphore *S) {
S->value--;
}
if (S->value < 0) {
add this process to S->list;
block();
}
• The signal () semaphore operation can now be defined as
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}
•Note that in this implementation, semaphore values
may be negative, although semaphore values are
never negative under the classical definition of
semaphores with busy waiting.
•If a semaphore value is negative, its magnitude is the
number of processes waiting on that semaphore.
•This fact results from switching the order of the
decrement and the test in the implementation of the
wait () operation.
• We say that a set of processes is in a deadlock state when every
process in the set is waiting for an event that can be caused only by
another process in the set. The events with which we are mainly
concerned here are resource acquisition and release.
• The implementation of a semaphore with a waiting queue may result in a
situation where two or more processes are waiting indefinitely for an event
• that can be caused only by one of the waiting processes. The event in
question is the execution of a signal() When such a state is reached, these
processes are said to be DEADLOCKED.
• To illustrate this, we consider a system consisting of two processes, Po and
P1, each accessing two semaphores, S and Q, set to the value 1:
Po P1
• wait(S); wait(Q);
• wait(Q); wait(S);
• signal(S); signal(Q);
• signal(Q); signal(S);