OS UNIT-II

 

UNIT-II

 

Processes: Process Concept, Process scheduling, Operations on processes, Inter-process communication. Threads and Concurrency: Multithreading models, Thread libraries, Threading issues. CPU Scheduling: Basic concepts, Scheduling criteria, Scheduling algorithms, Multiple processor scheduling.

 

PROCESSES: PROCESS CONCEPT

A process is a program in execution. For example, when we write a program in C or C++ and compile it, the compiler creates binary code. The original code and binary code are both programs. When we actually run the binary code, it becomes a process.

• A process is an 'active' entity instead of a program, which is considered a 'passive' entity.

• A single program can create many processes when run multiple times; for example, when we open a .exe or binary file multiple times, multiple instances begin (multiple processes are created). .

How Does a Process Look Like in Memory? 

A process in memory is divided into several distinct sections, each serving a different purpose. Here's how a process typically looks in memory.

• Text Section: A text or code segment contains executable instructions. It is typically a read only section

• Stack: The stack contains temporary data, such as function parameters, returns addresses, and local variables. 

• Data Section: Contains the global variable. 

• Heap Section: Dynamically memory allocated to process during its run time.

Attributes of a Process

A process has several important attributes that help the operating system manage and control it. These attributes are stored in a structure called the Process Control Block (PCB) (sometimes called a task control block). The PCB keeps all the key information about the process, including:

1. Process ID (PID): A unique number assigned to each process so the operating system can identify it.

2. Process State: This shows the current status of the process, like whether it is running, waiting, or ready to execute.

3. Priority and other CPU Scheduling Information: Data that helps the operating system decide which process should run next, like priority levels and pointers to scheduling queues.

4. I/O Information: Information about input/output devices the process is using.

5. File Descriptors: Information about open files and network connections.

6. Accounting Information: Tracks how long the process has run, the amount of CPU time used, and other resource usage data.

7. Memory Management Information: Details about the memory space allocated to the process, including where it is loaded in memory and the structure of its memory layout (stack, heap, etc.).

These attributes in the PCB help the operating system control, schedule, and manage each process effectively.

In an Operating System, a process goes through different states during its lifetime. These states represent what the process is currently doing. When you run a program (which becomes a process), it goes through different phases before it completion. These phases, or states, can vary depending on the operating system, but the most common process lifecycle includes two, five, or seven states.

The Two-State Model

The simplest way to think about a process's lifecycle is with just two states:

1. Running: This means the process is actively using the CPU to do its work.

2. Not Running: This means the process is not currently using the CPU. It could be waiting for something, like user input or data, or it might just be paused.

When a new process is created, it starts in the not running state. Initially, this process is kept in a program called the dispatcher. here’s what happens step by step:

1. Not Running State: When the process is first created, it is not using the CPU.

2. Dispatcher Role: The dispatcher checks if the CPU is free (available for use).

3. Moving to Running State: If the CPU is free, the dispatcher lets the process use the CPU, and it moves into the running state.

4. CPU Scheduler Role: When the CPU is available, the CPU scheduler decides which process gets to run next. It picks the process based on a set of rules called the scheduling scheme, which varies from one operating system to another.

The Five-State Model

The five-state process lifecycle is an expanded version of the two-state model. The two-state model works well when all processes in the not running state are ready to run. However, in some operating systems, a process may not be able to run because it is waiting for something, like input or data from an external device. To handle this situation better, the not running state is divided into two separate states:

  

Here’s a simple explanation of the five-state process model:

• New: This state represents a newly created process that hasn’t started running yet. It has not been loaded into the main memory, but its process control block (PCB) has been created, which holds important information about the process.

• Ready: A process in this state is ready to run as soon as the CPU becomes available. It is waiting for the operating system to give it a chance to execute.

• Running: This state means the process is currently being executed by the CPU. Since we’re assuming there is only one CPU, at any time, only one process can be in this state.

• Blocked/Waiting: This state means the process cannot continue executing right now. It is waiting for some event to happen, like the completion of an input/output operation (for example, reading data from a disk).

• Exit/Terminate: A process in this state has finished its execution or has been stopped by the user for some reason. At this point, it is released by the operating system and removed from memory.

The Seven-State Model

The states of a process are as follows: 

• New State: In this step, the process is about to be created but not yet created. It is the program that is present in secondary memory that will be picked up by the OS to create the process.

• Ready State: New -> Ready to run. After the creation of a process, the process enters the ready state i.e. the process is loaded into the main memory. The process here is ready to run and is waiting to get the CPU time for its execution. Processes that are ready for execution by the CPU are maintained in a queue called a ready queue for ready processes.

• Run State: The process is chosen from the ready queue by the OS for execution and the instructions within the process are executed by any one of the available processors.

 

 

• Blocked or Wait State: Whenever the process requests access to I/O needs input from the user or needs access to a critical region(the lock for which is already acquired) it enters the blocked or waits state. The process continues to wait in the main memory and does not require CPU. Once the I/O operation is completed the process goes to the ready state.

• Terminated or Completed State: Process is killed as well as PCB is deleted. The resources allocated to the process will be released or de-allocated.

• Suspend Ready: Process that was initially in the ready state but was swapped out of main memory (refer to Virtual Memory topic) and placed onto external storage by the scheduler is said to be in suspend ready state. The process will transition back to a ready state whenever the process is again brought onto the main memory.

• CPU and I/O Bound Processes: If the process is intensive in terms of CPU operations, then it is called CPU bound process. Similarly, If the process is intensive in terms of I/O operations then it is called I/O bound process. 

 

Types of Schedulers

• Long-Term Scheduler:  Decides how many processes should be made to stay in the ready state. This decides the degree of multiprogramming. Once a decision is taken it lasts for a long time which also indicates that it runs infrequently. Hence it is called a long-term scheduler.

• Short-Term Scheduler: Short-term scheduler will decide which process is to be executed next and then it will call the dispatcher. A dispatcher is a software that moves the process from ready to run and vice versa. In other words, it is context switching. It runs frequently. Short-term scheduler is also called CPU scheduler.

