OSC:Synchronization

From SOFTICE

Jump to: navigation, search

Contents


Synchronization

Pedagogical Objectives
  • Introduce Kernel APIs: sema_init(), init_MUTEX(), down_interruptible(), up(),
  • Big picture:
    • Implement classic IPC problems in kernel-space to explore the kernel synchronisation API
Developed by: Prerequisites: ProcFS
[edit]

Synopsis

When multiple processes can access the same data simultaneously, the only way to prevent data corruption is to use a locking mechanism. The Linux kernel implements two significant locking methods: spin locks and semaphores. There are also other methods for preventing simultaneous access, such as per-CPU data and disabling kernel preemption.

[edit]

[Briefing] Preventing Concurrent Access

Locks protect data by surrounding regions of code that manipulate it ('critical regions'). Since only one process can (typically) hold each lock, only one process is able to manipulate the protected data at a time. Spin locks and semaphores do this in very similar ways: before entering the critical region, the process attempts to acquire the lock. If the lock is already held, the process waits until the lock is released.

The two primary kinds of lock differ in what they do while waiting.

  • Spin locks repeatedly check the lock value in a tight loop, hence the 'spin'. A thread holding a spin lock is not allowed to sleep and cannot be preempted. This makes them effective for interrupt handlers, which are not allowed to sleep anyway.
  • Semaphores put the process to sleep, allowing the processor to work on other tasks until the lock is released. They are useful for locks that are held a long time, as the overhead of putting a process to sleep and waking it up can outweigh the cost of waiting for a short time.

Sometimes, a lock is not strictly necessary to protect data. For example, on uniprocessor machines, or when accessing per-CPU data, the only way multiple processes can access the same variable at the same time is if one of those processes gets preempted within the critical region. This can be prevented by disabling preemption during the critical region. (Spin locks automatically disable preemption.)

Warning: Linux kernel locks are not recursive; attempting to acquire a spin lock or mutex you already hold will result in a deadlock. Use caution when using locks.

[edit]

The Bad Old Days: The Big Kernel Lock and Coarse-Grained Locking

Prior to kernel version 2.0, there was very little need for locking; the Linux kernel did not support more than one processor. In 2.0, when SMP (Symmetric Multi-Processing) support was added, the entire kernel was turned into a giant critical section through a mechanism known as the Big Kernel Lock.

The Big Kernel Lock (or BKL) is a recursive spinlock; it is not an error to acquire it more than once, though it must be released once for every time it is acquired.

In kernel versions 2.2 through 2.6, the BKL has gradually been superseded by a series of more fine-grained locks. It has not yet disappeared entirely, though it protects a much smaller portion of the kernel... of course, it goes without saying that it should not be used in new code. References to lock_kernel, et cetera, are references to the BKL.

[edit]

Alternatives To Locking

Sometimes it is possible to avoid the need for locks altogether.

There are some algorithms that can prevent the need for a lock. [LDD3], chapter 5 (pages 123-124) detail a lock-free producer/consumer system, though it is limited to a single producer and a single consumer.

In addition, if the data being protected is a single integer, it is possible to use atomic operations on it in lieu of an explicit lock. The kernel provides the datatype atomic_t for this purpose; it is an integer value of at least 24 bits (due to some weirdness on the SPARC architecture) that is guaranteed to be updated and read atomically. To access a variable of type atomic_t, use the atomic_set, atomic_add, atomic_inc, atomic_dec, and atomic_read functions. (There are other atomic access instructions; see pages 124-126 of [LDD3] for details.)

[edit]

[Solved] Locking Examples

We include <linux/spinlock.h> and <asm/semaphore.h> to enable support for spin locks and semaphores, respectively. 

/*
 * Written by Benjamin Geiger, SOFTICE Project
 * (c) 2006 SOFTICE Project
 */

#include <linux/kernel.h>	/* Basic kernel routines. */
#include <linux/module.h>	/* Module support routines. */
#include <linux/unistd.h>	/* Various support routines. */

