logo

TechCodeview

Semaforer i processynkronisering

Semaforer er bare normale variabler, der bruges til at koordinere aktiviteterne i flere processer i et computersystem. De bruges til at gennemtvinge gensidig udelukkelse, undgå raceforhold og implementere synkronisering mellem processer.

Processen med at bruge Semaphores giver to operationer: vent (P) og signal (V). Venteoperationen formindsker værdien af ​​semaforen, og signaloperationen øger værdien af ​​semaforen. Når værdien af ​​semaforen er nul, vil enhver proces, der udfører en venteoperation, blive blokeret, indtil en anden proces udfører en signaloperation.



Semaforer bruges til at implementere kritiske sektioner, som er kodeområder, der kun skal udføres af én proces ad gangen. Ved at bruge semaforer kan processer koordinere adgang til delte ressourcer, såsom delt hukommelse eller I/O-enheder.

En semafor er en speciel form for synkroniseringsdata, der kun kan bruges gennem specifikke synkroniseringsprimitiver. Når en proces udfører en venteoperation på en semafor, kontrollerer operationen, om værdien af ​​semaforen er>0. Hvis det er tilfældet, formindsker den værdien af ​​semaforen og lader processen fortsætte sin eksekvering; ellers blokerer det processen på semaforen. En signaloperation på en semafor aktiverer en proces, der er blokeret på semaforen, hvis nogen, eller øger værdien af ​​semaforen med 1. På grund af denne semantik kaldes semaforer også tælle semaforer. Startværdien af ​​en semafor bestemmer, hvor mange processer der kan komme forbi venteoperationen.

uordensgennemgang af binært træ

Semaforer er af to typer:



  1. Binær semafor –
    Dette er også kendt som en mutex-lås. Den kan kun have to værdier – 0 og 1. Dens værdi initialiseres til 1. Den bruges til at implementere løsningen af ​​kritiske sektionsproblemer med flere processer.
  2. Tælle semafor -
    Dens værdi kan spænde over et ubegrænset domæne. Det bruges til at kontrollere adgangen til en ressource, der har flere forekomster.

Lad os nu se, hvordan det gør det.

Se først på to operationer, der kan bruges til at få adgang til og ændre værdien af ​​semaforvariablen.

P-og-V-drift-i-OS



Nogle punkter vedrørende P- og V-drift:

java indeholder understreng
  1. P-drift kaldes også vente-, dvale- eller neddrift, og V-drift kaldes også signal-, væknings- eller op-drift.
  2. Begge operationer er atomare og semafor(er) initialiseres altid til én. Her betyder atom den variabel, hvorpå læsning, ændring og opdatering sker på samme tid/øjeblik uden forkøbsret, dvs. mellem læsning, ændring og opdatering udføres ingen anden operation, der kan ændre variablen.
  3. En kritisk sektion er omgivet af begge operationer for at implementere processynkronisering. Se nedenstående billede. Den kritiske sektion af proces P er mellem P- og V-drift.

Lad os nu se, hvordan det implementerer gensidig udelukkelse. Lad der være to processer P1 og P2, og en semafor s initialiseres som 1. Hvis nu, hvis P1 går ind i sin kritiske sektion, bliver værdien af ​​semafor s 0. Hvis P2 nu vil ind i sin kritiske sektion, vil den vente til s> 0, dette kan kun ske, når P1 afslutter sit kritiske afsnit og kalder V-operation på semafor s.

ramme tkinter

På denne måde opnås gensidig udelukkelse. Se på billedet nedenfor for detaljer, som er en binær semafor.


Implementering: Binære semaforer