• Medium Scheduler: Suspension decision is taken by the medium-term scheduler. The medium-term scheduler is used for swapping which is moving the process from main memory to secondary and vice versa. The swapping is done to reduce degree of multiprogramming.

Operation on the Process

• Creation: The process will be ready once it has been created, enter the ready queue (main memory), and be prepared for execution.

• Planning: The operating system picks one process to begin executing from among the numerous processes that are currently in the ready queue. Scheduling is the process of choosing the next process to run.

• Application: The processor begins running the process as soon as it is scheduled to run. During execution, a process may become blocked or wait, at which point the processor switches to executing the other processes.

• Killing or Deletion: The OS will terminate the process once its purpose has been fulfilled. The process's context will be over there.

• Blocking: When a process is waiting for an event or resource, it is blocked. The operating system will place it in a blocked state, and it will not be able to execute until the event or resource becomes available.

• Context Switching: When the operating system switches from executing one process to another, it must save the current process's context and load the context of the next process to execute. This is known as context switching.

• Inter-Process Communication: Processes may need to communicate with each other to share data or coordinate actions. The operating system provides mechanisms for inter-process communication, such as shared memory, message passing, and synchronization primitives.

  Process Table and Process Control Block (PCB)

A Process Control Block (PCB) is a data structure used by the operating system to keep track of process information and manage execution.

• Each process is given a unique Process ID (PID) for identification.

• The PCB stores details such as process state, program counter, stack pointer, open files, and scheduling info.

• During a state transition, the OS updates the PCB with the latest execution data.

• It also includes register values, CPU quantum, and process priority.

• The Process Table is an array of PCBs that maintains information for all active processes.

Structure of the Process Control Block

A Process Control Block (PCB) is a data structure used by the operating system to manage information about a process. The process control keeps track of many important pieces of information needed to manage processes efficiently. The diagram helps explain some of these key data items.

 

• Pointer: It is a stack pointer that is required to be saved when the process is switched from one state to another to retain the current position of the process.

• Process state: It stores the respective state of the process.

• Process number: Every process is assigned a unique id known as process ID or PID which stores the process identifier.

• Program counter: Program Counter stores the counter, which contains the address of the next instruction that is to be executed for the process.

• Register: Registers in the PCB, it is a data structure. When a processes is running and it's time slice expires, the current value of process specific registers would be stored in the PCB and the process would be swapped out. When the process is scheduled to be run, the register values is read from the PCB and written to the CPU registers. This is the main purpose of the registers in the PCB.

• Memory limits: This field contains the information about memory management system used by the operating system. This may include page tables, segment tables, etc.

• List of Open files: This information includes the list of files opened for a process.

 

PROCESS SCHEDULING

Process scheduling is the activity of the process manager that handles the removal of the running process from the CPU and the selection of another process based on a particular strategy. Throughout its lifetime, a process moves between various scheduling queues, such as the ready queue, waiting queue or devices queue.

Categories of Scheduling

Scheduling falls into one of two categories:

• Non-Preemptive: In this case, a process's resource cannot be taken before the process has finished running. When a running process finishes and transitions to waiting state, resources are switched.

• Preemptive: In this case, the OS can switch a process from running state to ready state. This switching happens because the CPU may give other processes priority and substitute the currently active process for the higher priority process.

Refer Preemptive vs Non-Preemptive Scheduling for details.

Process Scheduler

Process Schedulers are fundamental components of operating systems responsible for deciding the order in which processes are executed by the CPU. In simpler terms, they manage how the CPU allocates its time among multiple tasks or processes that are competing for its attention.

Types of Process Schedulers

There are three types of process schedulers:

1. Long Term or Job Scheduler

Long Term Scheduler loads a process from disk to main memory for execution. The new process to the 'Ready State'.

• It mainly moves processes from Job Queue to Ready Queue.

• It controls the Degree of Multi-programming, i.e., the number of processes present in a ready state or in main memory at any point in time.

• It is important that the long-term scheduler make a careful selection of both I/O and CPU-bound processes. I/O-bound tasks are which use much of their time in input and output operations while CPU-bound processes are which spend their time on the CPU. The job scheduler increases efficiency by maintaining a balance between the two.

• In some systems, the long-term scheduler might not even exist. For example, in time-sharing systems like Microsoft Windows, there is usually no long-term scheduler. Instead, every new process is directly added to memory for the short-term scheduler to handle.

• Slowest among the three (that is why called long term).

2.1. Short-Term or CPU Scheduler

CPU Scheduler is responsible for selecting one process from the ready state for running (or assigning CPU to it).

• STS (Short Term Scheduler) must select a new process for the CPU frequently to avoid starvation.

• The CPU scheduler uses different scheduling algorithms to balance the allocation of CPU time.

• It picks a process from ready queue.

• Its main objective is to make the best use of CPU.

• It mainly calls dispatcher.

• Fastest among the three (that is why called Short Term).

The dispatcher is responsible for loading the process selected by the Short-term scheduler on the CPU (Ready to Running State). Context switching is done by the dispatcher only. A dispatcher does the following work: 

• Saving context (process control block) of previously running process if not finished.

• Switching system mode to user mode.

• Jumping to the proper location in the newly loaded program.

Note: Time taken by dispatcher is called dispatch latency or process context switch time.

 

2.2. Dispatcher

Dispatcher is a special type of program whose work starts after the scheduler. When the scheduler completes its task of selecting a process, it is the dispatcher that moves the process to the queue it needs to go to. The dispatcher is the module that hands over control of the CPU to the process that has been selected by the short-term scheduler. The following things happen in this function:

• switching context: Cores the current process and restores the state of the process to be run next.

• Switching to User Mode: Makes sure that it runs in the user mode and not kernel mode, which is for security and privilege break-

• Jumps to the correct location in the user program from where the program can be restarted.

