DISTRIBUTED OPERATING SYSTEM
#1

SUBMITTED BY:
Mr.Nandan Sujati Amandeep Kaur B Arun Sharma A Manjinder Singh A

[attachment=9482]
DISTRIBUTED OPERATING SYSTEM
Locking in the Multithreaded FreeBSD Kernel

1. Introduction
Prior to the SMPng project, SMP support in FreeBSD was limited to the i386 architecture and used one giant spin lock for the entire kernel . This kernel architecture is referred to as pre-SMPng. The goal of SMPng is to allow multiple threads to execute in the kernel concurrently on SMP system
2. Current Status
The SMPng project first began in June of 2000 with a presentation given to several FreeBSD developers by Chuck Paterson of BSDi explaining BSDi's SMP project to multithread their own kernel. This meeting set the basic design, and developers started working on code shortly after.
The first step was to implement the synchronization primitives. Once this was done, two mutexes were added. A spin mutex named sched_lock was used to protect the scheduler queues, sleep queues, and other scheduler data structures. A sleep mutex named Giant was added to protect everything else in the kernel. The second step was to move most interrupt handlers into interrupt threads. Interrupt threads are necessary so that an interrupt handler has a context in which to block on a lock without blocking an unrelated top half kernel thread. A few interrupt handlers such as those for clock interrupts and serial I/O devices still run in the context of the thread they interrupt and thus do not have a context in which to block. Once this was done, the old spl synchronization primitives were no longer needed and could be converted into nops. They are still left around for reference until code is converted to use locks, however.
Now that most of the infrastructure is in place, the current efforts are directed at adding locks to various data structures so that portions of code can be taken out from under Giant. There are still some infrastructure changes that need to be implemented as well. These include implementing a lock profiler that can determine which locks are heavily contested as well as where they are heavily contested. This will allow developers to determine when locking needs to be made more fine-grained.
3. Problems Presented by Concurrent Access to the Kernel
Multiple threads of execution within a BSD kernel have always presented a problem. Data structures are generally manipulated in groups of operations. If two concurrent threads attempt to modify the same shared data structure, then they can corrupt that data structure. Similarly, if a thread is interrupted and another thread accesses or manipulates a data structure that the first thread was accessing or manipulating, corruption can result. Traditional BSD did not need to address the first case, so it simply had to manage the second case using the following three methods:
 Threads that are currently executing kernel code are not preempted by other threads,
 Interrupts are masked in areas of the kernel where an interrupt may access or modify data currently being accessed or modified, and
 Longer term locks are acquired by synchronizing on a lock variable via sleep and wakeup.
