Page 287 - DCAP403_Operating System

Operating System

Notes last pointers). The current process is put on the wait queue in the sem_queue data structure
(sleeper) and the scheduler called to choose another process to run.
If all of the semaphore operations would have succeeded and the current process does not need
to be suspended, Linux goes ahead and applies the operations to the appropriate members of
the semaphore array. Now Linux must check that any waiting, suspended, processes may now
apply their semaphore operations. It looks at each member of the operations pending queue
(sem_pending) in turn, testing to see if the semphore operations will succeed this time. If they
will then it removes the sem_queue data structure from the operations pending list and applies
the semaphore operations to the semaphore array. It wakes up the sleeping process making
it available to be restarted the next time the scheduler runs. Linux keeps looking through the
pending list from the start until there is a pass where no semaphore operations can be applied
and so no more processes can be woken.
There is a problem with semaphores, deadlocks. These occur when one process has altered the
semaphores value as it enters a critical region but then fails to leave the critical region because
it crashed or was killed. Linux protects against this by maintaining lists of adjustments to the
semaphore arrays. The idea is that when these adjustments are applied, the semaphores will be
put back to the state that they were in before the a process’s set of semaphore operations were
applied. These adjustments are kept in sem_undo data structures queued both on the semid_ds
data structure and on the task_struct data structure for the processes using these semaphore
arrays.

Each individual semaphore operation may request that an adjustment be maintained. Linux
will maintain at most one sem_undo data structure per process for each semaphore array. If
the requesting process does not have one, then one is created when it is needed. The new sem_
undo data structure is queued both onto this process’s task_struct data structure and onto the
semaphore array’s semid_ds data structure. As operations are applied to the semphores in the
semaphore array the negation of the operation value is added to this semphore’s entry in the
adjustment array of this process’s sem_undo data structure. So, if the operation value is 2, then -2
is added to the adjustment entry for this semaphore.
When processes are deleted, as they exit Linux works through their set of sem_undo data
structures applying the adjustments to the semaphore arrays. If a semaphore set is deleted, the
sem_undo data structures are left queued on the process’s task_struct but the semaphore array
identifier is made invalid. In this case the semaphore clean up code simply discards the sem_

undo data structure.
13.8.6 Shared Memory

Shared memory allows one or more processes to communicate via memory that appears in all of
their virtual address spaces. The pages of the virtual memory is referenced by page table entries
in each of the sharing processes’ page tables. It does not have to be at the same address in all of
the processes’ virtual memory. As with all System V IPC objects, access to shared memory areas
is controlled via keys and access rights checking. Once the memory is being shared, there are
no checks on how the processes are using it. They must rely on other mechanisms, for example
System V semaphores, to synchronize access to the memory.
Each newly created shared memory area is represented by a shmid_ds data structure. These are
kept in the shm_segs vector.
The shmid_ds data structure describes how big the area of shared memory is, how many processes
are using it and information about how that shared memory is mapped into their address spaces.
It is the creator of the shared memory that controls the access permissions to that memory and
whether its key is public or private. If it has enough access rights it may also lock the shared
memory into physical memory.

280 LOVELY PROFESSIONAL UNIVERSITY