Example: Suppose there are 4 processes in the ready queue – P1, P2, P3, P4 with arrival times t0, t1, t2, t3 respectively. Using First-Come, First-Served (FCFS) scheduling:

• The scheduler selects P1 first since it arrived earliest.

• The dispatcher then removes P1 from the ready queue and gives it to the CPU.

• Next, the scheduler chooses P2, and the dispatcher passes it to the CPU, followed by P3 and P4.

 

 

3. Medium-Term Scheduler

Medium Term Scheduler (MTS) is responsible for moving a process from memory to disk (or swapping).

• It reduces the degree of multiprogramming (Number of processes present in main memory).

• A running process may become suspended if it makes an I/O request. A suspended processes cannot make any progress towards completion. In this condition, to remove the process from memory and make space for other processes, the suspended process is moved to the secondary storage. This process is called swapping and the process is said to be swapped out or rolled out. Swapping may be necessary to improve the process mix (of CPU bound and IO bound)

• When needed, it brings process back into memory and pick up right where it left off.

• It is faster than long term and slower than short term.

 

Some Other Schedulers

• I/O Schedulers: I/O schedulers are in charge of managing the execution of I/O operations such as reading and writing to discs or networks. They can use various algorithms to determine the order in which I/O operations are executed, such as FCFS (First-Come, First-Served) or RR (Round Robin).

• Real-Time Schedulers: In real-time systems, real-time schedulers ensure that critical tasks are completed within a specified time frame. They can prioritize and schedule tasks using various algorithms such as EDF (Earliest Deadline First) or RM (Rate Monotonic).

Comparison among Scheduler

Long Term Scheduler	Short Term Schedular	Medium Term Scheduler
It is a job scheduler	It is a CPU scheduler	It is a process-swapping scheduler.
The slowest scheduler.	Speed is the fastest among all of them.	Speed lies in between both short and long-term schedulers.
It controls the degree of multiprogramming	It gives less control over how much multiprogramming is done.	It reduces the degree of multiprogramming.
It is barely present or nonexistent in the time-sharing system.	It is a minimal time-sharing system.	It is a component of systems for time sharing.
It can re-enter the process into memory, allowing for the continuation of execution.	It selects those processes which are ready to execute	It can re-introduce the process into memory and execution can be continued.

OPERATIONS ON PROCESSES,

What is a Process in OS?

A process is a program in execution that undergoes a number of states in its lifetime. In each of these states, a process undergoes certain operations that enable the process to execute into completion.

States of a Process

The different states of a process are as follows −

• New − Process is created.
• Ready − Process is ready with all its resource allocation and waiting for CPU allocation.
• Running − Instructions in the process are being executed in CPU.
• Waiting − Process is in waiting for completion of an input output or any other event.
• Terminated − Process finishes execution and exits the system.

The process states are depicted in the following diagram –

 

 

Different Process Operations in Operating System

The operations on a process occur when the process is in a particular state or when the process makes a transition from one state to another. There are mainly four operations on a process −

• Process Creation
• Process Dispatch
• Process Pre-emption
• Process Blocking
• Process Termination

Process Creation

The first operation that a process undergoes when it enters a system is process creation. It involves formation of a process and is associated with New state of the process. Process creation occurs due to any of the following events −

• System initialization − When the computer is started, a number of system processes and background processes are created.
• User request − A user may start executing a program leading to creation of a process.
• Child process system call − A running process may create a child process by process creation system call.
• Batch system − The batch system may initiate batch jobs

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 −

 

Process Dispatch

When a process in the ready state is selected for execution by the scheduler, process dispatch operation occurs. Process dispatch is initiated according to the scheduling algorithm used. It may happen when the CPU becomes idle and the ready queue has processes, time quantum allotted for an on-going process expires, a high priority process enters the system or a hardware interrupt occurs. When a new process is assigned to the CPU, its status is loaded from its Process Control Block (PCB).

Process Preemption

Process pre-emption is an operation by which the execution of an on-going process is suspended and some other process is selected by the CPU for execution. Process pre-emption may occur when time quantum of on-going process expires, a high priority process enters the ready queue or a hardware interrupt occurs.

The preemption of executing processes in the CPU causes a phenomenon called context switch. Here, the context or state of the out-going process is stored in its PCB so that it can be reloaded when required and execution can be resumed from the same point as earlier.

The following diagram demonstrates process dispatch and process pre-emption −

Process Blocking

The on-going process is blocked and put in the Waiting state and swapped out of the CPU, if it needs some event to occur in order to proceed with execution. This event may be an input/output system call since the I/O events are executed in the main memory and don't require the processor.

Here, the operating system blocks the process, when the process itself demands so. After the event is complete, the process again goes to the ready state.

A diagram that demonstrates process blocking is as follows –

Process Termination

Process Termination is the operation of ending a process and releasing all the resources that have been held by the process. The process ceases to exist after its termination.

Similar to process creation, there may be multiple reasons for process termination, as follows −

• The process has completed the execution of its last instruction and so it is terminated by the operating system.
• A child process can be terminated by its parent process if its task is no longer relevant. The child process sends its status information to the parent process before it terminates. Also, when a parent process is terminated, its child processes are terminated as well as the child processes cannot run if the parent processes are terminated.
• The process can be terminated by the operating system if there are service errors.
• A hardware malfunction may also cause process termination.

In most cases, process termination occurs when a process executes to completion. The steps involved are as follows −

• The parent process issues a SIGTERM message to the child process as a signal to initiate termination.
• On receiving this signal, the child process performs clean-up procedures like releasing allocated resources, closing shared files, giving up access to shared variables and tables etc.
• The child process then exits and the control returns to either the parent process or the operating system.

 

 

 

INTER-PROCESS COMMUNICATION

Inter Process Communication (IPC)

Processes need to communicate with each other in many situations. Inter-Process Communication or IPC is a mechanism that allows processes to communicate.

• It helps processes synchronize their activities, share information and avoid conflicts while accessing shared resources.

• There are two method of IPC, shared memory and message passing. An operating system can implement both methods of communication.

Shared Memory

Communication between processes using shared memory requires processes to share some variable and it completely depends on how the programmer will implement it. 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.

 

In the above shared memory model, a common memory space is allocated by the kernel.

• Process A writes data into the shared memory region (Step 1).

• Process B can then directly read this data from the same shared memory region (Step 2).

• Since both processes access the same memory segment, this method is fast but requires synchronization mechanisms (like semaphores) to avoid conflicts when multiple processes read/write simultaneously.

 

Message Passing

Message Passing is a method where processes communicate by sending and receiving messages to exchange data.

• In this method, one process sends a message and the other process receives it, allowing them to share information.

• Message Passing can be achieved through different methods like Sockets, Message Queues or Pipes.

 

 

 

• In the above message passing model, processes exchange information by sending and receiving messages through the kernel.

• Process A sends a message to the kernel (Step 1).

• The kernel then delivers the message to Process B (Step 2).

• Here, processes do not share memory directly. Instead, communication happens via system calls (send(), recv(), or similar).

• This method is simpler and safer than shared memory because there’s no risk of overwriting shared data, but it incurs more overhead due to kernel involvement.

 

 

THREADS AND CONCURRENCY:

Threads are individual sequences of instructions within a program that the operating system can manage and execute independently. Concurrency is the general ability of a system to handle multiple tasks or threads at overlapping times, even on a single processor through rapid switching. 

 

Threads:

A process is an instance of a running program, and a thread is the smallest, independent unit of execution within that process. Threads within the same process are considered "lightweight" because they share the same memory space, code, and other system resources, which makes creating them and switching between them faster than with full processes. 

• Shared Resources: Threads share the process's code section, data section, and operating system resources (like open files).
• Private Resources: Each thread has its own unique components, including a thread ID, program counter, register set, and a stack for local variables and function calls. 

 

Concurrency:

Concurrency refers to the ability of a system to have multiple tasks in progress at the same time. 

• On a Single Core: Concurrency is achieved through context switching, where the CPU rapidly switches between different threads, giving the illusion that they are running simultaneously.
• On a Multi-Core System: Concurrency can be achieved through true parallelism, where multiple threads run at the exact same instant on separate CPU cores. 

 

 

 

MULTITHREADING MODELS,

Multi Threading Models in Process Management

Multithreading is a programming and execution model that allows multiple threads to exist within a single process, executing concurrently. Each thread represents a separate path of execution, enabling better responsiveness, resource utilization and parallelism, especially in modern multiprocessor systems.

Note: Multithreading is widely used in applications like web servers, interactive applications and high-performance computing where concurrent execution is essential.

Threading Models

Operating systems support threads through different threading models, which determine how threads are created, managed and mapped to CPU execution:

1. User-Level Threads (ULT)

Managed by a user-level library, not the OS.

Advantages:

• Greater flexibility and control: Programmers can customize scheduling.

• Portability: Works across multiple operating systems.

• Faster context switching: Switching between ULTs happens in user space.

Disadvantages:

• Blocking system calls: If one thread blocks, the entire process is blocked.

• Limited parallelism: Cannot utilize multiple CPUs effectively since the kernel is unaware of user threads.

2. Kernel-Level Threads (KLT)

Managed and scheduled directly by the operating system.

Advantages:

1. True parallelism: Can run on multiple CPUs simultaneously.

2. Better scalability: OS can efficiently schedule threads.

3. I/O efficiency: Other threads can continue if one thread blocks.

Disadvantages:

• Less flexible and portable: Managed by the OS, harder to customize.

• Higher overhead: Thread creation and context switching involve system calls.

3. Hybrid Threading Models

• Combines ULT and KLT advantages.

• Examples: Solaris and some modern OS use a two-level model, where user threads are mapped to kernel threads.

Advantages:

• Flexibility, control and efficient parallelism.

• Reduces blocking issues and improves concurrency.

Disadvantages:

• More complex to implement.

• Requires more system resources.

Mapping Models of Threads

1. Many-to-Many Model:

 

• Multiple user threads map to multiple kernel threads.

• If one thread blocks, others can continue.

• Provides high concurrency and is the most efficient model.

2. Many-to-One Model:

 

 

• Multiple user threads map to a single kernel thread.

• Blocking in one thread blocks the entire process.

• Efficient user-level management but poor multiprocessing utilization.

 

 3. One-to-One Model:

 

 

• Each user thread maps to a unique kernel thread.

• Multiple threads can run on multiple processors.

• Blocking in one thread does not affect others.

• Overhead is higher because each user thread requires a corresponding kernel thread.

 

Thread Libraries

 

Thread libraries provide APIs for creating and managing threads.

• User-level library: Runs entirely in user space; fast and flexible.

• Kernel-level library: Supported by the OS; better parallelism and fault tolerance.

 

Common thread libraries:

• POSIX Pthreads: Can be implemented as ULT or KLT.

• Windows Threads: Kernel-level library.

• Java Threads: Typically built on kernel threads in modern JVMs.

 

Advantages of Multithreading

1. Minimized Context Switching Time: Switching threads is faster than switching processes.

2. Concurrency: Multiple instruction sequences execute within a single process.

3. Resource Efficiency: Threads share memory and resources of their parent process.

4. Scalability on Multiprocessors: Threads can run on multiple CPUs, improving throughput.

5. Responsiveness: Interactive applications remain responsive even when performing heavy tasks.

 

Disadvantages of Multithreading

1. Complexity: Threaded code can be harder to write and debug.

2. High Management Overhead: Managing multiple threads may be costly for simple tasks.

3. Risk of Deadlocks and Race Conditions: Improper synchronization may cause concurrency issues.

4. Debugging Difficulty: Errors in multithreaded programs are often subtle and hard to reproduce.

 

 

THREAD LIBRARIES:

