Section A
a) Explain POSIX Threads
POSIX Threads (Pthreads) are a standard set of functions used for multithreading in C/C++
programs on UNIX/Linux systems.
They allow multiple threads to run simultaneously within the same process, improving
performance and resource sharing.
Pthreads provide functions for thread creation, synchronization, and communication.
b) Discuss the motivation for concurrency in software
Concurrency allows multiple tasks to execute at the same time.
It improves CPU utilization, increases program speed, and provides better responsiveness in
applications.
It is useful in multitasking systems, web servers, real-time systems, and parallel computing.
c) How Thread Synchronization takes place?
Thread synchronization is used to coordinate multiple threads and avoid conflicts while
accessing shared data.
It is achieved using synchronization tools like mutexes, semaphores, monitors, and condition
variables.
Synchronization prevents problems such as race conditions and data inconsistency.
d) Explain the term Deadlock
Deadlock is a condition where two or more processes/threads wait indefinitely for resources
held by each other.
In this situation, none of the processes can continue execution.
Deadlock usually occurs due to improper resource allocation and synchronization.
e) Name some common Parallel Programming Problems
Some common problems in parallel programming are:
• Race condition
• Deadlock
• Starvation
• Load balancing
• Communication overhead
• Synchronization issues
These problems affect the performance and correctness of parallel programs.
f) Discuss how threads overhead can be minimized
Thread overhead can be minimized by reducing unnecessary thread creation and destruction.
Using thread pools, efficient synchronization methods, and balanced workload distribution
also helps.
Minimizing context switching improves overall system performance.
g) Define Live Locks
Livelock is a condition where threads/processes keep changing their states in response to
each other but still make no progress.
Unlike deadlock, the processes are active but unable to complete their tasks.
It usually happens due to excessive resource coordination attempts.
Section B (Easy 10 Marks Answers)
2(a) Amdahl’s Law
Amdahl’s Law is used to find the maximum speedup of a program using multiple processors
in parallel computing.
It states that the performance improvement depends on the parallel part of the program.
Formula:
Speedup = 1/ (1-P) + P/N
Where:
• P = Parallel portion of program
• N = Number of processors
Performance Criteria
1. Speedup – Increase in execution speed.
2. Efficiency – Proper use of processors.
3. Scalability – Ability to work with more processors.
4. Execution Time – Total time taken by program.
Limitations
• Sequential part reduces overall speedup.
• Communication overhead is ignored.
• Not suitable for very large distributed systems.
Conclusion
Amdahl’s Law helps in measuring the benefits and limits of parallel computing systems.
2(b) Semaphores and its Types
A semaphore is a synchronization tool used to control access to shared resources in
multithreading and parallel programming.
It prevents race conditions and maintains proper execution of processes.
Operations
1. Wait (P) – Decreases semaphore value.
2. Signal (V) – Increases semaphore value.
Types of Semaphores
1. Binary Semaphore
• Value is either 0 or 1.
• Used like a mutex lock.
• Only one process can access resource at a time.
2. Counting Semaphore
• Value can be more than 1.
• Used when multiple resources are available.
Example
Suppose two threads want to use a printer:
• Semaphore value = 1
• First thread accesses printer.
• Second thread waits until printer becomes free.
Advantages
• Prevents data corruption
• Provides synchronization
Disadvantages
• May cause deadlock if not used properly
Conclusion
Semaphores are important for safe resource sharing in parallel systems.
2(c) Error Diffusion and Floyd-Steinberg
Algorithm
Error diffusion is an image processing method used to convert grayscale images into black-
and-white images.
The error generated at one pixel is distributed to neighboring pixels.
Steps
1. Read pixel value.
2. Convert it to black or white.
3. Calculate error.
4. Spread error to nearby pixels.
Error Formula =
error = original pixel – new pixel
Floyd-Steinberg Algorithm
This algorithm distributes error using fixed weights.
X 7/16
3/16 5/16 1/16
Error Distribution
• Right pixel → 7/16
• Bottom-left → 3/16
• Bottom → 5/16
• Bottom-right → 1/16
Advantages
• Better image quality
• Preserves image details
Disadvantages
• More processing required
Conclusion
Floyd-Steinberg algorithm is widely used for high-quality image conversion.
2(d) Shared Memory Programming with
OpenMP
Shared memory programming is a model where multiple threads share the same memory
space.
OpenMP is an API used for parallel programming in C, C++ and Fortran.
Features of OpenMP
• Easy to use
• Supports multithreading
• Improves performance
Important Directives
1. #pragma omp parallel – Creates threads
2. #pragma omp for – Divides loop among threads
3. #pragma omp critical – Protects shared data
Example
#pragma omp parallel
{
printf("Hello");
}
Advantages
• Faster execution
• Better CPU utilization
Disadvantages
• Works only in shared memory systems
Applications
• Scientific computing
• Image processing
Conclusion
OpenMP is a simple and effective tool for parallel programming.
2(e) IA-32 Architecture and Pipeline Stall
Avoidance
IA-32 is Intel’s 32-bit processor architecture used in Pentium systems.
It supports multitasking, pipelining, and virtual memory.
Main Components
1. Registers
2. Cache Memory
3. ALU
4. Pipeline Unit
Pipeline Stages
1. Fetch
2. Decode
3. Execute
4. Memory Access
5. Write Back
Pipeline Stall
A pipeline stall occurs when the next instruction cannot execute immediately.
Causes
• Data hazards
• Control hazards
• Resource conflicts
Methods to Avoid Pipeline Stalls
1. Branch Prediction
Predicts branch instructions early.
2. Data Forwarding
Sends data directly between stages.
3. Instruction Prefetching
Fetches instructions before needed.
4. Out-of-Order Execution
Executes independent instructions first.
Advantages
• Improves processor speed
• Better instruction execution
Conclusion
IA-32 architecture improves performance using pipelining and advanced execution
techniques.
Section C Answers (Easy 10 Marks)
3(a) Flynn’s Taxonomy of Parallel
Computing
Flynn’s Taxonomy is a classification of computer architectures based on the number of
instruction streams and data streams processed simultaneously.
It was proposed by Michael Flynn.
There are four types of architectures:
1. SISD (Single Instruction Single Data)
• One processor executes one instruction on one data at a time.
• Used in traditional sequential computers.
Features
• Simple architecture
• No parallelism
• Low performance
Example
• Old single-core computers
2. SIMD (Single Instruction Multiple Data)
• One instruction operates on multiple data items simultaneously.
• Same operation is performed on different data.
Features
• High speed for repetitive tasks
• Used in image and video processing
Example
• GPUs
• Vector processors
3. MISD (Multiple Instruction Single Data)
• Multiple instructions operate on same data stream.
• Rarely used architecture.
Features
• High reliability
• Mainly used in fault-tolerant systems
Example
• Space and aircraft control systems
4. MIMD (Multiple Instruction Multiple Data)
• Multiple processors execute different instructions on different data simultaneously.
Features
• True parallel processing
• High performance
• Most modern multicore systems use this
Example
• Multicore processors
• Distributed systems
Advantages of Flynn’s Taxonomy
• Easy classification of architectures
• Helps understand parallel systems
• Useful in system design
Conclusion
Flynn’s Taxonomy explains different types of parallel computer architectures based on
instruction and data streams.
3(b) Synchronization Primitives in Parallel
Programming
Synchronization primitives are tools used to coordinate multiple threads or processes in
parallel programming.
They help avoid race conditions and ensure correct execution.
Types of Synchronization Primitives
1. Mutex (Mutual Exclusion)
A mutex allows only one thread to access a shared resource at a time.
Features
• Prevents data corruption
• Used in critical sections
Example
Printer access by multiple threads.
2. Semaphore
Semaphore controls access to shared resources using a counter.
Types
• Binary Semaphore
• Counting Semaphore
Uses
• Process synchronization
• Resource management
3. Barrier
Barrier forces all threads to wait until every thread reaches the same point.
Uses
• Parallel algorithms
• Scientific computing
4. Condition Variable
Condition variable allows threads to wait until a specific condition becomes true.
Uses
• Producer-consumer problems
Challenges in Parallel Programming
1. Race Condition
Occurs when multiple threads access shared data simultaneously.
2. Deadlock
Processes wait forever for resources.
3. Starvation
A process never gets CPU resources.
4. Livelock
Processes keep changing state but make no progress.
5. Synchronization Overhead
Too much synchronization reduces performance.
Conclusion
Synchronization primitives are essential for safe and efficient parallel programming.
4(a) Thread Creation and Thread
Management
A thread is the smallest unit of execution inside a process.
Multithreading allows multiple threads to run simultaneously.
Thread Creation
Threads are created using thread libraries such as POSIX Threads (Pthreads).
Steps
1. Create thread
2. Execute task
3. Synchronize threads
4. Terminate thread
Example Function
pthread_create();
Thread Management
Thread management controls execution of threads.
Operations
1. Creation – Start new thread
2. Scheduling – CPU allocates execution time
3. Synchronization – Coordinates shared data access
4. Termination – Ends thread execution
Advantages of Multithreading
• Faster execution
• Better CPU utilization
• Improved responsiveness
Disadvantages
• Synchronization complexity
• Possible deadlocks
Applications
• Web servers
• Games
• Parallel computing
Conclusion
Thread management improves system performance by efficiently handling multiple threads.
4(b) Decomposition and its Types
Decomposition is the process of dividing a large problem into smaller tasks for parallel
execution.
It improves performance and reduces execution time.
Types of Decomposition
1. Data Decomposition
Data is divided into smaller parts and processed in parallel.
Example
Large matrix divided among processors.
Advantages
• Easy implementation
• Better load balancing
2. Task Decomposition
Different tasks are assigned to different processors.
Example
One processor handles input, another handles calculations.
Advantages
• Efficient multitasking
• Better resource usage
3. Recursive Decomposition
Problem is repeatedly divided into subproblems.
Example
Merge Sort algorithm.
4. Domain Decomposition
Problem domain is divided into regions.
Example
Weather simulation systems.
Advantages
• Faster computation
• Better processor utilization
Disadvantages
• Communication overhead
• Synchronization issues
Conclusion
Decomposition is important in parallel computing for dividing work efficiently among
processors.
5(a) Compare and Contrast Mutual
Exclusion (Mutex) and Locks
Mutex and locks are synchronization mechanisms used to protect shared resources in
multithreading.
They prevent multiple threads from accessing critical sections simultaneously.
Mutex
Mutex stands for Mutual Exclusion.
Only one thread can access the resource at a time.
Features
• Ownership based
• Simple synchronization
• Used in thread programming
Example
pthread_mutex_lock();
Locks
Locks are general synchronization mechanisms used to control resource access.
Types:
• Spin lock
• Read-write lock
Features
• Controls concurrent access
• Used in operating systems
Difference Between Mutex and Lock
Mutex Lock
Specific type of lock General synchronization tool
Has ownership May or may not have ownership
Simpler More flexible
Used mainly in threads Used in many synchronization methods
Advantages
• Prevents race conditions
• Maintains data consistency
Disadvantages
• Incorrect use may cause deadlock
Conclusion
Mutex is a special type of lock used for mutual exclusion in multithreaded systems.
5(b) Threading API’s for Microsoft .NET
Framework
The .NET Framework provides threading APIs for developing multithreaded applications.
These APIs help create, manage, and synchronize threads.
Important Threading APIs
1. Thread Class
Used to create and control threads.
Functions
• Start()
• Sleep()
• Join()
Example
Thread t = new Thread(method);
[Link]();
2. ThreadPool
Manages a pool of reusable threads.
Advantages
• Reduces thread creation overhead
• Better performance
3. Task Parallel Library (TPL)
Provides easy parallel programming using tasks.
Example
[Link](() => {
[Link]("Task");
});
4. Synchronization APIs
Used for thread coordination.
Examples:
• Mutex
• Semaphore
• Monitor
Advantages of .NET Threading
• Easy multithreading
• Better CPU utilization
• Improved application performance
Disadvantages
• Complex debugging
• Synchronization overhead
Applications
• Web applications
• Games
• Parallel systems
Conclusion
Microsoft .NET threading APIs provide efficient tools for creating and managing
multithreaded applications.
6(a) Short Notes on OpenMP
(i) OpenMP Library Functions
OpenMP library functions are used to control and manage parallel execution in shared
memory programming.
These functions are available through the omp.h header file.
Common OpenMP Functions
1. omp_get_thread_num()
Returns the ID number of the current thread.
Example
int id = omp_get_thread_num();
2. omp_get_num_threads()
Returns the total number of threads running.
int n = omp_get_num_threads();
3. omp_set_num_threads()
Sets the number of threads for execution.
omp_set_num_threads(4);
4. omp_get_max_threads()
Returns maximum available threads.
5. omp_get_wtime()
Used to measure execution time.
Advantages
• Easy thread management
• Improves program performance
• Simple parallel programming
Applications
• Scientific computing
• Matrix operations
• Image processing
Conclusion
OpenMP library functions help programmers create and control parallel programs easily.
(ii) OpenMP Environment Variables
OpenMP environment variables are used to control the behavior of parallel programs.
They are set before program execution.
Important Environment Variables
1. OMP_NUM_THREADS
Sets number of threads.
OMP_NUM_THREADS = 4
2. OMP_SCHEDULE
Controls loop scheduling method.
Types:
• Static
• Dynamic
3. OMP_DYNAMIC
Enables or disables dynamic adjustment of threads.
4. OMP_NESTED
Controls nested parallelism.
Advantages
• Easy program control
• Better performance tuning
• Flexible execution
Conclusion
OpenMP environment variables improve performance and provide better control over parallel
execution.
6(b) Loop Scheduling and Portioning
Loop scheduling is the process of dividing loop iterations among multiple threads in parallel
programming.
Portioning means distributing work equally among processors.
OpenMP provides different scheduling methods.
Types of Loop Scheduling
1. Static Scheduling
Iterations are divided equally before execution.
Features
• Simple and fast
• Less overhead
Example
#pragma omp for schedule(static)
2. Dynamic Scheduling
Iterations are assigned during execution.
Features
• Better load balancing
• Higher overhead
Example
#pragma omp for schedule(dynamic)
3. Guided Scheduling
Large chunks are assigned first, then smaller chunks later.
Features
• Reduces overhead
• Good load balancing
4. Runtime Scheduling
Scheduling type is decided at runtime using environment variables.
Advantages of Loop Scheduling
• Better CPU utilization
• Faster execution
• Balanced workload
Disadvantages
• Synchronization overhead
• Complex scheduling in large systems
Conclusion
Loop scheduling and portioning improve performance by distributing work efficiently among
threads.
7(a) ABA Problem in Multicore
Programming and its Solution
The ABA problem occurs in multicore programming when a shared variable changes from A
to B and back to A again.
A thread may think the value never changed, causing incorrect execution.
It commonly occurs in lock-free data structures.
Example of ABA Problem
1. Thread T1 reads value A.
2. Thread T2 changes A → B → A.
3. T1 checks value again and thinks nothing changed.
This creates inconsistency in the program.
Problems Caused
• Incorrect synchronization
• Data inconsistency
• System errors
Solution of ABA Problem
1. Version Counter
Attach a version number with data.
Example:
• A1 → B2 → A3
Even if value becomes A again, version changes.
2. Tagged Pointer
Adds extra information with memory address.
3. Locks and Mutex
Use synchronization mechanisms to avoid simultaneous modification.
Advantages of Solution
• Better data consistency
• Safe parallel execution
• Prevents synchronization errors
Conclusion
ABA problem is common in lock-free programming and can be solved using version counters
and synchronization methods.
7(b) Heavily Contended Locks and Their
Solutions
A heavily contended lock occurs when many threads try to access the same lock
simultaneously.
This causes delays and reduces system performance.
Problems of Heavily Contended Locks
1. Increased waiting time
2. CPU wastage
3. Poor scalability
4. Reduced performance
Causes
• Too many threads
• Shared resource access
• Long critical sections
Solutions for Heavily Contended Locks
1. Fine-Grained Locking
Use separate locks for different resources.
Advantage
Reduces waiting among threads.
2. Read-Write Locks
Allows multiple readers but only one writer.
Advantage
Improves performance for read-heavy systems.
3. Lock-Free Programming
Uses atomic operations instead of locks.
Advantage
Reduces blocking.
4. Backoff Algorithms
Threads wait for some time before retrying.
Advantage
Reduces CPU contention.
5. Thread Scheduling
Efficient scheduling reduces lock competition.
Advantages of Solutions
• Better scalability
• Faster execution
• Reduced waiting time
Conclusion
Heavily contended locks reduce parallel system performance. Proper locking techniques and
lock-free methods help improve efficiency.