Operating System Interview Questions
What is a process and process table? What are different states of process
A process is an instance of program in execution. For example a Web Browser is a process, a shell (or command prompt) is a process.
The operating system is responsible for managing all the processes that are running on a computer and allocated each process a certain amount of time to use the processor. In addition, the operating system also allocates various other resources that processes will need such as computer memory or disks. To keep track of the state of all the processes, the operating system maintains a table known as the process table. Inside this table, every process is listed along with the resources the processes is using and the current state of the process.
Processes can be in one of three states: running, ready, or waiting. The running state means that the process has all the resources it need for execution and it has been given permission by the operating system to use the processor. Only one process can be in the running state at any given time. The remaining processes are either in a waiting state (i.e., waiting for some external event to occur such as user input or a disk access) or a ready state (i.e., waiting for permission to use the processor). In a real operating system, the waiting and ready states are implemented as queues which hold the processes in these states. The animation below shows a simple representation of the life cycle of a process (Source:http://courses.cs.vt.edu/csonline/OS/Lessons/Processes/index.html)
A process is an instance of program in execution. For example a Web Browser is a process, a shell (or command prompt) is a process.
The operating system is responsible for managing all the processes that are running on a computer and allocated each process a certain amount of time to use the processor. In addition, the operating system also allocates various other resources that processes will need such as computer memory or disks. To keep track of the state of all the processes, the operating system maintains a table known as the process table. Inside this table, every process is listed along with the resources the processes is using and the current state of the process.
Processes can be in one of three states: running, ready, or waiting. The running state means that the process has all the resources it need for execution and it has been given permission by the operating system to use the processor. Only one process can be in the running state at any given time. The remaining processes are either in a waiting state (i.e., waiting for some external event to occur such as user input or a disk access) or a ready state (i.e., waiting for permission to use the processor). In a real operating system, the waiting and ready states are implemented as queues which hold the processes in these states. The animation below shows a simple representation of the life cycle of a process (Source:http://courses.cs.vt.edu/csonline/OS/Lessons/Processes/index.html)
What is a Thread? What are the differences between process and thread?
A thread is a single sequence stream within in a process. Because threads have some of the properties of processes, they are sometimes called lightweight processes. Threads are popular way to improve application through parallelism. For example, in a browser, multiple tabs can be different threads. MS word uses multiple threads, one thread to format the text, other thread to process inputs, etc.
A thread has its own program counter (PC), a register set, and a stack space. Threads are not independent of one other like processes as a result threads shares with other threads their code section, data section and OS resources like open files and signals. Seehttp://www.personal.kent.edu/~rmuhamma/OpSystems/Myos/threads.htm for more details.
A thread is a single sequence stream within in a process. Because threads have some of the properties of processes, they are sometimes called lightweight processes. Threads are popular way to improve application through parallelism. For example, in a browser, multiple tabs can be different threads. MS word uses multiple threads, one thread to format the text, other thread to process inputs, etc.
A thread has its own program counter (PC), a register set, and a stack space. Threads are not independent of one other like processes as a result threads shares with other threads their code section, data section and OS resources like open files and signals. Seehttp://www.personal.kent.edu/~rmuhamma/OpSystems/Myos/threads.htm for more details.
What is deadlock?
Deadlock is a situation when two or more processes wait for each other to finish and none of them ever finish. Consider an example when two trains are coming toward each other on same track and there is only one track, none of the trains can move once they are in front of each other. Similar situation occurs in operating systems when there are two or more processes hold some resources and wait for resources held by other(s).
Deadlock is a situation when two or more processes wait for each other to finish and none of them ever finish. Consider an example when two trains are coming toward each other on same track and there is only one track, none of the trains can move once they are in front of each other. Similar situation occurs in operating systems when there are two or more processes hold some resources and wait for resources held by other(s).
What are the necessary conditions for deadlock?
Mutual Exclusion: There is s resource that cannot be shared.
Hold and Wait: A process is holding at least one resource and waiting for another resource which is with some other process.
No Preemption: The operating system is not allowed to take a resource back from a process until process gives it back.
Circular Wait: A set of processes are waiting for each other in circular form.
Mutual Exclusion: There is s resource that cannot be shared.
Hold and Wait: A process is holding at least one resource and waiting for another resource which is with some other process.
No Preemption: The operating system is not allowed to take a resource back from a process until process gives it back.
Circular Wait: A set of processes are waiting for each other in circular form.
What is Virtual Memory? How is it implemented?
Virtual memory creates an illusion that each user has one or more contiguous address spaces, each beginning at address zero. The sizes of such virtual address spaces is generally very high.
The idea of virtual memory is to use disk space to extend the RAM. Running processes don’t need to care whether the memory is from RAM or disk. The illusion of such a large amount of memory is created by subdividing the virtual memory into smaller pieces, which can be loaded into physical memory whenever they are needed by a process.
Virtual memory creates an illusion that each user has one or more contiguous address spaces, each beginning at address zero. The sizes of such virtual address spaces is generally very high.
The idea of virtual memory is to use disk space to extend the RAM. Running processes don’t need to care whether the memory is from RAM or disk. The illusion of such a large amount of memory is created by subdividing the virtual memory into smaller pieces, which can be loaded into physical memory whenever they are needed by a process.
What is Thrashing?
Thrashing is a situation when the performance of a computer degrades or collapses. Thrashing occurs when a system spends more time processing page faults than executing transactions. While processing page faults is necessary to in order to appreciate the benefits of virtual memory, thrashing has a negative affect on the system. As the page fault rate increases, more transactions need processing from the paging device. The queue at the paging device increases, resulting in increased service time for a page fault (Source: http://cs.gmu.edu/cne/modules/vm/blue/thrash.html)
Thrashing is a situation when the performance of a computer degrades or collapses. Thrashing occurs when a system spends more time processing page faults than executing transactions. While processing page faults is necessary to in order to appreciate the benefits of virtual memory, thrashing has a negative affect on the system. As the page fault rate increases, more transactions need processing from the paging device. The queue at the paging device increases, resulting in increased service time for a page fault (Source: http://cs.gmu.edu/cne/modules/vm/blue/thrash.html)
"The term thrashing is actually related to the virtual memory, that an operating system uses in order to provide extra amount of memory or space for the processes. What dose it actually mean by the term thrashing is that, when the process is ready to be loaded in the memory, only a few or some pages(parts) of the process are loaded in the actual physical memory, and rest are in the swap-space(the virtual memory or the disk).
Now if the page that the process needs to execute, is not loaded in the memory, it generates a page-fault and asks the OS to replace the page. Here the process resumes its execution.
Some times, the page replaced by the OS is again required by the process therefore it again asks the OS to load it in the memory, replacing some other page and so on. since the process is not executing, therefore the CPU utilization is 0, However the disk read and write are at the peak.
Our OSs are designed in such a way that when the CPU utilization decreases it initiates another process in the memory. The next process have to wait now because the first process is busy. Again since the CPU is not being utilized or it is 0(in our example), the OS initiates another process, and the same thing happen.
Therefore, the CPU utilization decreases to an extreme minimum level, while the processes are busy reading and writing(swapping the pages). This is called thrashing!"
What is Belady’s Anomaly?
Bélády’s anomaly is an anomaly with some page replacement policies where increasing the number of page frames results in an increase in the number of page faults. It occurs with First in First Out page replacement is used. See the wiki page for an example and more details.
Bélády’s anomaly is an anomaly with some page replacement policies where increasing the number of page frames results in an increase in the number of page faults. It occurs with First in First Out page replacement is used. See the wiki page for an example and more details.
Differences between mutex and semphore?
See http://www.geeksforgeeks.org/mutex-vs-semaphore/
See http://www.geeksforgeeks.org/mutex-vs-semaphore/
- Practice Quizzes on Operating System topics
- Last Minute Notes – OS
- OS articles
We will soon be covering more Operating System questions. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Source : http://quiz.geeksforgeeks.org/commonly-asked-operating-systems-interview-questions-set-1/
Mutex vs Semaphore
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, 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 onatomicity 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 vary with implementation.
Consider the standard producer-consumer problem. Assume, we have a buffer of 4096 byte length. A producer thread collects the data and writes it to the buffer. A consumer thread processes 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 is 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 calls you, an interrupt is triggered upon which an interrupt service routine (ISR) signals 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 is 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 happens 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 suggest to treat them separately, as it is 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 in 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 has a 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 gets the 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 necessary. 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 mutex is not available the function returns immediately whereas the API pthread_mutex_lock() blocks the thread till resource is available.
References:
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.
Exercise:
Implement a program that prints a message “An instance is running” when executed more than once in the same session. For example, if we observe word application or Adobe reader in Windows, we can see only one instance in the task manager. How to implement it?
Article compiled by Venki. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Another Great Resource : http://www.careerride.com/OS-semaphore.aspx
Comments
Post a Comment