The Operating System is an interface between the user and hardware that enables the interaction of computer hardware and software or it can act as a bridge between the user and the application. It ensures that various software programs can run efficiently and interact with hardware as needed. Some Popular Operating Systems are Linux, Unix, Microsoft Windows, and so on. Without an operating system computer is useless.

Threads in Operating Systems

A thread is a path of execution that is composed of a program counter, thread id, stack and set of registers within the process. In general, a thread is a least unit of the process that represents an independent sequence of execution within that process. It is a basic unit of CPU utilization that makes communication more effective and efficient, enables the utilization of multiprocessor architectures to a great scale and greater efficiency, and reduces the time required in context switching. With the support of multiprocessor architecture, the communication between the multiple thread is easier as they share memory resources. Sometimes thread also called a lightweight processes because they have their own stack but can access shared resources.

Thread Libraries

• Thread library is a thread API (Application Programming Interface) which is a set of functions, methods and routine provided by operating system for creating, managing and coordination of the threads.

• Thread libraries may be implemented either in user space or kernel space library.

• If the thread library is implemented at the userspace then the code and information of thread library would be reside in user space, In this scenario invoking any function from thread library would be simple function call and can't be a system call.

• But if the thread library is implemented at the kernelspace then the code and information of thread library would be reside in kernel space and supported by operating system, In this scenerio invoking any function from thread library would be system call to the kernel.

• The former API involves functions implemented solely within user space, with no kernel support. But latter involves system calls, and requires a kernel with thread library support as mentioned in last previous point. These libraries provide a tools to the programmer for efficient management, creation and fast execution of operations.

 

 

Need of Thread Library

• Thread Library allow us to perform or execute multiple task at the same time, with the help of this functionality we can utilize our CPU and hardware and also improve our performance.

• Even in andorid development their is a concept called Kotlin Coroutines which also work on same concept for performing multiple task at the same time with the help of thread library (dependency) for efficient execution of tasks.

• Thread libraries provide standard way to work with thread over various operating systems and platforms.

• When multiple threads are working together they need data of another threads to performs operations , so in thread library it provides mechanisms like semaphores, mutexes that allow to share data between threads without data stealing/loss.

• They have ability to create new thread within the applications and execute separated by thread.

 

Best Thread Libraries

There are lots of thread libraries available, but some of them are widely used. let's digout some most widely used thread libraries.

 

Java Threads

• Thread is a primary model of program execution in java program and java language and it's API provides a rich variety of features for the creation and the management of threads. As name signifies that it's code written in java language.

• However in most instances the the JVM (Java Virtual Machine) is running on top of host operating system, the java thread API typically implemented using thread library available on the host system, Which signifies that on window system the java thread is implemented through Win32 API.

• It provide built-in support for multi-threading through java.lang.Thread and it also provide high level thread management.

 

Pthread

• It is also known as POSIX thread, it is an execution model that exists independently from a programming language as well as a parallel model.

• Pthread library can be implemented either at the userspace or kernel space. The Pthread is often implemented at the Linux, unix and solaris, and it is highly portable as its code written in pthread can typically be compiled and run on different unix without much modifications.

• Pthread program always have pthread.h header file. Windows doesn't support pthread standard. It support C and C++ languages.

• Pthread are use to leverage the energy of multiple processors, because process is ruptured into thread and each thread use processor for perform task so here multiple thread are execute at the same time and this phenomenon create concurrent.

• Basically Concurrent or parallelism concept is created by processor in order to boost the execution of thread.

 

Win32 Thread

• Win32 thread is a part of Windows operating system and it is also called as Windows Thread. It is a kernel space library.

• In this thread we can also achieve parallelism and concurrency in same manner as in pthread.

• Win32 thread are created with the help of createThread() function. Window thread support Thread Local Storage (TLS) as allow each thread to have its own unique data, and these threads can easily share data as they declared globally.

• They providing native and low level support for multi-threading. It means they are tightly integrated with window OS and offer efficient creation and thread management.

 

THREADING ISSUES:

Multithreading in an operating system offers significant benefits like improved performance and responsiveness, but it introduces several complex issues for application programmers and system designers. The primary threading issues revolve around synchronization, resource management, and system call semantics. 

Core Concurrency Issues

The most common and challenging issues when multiple threads run concurrently and share resources are:

• Race Conditions: This occurs when two or more threads access shared data concurrently, and the final result depends on the specific order in which they access and modify the data. Race conditions lead to unpredictable and inconsistent behavior or corrupted data, making them difficult to debug.
• Deadlock: A situation where two or more threads are blocked forever, each waiting for a resource that another thread in the group is holding. Deadlocks can cause a program or even the entire system to freeze.
• Synchronization Problems: The general challenge of coordinating the actions of multiple threads to ensure data consistency and prevent race conditions. This requires using mechanisms like mutexes, semaphores, and locks, which add complexity and overhead.
• Resource Contention and Overhead: While threads use fewer resources than processes, managing a large number of threads still consumes memory and CPU time. Excessive thread creation or frequent context switching (the process of saving the state of one thread and loading another) can degrade performance, especially if not managed efficiently (e.g., using thread pools). 

Operating System-Specific Issues

Beyond general concurrency problems, the interaction between threads and the operating system kernel presents specific challenges: 

• Thread Cancellation: Terminating a thread before it has completed its task.
• Asynchronous cancellation immediately stops the target thread, which can leave shared resources in an inconsistent or corrupted state (e.g., a lock held indefinitely).
• Deferred cancellation is safer, allowing the target thread to periodically check if it should terminate and perform necessary cleanup before exiting.
• Signal Handling: In a multithreaded process, it is complex to determine which thread should receive an asynchronous signal (e.g., a user terminating the program with specific keystrokes). Different OS implementations handle this differently (e.g., delivering to a specific thread, all threads, or an assigned thread).
• fork() and exec() System Calls: When a thread invokes the fork() system call to create a new process, an issue arises as to whether the new child process should duplicate all threads of the parent or be single-threaded. Many UNIX systems provide two versions of fork() to address this. The exec() system call, conversely, replaces the entire process (including all its threads) with a new program image.
• Thread-Specific Data: In a process where threads share most resources (memory, files), there are situations where each thread needs its own private copy of certain data (e.g., a unique transaction ID). Mechanisms for thread-local storage (TLS) are required to manage this effectively, which can increase memory overhead. 

 

 CPU SCHEDULING: BASIC CONCEPTS, SCHEDULING CRITERIA

CPU scheduling is the task performed by the CPU that decides the way and order in which processes should be executed. There are two types of CPU scheduling - Preemptive, and non-preemptive. The criteria the CPU takes into consideration while "scheduling" these processes are - CPU utilization, throughput, turnaround time, waiting time, and response time.

What is CPU Scheduling?

Before we get to CPU scheduling, let's define a process. A process is essentially just a set of instructions or a program in execution.

 

As you can see in the diagram above, we have processes that come from the job queue to the ready queue (in primary memory) that are one by one, in some manner given resources, and then their execution is completed.

Say you have a uni programming system (like MS-DOS) and a process that requires I/O is being executed. While it waits for the I/O operations to complete, the CPU remains idle. This is wrong, because we're wasting the resources of the CPU, as well as time, and might result in some processes waiting too long for their execution.

In multiprogramming systems, however, the CPU does not remain idle whenever a process currently executing waits for I/O. It starts the execution of other processes, making an attempt to maximize CPU utilization. How does the CPU decide which process should be executed next from the ready queue for maximum utilization of the CPU? This procedure of "scheduling" the processes, is called CPU scheduling.

What are the Types of CPU Scheduling?

There are essential 4 conditions under which CPU scheduling decisions are taken:

1. If a process is making the switch between the running state to the waiting state (could be for an I/O request, or invocation of wait() for terminating one of its child processes)
2. If a process is making the switch from the running state to the ready state (on the occurrence of an interrupt, for example)
3. If a process is making the switch between waiting and ready state (e.g. when its I/O request completes)
4. If a process terminates upon completion of execution.

So in the case of conditions 1 and 4, the CPU does not really have a choice of scheduling, if a process exists in the ready queue the CPU's response to this would be to select it for execution. In cases 2 and 3, the CPU has a choice of selecting a particular process for executing next.

There are mainly two types of CPU scheduling:

 

 Non-Preemptive Scheduling

In the case of non-preemptive scheduling, new processes are executed only after the current process has completed its execution. The process holds the resources of the CPU (CPU time) till its state changes to terminated or is pushed to the process waiting state. If a process is currently being executed by the CPU, it is not interrupted till it is completed.

Once the process has completed its execution, the processer picks the next process from the ready queue (the queue in which all processes that are ready for execution are stored).

 

For Example:

In the image above, we can see that all the processes were executed in the order in which they appeared, and none of the processes were interrupted by another, making this a non-preemptive, FCFS (First Come, First Served) CPU scheduling algorithm. P2 was the first process to arrive (arrived at time = 0), and was hence executed first. Let's ignore the third column for a moment; we'll get to that soon. Process P3 arrived next (at time = 1) and was executed after the previous process - P2 was done executing, and so on.

Some examples of non-preemptive scheduling algorithms are - Shortest Job First (SJF, non-preemptive), and Priority scheduling (non-preemptive).

Preemptive Scheduling

Preemptive scheduling takes into consideration the fact that some processes could have a higher priority and hence must be executed before the processes that have a lower priority.

In preemptive scheduling, the CPU resource is allocated to a process for only a limited period of time and then those resources are taken back and assigned to another process (the next in execution). If the process was yet to complete its execution, it is placed back in the ready state, where it will remain till it gets a chance to execute once again.

So, when we take a look at the conditions under which CPU scheduling decisions are taken on the basis of which CPU provides its resources to processes, we can see that there isn't really a choice in making a decision when it comes to condition 1 and 4. If we have a process in the ready queue, we must select it for execution.

However, we do have a choice in conditions 2 and 3. If we opt to make the choice of scheduling only if a process terminates (condition 4) or if the current process execution is waiting for I/O (condition 1) then we can say that our scheduling is non-preemptive, however, if we make scheduling decisions in other conditions as well, we can say that our scheduling process is preemptive.

Criteria of CPU Scheduling

Now let's discuss CPU Scheduling has several criteria. Some of them are mentioned below.

1. CPU utilization: The main objective of any CPU scheduling algorithm is to keep the CPU as busy as possible. Theoretically, CPU utilization 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. 

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

3. Turnaround Time: For a particular process, an important criterion 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 the ready queue, executing in CPU and waiting for I/O. 

Turn Around Time = Completion Time - Arrival Time.

 

 

 

4. 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. 

Waiting Time = Turnaround Time - Burst Time.

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

Response Time = CPU Allocation Time(when the CPU was allocated for the first) - Arrival Time

6. Completion Time: The completion time is the time when the process stops executing,  which means that the process has completed its burst time and is completely executed.

7. Priority: If the operating system assigns priorities to processes, the scheduling mechanism should favor the higher-priority processes.

8. Predictability: A given process always should run in about the same amount of time under a similar system load.

 

Factors Influencing CPU Scheduling Algorithms

There are many factors that influence the choice of CPU scheduling algorithm. Some of them are listed below.

• The number of processes.

• The processing time required.

• The urgency of tasks.

• The system requirements.

Selecting the correct algorithm will ensure that the system will use system resources efficiently, increase productivity and improve user satisfaction.

 

SCHEDULING ALGORITHMS

CPU Scheduling Algorithms

There are several CPU Scheduling Algorithms, that are listed below:

 

1. Non- Preemptive Scheduling Algorithms

• First Come First Served (FCFS)

• Shortest Job First (SJF)

• Longest Job First (LJF)

2. Preemptive Scheduling Algorithms

• Priority Scheduling

• Round Robin (RR)

• Shortest Remaining Time First (SRTF)

• Longest Remaining Time First (LRTF)

