Category: Operating System
Both the Shell and the Kernel
are the Parts of this Operating System. These Both Parts are used for
performing any Operation on the System. When a user gives his Command
for Performing Any Operation, then the Request Will goes to the Shell
Parts, The Shell Parts is also called as the Interpreter which translate
the Human Program into the Machine Language and then the Request will
be transferred to the Kernel. So that Shell is just called as the
interpreter of the Commands which Converts the Request of the User into
the Machine Language.
Kernel is also called as the heart of the Operating System and the Every Operation is performed by using the Kernel
, When the Kernel Receives the Request from the Shell then this will
Process the Request and Display the Results on the Screen. The various
Types of Operations those are Performed by the Kernel are as
followings:-
1) It Controls the State the Process Means it checks whether the Process is running or Process is Waiting for the Request of the user.
2) Provides the Memory for the Processes those are Running on the System
Means Kernel Runs the Allocation and De-allocation Process , First When
we Request for the service then the Kernel will Provides the Memory to
the Process and after that he also Release the Memory which is Given to a
Process.
3) The Kernel also Maintains a Time table for all the Processes those are Running Means the Kernel also Prepare the Schedule Time means this will Provide the Time to various Process of the CPU and the Kernel also Puts the Waiting and Suspended Jobs into the different Memory Area.
4) When a Kernel
determines that the Logical Memory doesn’t fit to Store the Programs.
Then he uses the Concept of the Physical Memory which Will Stores the
Programs into Temporary Manner. Means the Physical Memory of the System
can be used as Temporary Memory.
5) Kernel
also maintains all the files those are Stored into the Computer System
and the Kernel Also Stores all the Files into the System as no one can
read or Write the Files without any Permissions. So that the
Kernel System also Provides us the Facility to use the Passwords and
also all the Files are Stored into the Particular Manner.
As
we have learned there are Many Programs or Functions those are
Performed by the Kernel But the Functions those are Performed by the
Kernel will never be Shown to the user. And the Functions of the Kernel
are Transparent to the user.
Mutex vs Semaphore
April 12, 2011
What are the differences between Mutex vs Semaphore? When to use mutex and when to use semaphore?
Concrete understanding of Operating System concepts is required to design/develop smart applications. Our objective is to educate the reader on these concepts and learn from other expert geeks.
As per operating system terminology, the mutex and semaphore are kernel resources that provide synchronization services (also called as synchronization primitives). Why do we need such synchronization primitives? Won’t be only one sufficient? To answer these questions, we need to understand few keywords. Please read the posts on atomicity and critical section. We will illustrate with examples to understand these concepts well, rather than following usual OS textual description.
The producer-consumer problem:
Note that the content is generalized explanation. Practical details will vary from implementation.
Consider the standard producer-consumer problem. Assume, we have a buffer of 4096 byte length. A producer thread will collect the data and writes it to the buffer. A consumer thread will process the collected data from the buffer. Objective is, both the threads should not run at the same time.
Using Mutex:
A mutex provides mutual exclusion, either producer or consumer can have the key (mutex) and proceed with their work. As long as the buffer is filled by producer, the consumer needs to wait, and vice versa.
At any point of time, only one thread can work with the entire buffer. The concept can be generalized using semaphore.
Using Semaphore:
A semaphore is a generalized mutex. In lieu of single buffer, we can split the 4 KB buffer into four 1 KB buffers (identical resources). A semaphore can be associated with these four buffers. The consumer and producer can work on different buffers at the same time.
Misconception:
There is an ambiguity between binary semaphore and mutex. We might have come across that a mutex is binary semaphore. But they are not! The purpose of mutex and semaphore are different. May be, due to similarity in their implementation a mutex would be referred as binary semaphore.
Strictly speaking, a mutex is locking mechanism used to synchronize access to a resource. Only one task (can be a thread or process based on OS abstraction) can acquire the mutex. It means there will be ownership associated with mutex, and only the owner can release the lock (mutex).
Semaphore is signaling mechanism (“I am done, you can carry on” kind of signal). For example, if you are listening songs (assume it as one task) on your mobile and at the same time your friend called you, an interrupt will be triggered upon which an interrupt service routine (ISR) will signal the call processing task to wakeup.
General Questions:
1. Can a thread acquire more than one lock (Mutex)?
Yes, it is possible that a thread will be in need of more than one resource, hence the locks. If any lock is not available the thread will wait (block) on the lock.
2. Can a mutex be locked more than once?
A mutex is a lock. Only one state (locked/unlocked) is associated with it. However, a recursive mutex can be locked more than once (POSIX complaint systems), in which a count is associated with it, yet retains only one state (locked/unlocked). The programmer must unlock the mutex as many number times as it was locked.
3. What will happen if a non-recursive mutex is locked more than once.
Deadlock. If a thread which had already locked a mutex, tries to lock the mutex again, it will enter into the waiting list of that mutex, which results in deadlock. It is because no other thread can unlock the mutex. An operating system implementer can exercise care in identifying the owner of mutex and return if it is already locked by same thread to prevent deadlocks.
4. Are binary semaphore and mutex same?
No. We will suggest to treat them separately, as it was explained signalling vs locking mechanisms. But a binary semaphore may experience the same critical issues (e.g. priority inversion) associated with mutex. We will cover these later article.
A programmer can prefer mutex rather than creating a semaphore with count 1.
5. What is a mutex and critical section?
Some operating systems use the same word critical section in the API. Usually a mutex is costly operation due to protection protocols associated with it. At last, the objective of mutex is atomic access. There are other ways to achieve atomic access like disabling interrupts which can be much faster but ruins responsiveness. The alternate API makes use of disabling interrupts.
6. What are events?
The semantics of mutex, semaphore, event, critical section, etc… are same. All are synchronization primitives. Based on their cost in using them they are different. We should consult the OS documentation for exact details.
7. Can we acquire mutex/semaphore in an Interrupt Service Routine?
An ISR will run asynchronously in the context of current running thread. It is not recommended to query (blocking call) the availability of synchronization primitives in an ISR. The ISR are meant be short, the call to mutex/semaphore may block the current running thread. However, an ISR can signal a semaphore or unlock a mutex.
8. What we mean by “thread blocking on mutex/semaphore” when they are not available?
Every synchronization primitive will have waiting list associated with it. When the resource is not available, the requesting thread will be moved from the running list of processor to the waiting list of the synchronization primitive. When the resource is available, the higher priority thread on the waiting list will get resource (more precisely, it depends on the scheduling policies).
9. Is it necessary that a thread must block always when resource is not available?
Not necessarily. If the design is sure ‘what has to be done when resource is not available‘, the thread can take up that work (a different code branch). To support application requirements the OS provides non-blocking API.
For example POSIX pthread_mutex_trylock() API. When the mutex is not available the function will return immediately where as the API pthread_mutex_lock() will block the thread till resource is available.
References:
http://www.netrino.com/node/202
http://doc.trolltech.com/4.7/qsemaphore.html
Also compare mutex/semaphores with Peterson’s algorithm and Dekker’s algorithm. A good reference is the Art of Concurrency book. Also explore reader locks and writer locks in Qt documentation.
Concrete understanding of Operating System concepts is required to design/develop smart applications. Our objective is to educate the reader on these concepts and learn from other expert geeks.
As per operating system terminology, the mutex and semaphore are kernel resources that provide synchronization services (also called as synchronization primitives). Why do we need such synchronization primitives? Won’t be only one sufficient? To answer these questions, we need to understand few keywords. Please read the posts on atomicity and critical section. We will illustrate with examples to understand these concepts well, rather than following usual OS textual description.
The producer-consumer problem:
Note that the content is generalized explanation. Practical details will vary from implementation.
Consider the standard producer-consumer problem. Assume, we have a buffer of 4096 byte length. A producer thread will collect the data and writes it to the buffer. A consumer thread will process the collected data from the buffer. Objective is, both the threads should not run at the same time.
Using Mutex:
A mutex provides mutual exclusion, either producer or consumer can have the key (mutex) and proceed with their work. As long as the buffer is filled by producer, the consumer needs to wait, and vice versa.
At any point of time, only one thread can work with the entire buffer. The concept can be generalized using semaphore.
Using Semaphore:
A semaphore is a generalized mutex. In lieu of single buffer, we can split the 4 KB buffer into four 1 KB buffers (identical resources). A semaphore can be associated with these four buffers. The consumer and producer can work on different buffers at the same time.
Misconception:
There is an ambiguity between binary semaphore and mutex. We might have come across that a mutex is binary semaphore. But they are not! The purpose of mutex and semaphore are different. May be, due to similarity in their implementation a mutex would be referred as binary semaphore.
Strictly speaking, a mutex is locking mechanism used to synchronize access to a resource. Only one task (can be a thread or process based on OS abstraction) can acquire the mutex. It means there will be ownership associated with mutex, and only the owner can release the lock (mutex).
Semaphore is signaling mechanism (“I am done, you can carry on” kind of signal). For example, if you are listening songs (assume it as one task) on your mobile and at the same time your friend called you, an interrupt will be triggered upon which an interrupt service routine (ISR) will signal the call processing task to wakeup.
General Questions:
1. Can a thread acquire more than one lock (Mutex)?
Yes, it is possible that a thread will be in need of more than one resource, hence the locks. If any lock is not available the thread will wait (block) on the lock.
2. Can a mutex be locked more than once?
A mutex is a lock. Only one state (locked/unlocked) is associated with it. However, a recursive mutex can be locked more than once (POSIX complaint systems), in which a count is associated with it, yet retains only one state (locked/unlocked). The programmer must unlock the mutex as many number times as it was locked.
3. What will happen if a non-recursive mutex is locked more than once.
Deadlock. If a thread which had already locked a mutex, tries to lock the mutex again, it will enter into the waiting list of that mutex, which results in deadlock. It is because no other thread can unlock the mutex. An operating system implementer can exercise care in identifying the owner of mutex and return if it is already locked by same thread to prevent deadlocks.
4. Are binary semaphore and mutex same?
No. We will suggest to treat them separately, as it was explained signalling vs locking mechanisms. But a binary semaphore may experience the same critical issues (e.g. priority inversion) associated with mutex. We will cover these later article.
A programmer can prefer mutex rather than creating a semaphore with count 1.
5. What is a mutex and critical section?
Some operating systems use the same word critical section in the API. Usually a mutex is costly operation due to protection protocols associated with it. At last, the objective of mutex is atomic access. There are other ways to achieve atomic access like disabling interrupts which can be much faster but ruins responsiveness. The alternate API makes use of disabling interrupts.
6. What are events?
The semantics of mutex, semaphore, event, critical section, etc… are same. All are synchronization primitives. Based on their cost in using them they are different. We should consult the OS documentation for exact details.
7. Can we acquire mutex/semaphore in an Interrupt Service Routine?
An ISR will run asynchronously in the context of current running thread. It is not recommended to query (blocking call) the availability of synchronization primitives in an ISR. The ISR are meant be short, the call to mutex/semaphore may block the current running thread. However, an ISR can signal a semaphore or unlock a mutex.
8. What we mean by “thread blocking on mutex/semaphore” when they are not available?
Every synchronization primitive will have waiting list associated with it. When the resource is not available, the requesting thread will be moved from the running list of processor to the waiting list of the synchronization primitive. When the resource is available, the higher priority thread on the waiting list will get resource (more precisely, it depends on the scheduling policies).
9. Is it necessary that a thread must block always when resource is not available?
Not necessarily. If the design is sure ‘what has to be done when resource is not available‘, the thread can take up that work (a different code branch). To support application requirements the OS provides non-blocking API.
For example POSIX pthread_mutex_trylock() API. When the mutex is not available the function will return immediately where as the API pthread_mutex_lock() will block the thread till resource is available.
References:
http://www.netrino.com/node/202
http://doc.trolltech.com/4.7/qsemaphore.html
Also compare mutex/semaphores with Peterson’s algorithm and Dekker’s algorithm. A good reference is the Art of Concurrency book. Also explore reader locks and writer locks in Qt documentation.
|
A mutex is a mutual exclusion semaphore,
a special variant of a semaphore that only allows one locker at a time
and whose ownership restrictions may be more stringent than a normal
semaphore.
In other words, it's equivalent to a normal counting semaphore with a count of one and the requirement that it can only be released by the same thread that locked it. A semaphore, on the other hand, has a count and can be locked by that many lockers concurrently. And it may not have a requirement that it be released by the same thread that claimed it (but, if not, you have to carefully track who currently has responsibility for it, much like allocated memory). So, if you have a number of instances of a resource (say three tape drives), you could use a semaphore with a count of 3. Note that this doesn't tell you which of those tape drives you have, just that you have a certain number. Also with semaphores, it's possible for a single locker to lock multiple instances of a resource, such as for a tape-to-tape copy. If you have one resource (say a memory location that you don't want to corrupt), a mutex is more suitable. Equivalent operations are: |
http://stackoverflow.com/questions/4039899/when-should-we-use-mutex-and-when-should-we-use-semaphore
http://www.geeksforgeeks.org/mutex-vs-semaphore/
http://www.makelinux.net/ldd3/chp-5-sect-3
http://ecomputernotes.com/fundamental/disk-operating-system/what-is-shell-and-kernel
Public speaking is probably one of the most nerve-racking experiences that any of us have to deal with.
![\begin{displaymath}\left[ \begin{array}{rrr} -1 & 0 & 1 -1 & 0 & 1 -1 & 0 ...
...& 0 1 & 0 & -1 0 & -1 & -1
\end{array} \right], \;\;\;
\end{displaymath}](http://fourier.eng.hmc.edu/e161/lectures/gradient/img46.png)
![\begin{displaymath}\left[ \begin{array}{rrr} 1 & 0 & -1 1 & 0 & -1 1 & 0 &...
...} -1 & -1 & 0 -1 & 0 & 1 0 & 1 & 1
\end{array} \right]
\end{displaymath}](http://fourier.eng.hmc.edu/e161/lectures/gradient/img47.png)
![\begin{displaymath}
\left[ \begin{array}{rrr} 1 & 1 & 1 1 & -2 & 1 -1 & -...
...& 1 0 & 0 & 0 -1 & -2 & -1
\end{array} \right], \;\;\;
\end{displaymath}](http://fourier.eng.hmc.edu/e161/lectures/gradient/img48.png)
![\begin{displaymath}
\left[ \begin{array}{rrrrr} 1 & 1 & 1 & 1 & 1 -.32 & .78 ...
...2 & .78 & 1 \\
-1 & -1 & -1 & -.32 & 1
\end{array} \right]
\end{displaymath}](http://fourier.eng.hmc.edu/e161/lectures/gradient/img49.png)
Common Names: Laplacian, Laplacian of Gaussian, LoG, Marr Filter
has the form:
