A little thought on synchronization – in the next article, we learned that gliBC’s pthread_cond_timedwait underlayer is implemented using the Linux futex mechanism.

More articles can be found on my blog: github.com/farmerjohng…

The ideal synchronization mechanism would be to use atomic instructions to solve problems in user mode when there are no lock conflicts, and to use system calls provided by the kernel to sleep and wake up when there is a pending wait. In other words, in the event of a user-mode spin failure, can the process be suspended and woken up by the thread holding the lock when it releases the lock? If you haven’t thought about it more deeply, you probably think something like this will do (pseudocode) :

Void lock(int lockval) {// Trylock is a user-level spin lockwhile(! trylock(lockval)) {wait(a); }} Boolean trylock(int lockval){int I =0; //localval=1 indicates that the lock is successfulwhile(! CompareAndSet (lockval, 0, 1)) {if(++i>10){
			return false; }}return true; } void unlock(int lockval) {compareAndSet(lockval,1,0); notify(); }Copy the code

The problem with this code is that there is a window between the trylock and wait calls: if a thread trylock fails and the thread holding the lock releases the lock, the current thread will still call WAIT, but no one will wake it up again.

In order to solve the above problems, the Linux kernel introduced the futex mechanism. Futex mainly consists of two methods: futex_wait and futex_wake, which are defined as follows

* / *uaddr==val * / *uaddr==valwaitint futex_wait(int *uaddr, int val); Int futex_wake(int *uaddr, int n); futex_wake(int *uaddr, int n);Copy the code

Futex checks whether addr is equal to val before actually suspending the process, and returns immediately if it is not, resuming trylock in user mode. Otherwise, the current thread is inserted into a queue and suspended.

Some thoughts on synchronization – the background and basic principles of FUtex are introduced in the previous article. Those who are not familiar with Futex can have a look first.

This paper will deeply analyze the implementation of FUtex, so that readers can have an intuitive understanding of the lowest implementation of lock, combined with the previous two articles (a little thinking about synchronization – on and a little thinking about synchronization – below) to have a comprehensive understanding of the synchronization mechanism of operating system.

The term process below includes regular processes and threads.

futex_wait

Before looking at the source code analysis below, consider a question: how do I ensure that the value of val has not been modified by another process when I suspend the process?

The code is in kernel/futex.c

static int futex_wait(u32 __user *uaddr, int fshared, u32 val, ktime_t *abs_time, u32 bitset, int clockrt) { struct hrtimer_sleeper timeout, *to = NULL; struct restart_block *restart; struct futex_hash_bucket *hb; struct futex_q q; int ret; . // Set the hrtimer for a scheduled task: if the process is not woken up after a certain period of time (abs_time), the process is woken upwaitThe process ofif(abs_time) { ... hrtimer_init_sleeper(to, current); . } retry: // Init ret = futex_wait_setup(uaddr, val, fshared, &q, &hb); // If val has changed, it returns directlyif(ret) goto out; // Change the current process state to TASK_INTERRUPTIBLE, insert it into the FUtex wait queue, and reschedule. futex_wait_queue_me(hb, &q, to); /* If we were woken (and unqueued), we succeeded, whatever. */ ret = 0; // If unqueue_me succeeds, a timeout is triggered (this fails because futex_wake removes the process from the wait queue)if(! unqueue_me(&q)) goto out_put_key; ret = -ETIMEDOUT;if(to && ! to->task) goto out_put_key; /* * We expect signal_pending(current), but we might be the * victim of a spurious wakeup as well. */if(! signal_pending(current)) { put_futex_key(fshared, &q.key); goto retry; } ret = -ERESTARTSYS;if(! abs_time) goto out_put_key; . out_put_key: put_futex_key(fshared, &q.key); out:if(to) {// Cancel the scheduled task hrtimer_cancel(&to->timer); destroy_hrtimer_on_stack(&to->timer); }return ret;
}
Copy the code

The current process is inserted into a wait queue before blocking. Note that the wait queue is a globally unique structure similar to Java HashMap.

struct futex_hash_bucket { spinlock_t lock; Struct plist_head chain; }; static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];Copy the code

Focus on futex_WAIT_setup and the two functions futex_WAIT_queue_me