• Multilevel Queue Scheduling

• Multilevel Feedback Queue Scheduling

 

 

NON–PREEMPTIVE SCHEDULING ALGORITHMS

In non-preemptive scheduling, once a process starts executing on CPU, it cannot be stopped until it finishes.

CPU stays with the process until it completes or switches voluntarily (I/O).

Non-preemptive algorithms include:

1 First Come First Served (FCFS)
2 Shortest Job First (SJF)
3 Longest Job First (LJF)

 

1. First Come First Served (FCFS)

Definition:

The process that arrives first will be executed first.
Follows FIFO (First In First Out) approach.

Characteristics

• Non-preemptive
• Simple and easy to implement
• Used in batch systems

 

Example:

Process	Arrival Time	Burst Time
P1	0	5
P2	2	3
P3	4	2

Execution Order: P1 → P2 → P3

Gantt chart:

| P1 |------5------| P2 |--3--| P3 |-2-|

0                5         8   10

 

Turnaround Time (TAT):

Completion Time – Arrival Time

TAT(P1) = 5 – 0 = 5
TAT(P2) = 8 – 2 = 6
TAT(P3) = 10 – 4 = 6

Waiting Time (WT):

TAT – Burst Time

WT(P1) = 5 – 5 = 0
WT(P2) = 6 – 3 = 3
WT(P3) = 6 – 2 = 4

 

Advantages

• Very simple
• Fair to processes (in order of arrival)

Disadvantages

• Convoy effect – Short processes wait for long ones
• Not optimal for performance

 2. Shortest Job First (SJF) – Non-Preemptive

Definition:

The process with the smallest burst time is selected first.

 Characteristics

• Optimal in terms of average waiting time
• Requires knowledge of process burst times
• Can cause starvation to long processes

Example 2:

Process	Arrival Time	Burst Time
P1	0	7
P2	2	4
P3	4	1
P4	5	4

Execution:

At time 0 → Only P1 → Start P1
At time 7 → Available: P2(4), P3(1), P4(4) → Choose P3
Then → P2 or P4 (tie → FCFS) → P2
Finally → P4

Gantt Chart

| P1 |------7------| P3 |-1-| P2 |--4--| P4 |--4--|

0                7    8      12        16

 

Advantages

• Minimum average waiting time
• Good for short jobs

Disadvantages

• Long processes may starve
• Burst time must be known

 

3. Longest Job First (LJF) – Non-Preemptive

✔ Definition:

The process with the largest burst time is executed first.

✔ Characteristics

• Opposite of SJF
• Larger jobs get priority
• Short processes may suffer delay

 

Example 3:

Process	Arrival Time	Burst Time
P1	0	2
P2	1	6
P3	3	4

Execution:

At time 0 → P1 arrives → start P1
At time 2 → P2 & P3 available → choose P2 (largest burst time 6)
Then → P3

Gantt Chart

| P1 |-2-| P2 |------6------| P3 |--4--|

0     2               8       12

 

Advantages

• Good for long jobs
• Useful in systems where long jobs are priority

Disadvantages

• Short jobs may starve
• Larger waiting time for small tasks
• Not optimal for turnaround time

                                    

Algorithm	Selection Criteria	Preemption	Best For	Problem
FCFS	Arrival Time	No	Simple batch OS	Convoy effect
SJF	Smallest burst time	No	Reducing avg waiting time	Starvation of long jobs
LJF	Largest burst time	No	Long tasks priority	Starvation of short jobs

 

 

PREEMPTIVE SCHEDULING ALGORITHMS

In preemptive scheduling, the CPU can be taken away from a process before it finishes execution.

The OS interrupts a running process when:

• A higher priority process arrives
• Time quantum expires
• A shorter job arrives (SRTF)

Preemption improves responsiveness, especially in time-sharing systems.

 

1. Priority Scheduling (Preemptive)

Definition

Each process is assigned a priority number.
The CPU is always given to the highest priority process.

Lower number = Higher priority (common convention)

Preemptive rule

If a new process arrives with higher priority, it preempts the running process.

Example:

Process	Arrival Time	Burst Time	Priority
P1	0	5	2
P2	1	3	1
P3	3	2	3

Execution:

• At t=0 → P1 runs
• At t=1 → P2 arrives (priority 1) → preempts P1
• After P2 → P1 → P3

Gantt Chart:

| P1 |--1--| P2 |--3--| P1 |--4--| P3 |-2-|

0       1      4        8        10

 

Advantages

• Suitable for real-time systems
• Important tasks get CPU quickly

Disadvantages

• Lower priority processes starve
• Need careful priority assignment

 

2. Round Robin (RR)

Definition

Each process gets equal time slice / time quantum (q) in cyclic order.

Common q values: 10ms, 20ms

Preemption rule

If a process does not finish in its time quantum, it is preempted and moved to the end of the ready queue.

 

Example (q = 2 ms):

Process	Arrival Time	Burst Time
P1	0	5
P2	1	3
P3	2	1

Gantt Chart:

P1 P2 P3 P1 P2 P1

0  2  4  5  7  9 10

 

Advantages

• Fair → every process gets CPU
• Good for time-sharing systems
• No starvation

Disadvantages

• Larger waiting time if q is large
• More context switching if q is small

 

3. Shortest Remaining Time First (SRTF)

Definition

Preemptive version of Shortest Job First (SJF)
CPU is given to the process with least remaining burst time.

Preemption rule

If a new process arrives with shorter remaining time, it preempts the current one.

 

Example:

Process	AT	BT
P1	0	7
P2	2	4
P3	4	1

Execution:

• P1 (0–2)
• P2 arrives (remaining 4 < 5) → preempts P1
• P3 arrives (1 < 3) → preempts P2
• P3 → P2 → P1

Gantt Chart:

P1 |--2--| P2 |--2--| P3 |-1-| P2 |--2--| P1 |--5--|

0        2        4      5        7        12

 

Advantages

• Minimum average waiting time
• Suitable for interactive systems