With the advent of MP systems, however, these methods are not sufficient to cover both problematic cases. Not allowing threads in the kernel to be preempted does nothing to prevent two threads on different CPUs from accessing the same shared data structure concurrently. Interrupt masking only affects the current CPU, thus an interrupt on one CPU could corrupt data structures being used on another CPU. The third method is not completely broken since the locks are sufficient to protect the data they protected originally. However, race conditions on the locking and unlocking thread itself can lead to temporary hangs of threads.
The pre-SMPng kernel addressed this situation on SMP systems by only allowing one processor to execute in the kernel at a time. This preserved the UP model for the kernel at the expense of disallowing any concurrent access to the kernel.
4. Basic Tools
Fortunately, MP-capable CPUs provide two mechanisms to deal with these problems: atomic operations and memory barriers.
a. Atomic Operations
An atomic operation is any operation that a CPU can perform such that all results will be made visible to each CPU at the same time and whose operation is safe from interference by other CPUs. For example, reading or writing a word of memory is an atomic operation. Unfortunately, reading and writing are only of limited usefulness alone as atomic operations. The most useful atomic operations allow modifying a value by both reading the value, modifying it, and writing it as a single atomic change. The details of FreeBSD's atomic operation API can be found in the atomic manual page .
Atomic operations alone are not very useful. An atomic operation can only modify one variable. If one needs to read a variable and then make a decision based on the value of that variable, the value may change after the read, thus rendering the decision invalid. For this reason, atomic operations are best used as building blocks for higher level synchronization primitives or for noncritical statistics.
b. Memory Barriers
Many modern CPUs include the ability to reorder instruction streams to increase performance . On a UP machine, the CPU still operates correctly so long as dependencies are satisfied by either extra logic on the CPU or hints in the instruction stream. On a SMP machine, other CPUs may be operating under different dependencies, thus the data they see may be incorrect. The solution is to use memory barriers to control the order in which memory is accessed. This can be used to establish a common set of dependencies among all CPUs.
In FreeBSD, memory barriers are provided via the atomic operations API. The API is modeled on the memory barriers provided on the IA64 CPU. The API includes two types of barriers: acquire and release. An acquire barrier guarantees that the current atomic operation will complete before any following memory operations. This type of barrier is used when acquiring a lock to guarantee that the lock is acquired before any protected operations are performed. A release barrier guarantees that all preceding memory operations will be completed and the results visible before the current atomic operation completes. As a result, all protected operations will only occur while the lock is held. This allows a dependency to be established between a lock and the data it protects.
5. Synchronization Primitives
Several synchronization primitives have been introduced to aid in multithreading the kernel. These primitives are implemented by atomic operations and use appropriate memory barriers so that users of these primitives do not have to worry about doing it themselves. The primitives are very similar to those used in other operating systems including mutexes, condition variables, shared/exclusive locks, and semaphores.
a. Mutexes
The mutex primitive provides mutual exclusion for one or more data objects. Two versions of the mutex primitive are provided: spin mutexes and sleep mutexes.
Spin mutexes are a simple spin lock. If the lock is held by another thread when a thread tries to acquire it, the second thread will spin waiting for the lock to be released. Due to this spinning nature, a context switch cannot be performed while holding a spin mutex to avoid deadlocking in the case of a thread owning a spin lock not being executed on a CPU and all other CPUs spinning on that lock. An exception to this is the scheduler lock, which must be held during a context switch. As a special case, the ownership of the scheduler lock is passed from the thread being switched out to the thread being switched in to satisfy this requirement while still protecting the scheduler data structures. Since the bottom half code that schedules threaded interrupts and runs non-threaded interrupt handlers also uses spin mutexes, spin mutexes must disable interrupts while they are held to prevent bottom half code from deadlocking against the top half code it is interrupting on the current CPU. Disabling interrupts while holding a spin lock has the unfortunate side effect of increasing interrupt latency.
To work around this, a second mutex primitive is provided that performs a context switch when a thread blocks on a mutex. This second type of mutex is dubbed a sleep mutex. Since a thread that contests on a sleep mutex blocks instead of spinning, it is not susceptible to the first type of deadlock with spin locks. Sleep mutexes cannot be used in bottom half code, so they do not need to disable interrupts while they are held to avoid the second type of deadlock with spin locks.
As with Solaris, when a thread blocks on a sleep mutex, it propagates its priority to the lock owner. Therefore, if a thread blocks on a sleep mutex and its priority is higher than the thread that currently owns the sleep mutex, the current owner will inherit the priority of the first thread. If the owner of the sleep mutex is blocked on another mutex, then the entire chain of threads will be traversed bumping the priority of any threads if needed until a runnable thread is found. This is to deal with the problem of priority inversion where a lower priority thread blocks a higher priority thread. By bumping the priority of the lower priority thread until it releases the lock the higher priority thread is blocked on, the kernel guarantees that the higher priority thread will get to run as soon as its priority allows.
These two types of mutexes are similar to the Solaris spin and adaptive mutexes. One difference from the Solaris API is that acquiring and releasing a spin mutex uses different functions than acquiring and releasing a sleep mutex. A difference with the Solaris implementation is that sleep mutexes are not adaptive.
b. Condition Variables
Condition variables provide a logical abstraction for blocking a thread while waiting for a condition. Condition variables do not contain the actual condition to test, instead, one locks the appropriate mutex, tests the condition, and then blocks on the condition variable if the condition is not true. To prevent lost wakeups, the mutex is passed in as an interlock when waiting on a condition.
FreeBSD's condition variables use an API quite similar to those provided in Solaris. The only differences being the lack of a cv_wait_sig_swap and the addition of cv_init and cv_destroy constructors and destructors. The implementation also differs from Solaris in that the sleep queue is embedded in the condition variable itself instead of coming from the hashed pool of sleep queues’ used by sleep and wakeup.
c. Shared/Exclusive Locks
Shared/Exclusive locks, also known as sx locks, provide simple reader/writer locks. As the name suggests, multiple threads may hold a shared lock simultaneously, but only one thread may hold an exclusive lock. Also, if one thread holds an exclusive lock, no threads may hold a shared lock.
FreeBSD's sx locks have some limitations not present in other reader/writer lock implementations. First, a thread may not recursively acquire an exclusive lock. Secondly, sx locks do not implement any sort of priority propagation. Finally, although upgrades and downgrades of locks are implemented, they may not block. Instead, if an upgrade cannot succeed, it returns failure, and the programmer is required to explicitly drop its shared lock and acquire an exclusive lock. This design was intentional to prevent programmers from making false assumptions about a blocking upgrade function. Specifically, a blocking upgrade must potentially release its shared lock. Also, another thread may obtain an exclusive lock before a thread trying to perform an upgrade. For example, if two threads are performing an upgrade on a lock at the same time.
d. Semaphores
FreeBSD's semaphores are simple counting semaphores that use an API similar to that of POSIX.4 semaphores. Since sema_wait and sema_timedwait can potentially block, mutexes must not be held when these functions are called.
Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK HERE

So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page
Popular Searches: soa distributed operating system, solaris, giant, lataest seminar topics ralated to distributed operating system, a m o e b a the study of a distributed operating system abstract, mirroring freebsd, kerberos solaris,

[-]
Quick Reply
Message
Type your reply to this message here.

Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  Data Security in Local Network using Distributed Firewalls computer science crazy 10 14,787 30-03-2014, 04:40 AM
Last Post: Guest
  eyeOS cloud operating system full report seminar topics 8 11,154 20-03-2014, 11:26 PM
Last Post: seminar report asees
Thumbs Up Fiber Distributed Data Interface Computer Science Clay 1 8,283 23-01-2013, 03:48 PM
Last Post: seminar details
  QNX Operating System computer science crazy 1 3,029 22-12-2012, 11:15 AM
Last Post: seminar details
Smile PLAN 9 Operating system computer science crazy 1 1,977 11-12-2012, 01:32 PM
Last Post: seminar details
  ]Operating System Support seminar class 1 2,039 11-12-2012, 01:32 PM
Last Post: seminar details
  RTX51 Real-time Operating System project report helper 1 2,269 24-11-2012, 03:59 PM
Last Post: RAGHAVENDRA K S
  Distributed Cache Updating for the Dynamic Source Routing Protocol seminar class 3 2,286 17-11-2012, 01:26 PM
Last Post: seminar details
  RTOS - Real Time Operating Systems full report project report tiger 6 11,832 22-10-2012, 01:54 PM
Last Post: seminar details
  distributed database full report project report tiger 3 5,221 05-09-2012, 04:04 PM
Last Post: acceriott

Forum Jump: