In the kernel, when multiple processes access and operate shared resources at the same time, it is possible for each process to overwrite the shared data, which is a type of hidden danger that causes system instability. In the case of multi-core, the competition of multi-processors and multi-processes will also become more complicated. This part introduces two sets of experiments, namely spinlock and semaphore mechanism.

Lab2-1 Spinlock

1. Principle

Spinlock (spinlock) means that when a thread acquires a lock, if the lock has been acquired by other threads, then the thread will wait in a loop, and then continuously judge whether the lock can be successfully acquired, and will not exit until the lock is acquired cycle. The key to locking the critical section is the use of the primitive cmpxchg. The function of cmpxchg is to test and assign values, which we use to complete the lock test and lock. Finally, based on the instruction, it is encapsulated, using embedded assembly, and writing functions such as locking to realize our basic operations on locks.

Why both acquire() and release() use xchg instruction?

Accessing and modifying the variable locked in the ordinary way has a race condition. There may be two CPUs reading the value of locked to 0 at the same time, thinking that both can obtain the data structure occupied by the lock, and then set locked to 1 to occupy the lock. In fact, two CPUs acquire the lock at the same time, which violates the mutual exclusion of accessing the data structure. The root cause of this phenomenon is that reading and modifying variables is not an atomic operation. The process is continuously uninterruptible, and only one CPU is allowed to access it, so that the atomic operation of accessing locked can be realized.

xv6 is implemented using the xchg instruction under the x86 architecture. xchg atomically exchanges the value of a register and a memory word.

The function acquire uses xchg repeatedly in the loop, and reads lk->locked each time. The value of lk->locked is 0, indicating that the lock is available, and then sets lk->locked to 1. If the lock is already held, that is, lk->locked has been set to 1, xchg will return 1 and continue the loop. If xchg returns 0, it means that acquire has successfully acquired the lock, that is, locked has changed from 0 to 1, and the loop can stop at this time.

Once the lock is acquired, acquire will record the CPU and stack information that acquired the lock for debugging. When a process acquires a lock but does not release it, this information can help us find the problem. This information is also protected by a lock and can only be modified while holding the lock.

Through this implementation, when each CPU or process accesses a data structure that may be in competition, it must obtain the lock of this data in advance. If the lock cannot be obtained temporarily, it will continuously test the spin and release the lock after processing the data. occupancy so that another CPU or process can reoccupy the lock.

2. To do

Add the files spinlock.h and spinlock.c.

First, an explanation of the core function cmpxchg

1
2
3
4
5
6
7
8
9

uint cmpxchg(uint oldval, uint newval, volatile uint* lock_addr)
{
    uint result;
    __asm__ __volatile__("lock; cmpxchg %0, %2"
                    : "+m" (*lock_addr), "=a" (result)
                    : "r"(newval), "1"(oldval)
                    :"cc");
    return result;
}

Among them, __asm__ is used to declare an embedded assembly expression, and __volatile__ declares not to optimize assembly instructions. Its parameters have four parts: assembly instruction sequence, output part, input part, and operation constraints; each part is separated by a colon ‘:’ open.

1. Multiple statements in the instruction sequence are separated by semicolons or newlines.
2. Number all the variables that appear in order, that is, lock_addr is No. 0, result is No. 1, newval is No. 2, and oldval is No. 3.
3. %0 and %2 in the instruction sequence are placeholders, which represent the variables corresponding to the numbers, namely lock_addr and newval.
4. The input part is similar to the output part, the preceding string is a qualifier, and the parameters in the following brackets specify variables:
   • m stands for memory variable.
   • a means to use eax.
   • r means to use one of the general-purpose registers eax, ebx, ecx, edx, esi, edi.
   • 1 means use the same register as the number variable, the register used by the number 1 variable result is eax, then oldval also uses eax.
5. ‘+’ and ‘=’ limit reading and writing, ‘=’ is write-only (output operand), ‘+’ is read-write (input and output operand).
6. “cc”: When an inline assembly instruction contains conditional flags that affect the eflags register, then you need to use “cc” to declare this.

In summary, the inline assembly function is changed to an assembly statement (assuming newval uses ebx).

1
2
3
4
5
6
7
8
9
10
11
12

__asm__ __volatile__("lock; cmpxchg %0, %2" :
                       "+m" (*lock_addr), "=a" (result) :
                       "r"(newval), "1"(oldval) :
                       "cc");
#输入部分：
mov ebx,newval
mov eax,oldval
#指令序列
lock
cmpxchg lock_addr,ebx
#输出部分
mov result,eax

The cmpxchg instruction compares the destination operand with eax, and then performs an assignment operation based on the comparison result. There are two results, equal or unequal:

If they are equal (oldval==lock_addr), give the source operand to the destination operand: lock_addr newval.

By the output section: result oldval.

If not equal (oldval != lock_addr), give the destination operand to eax, and then give result from the output part, that is, result lock_addr.

Written in c language code, the function cmpxchg is roughly:

1
2
3
4
5
6
7
8
9
10

uint cmpxchg(uint oldval, uint newval, volatile uint* lock_addr)
{
    if(*lock_addr == oldval) {
        *lock_addr = newval;
        return oldval;
    }
    else {
        return *lock_addr
    }
}

In the application lock function

1
2
3
4
5

void acquire(struct spinlock *lock)
{
  while(cmpxchg(0, 1, &lock->locked) == 1)
    ;
}

That is, when oldval=0, newval=1, 0 means it is available, and 1 means it has been occupied by other processes.

The function cmpxchg function is:

• If locked==0, set it to 1 and return 0—indicating that the process application is successful.
• If locked!=0, it will return locked, and since the value of locked is 1 at this time, it will return 1—indicating that the process application has failed, and the resource is being used by other processes.