static int futex_wait_setup(u32 __user *uaddr, u32 val, int fshared, struct futex_q *q, struct futex_hash_bucket **hb) { u32 uval; int ret; retry: q->key = FUTEX_KEY_INIT; // initialize futex_q ret = get_futex_key(uaddr, fshared, &q->key, VERIFY_READ);if(unlikely(ret ! = 0))returnret; Retry_private: // Get the spin lock *hb = queue_lock(q); Ret = get_fuTEX_value_locked (&uval, uaddr); . // If the value pointed to by uaddr is not equal to val, it indicates that another process has changed the value pointed to by uaddr.if(uval ! Queue_unlock (q, *hb); ret = -EWOULDBLOCK; }...return ret;
}
Copy the code

The futex_WAIT_setup function does two main things, one is to get the spin lock and the other is to determine if *uaddr is the expected value.

static void futex_wait_queue_me(struct futex_hash_bucket *hb, struct futex_q *q, Struct hrtimer_sleeper *timeout) {// Set the process state to TASK_INTERRUPTIBLE, Only the set_CURRENT_STATE (TASK_INTERRUPTIBLE) process in the // TASK_RUNNING state is selected during CPU scheduling. // Insert the current process (q encapsulation) into the wait queue, and release the spin lock queue_me(q, hb); // Start a scheduled taskif (timeout) {
		hrtimer_start_expires(&timeout->timer, HRTIMER_MODE_ABS);
		if(! hrtimer_active(&timeout->timer)) timeout->task = NULL; } /* * If we have been removed from thehash list, then another task
	 * has tried to wake us, and we can skip the call to schedule().
	 */
	if(likely(! Plist_node_empty (& q - > list))) {/ / if there is no set expiration time | | set the expiration time and has not expiredif(! The timeout | | timeout - > task) / / system to process scheduling, at this time of the CPU to perform other processes, the process will block the schedule here (); __set_current_state(TASK_RUNNING); }Copy the code

Futex_wait_queue_me does several things:

  1. Inserts the current process into the wait queue
  2. Starting a Scheduled Task
  3. Rescheduling process

How to guarantee atomicity between condition and wait

Spin locks are added to the futex_WAIT_setup method; Set the state to TASK_INTERRUPTIBLE in fuTEX_WAIT_QUEUe_ME, and call Queue_me to insert the current thread into the wait queue before releasing the spin lock. This means that the process of checking the value of the UADDR is placed in the same critical section as the process of suspending. When the spin lock is released, it does not matter to change the value of the ADDR address, because the current process is already in the queue and can be woken up by WAKE without the problem mentioned at the beginning of this article.

Futex_wait summary

To summarize the fuTEX_wait process:

  1. Add the spin lock
  2. Checks if *uaddr is equal to val, and returns immediately if it is not
  3. Sets the process state toTASK_INTERRUPTIBLE
  4. Inserts the current process into the wait queue
  5. Release the spin lock
  6. Create a scheduled task: Wakes up a process that has not been woken up for a certain period of time
  7. Suspend the current process

futex_wake

futex_wake

static int futex_wake(u32 __user *uaddr, int fshared, int nr_wake, u32 bitset) { struct futex_hash_bucket *hb; struct futex_q *this, *next; struct plist_head *head; union futex_key key = FUTEX_KEY_INIT; int ret; . Ret = get_futex_key(uaddr, fshared, &key, VERIFY_READ);if(unlikely(ret ! = 0)) goto out; Hb = hash_futex(&key); // Add spin lock to hb (&hb->lock); head = &hb->chain; // Go through the hb list. Note that the nodes stored in the list are of type plist_node, while this is of type futex_q. Plist_for_each_entry_safe (this, next, head, list) {plist_for_each_entry_safe(this, next, head, list)if(match_futex (&this->key, &key)) { ... // wake up the corresponding process wake_futex(this);if (++ret >= nr_wake)
				break; }} // Release spin_unlock(&hb->lock); put_futex_key(fshared, &key); out:return ret;
}
Copy the code

The fuTEX_WAKE process is as follows:

  1. Find the uADDRfutex_hash_bucketHb in the code
  2. Spin lock hb
  3. Traverse fb’s linked list to find the node corresponding to uaddr
  4. callwake_futexEvoke the process of waiting
  5. Release the spin lock

Wake_futex sets the state of the specified process to TASK_RUNNING and adds the process to the system scheduling list. At the same time, the process is removed from the futex waiting queue. The specific code is not analyzed, and those who are interested can study by themselves.

End

Already in Java, Object. Wait and Thread. Sleep and so on the underlying Thread synchronization is done with futex, understand futex implementation can help you better understand and use these upper synchronization mechanism. In addition, due to the limited space and energy, there is no specific analysis related to process scheduling, but it does not prevent the understanding of the content of the article.