2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
2024-07-04: Notes on operating system synchronization and mutual exclusion
Concurrent processes or programs lose their closure when they are executed. That is, if two programs use a shared resource in different regions, the results of each run may be different.
The reason is that we did not protect the shared resource x that both program a and program b have to access.
The relationship of mutual restraint is synchronization. In simple terms, synchronization means that there must be an order when the processes are executed.
The indirect mutual restriction relationship is called a mutually exclusive relationship, e.g. a printer
"Producer and Consumer Model"
counter+ +
首先把变量放到寄存器里面
register1 = counter;
接下来对寄存器进行一个自增
register1 = register1 + 1;
再把结果返回到counter里
counter = register1;
counter- -
首先把变量放到寄存器里面
register2 = counter;
接下来对寄存器进行一个自减
register2 = register2 - 1;
再把结果返回到counter里
counter = register2;
Solution: Treat counter as a critical resource and allow processes to access the variable counter exclusively (we will learn about synchronization mechanisms later)
Regardless of whether it is a hardware critical resource or a software critical resource, multiple processes must access it mutually exclusively.
These areas are essentially codes
When no process is in the critical section, it indicates that the critical section resources are idle. A process requesting to enter the critical section should be allowed to enter its own critical section immediately to effectively utilize resources.
When a process enters the critical section, it indicates that the critical resource is being accessed, so other processes trying to enter the critical section must wait to ensure mutual exclusive access to the critical resource.
For processes that require access to critical resources, it should be ensured that they can enter their own critical section within a limited time to avoid falling into a "waiting to die" state.
When a process cannot enter its critical section, it should release the processor (CPU) immediately to prevent the process from falling into a "busy waiting" state.
两个进程必须交替进入临界区，若一个进程不再进入临界区，则另一个进程也无法进入临界区，违背了“空闲让进”准则
The double-flag check method sets a Boolean array flag[2] to mark the willingness of each process to enter the critical section. flag[i]=true means that Pi wants to enter the critical section.
- The while loop is equivalent to the traffic light mechanism
- Setting the other party's flag is equivalent to changing the other party's traffic light
- However, since both processes check the flag first [check the traffic light first], both are false [both are green] at the beginning, it is possible that the two processes pass the traffic light at the same time and enter the critical section together.
The double-flag post-check method checks the other party's flag and then sets its own. These two operations cannot be completed in one go, so the two processes may enter the critical section at the same time; so the post-check method was invented, first setting its own flag, then checking the other party's flag, if the other party's flag is true, wait; otherwise enter the critical section
Peterson's algorithm combinesSingle-sign methodandDouble sign post-inspectionThe idea is to use flag[] to solve the mutual exclusion access problem, and then use turn to solve the starvation problem.
If both parties are competing to enter the critical section, the process can give the opportunity to enter the critical section to the other party.
Before each process enters the critical section, it sets its own flag and sets the turn flag to allow entry. After that, it simultaneously detects the flag and turn of the other party to ensure that when both parties request to enter the critical section at the same time, only one process is allowed to enter.
Did not give up the right to wait
It is difficult and very limited for software to solve the problem of mutually exclusive entry of each process into the critical section, so the computer provides some special hardware instructions to solve the problem.
The TS instruction can be considered as a function process (primitive) that is integral to the execution process.
To use TS to manage critical sections, set a lock for each critical resource.
Called the swap instruction, it is used to exchange the contents of two words
It is defined as an integer S used to represent the number of resources. There are only three operations on this integer semaphore: initialization (assigning initial value), wait (self-decrement), signal (self-increment)
Process synchronization mechanism without "busy waiting" phenomenon
- The wait operation is equivalent to the P operation.
- The signal operation is equivalent to the V operation.
- Just two different names, the functions are exactly the same
- wait(A) = P(A)
- signal(B) = V(A)
Set a mutual exclusion semaphore mutex=1, and then place the critical section for each process to access critical resources between wait(mutex) and signal(mutex)
Set a synchronization semaphore S=0, so that the statement that needs to be executed first is signal(S), and then wait(S) is executed.
I have devoted myself to the research of technology for more than 30 years. I am proficient in various languages such as Java, Linux, JavaScript, PHP, CSS, etc. I have made many contributions in the field of open source. I have established a developer documentation site to share some problems in technology development for everyone to read.
