Invented by LO; SHI-WU

In computer systems, when many things want to use the same resource at once, there needs to be a fair and smart way to make sure only one can use it at a time. This is called mutual exclusion. A new patent application brings a fresh approach to this problem for multi-core processors. In this article, we will break down the market need, look at the science and older solutions, and finally dive into what makes this new invention stand out.

Background and Market Context

Modern computers keep getting faster by adding more cores to their processors. Each core is like a worker in a team; together, they can do many things at once. Sometimes, all these workers want to use the same tool at the same time. If they fight over the tool or use it wrongly, the team slows down or even fails. That’s why there are rules—called locks—to make sure only one worker uses the tool at a time.

In computer talk, the “tool” is often a piece of memory, a data structure, or a device. The “critical section” is the part of the computer code that uses this shared thing. If more than one core or thread enters a critical section at once, the data might get messed up, causing errors or crashes. So, mutual exclusion mechanisms are used to protect the critical section. But as computers grow more powerful and run more threads, these locks can become the very thing that slows everything down.

Let’s imagine a modern server in a cloud data center. It runs hundreds of tasks, each asking for quick access to shared resources. When the old way of locking is used, some tasks wait too long for their turn, wasting power and time. Some lucky tasks might get the lock again and again, while others starve. This is unfair and inefficient. Companies that run data centers or build big software systems want better ways to manage all these requests. They want fairness, speed, and low energy use. This is where new mutual exclusion methods, like the one in the patent application, become very important.

The computer industry is always searching for ways to get the most out of their hardware. With the rise of artificial intelligence, cloud computing, and big databases, the need for better locking systems is only getting stronger. If a company can offer a way to let many threads and cores work together without waiting too long, it can save a lot of money, deliver faster services, and use less energy. This is why inventions in this area are so valuable.

Scientific Rationale and Prior Art

The idea of mutual exclusion is not new. Since the early days of computers, programmers have had to find ways to keep shared data safe from being changed by more than one process at a time. The earliest locks were simple, like a flag that says “I am busy.” If a thread saw the flag, it would wait until the flag was cleared. This approach, called a spinlock, works well when only a few threads are involved, but it does not scale as computers add more and more cores.

To make things better, more advanced locks were invented. The ticket lock gives each thread a ticket, like at a bakery. When your ticket number is called, you get to enter the critical section. This is fairer, but as more threads join, the process of waiting and checking the ticket slows things down. Many threads have to keep looking at the same number, which can clog up the communication lines inside the processor.

Other locks, like MCS locks, keep a list of threads waiting for the lock. When a thread leaves, it wakes up the next one in line. This reduces contention but can be complex to manage, especially when there are many cores, each with their own memory spaces (as in NUMA systems). NUMA (Non-Uniform Memory Access) means that the time it takes for a core to access memory depends on where the memory is located. Some locks, like C-BO-MCS, try to take the memory layout into account, but still have trouble when many threads compete at once.

A big problem with these older locks is something called “spinning.” When a thread spins, it keeps checking if the lock is free, using up valuable processor time and power without actually doing useful work. This is especially bad when the number of threads is larger than the number of cores, a situation called oversubscription. In oversubscription, threads often end up wasting energy and causing delays.

Fairness is another concern. Some locks let certain threads get the lock more often, while others wait much longer. This is called the “convoy” problem, where a slow thread can block everyone else. As the number of threads grows, the risk of unfairness and waste grows too. In high-contention environments, like databases or parallel applications, these issues can lead to big slowdowns.

Recently, the industry has seen new lock algorithms that try to balance fairness and speed. For example, ShflLock and C-BO-MCS use grouping and shuffling to move threads around, but can still run into trouble when the queue gets long or when many threads are waiting. Each of these solutions brings improvements but still faces trade-offs between fairness, speed, and resource use.

The patent application recognizes these limits. It sees that simple locks waste resources, advanced locks get too complex, and all of them can still leave some threads waiting too long. So, it proposes a new way—one that keeps things simple, fair, and efficient, even as the number of threads and cores grows.

Invention Description and Key Innovations

The new method starts by breaking down the problem into two levels: one for the whole processor (the cores) and one for the smaller units (the threads on each core). The system uses two modules: a multicore-lock-unlock module and a multithread-lock-unlock module. Only one core at any time can enter the critical section, and on that core, only one thread can do so. This two-layer control stops both inter-core and intra-core fights over the shared resource.

Let’s look at how this works in practice:

Before any thread tries to use the shared resource, the system sets up special counters and flags for each core. These counters show how many threads on that core want to enter the critical section. The flags show if the core is currently allowed to access the critical section. This setup uses “atomic operations,” which means changes happen all at once, so there’s no chance for two threads to mess up the numbers at the same time.

When a thread wants in, it increases its core’s waiting counter. If it’s the only one waiting, it locks the critical section for its core right away. If not, it gets a “ticket” for its turn. The tickets and grants are stored in arrays, one for each core, so the system knows who is next.

The thread then checks if it’s its turn by comparing its ticket to the current grant number. If it is, the thread goes in; if not, it waits, either by spinning or yielding its place so other threads can run. This waiting is smart: instead of wasting power spinning all the time, threads can go to sleep and wake up only when it’s their turn. This prevents the system from getting clogged up with useless work.

When a thread leaves the critical section, it decreases its core’s waiting count. If there are more threads waiting, the system finds the next core in order that has waiting threads and wakes up the right thread there. This routing is handled by special order arrays, which can be customized for different hardware setups.

There are two main embodiments in this invention: RON-Ticket and RON-Plock.

RON-Ticket uses a ticket and grant system, as described above. Each core keeps track of its own ticket and grant numbers, and the system as a whole moves through the threads in a fair and predictable way. This means no thread can be skipped forever, and everyone will get their turn.

RON-Plock focuses on spinning, but does it in a smart way. Each core has a lock variable and a count of waiters. Threads try to take the lock; if they fail, they check a shared “InUse” flag. This helps prevent more than one thread from entering at the same time and reduces wasted effort. When a thread unlocks, it checks all the cores to see who is waiting next, then passes the lock along in a round-robin fashion.

Both systems are built on atomic operations. This keeps everything safe and avoids the classic “race conditions” that plague multi-threaded code. By using arrays for each core, the system avoids too much traffic over shared variables and keeps performance high even as the number of cores and threads grows.

The invention has been tested on modern processors with many cores and under real workloads, such as Google’s LevelDB. The results show that RON-Ticket and RON-Plock perform better than older locks, especially when there are more threads than cores or when there is heavy contention. They keep waiting times short and make sure no single thread hogs the lock.

This new approach is flexible. Because the control structures—like the WaitArray and ticket counters—are easy to set up and reuse, the invention can handle systems with thousands of locks or changing numbers of threads. It also fits well with both high-contention (many threads fighting for the same lock) and low-contention (only a few threads at a time) situations.

By balancing fairness, speed, and resource use, this invention opens the door for bigger, faster, and more reliable computer systems. It offers a building block for everything from databases to cloud servers to AI engines. And because it is simple to use and extend, it can be adopted widely with little cost or risk.

Conclusion

Mutual exclusion in multi-core processors is a tough challenge that grows as our computers get smarter and more powerful. The new method described here solves many of the old problems by giving each core and thread a fair shot, keeping waiting times low, and using resources wisely. With simple but strong structures and clever use of atomic operations, the invention brings real improvements to both speed and fairness. As computers continue to evolve, solutions like this will be key to unlocking their full potential, making sure that every task gets its turn and every user gets the best possible service.

Click here https://ppubs.uspto.gov/pubwebapp/ and search 20250362976.