Synchronization Techniques
- Synchronization techniques are essential for operating systems to manage concurrent tasks efficiently. They ensure that multiple tasks or threads can operate simultaneously without interfering with each other, preventing issues such as data corruption, race conditions, and deadlocks.
Type 1
Normal and Clock-Driven Schedulers
- Normal Schedulers: These schedulers decide the order in which tasks are executed based on priority or other criteria. They are dynamic and can change the execution order based on system conditions.
- Clock-Driven Schedulers: These schedulers operate based on a clock. Tasks are executed at specific times or intervals, making them predictable and suitable for real-time systems.
Mutex Semaphores
- A.Mutex (Mutual Exclusion): A mechanism to ensure that multiple threads do not concurrently access a critical section of code or data. Mutexes prevent race conditions by allowing only one thread to access the resource at a time.
- B.Semaphores: These are signaling mechanisms that can control access to resources by multiple threads. A semaphore maintains a count and allows threads to acquire or release resources based on this count.
- Types of Semaphores
Monitors and Condition Variables
- C.Monitors: High-level synchronization constructs that provide a mechanism to manage mutual exclusion and synchronization. A monitor encapsulates shared variables, operations on them, and the necessary synchronization.
- D.Condition Variables: These are used within monitors to allow threads to wait for certain conditions to be true before proceeding. Condition variables are often used in conjunction with mutexes to manage complex synchronization scenarios.
--------------------------------------------------------------
Type 2 :
Clock and Priority-Driven Schedulers
- Clock-Driven Schedulers: As mentioned earlier, these schedulers trigger task execution based on time intervals, ensuring tasks run at predictable times.
- Priority-Driven Schedulers: These schedulers assign priorities to tasks and execute them based on their priority levels. Higher priority tasks are executed before lower priority ones.
A.Non-Preemptive Critical Section Protocol (NPCS)
- NPCS: A synchronization protocol where a task, once it enters a critical section, cannot be preempted by other tasks until it exits the critical section. This ensures that critical sections are executed without interruption, but it can lead to longer waiting times for other tasks.
B.Priority Inheritance Protocol
- Priority Inheritance Protocol: A protocol used to handle priority inversion, where a lower-priority task holds a resource needed by a higher-priority task. In this protocol, the lower-priority task temporarily inherits the higher priority of the waiting task to reduce blocking time.
- SO WHAT IS THE PRIORITY INVERSION ???
- In Simple words : its like the task with lower priority makes task with heigher priority waits longer than expected
C.Priority Ceiling Protocol
- Priority Ceiling Protocol: Another protocol to manage priority inversion. Each resource is assigned a priority ceiling, which is the highest priority of any task that may lock the resource. A task can lock a resource only if its priority is higher than the current system ceiling. This prevents priority inversion and ensures a bounded blocking time.
Code
-
Mutex
- General blocked Queue Implementation : used in Mutex.h file
#ifndef OPERATING_SYSTEM_GENERALBLOCKEDQUEUE_H
#define OPERATING_SYSTEM_GENERALBLOCKEDQUEUE_H
#define MAX_PROCESSES 3
#include "Process.h"
typedef struct {
Process *queue[MAX_PROCESSES];
int front;
int rear;
int capacity;
} BlockedQueue;
void init_BlockedQueue(BlockedQueue *blockedQueue) {
blockedQueue->front = 0;
blockedQueue->rear = -1;
blockedQueue->capacity = MAX_PROCESSES;
}
int isBlockedEmpty(BlockedQueue* queues) {
return queues->rear == -1;
}
int isBlockedFull(BlockedQueue* queues) {
return queues->rear+1 == queues->capacity;
}
void printBlocked(BlockedQueue* queue){
printf("General Blocked Queue: ");
for(int i = 0; i <= queue->rear; i++){
printf("%d ",queue->queue[i]->pcb->processID);
}
printf("\n");
}
void enqueueBlocked(BlockedQueue *queue, Process * process) {
if(isBlockedFull(queue)){
printf("Queue is Full\n");
return;
}
queue->queue[++queue->rear] = process;
printf("\n");
printf("enqueue process %d\n", process->pcb->processID);
printBlocked(queue);
printf("\n");
}
void dequeueBlocked(BlockedQueue *queue, Process* unblocked) {
if(isBlockedEmpty(queue)){
printf("General Blocked queue is empty\n");
return;
}
int removed = -1;
for(int i = 0; i <= queue->rear; i++){
if(queue->queue[i] == unblocked){
// or check if processId's are equal, if something goes wrong
removed = i;
}
}
int id = queue->queue[removed]->pcb->processID;
for(int i = removed; i < queue->rear; i++){
queue->queue[i] = queue->queue[i+1];
}
queue->rear--;
printf("\n");
printf("dequeue process %d\n", id);
printBlocked(queue);
printf("\n");
}
#endif //OPERATING_SYSTEM_GENERALBLOCKEDQUEUE_H
- Mutex.h file
#ifndef OPERATING_SYSTEM_MUTEX_H
#define OPERATING_SYSTEM_MUTEX_H
#include "Process.h"
#include "GeneralBlockedQueue.h"
typedef struct {
Process* queue[3];
int front;
int rear;
int capacity;
}LockQueue;
typedef struct {
enum {zero,one} value;
char resourceName[10];
LockQueue queue;
int ownerID;
}MUTEX;
enum state {Failed = -1, Success = 0, Blocked = 1};
void init_mutex(MUTEX *mutex, char name[]) {
mutex->value = one; // Assuming 'zero' means unlocked. No 'one means unlocked you twat
strcpy(mutex->resourceName,name);
mutex->queue.front = 0;
mutex->queue.rear = -1;
mutex->queue.capacity = 3;
mutex->ownerID = -1; // No owner initially
}
int isLockQueueEmpty(LockQueue* queues) {
return queues->rear == -1;
}
int isLockQueueFull(LockQueue* queues) {
return queues->rear+1 == queues->capacity;
}
void printMutexQ(MUTEX *m){
printf("Mutex🔒 %s ownerID: %d\n", m->resourceName, m->ownerID);
printf("🔒LockQueue🔒: ");
for(int i = 0; i<=m->queue.rear; i++){
printf("%d ", m->queue.queue[i]->pcb->processID);
}
printf("\n");
}
void enqueueLock(LockQueue *queue, Process * process) {
if(isLockQueueFull(queue)){
printf("Queue is Full\n");
return;
}
queue->queue[++queue->rear] = process;
}
Process* dequeueLock(LockQueue *queue) {
int highest = 5;
int highi = 0;
for(int i = 0; i < queue->rear; i++){
if(queue->queue[i]->pcb->currentPriority < highest){
highest = queue->queue[i]->pcb->currentPriority;
highi = i;
}
}
Process *process = queue->queue[highi];
for(int i = highi; i < queue->rear; i++){
queue->queue[i] = queue->queue[i+1];
}
queue->rear--;
return process;
}
enum state semWait(MUTEX *m , Process * p) {
if (m->value == one) {
m->ownerID = p->pcb->processID;
m->value = zero;
return Success;
}
printf("\n");
enqueueLock(&m->queue,p);
printMutexQ(m);
printf("\n");
return Blocked;
}
Process *semSignal(MUTEX *m , Process* p) {
if(m->ownerID == p->pcb->processID){
if (isLockQueueEmpty(&m->queue)){
m->value = one;
m->ownerID = -1;
return NULL;
}
else {
printf("\n");
Process * proc = dequeueLock(&m->queue);
m->ownerID = proc->pcb->processID;
printMutexQ(m);
printf("\n");
return proc;
}
}
return NULL;
}
#endif //OPERATING_SYSTEM_MUTEX_H
-
Binary Semaphore (The code idea)
struct binary_semaphore {
enum {zero,one} value;
queueType queue;
};
void semWaitB(binary_semaphore s) {
if (s.value == one)
s.value = zero;
else {
/* place this process in s.queue */
}
}
void semSignalB(semaphore s) {
if (s.queue.isEmpty())
s.value = one;
else {
/* remove a process P from s.queue and place it on ready list*/
}
}
-
Counting Semaphore (Code Idea)
Counting Semaphore
struct semaphore {
int count;
queueType queue;
};
void semWait(semaphore s) {
s.count--;
if (s.count < 0) {
/* place this process in s.queue */
/* block this process */
}
}
void semSignal(semaphore s) {
S.count++;
if (s.count <= 0) {
/* remove a process P from s.queue and place it on ready list*/
}
}
These synchronization techniques are crucial in concurrent and real-time systems to ensure the correct and efficient execution of tasks, preventing issues like race conditions, deadlocks, and priority inversion.
--------------------------------------------------------
We'll talk about Producer and Consumer Issues Next Time and synchronization techniques are what assess it. Also i will provide you with some questions and their answers related to producer and consumer part.
In case today's portion is unclear, kindly provide a remark to further explain it 😊. It is a complicated part, I know that 🫡
- So please let me know which part you want next time .
- More illustration for Synchronization Techniques
- Producer and Consumer
Comments (1)