Disadvantages

• Starvation for long jobs
• Frequent preemption → overhead

 

4. Longest Remaining Time First (LRTF)

Definition

CPU is given to the process with the highest remaining burst time.

(Opposite of SRTF)

Preemption rule

If a new process arrives with larger remaining time, it preempts the CPU.

Example:

Process	AT	BT
P1	0	3
P2	1	6
P3	3	4

Execution:

• t=0 → P1
• t=1 → P2 arrives → larger → preempts
• t=3 → P3 arrives (remaining 6 > 4) → no preemption
• After P2 → P3 → P1

Gantt Chart:

P1 |-1-| P2 |------6------| P3 |--4--| P1 |-2-|

0     1               7       11      13

 

Advantages

• Good for systems where long jobs must not wait
• Higher throughput for long tasks

Disadvantages

• Short tasks starve
• Larger waiting time

 

5. Multilevel Queue Scheduling (MLQ)

Definition

Processes are divided into multiple fixed queues based on priority or type.

Typical queues:

1. System Processes
2. Interactive Processes
3. Interactive Editing
4. Batch Jobs
5. Student/Background Jobs

Characteristics

• Each queue has its own scheduling algorithm
• Queues have fixed priority levels

 

Example:

• Queue 1: Interactive → Round Robin
• Queue 2: Batch → FCFS
• Queue 1 always has priority over Queue 2

If Queue 1 is non-empty → CPU never goes to Queue 2.

 

Advantages

• Suitable for systems with different process types
• Very structured and organized

Disadvantages

• Lower queues may starve
• No movement between queues

 

6. Multilevel Feedback Queue Scheduling (MLFQ)

Definition

Similar to MLQ, but processes can move between queues based on behavior.

Goal

• Give short jobs better CPU time
• Reduce starvation
• Adjust priority dynamically

 

Characteristics:

• Multiple queues with different priorities
• Higher priority → smaller time quantum
• If process uses full quantum, move it down
• If process waits too long, move it up

 

Example Queue Setup:

Queue	Priority	Time Quantum
Q1	Highest	4 ms
Q2	Medium	8 ms
Q3	Lowest	FCFS

Execution:

• New processes enter Q1
• If they need more time → go to Q2
• If still more → Q3

Advantages

• Prevents starvation
• Adaptive system
• Good for general-purpose OS

Disadvantages

• Complex to implement
• Hard to tune parameters (q, queue count)

 

Algorithm	Preemption	Strategy	Starvation?	Best For
Priority	Yes	Highest priority	Yes	Real-time
RR	Yes	Fixed quantum	No	Time-sharing
SRTF	Yes	Shortest remaining time	Yes	Low waiting time
LRTF	Yes	Longest remaining time	Yes	Long jobs
MLQ	Yes/No	Fixed queues	Yes	Multi-user OS
MLFQ	Yes	Dynamic queues	No	General OS

                      

 MULTIPLE PROCESSOR SCHEDULING.

CPU Scheduling is a mechanism by which an operating system decides which task or process should execute on the CPU at any given moment. When a system contains more than one CPU, Multiple-Processor Scheduling involves distributing tasks across multiple processors. This enables several tasks to be processed in parallel, improving performance significantly.

 

Key Challenges:

• Deciding which CPU handles which task.

• Balancing workloads between processors to avoid idle CPUs or overloaded processors.

Note: In multiple processor scheduling, there are cases when the processors are identical i.e. Homogenous, in terms of their functionality, we can use any processor available to run any process in the queue.

Approaches to Multiple-Processor Scheduling

Asymmetric Multiprocessing (AMP)

• One processor acts as a Master Server handling scheduling decisions and I/O operations.

• Other processors execute only user code.

• Simple design, reduces data-sharing complexity.

Symmetric Multiprocessing (SMP)

• Each processor can schedule tasks independently.

• Two models of task queues:

Common Ready Queue: All CPUs access a shared queue of ready processes.
Private Ready Queues: Each CPU has its own queue of ready processes.

Important Concepts in Multiprocessor Scheduling

1. Processor Affinity

• A process prefers to run on the same processor it previously ran on.

• Benefits: Data stays in the CPU cache & reduces cache misses and improves performance.

Types of Affinity:

• Soft Affinity: OS attempts (but does not guarantee) to keep a process on the same CPU.

• Hard Affinity: Restricts the process to run only on a specific subset of processors using system calls (e.g., sched_setaffinity() in Linux).

2. Load Balancing

Essential to avoid:

• Overloaded processors with long queues.

• Idle processors while other processors are busy.

Two approaches:

1. Push Migration: A processor actively moves tasks from itself to less busy processors to balance load.

2. Pull Migration: An idle processor pulls tasks from busy processors to balance its workload.

3. Multicore Processors

• Multiple processor cores on a single physical chip.

• Each core appears as an independent processor to the OS.

Challenge: Memory Stall

• Happens when a processor waits for data not present in cache.

• Up to 50% of time can be wasted waiting for memory.

Solution: Multithreading within Cores

• Coarse-Grained Multithreading: Switch thread when long latency events occur (e.g., cache miss).

• Fine-Grained Multithreading: Switch threads every instruction cycle, keeping the pipeline filled with minimal overhead.

4. Virtualization and Threading

• Single physical CPU appears as multiple virtual CPUs to virtual machines.

• Host OS manages multiple guest OS instances.

• Problem: Time-slice distortion - guest OS time slices may not match real CPU cycles due to virtualization overhead.

Impacts: Poor response times for virtualized systems & Time-of-day clocks may be inaccurate.

Pros of Multiple-Processor Scheduling

• High throughput by parallel execution of tasks.

• Better resource utilization.

• Scalability for large applications and real-time systems.

Cons of Multiple-Processor Scheduling

• Complex implementation and maintenance.

• Difficult load balancing.

• Increased overhead due to process migration and affinity management.

• Virtualization may affect real-time guarantees.

 

 

************END of UNIT-II ************