#include <linux/spinlock.h>
#include <asm/semaphore.h>

/* Declare that the code is under the GPL. */
MODULE_LICENSE("GPL");

Declare our locks and miscellaneous variables. 

/* init_module: Put the module into the kernel. */
int init_module()
{
	static spinlock_t spin;
	static struct semaphore sem;

	unsigned long flags;
	int data;
	
	printk("Demonstrating locks...");

Initialize and use a spin lock.

There are three variants of spin lock and unlock functions:

  • spin_lock/spin_unlock
  • spin_lock_irq/spin_unlock_irq
  • spin_lock_irqsave/spin_unlock_irqrestore

The bare spin_lock and spin_unlock calls do not disable interrupts. spin_lock_irq and spin_unlock_irq disable and re-enable interrupts unconditionally, and spin_lock_irqsave and spin_unlock_irqrestore disable and re-enable interrupts if and only if they were enabled at the time spin_lock_irqsave was called. If you know for a fact that interrupts will always be enabled or disabled when the process reaches the locking function, use one of the first two pairs. Otherwise, use the third; it has a bit more overhead but is safer.

spin_lock_irqsave and spin_unlock_irqrestore are implemented partially as macros, so the second parameter can be modified even though it appears to be passed by value. (It is also an error to pass a pointer.) 

	/* Spinlocks are intended to be held for a short time. */
	spin_lock_init(&spin);
	
	spin_lock_irqsave(&spin, flags);
	data = 1;
	spin_unlock_irqrestore(&spin, flags);

Initialize and use a mutex.

A mutex (short for mutual exclusion) is merely a semaphore with a count of one. Like a spin lock, it only allows one process into the critical region at a time. Unlike a spin lock, it allows the process to sleep when the lock is already held and wake up when the lock is released. 

	/* Semaphores have more overhead but can sleep. */
	init_MUTEX(&sem);

	down_interruptible(&sem);
	data = 2;
	up(&sem);

Initialize and use a counting semaphore.

Semaphores with a count greater than one are called "counting semaphores" to distinguish them from mutexes. They do not implement mutual exclusion; multiple processes (specifically, a number of processes equal to the count) can be in the critical region simultaneously. However, they are useful to limit resource usage, keeping more than a certain number of processes out of an intensive area. 

	/* In addition, semaphores can allow more than one person to
	   hold them at the same time. */

	sema_init(&sem, 3);
	
	down_interruptible(&sem);
	down_interruptible(&sem);
	down_interruptible(&sem);

	data = 3;

	up(&sem);
	up(&sem);
	up(&sem);

The rest is boilerplate. 

	printk(" done.\n");

	return 0;
}

/* cleanup_module: Remove the module from the kernel. */
void cleanup_module()
{
}
[edit]

[Exercises]

[edit]

Exercise 1: Simplified Producer/Consumer

We are going to implement a LKM which is going to regulate access to a shared integer variable following the producer-consumer algorithm discussed in the lectures. The producer and consumer will be two user-land programs which will work as follows:

  • The producer will use the open system call, specifying the filename "softice:prod" to notify the LKM that it wants to produce some data. Producing some data means, in his exercises, that we want to increase the value of the shared integer (a variable stored inside the LKM) by 1. We'll assume that we initialize it to 0 in the LKM initialization function. To facilitate debugging, the LKM will simply use printk to display the value that was just produced by the user-land program ("[prod cons LKM] producer (pid=1234) just produced value 1"). The producer will therefore not send any data per se to the LKM but simply trigger the LKM to increase the stored value. You will write your producer so that it increases this value 10 times and sleep for random number of seconds (1-3) between each call to open.
  • The consumer will use the open system call, specifying the filename "softice:cons" to notify the LKM that it wants to read data. As for the producer, the LKM will be responsible for displaying the result of the operation: "[prod cons LKM] consumer (pid=5678) just consumed value 1"). The consumer therefore doesn't read the value stored by the LKM but simply instructs the latter to display its contents (this makes the module way easier). You will write your consumer so that it "reads" the value 10 times and sleep for a random number of seconds (1-3) between each call to open.

