Transcript Synchronization Presentation (10-09-06)

Synchronization
September 15, 2006
These people do not actually
work at RightNow.
© 2006 RightNow Technologies, Inc.
Outline
•
•
•
•
Historical solutions
Synchronization Primitives
Brief word on concurrency
Semaphores in depth
– semid_ds
– sem
– Working with semaphores
• References
Peterson's Algorithm
boolean lockA = lockB = false;
int turn = A; // or B
//Thread A:
//Thread B:
lockA = true;
turn = B;
while( lockB && turn != A )
{
}
lockB = true;
turn = A;
while( lockA && turn != B )
{
}
lockA = false;
lockB = false;
Dekker's Algorithm
boolean lockA = lockB = false;
int turn = A; // or B
//Thread A:
//Thread B:
lockA = true;
while(lockB)
{
if (turn != A)
{
lockA = false;
while(turn != A){}
lockA = true;
}
}
lockA = false;
turn = B;
lockB = true;
while(lockA)
{
if (turn != B)
{
lockB = false;
while(turn != B){}
lockB = true;
}
}
lockB = false;
turn = A;
Synchronization Primitives
•
•
•
•
•
•
•
•
•
Per-CPU variables
Atomic operation
Memory barrier
Spin lock
Seqlocks
Read-copy-update
Semaphore
Local interrupt disabling
Local softirq disabling
Synchronization Primitives – cont.
• Per-CPU Variables
– Array of data structures that can be accessed by only 1 CPU
– Only useful when data can be split across CPUs
– Fails if kernel preemption is enabled (race conditions)
• Atomic operation
– Read-modify-write
o atomic_read(v)
o atomic_set(v, i) – (test & set)
o atomic_add(i, v)
– Another set operates on bit masks
Synchronization Primitives – cont.
• Memory barrier
– Avoids code optimization problems by creating a barrier that
ensures that all code before the barrier gets executed
before code after the barrier
• Spin locks
– Busy wait while blocked
– Useful for multi-processor systems when the critical code
will execute very fast
o 1 = unlocked, 0 = locked
– Read/Write Spin Locks
Synchronization Primitives – cont.
• Seqlocks
– Read/Write spin locks that give high priority to writers
• Read-Copy Update
– Allows many readers and writers
– No locks or counters
– Writer just copies the old data, updates it and changes the
pointer
– Old data cannot be freed until all readers are finished
Synchronization Primitives – cont.
• Semaphores
– Kernel and System V IPC (User)
– count
o If count > 0 the resource is free
o count = 0 means the resource is 100% utilized but the wait
queue is empty
o If count < 0 the resource is 100% utilized and there are
processes in the wait queue
– wait – pointer to the wait queue
– sleepers – flag that is set if there are processes that are
waiting blocked
– More to come!
Synchronization Primitives – cont.
• Local Interrupt Disabling
– Creates a critical section in the kernel so that even
hardware interrupts won’t break the execution of a set of
statements
– CPU specific
• Local softirq disabling
– Disable deferrable functions w/o disabling interrupts
– Increment the softirq counter to disable; decrement the
softirq counter to enable
++ Concurrency
• Maximize the number of I/O devices operating
– Disable interrupts for very short periods
• Maximize the number of productive CPUs
– Avoid using spin locks if possible
More on Semaphores (semid_ds)
/* One semid data structure for each set
of semaphores in the system. */
struct semid_ds
{
struct ipc_perm sem_perm; /*
permissions .. see ipc.h */
time_t sem_otime; /* last semop
time */
time_t sem_ctime; /* last change
time */
struct sem *sem_base; /* ptr to
first semaphore in array */
struct wait_queue *eventn;
struct wait_queue *eventz;
struct sem_undo *undo; /* undo
requests on this array */
ushort sem_nsems; /* no. of
semaphores in array */
};
•sem_perm
–
This is an instance of the ipc_perm
structure, which is defined for us in
linux/ipc.h. This holds the permission
information for the semaphore set,
including the access permissions, and
information about the creator of the
set (uid, etc).
•sem_otime
–
Time of the last semop() operation
•sem_ctime
–
Time of the last change to this
structure (mode change, etc)
•sem_base
–
Pointer to the first semaphore in the
array (see next structure)
•sem_undo
–
Number of undo requests in this array
•sem_nsems
–
Number of semaphores in the
semaphore set (the array)
More on Semaphores (sem)
•/* One semaphore structure for each
semaphore in the system. */
struct sem
{
short sempid; /* pid of last operation */
ushort semval; /* current value */
ushort semncnt; /* num procs awaiting
increase in semval */
ushort semzcnt; /* num procs awaiting
semval = 0 */
};
•sem_pid
–
The PID (process ID) that performed
the last operation
•sem_semval
–
The current value of the semaphore
•sem_semncnt
–
Number of processes waiting for
resources to become available
•sem_semzcnt
–
Number of processes waiting for
100% resource utilization
Working with Semaphores
int semget ( key_t key, int nsems, int semflg );
int semop ( int semid, struct sembuf *sops, unsigned nsops);
struct sembuf
{
ushort sem_num; /* semaphore index in array */
short sem_op; /* semaphore operation */
short sem_flg; /* operation flags */
};
Working with Semaphores – cont.
int semctl ( int semid, int semnum, int cmd, union semun arg );
union semun
{
int val; /* value for SETVAL */
struct semid_ds *buf; /* buffer for IPC_STAT & IPC_SET */
ushort *array; /* array for GETALL & SETALL */
struct seminfo *__buf; /* buffer for IPC_INFO */ void *__pad;
};
Semaphore Commands
•IPC_STAT
–
Retrieves the semid_ds structure for a
set, and stores it in the address of the
buf argument in the semun union.
•IPC_SET
–
Sets the value of the ipc_perm
member of the semid_ds structure for
a set. Takes the values from the buf
argument of the semun union.
•GETPID
–
•GETVAL
–
Removes the set from the kernel.
•GETALL
–
Used to obtain the values of all
semaphores in a set. The integer
values are stored in an array of
unsigned short integers pointed to by
the array member of the union.
•GETNCNT
–
Returns the number of processes
currently waiting for resources.
Returns the value of a single
semaphore within the set.
•GETZCNT
–
•IPC_RMID
–
Returns the PID of the process which
performed the last semop call.
Returns the number of processes
currently waiting for 100% resource
utilization.
•SETALL
–
Sets all semaphore values with a set
to the matching values contained in
the array member of the union.
•SETVAL
–
Sets the value of an individual
semaphore within the set to the val
member of the union.
References
• D. Bovet and M. Cesati. Understanding the Linux Kernel,
Third Edition.O'Reilly and Associates, Inc., 2002.
• The Linux Documentation Project:
http://www.tldp.org/LDP/lpg/node46.html
• R. Kline. Peterson's Algorithm, 2006.
http://www.cs.wcupa.edu/~rkline/OS/Peterson.html