The 10th operating system members’ meeting of the year has begun!
The purpose of the monthly meeting is to communicate with each other and solve the recent problems in the work, so as to improve the efficiency of the whole computer system. Because computer hardware is evolving rapidly, and operating systems are the middle layer that connects computer hardware to applications and will soon be obsolete if they stand still, everyone in the operating system attaches great importance to monthly meetings.
This time it was the process and thread brothers who raised the question.
Standing in front of the crowd, thread looked scared and prodded the process to let him speak first. The process quickly gathered his thoughts, straightened himself up and said, “This time the problem was found in a reservation system. I have drawn the simple logic of the system while you look at me and say.”
“The booking system is divided into a server and a client. When the user establishes a connection with the server, the server will create a new thread to serve the client. The booking logic goes like this:
This logic is fine on its own, but in practice it can be wrong because there are often multiple users trying to book a ticket at the same time. Something like this:
Before thread A determines the remaining tickets (let’s say 1) but fails to book, thread B gets the information that the remaining tickets are 1, so THREAD B also thinks that it can book, and finally two tickets are sold for one ticket. “
Memory cut to the chase: “I see this is several threads execute the flow conflict problem, originally should one thread after the booking operation, another thread can query the remaining tickets. There are bound to be other unexpected problems with flow crossing like this.”
The process admired and said: “Ah, the memory you said is too reasonable, I also encountered a similar situation, last time I and another process share a part of the memory space, the result in the use of the same data, he wrote I just into the data overwrite, so that I behind the calculation of all errors.”
At this point, Disk expressed his opinion: “The execution flow problem, which seems to be the process scheduler’s pot, has to kick someone off the CPU when they are executing a critical step! If only the scheduler had waited a little longer, wouldn’t this problem be solved?”
Hearing this, the process scheduler angrily stood up and said, “You, how can you make people clean out of nothing! I don’t decide when to switch processes, okay? I’m in charge of selecting the most cpu-worthy process from the ready queue. By the time I start scheduling, those processes have already been dropped by the operating system.”
The operating system adds: “The scheduler is right that the timing of scheduling is determined by interruptions. It looks like this happens when the process runs out of time, there is a clock break, and another process grabs the CPU resource.”
Disk listen to, embarrassed of say: “sorry, just was I too arbitrary. So you’re saying that when we get to this part of the code, we can solve the problem by masking the clock interrupt like this?”
The operating system shakes its head: “Interrupt-disabled” does prevent the process from switching while running this part of the code, but clock interrupts are a very important feature of mine. How can I just hand over control to a human? What if some programmer wants their code to completely hog the CPU, without giving me a clock interrupt to turn on? There’s no way I’m going to hand over such important access. I’m responsible for the system.”
“On top of that, you should also know that this is a multi-core era, and even if you disable clock interrupts on this CPU, other cores can still switch processes and access the data. Disk ah, you obviously save so many files, how to know or so little…”
Disk indignant way: “don’t look down upon me, I this to find a way to solve this problem!”
The CPU says, “Let me get this straight. Our goal now is not to have two processes execute this code at the same time — let’s call this code a critical section. In other words, we need to have processes that mutually exclude each other in the critical section. So let’s lock this critical section,”
“Lock? What does that mean?”
“Locking is a metaphor. In fact,” lock “is just a shared variable. We can make it have two values: OPEN and CLOSE. A process, such as A, checks to see if the lock is OPEN before it enters the critical section, and if so, changes the lock to CLOSE, so that other processes, when they enter the critical section, find that the lock is closed, and let them loop until A exits the critical section and opens the lock.”
Memory frowned and realized that it wasn’t that simple — if A found the lock open, but switched to process B before A closed the lock, B would also find the lock open, and B would also be able to enter the critical section!
At this point, the memory tells the CPU about the problem, but the CPU says, that’s not a problem for him.
The computer had a hardware-supported instruction, TSL (Test and set Lock), which guaranteed that the operations of reading and writing were “indivisible,” meaning that no other processor could access the memory word until the instruction ended.
“The TSL instruction reads the memory word lock into a register, and then writes a non-zero value to the corresponding memory address. Then we can use this instruction to improve the method of locking, like this:
We have the process call enter_region before entering the critical region, and if the lock is already closed (indicating that the lock is non-zero), we loop on enter_region until the lock is opened, and then enter the critical region. Leave_region is called to open the lock once the critical region is left. Wouldn’t that solve your problem? “
Memory nodded and said, “This is really a good way to solve the mutual exclusion problem of critical sections.”
However, the operating system is not happy with this solution: “This solution is busy waiting and wasting CPU resources. I think this TSL solution needs to be improved.”
There was silence — no one had a better idea, and the meeting seemed to freeze.
Who can think of a better solution?
Haha, I foreshadowed it in the article, and guess who found a better way?
If you think my writing is good, just give it a thumbs up!
Disclaimer: Original article, unauthorized reprint prohibited