The LKM code will be responsible for ensuring mutual exclusive access to the shared integer as well as synchronization. To do so, we will simply implement a 3 semaphores solution to the producer-consumer problem (cf. lectures) using the kernel's semaphores API described in the previous section. Refer to the "[Solved]" section of laboratory #2 "Stealth Processes & PCBs" through this link to see an example of a LKM which intercepts the open system call and uses it to receive "commands" from user-space programs.



[edit]

Exercise 2: Simplified Readers/Writers Problem

We are going, as we did in the above exercise, to work on a simplified version of another well-known IPC problem; the readers/writers problem. The main objective is to make you practice the kernel API for reader/writer locks. The kernel already provides you with a construct meant to help you implement solutions to such problem since their occurrence is common in the kernel code itself.


You can start this code exactly as the precedent. However, make sure you are using a single reader/writer spinlock or semaphore instead of the 3 semaphores. You will find details on these APIs in [LJ-love]. Hint: start by a problem with only a single writer and a single reader then generalize.

[edit]

[Projects]

[edit]

Project 1: Producer/Consumer with strings bounded buffer

Write a LKM which creates a file /proc/prodcons that works as a sequence of buffers; each call to write() should add one string to the buffer, and each call to read() should remove that string from the buffer. If the buffer is (full/empty), (write/read) should wait until (an empty slot/some data) is available. You will limit the size of the strings that can be written to the LKM buffer as well as their number (bounded buffer).

In order to test your LKM, you will also write two user-land programs which will respectively act as a:

  • producer:
    • calling write to add a string to /proc/prodcons
    • displaying on the screen "[producer] writing string: xxxx"
    • sleeping a random number of seconds
    • repeating this scenario 3 times with 3 different strings
  • consumer:
    • sleeping a random number of seconds (1-3)
    • calling read to get a string from /proc/prodcons
    • displaying it on the screen as "[consumer] reading string: xxxx"
    • reading another one until we read 3 of them


[edit]

Project 2: Readers/Writers

Use a ProcFS file to simulate a reader/writer scenario, controlling access to a memory buffer using a read/write semaphore (not a spin lock):

  • Calls to the write function must acquire the write lock on the buffer.
  • Calls to the read function must acquire the read lock on the buffer.
  • The read and write functions should sleep while the lock is held: the reader should sleep for 3-5 seconds and the writer should sleep for 10 or more.

Using this module, determine:

  • What happens if one reader tries to acquire the lock while another reader is already holding it?
  • What happens if a reader tries to acquire the lock while another writer is holding it?
  • What happens if a writer tries to acquire the lock while a reader is holding it?
  • What happens if one writer tries to acquire the lock while another writer is holding it?
  • What happens if a reader is holding the lock, a writer is waiting on the lock, and another reader also attempts to acquire the lock?
  • What happens if a writer is holding the lock, a reader is waiting on the lock, and another writer also attempts to acquire the lock?
[edit]

References

[LDD3] Linux Device Drivers 3E (safary reference)

[LKD2] Linux Kernel Development, Second Edition

  • Robert Love
  • Novell Press
  • Chapter(s): 9 (Kernel Synchronization Methods)


[edit]

References (Textbooks)

[NUTT] Operating Systems, 3/e


[STALL] Operating Systems, Internals and Design Principles


[SILB] Operating System Concepts with Java

  • http://os-book.com/
  • Abraham Silberschatz, Peter Baer Galvin, Greg Gagne
  • Wiley, ISBN: 978-0-471-76907-1
  • Chapter(s): #6 (Processes Synchronization)


[DEIT] Operating Systems

  • Deitel, ISBN: 0131828274
  • Chapter(s): #5 (Asynchronous Concurrent Execution)
Retrieved from "http://softice.lakeland.usf.edu/wiki/index.php/OSC:Synchronization"
Personal tools