C++ 
struct semaphore {    enum value(0, 1);  // q contains all Process Control Blocks (PCBs)  // corresponding to processes got blocked  // while performing down operation.  Queueq; }; P(semafor s) { if (s.værdi == 1) { s.værdi = 0;  } else { // tilføj processen til ventekøen q.push(P) sleep();  } } V(semafor s) { if (s.q er tom) { s.value = 1;  } else { // vælg en proces fra ventekøen. Process p = q.front();  // fjern processen fra at vente, som den er blevet // sendt til CS q.pop();  vågne op(p);  } } // Denne kode er ændret af Susobhan Akhuli>
C 
#include  #include #include struct semaphore{  Queueq;  int værdi; }; void P(struct semafor s) { if (s.value == 1) { s.value = 0;  } andet { s.q.push(P);   søvn();  } } void V(semafor s) { if (s.q er tom) { s.value = 1;  } else { // Hent en proces fra Waiting Queue Process p = q.front();  // Fjern processen fra at vente q.pop();  vågne op(p);  } } int main() { printf('Dette er Hemish!!');    // Denne kode er bidraget af Himesh Singh Chauhan return 0; } // Denne kode er ændret af Susobhan Akhuli>
Java 
import java.util.*; class Semaphore {  public enum Value { Zero, One }  public Queueq = ny LinkedList();  offentlig Værdi værdi = Værdi.En;  public void P(Semaphore s, Process p) { if (s.value == Value.One) { s.value = Value.Zero;  } else { // tilføj processen til ventekøen q.add(p);  p.Søvn();  } } public void V(Semaphore s) { if (s.q.size() == 0) { s.value = Value.One;  } else { // vælg en proces fra ventekøen. Process p = q.peek();  // fjern processen fra at vente, da den er blevet sendt til CS q.remove();  s. Wakeup();  } } }>
Python3 
from enum import Enum from queue import Queue class Semaphore: class Value(Enum): Zero = 0 One = 1 def __init__(self): self.q = Queue() self.value = Semaphore.Value.One def P(self, s, p): if s.value == Semaphore.Value.One: s.value = Semaphore.Value.Zero else: # add the process to the waiting queue s.q.put(p) p.Sleep() def V(self, s): if s.q.qsize() == 0: s.value = Semaphore.Value.One else: # select a process from waiting queue p = s.q.queue[0] # remove the process from waiting as it has # been sent for CS s.q.get() p.Wakeup()>
C# 
using System.Collections.Generic; class Semaphore {  public enum value { Zero, One }  public Queueq = ny kø();  public void P(Semaphore s, Process p) { if (s.value == value.One) { s.value = value.Zero;  } else { // tilføj processen til ventekøen q.Enqueue(p);  p.Søvn();  } } public void V(Semaphore s) { if (s.q.Count == 0) { s.value = value.One;  } else { // vælg en proces fra ventekøen. Process p = q.Peek();  // fjern processen fra at vente, som den er blevet // sendt til CS q.Dequeue();  s. Wakeup();  } } }>
Javascript 
class Semaphore {  constructor() {  this.value = 0;  // q contains all Process Control Blocks (PCBs)  // corresponding to processes got blocked  // while performing down operation.  this.q = [];  }  P() {  if (this.value == 1) {  this.value = 0;  } else {  // add the process to the waiting queue  this.q.push(P);  sleep();  }  }  V() {  if (this.q.length == 0) {  this.value = 1;  } else {  // select a process from waiting queue  let p = this.q.shift();  // remove the process from waiting as it has been  // sent for CS  wakeup(p);  }  } }>

Beskrivelsen ovenfor er for binær semafor, som kun kan tage to værdier 0 og 1 og sikre gensidig udelukkelse. Der er en anden type semafor kaldet tælle semafor, som kan tage værdier større end én.

Antag nu, at der er en ressource, hvis antal forekomster er 4. Nu initialiserer vi S = 4, og resten er det samme som for binær semafor. Når processen ønsker den ressource, kalder den P eller venter på funktion, og når den er færdig, kalder den V eller signalfunktion. Hvis værdien af ​​S bliver nul, skal en proces vente, indtil S bliver positiv. Antag for eksempel, at der er 4 processer P1, P2, P3, P4, og de kalder alle vente-operation på S (initialiseret med 4). Hvis en anden proces P5 vil have ressourcen, skal den vente, indtil en af ​​de fire processer kalder signalfunktionen, og værdien af ​​semaforen bliver positiv.

Begrænsninger:

  1. En af de største begrænsninger ved semafor er prioritetsinversion.
  2. Deadlock, antag, at en proces forsøger at vække en anden proces, der ikke er i søvntilstand. Derfor kan et dødvande blokere på ubestemt tid.
  3. Operativsystemet skal holde styr på alle opkald for at vente og signalere semaforen.

Problem i denne implementering af en semafor:

Det største problem med semaforer er, at de kræver travl ventetid. Hvis en proces er i den kritiske sektion, vil andre processer, der forsøger at komme ind i den kritiske sektion, vente, indtil den kritiske sektion ikke er optaget af nogen proces. Når en proces venter, så kontrollerer den løbende for semaforværdi (se på denne linje, mens (s==0); i P-drift) og spild CPU-cyklus.

Der er også en chance for spinlock, da processerne fortsætter med spins, mens de venter på låsen. For at undgå dette er en anden implementering angivet nedenfor.

design mønstre i java

Implementering: Tælle semafor

CPP 
struct Semaphore {  int value;  // q contains all Process Control Blocks(PCBs)  // corresponding to processes got blocked  // while performing down operation.  Queueq; }; P(Semaphore s) { s.value = s.value - 1;  hvis (s.værdi< 0) {  // add process to queue  // here p is a process which is currently executing  q.push(p);  block();  }  else  return; } V(Semaphore s) {  s.value = s.value + 1;  if (s.value <= 0) {  // remove process p from queue  Process p = q.pop();  wakeup(p);  }  else  return; }>
Java 
import java.util.LinkedList; import java.util.Queue; // semaphore class  class Semaphore {  // our value  int value;  Queueq;  public Semaphore(int value) { this.value = værdi;  q = new LinkedList();  } public void P(Process p) { value--;  hvis (værdi< 0) {  q.add(p);  p.block();  }  }  public void V()  {  value++;  if (value <= 0) {  Process p = q.remove();  p.wakeup();  }  } }>
Python3 
import heapq # Global Variable to track the Processes going into Critical Section COUNTER=1 class Semaphore: def __init__(self,value): # Value of the Semaphore passed to the Constructor self.value=value # The Waiting queue which will be using the heapq module of Python self.q=list() def getSemaphore(self):  ''' Function to print the Value of the Semaphore Variable ''' print(f'Semaphore Value: {self.value}') def block(process): print(f'Process {process} Blocked.') def wakeup(process): print(f'Process {process} Waked Up and Completed it's work.') def P(s): global COUNTER s.value=s.value-1 if(s.value<0): heapq.heappush(s.q,COUNTER) block(COUNTER) else: print(f'Process {COUNTER} gone inside the Critical Section.') COUNTER+=1 return def V(s): global COUNTER s.value=s.value+1 if(s.value<=0): p=heapq.heappop(s.q) wakeup(p) COUNTER-=1 else: print(f'Process {COUNTER} completed it's work.') COUNTER-=1 return # Can Pass the Value of the Counting Semaphore to the Class Constructor # Example for Counting Semaphore value as 2 s1=Semaphore(2) s1.getSemaphore() P(s1) s1.getSemaphore() P(s1) s1.getSemaphore() P(s1) s1.getSemaphore() V(s1) s1.getSemaphore() V(s1) s1.getSemaphore() V(s1) s1.getSemaphore() # This Code is Contributed by Himesh Singh Chauhan>
C# 
using System.Collections.Generic; public class Semaphore {  public int value;  // q contains all Process Control Blocks(PCBs)  // corresponding to processes got blocked  // while performing down operation.  Queueq = ny kø();  public void P(Process p) { value--;  hvis (værdi< 0) {  // add process to queue  q.Enqueue(p);  p.block();  }  }  public void V()  {  value++;  if (value <= 0) {  // remove process p from queue  Process p = q.Dequeue();  p.wakeup();  }  } }>
JavaScript 
// Define a Semaphore object function Semaphore() {  this.value = 0;  this.q = []; // Initialize an array to act as a queue } // Implement the P operation Semaphore.prototype.P = function(p) {  this.value = this.value - 1;  if (this.value < 0) {  // Add process to queue  this.q.push(p);  // Assuming block() and wakeup() functions are defined elsewhere  block();  } }; // Implement the V operation Semaphore.prototype.V = function() {  this.value = this.value + 1;  if (this.value <= 0) {  // Remove process p from queue  var p = this.q.shift();  // Assuming wakeup() function is defined elsewhere  wakeup(p);  } }; // This code is contributed by Susobhan Akhuli>

I denne implementering, når processen venter, føjes den til en ventende kø af processer forbundet med den semafor. Dette gøres gennem systemkaldet blok() på den proces. Når en proces er afsluttet, kalder den signalfunktionen, og en proces i køen genoptages. Den bruger wakeup() systemkaldet.

Fordele ved semaforer:

  • En enkel og effektiv mekanisme til processynkronisering
  • Understøtter koordinering mellem flere processer
  • Giver en fleksibel og robust måde at administrere delte ressourcer på.
  • Det kan bruges til at implementere kritiske sektioner i et program.
  • Det kan bruges til at undgå løbsforhold.

Ulemper ved semaforer:

  • Det kan føre til ydeevneforringelse på grund af overhead forbundet med vente- og signaloperationer.
  • Kan resultere i dødvande, hvis det bruges forkert.
  • Det blev foreslået af Dijkstra i 1965, hvilket er en meget vigtig teknik til at styre samtidige processer ved at bruge en simpel heltalsværdi, som er kendt som en semafor. En semafor er simpelthen en heltalsvariabel, der deles mellem tråde. Denne variabel bruges til at løse det kritiske sektionsproblem og til at opnå processynkronisering i multiprocessing-miljøet.
  • Det kan forårsage ydeevneproblemer i et program, hvis det ikke bruges korrekt.
  • Det kan være svært at fejlfinde og vedligeholde.
  • Det kan være tilbøjeligt til raceforhold og andre synkroniseringsproblemer, hvis det ikke bruges korrekt.
  • Det kan være sårbart over for visse typer angreb, såsom lammelsesangreb.