What is meant by multiplexing?

- Multiplexing or muxing is a very important process in computer networks and the telecommunications. 

Using this process, a number of digital data streams or analog message signals are combined as one signal and then transported over the common medium. 

- Multiplexing is used wherever it is required to share a resource that is very expensive. 

- The most common example of multiplexing is of using one wire for several telephone calls. 

- The origin of the multiplexing dates back to 1870s when telegraphy was started.

- Now it is used to a great extent in the field of communications. 

- The telephone carrier multiplexing was developed by George Owen Squire in the field of telephony. 

- The communication channel over which the multiplexed signal might be transmitted might be a physical transmission medium. 

- The high level communication channel’s capacity is divided by multiplexing process in to a number of low level logical channels where for each message or data stream one channel is used. 

- Demultiplexing is the reverse process of multiplexing. 

- This is used for the extraction of the original signals on the reception side.

- A multiplexer or MUX is a device that is used for carrying out the multiplexing process and the demultiplexer or DEMUX is the device that performs demultiplexing. 

- IMUX or inverse multiplexing is another process whose aim is just the opposite of the multiplexing.

- It breaks down a single data stream in to various streams while transferring them at the same time over various communication channels.

- Later, the original stream is recreated.

Types of Multiplexing

Many different types of multiplexing technologies are available today. Each has its own significance:

Ø SDM or space-division multiplexing: 

This technique implies on using different point – to – point wires for individual communication channels. For example, an audio cable of analogue stereo, multi – pair telephone cable, switched star network, mesh network. However typically the wired SDM is not usually considered as multiplexing. In SDM a phased array antenna is formed by multiple antennas. For example MIMO (multiple – input and multiple – output), SIMO (simple – input and multiple – output), MISO (multiple – input and single – output) etc.

Ø  FDM or frequency-division multiplexing: 

This is considered to be an analog process, here the signals are sent in to different frequency ranges over a shared medium. For example, TV and radio broadcasting from satellite stations through the earth’s atmosphere. One cable is given in each house but over this cable many signals can be sent to other subscribers also. For accessing the desired signal, the users require to tune to that particular frequency. WDM or wavelength division multiplexing is a variant of FDM.

Ø TDM or time-division multiplexing: 

Unlike FDM, TDM is a digital technology but very rarely it might be used as an analog technology also. The process involves putting bytes in a sequence for each input stream one by one. this sequencing is done in such a way that the receiver can appropriately  receive them. If this is done quickly, the fact that another logical communication path was served in that circuit time won’t be detected by the receiver.

Ø  CDM or code-division multiplexing: 

In this multiplexing technique, the same frequency spectrum is shared by the several channels at the same time. Also the bandwidth of the spectrum is quite high when compared to the symbol rate or the bit rate. It is implemented in either of the two forms namely direct sequence spread spectrum and frequency hopping.

Some other types of multiplexing techniques which are less prominent are:

Polarization-division multiplexing: Used in optical and radio communications.

Orbital angular momentum multiplexing

What is Process State Diagram?

In the systems where multiple processors or multitasking is involved, a process has to go through a number of states. In this article we shall discuss about these states. 

The kernel of the operating system may not recognize these states distinctly but still for the understanding of how the processes are executed they act as useful abstractions. 

These various states can be looked up in a process state diagram for a systematic view. This diagram shows the transitions of the process between various states with arrows. Processes can be stored both in the secondary or virtual memory and in the main memory as per the situation.

Process States

- The primary process states occur in all types of the systems. 

- Processes in these states are usually stored in the main memory. 

Basically there are 5 major states of any process as discussed below:

Ø  Created: 

- It is also known as the ‘new’ state. 

- A process occupies this state up on it creation. 

- While waiting for being admitted to the next ready state this process lies in this state. 

- The admission scheduler will decide whether to admit the process to next state or to delay it on a short or long term. 

- However, this admission is approved in an automatic way in most of the desktop computers. 

- But in the systems with real time operating systems this is not true. 

- Here, the admission might be delayed by a certain amount of time.

- If too many states are admitted to the ready state in a real time operating system, condition of over contention and over saturation might occur disabling the system to meet its deadlines.

Ø  Ready or Waiting: 

- This state is taken up a process when it has been loaded in to the physical memory of the system and is waiting to be executed by the processor or precisely waiting to be context switched by the dispatcher. 

- At any instant of time there might be a number of processes waiting for their execution. 

- Here the processes have to wait in a queue called the run queue out of which only one process will be taken up by a processor. 

- Processes that are waiting for obtaining input from some event are not put in to this ready queue.

Ø  Running: 

- When a process is selected by the CPU for execution, its state is changed to running. 

- One of the processors executes the instructions of the process one by one. 

- Only one process can be run by the process at a time.

Ø Blocked: 

- When a process is blocked because of some event such as I/O operations is put in to the blocked state. 

- Another reason for a process being a blocked state can be its running out of the CPU time allocated to it.

Ø  Terminated: 

- Termination of a process may occur when either its execution is complete or it has been explicitly killed.

- This state is called the terminated or halted. 

- This process is called a zombie process if after coming in the terminated state it is not removed from the main memory. 

There are two additional states for supporting the virtual memory. In these states the process is usually stored in the secondary memory of the system:

Ø Swapped out or Waiting: 

- A process is said to be swapped out when it is removed from the primary memory and placed in the secondary memory. 

- This is done by the mid - term scheduler. 

- After this the state of this process changes to waiting.  

Ø  Swapped out and Blocked:

- In some cases, the processes that were in blocked state might be swapped out. 

- The same process might be again swapped in providing the conditions remain the same.

What is CPU Scheduling Criteria?

Scheduling is an essential concept that serves in the multitasking, multiprocessor and distributed systems. There are several schedulers available for this purpose. But these schedulers also require a criterion up on which they can decide how to schedule the processes. In this article we discuss about these scheduling criteria. Today a number of scheduling algorithms are available and all these have different properties. This is why these may work up on different scheduling criteria. Also the chosen algorithm may favor one class of processes more than the other.

What Criteria is used by algorithms for Scheduling?

Below mentioned are some of the criteria used by these algorithms for scheduling:
1. CPU utilization:
- It is a property of a good system to keep the CPU as busy as possible all the time.
- Thus, this utilization ranges from 0 percent to 100 percent.
- However, in the systems that are loaded lightly, the range is around 40 percent and for the systems heavily loaded it ranges around 90 percent.

2. Throughput:
- The work is said to be done if the CPU is busy with the execution of the processes.
- Throughput is one measure of CPU performance and can be defined as the number of processes being executed completely in a certain unit of time.
- For example, in short transactions throughput might range around like 10 processes per second.
- In longer transactions this may range around only one process being executed in one hour.

3. Turnaround time:
- This is an important criterion from the point of view of a process.
- This tells how much time the processor has taken for execution of  a processor.
- The turnaround time can be defined as the time duration elapsed from the submission of the process till its completion.

4. Waiting time:
- The amount of time taken for the process for its completion is not affected by the CPU scheduling algorithms.
- Rather, these algorithms only affects the time when the process is in waiting state.
- The time for which the process waits is called the waiting time.

5. Response time:
- The turnaround is not a good criterion in all the situations.
- The response time is favorable in the case of the interactive systems.
- It happens many a times that a process is able to produce the output in a fairly short time compared to the expected time.
- This process then can continue with the next instructions.
- The time taken for a process from its submission till production of the first response is calculated as the response time and is another criterion for the CPU scheduling algorithms.

All these are the primary performance criteria out of which one or more can be selected by a typical CPU scheduler. These criteria might be ranked by the scheduler depending up on their importance. One common problem in the selection of performance criteria is the possibility of conflict ion between them.
For example, increasing the number of active processes will increase the CPU utilization but at the same time will decrease the response time. This is often desirable to produce reduction in waiting time and turnaround time also. In a number of cases the average measure is optimized. But there are certain cases also where it is more beneficial to optimize the maximum or the minimum values.
It is not necessary that a scheduling algorithm that maximizes the throughput will decrease the turnaround time. Out of a mix of short and long jobs, if a scheduler runs only the short jobs, it will produce the best throughput. But at the same time the turnaround time for the long jobs will be so high which is not desirable.

Explain the various techniques for Deadlock Prevention

Deadlocks are like a nightmare for the programmers who design and write the programs for the multitasking or multiprocessing systems. For them it is very important to know about how to design programs in such a way as to prevent the deadlocks. 

Deadlocks are a more common problem in the distributed systems which involve a use of the concurrency control and distributed transactions. The deadlocks that occur in these systems are termed as the distributed deadlocks. 

It is possible to detect them using either of the following means:

1. Building a global wait for graph from a local one through a deadlock detector.

2. Using distributed algorithms such as the edge chasing.

- An atomic commitment protocol similar to a two phase commit is used for automatically resolving the distributed deadlocks. 

- Therefore, there is no need for any other resolution mechanism or a global wait for graph. 

- But this is possible only in the commitment ordering based distributed environments. 

- For the environments that have 2 – phase locking, a similar automatic global deadlock resolution takes place.

- There is another class of deadlocks called the phantom deadlocks. 

- These are the ones detected in the system because of some internal delays but they actually do not exist during the detection time.

- Today, their exist a number of ways using which the parallelism can be increased where otherwise severe deadlocks might have been caused by the recursive locks. 

- But like for everything else, this also has a price.

- You either have to accept one of these or both i.e., the data corruption or the performance/ overhead. 

- Preemption and lock–reference counting, WFG or wait – for graph are some of the examples of this. 

- These can be followed either by allowing for the data corruption during the preemption or by using version.

- Apart from these heuristic algorithms and the algorithms that can track all the cycles causing the deadlocks can be used for preventing the deadlocks.

- These algorithms even though they don’t offer 100 percent parallelism, they prevent deadlocks by providing an acceptable degree of the performance overhead versus parallelism. 

This example will make it clearer: 

- Consider at a crossing junction there are 2 trains approaching each other. 

- Their collision can be prevented by some just-in-time prevention means. 

- This mean can be person at the crossing having a switch pressing which will allow only one of them to cross on to the succeeding track super passing the other trains that are also waiting. 

- There are following two types of deadlocks:

1. Recursive locks: In such locks, only one thread can pass through it. Any other threads or processes entering the lock need to wait for the initial one to pass through after its task is finished.
2. Non – recursive locks: Here only once a thread can enter the lock. If the same thread again tries to enter the lock without unlocking it, a deadlock can occur.

- There are issues with both of these. 

- The first one does not provides distributed deadlock prevention and the latter one has no concerns for the deadlock prevention. 

- In the first one, if the number of threads trying to enter the lock equals the number of locked threads, then one of the threads has to be assigned as the super one and then only one can execute it till completion. 

- After the execution of the super thread is complete, the condition reverts back from the recursive lock and the super thread removes its status of being super thread and sends a notification to the locker that the condition has to be re-checked. 

Define the Virtual Memory technique?

Modern operating systems come with multitasking kernels. These multitasking kernels often run in to the problems related to memory management. Physical memory does not suffice for them to execute the tasks assigned to them because of being fragmented. So they have to take some additional from the secondary memory. But they cannot use this memory directly. Virtual memory offers a solution to this problem. 

What is Virtual Memory technique?

- Using this technique makes the fragmented main memory available to the kernels as a contiguous main memory. 

- Since it is really not the main memory but just appears to be, it has been named as the virtual memory and this technique is called the virtual memory technique. 

- Since, it helps in managing the memory, it is essential a memory management technique. 

- The main storage gets fragmented because of many programming and processing problems. 

- The main memory available to the processes and the tasks is virtualized by the virtual memory technique and then it appears to the process as a contiguous memory location. 

- This memory is a global address space. 

- Virtual address spaces such as these are managed by the operating system. 

- The real memory is assigned to the virtual memory by the operating system itself. 

- The virtual addresses of the allocated virtual address spaces are translated in to the physical addresses automatically by the CPU. 

- It achieves this with the help of some memory management hardware specially designed for this purpose. 

- The processes continue to execute uninterrupted as long as this hardware properly translates the virtual addresses in to real memory addresses properly. 

- If it fails in doing so at any point of time, the execution comes to a halt and the control is transferred to the operating system. 

- The duty of the operating system now is to move the requested memory page to the main memory from the backing store. 

- Once done with this, it then returns the control again to the process that was interrupted. 

- It greatly simplifies the whole execution process. 

- Even if the application would require more data or code that would fit in real memory, it does not have to be moved to and fro between the backing store and the real memory. 

- Furthermore, this technique also offers protection to the processes that are provided distinct address spaces by the isolation of the memory allocate to them from other tasks.

- Application programming has been made a lot easier with the help of the virtual memory technique since it hides the fragmentation defects of the real memory. 

- The burden of memory hierarchy management is delegated to the kernel which eliminates the need for the explicit handling of the overlays by the program. 

- Thus each process can execute in an address space that is dedicated to it. 

- The need for relocating the code of the program is obviated along with using relative addressing for accessing the memory. 

- The concept of virtual memory was generalized and eventually named as memory virtualization. 

- Gradually, the virtual memory has become an inseparable part of the architecture of the modern computers. 

- For implementing it, dedicated hardware support is absolutely necessary. 

- This hardware is built in to the CPU in some sort of memory management hardware. - If required for boosting the performance of the virtual memory, some virtual machines and emulators may employ some additional hardware support. 

- The older mainframe computers did not have any support for the virtual memory concept. 

- In virtual memory technique, each program can solely access the virtual memory.

What are different types of schedulers and their workings?

Scheduling is an important part of the working of operating systems. 

- The scheduler is the component that provides access to the resources to the processes, threads and data flows. 

- These resources may include time of the processor and the communications bandwidth. 

- Scheduling is necessary for effectively balancing the load of the system and achieving the target of QoS or quality of service. 

- Scheduling is also necessary for the systems that do multitasking and multiplexing on a single processor since they need to divide the CPU time between many processes. 

- In multiplexing, it is required for timing the simultaneous transmission of the multiple flows.

Important things about Scheduler

There are 3 things which most concern the scheduler:

1. Throughput
2. Latency inclusive of the response time and the turnaround time
3. Waiting time or the fairness time

- But when practically implemented, conflicts arise between these goals for example between latency and throughput. 

- It is the scheduler that can make a compromise between any two goals. 

- Based on the user’s requirements and the objectives it is decided to which goal the preference has to be given. 

- In systems such as the embedded systems and robotics that operate in real time environment, it has to be ensured by the scheduler that the processes are capable of meeting the deadlines. 

- This is a very critical factor in maintaining the stability of the system. 

- The administrative back end is used for managing the scheduled tasks that are then sent to the mobile devices.  

Types of Schedulers

There are 3 different types of schedulers available which we discuss below:

Long term Schedulers or Admission Schedulers: 

- The purpose of this type of scheduler is to decide about the processes and jobs to be admitted or added to the ready queue. 

- When a program makes an attempt for executing a process, it is the responsibility of the long – term scheduler to delay or authorize the request for admitting the process to the ready queue. 

- Thus, what all processes will be executed by the system is dictated by this scheduler. 

- It also dictates about the degree of the concurrency and handling of the CPU intensive and I/O intensive processes. 

- Modern operating systems use this for making sure that there is enough time for the processes to finish of their tasks. 

- Modern GUIs would be of very less use if there was no real time scheduling. 

- The long term queue resides in the secondary memory.

Medium term Schedulers: 

- This scheduler serves the purpose of removing the processes from the physical memory and placing them in the virtual memory and even vice versa. 

- This process is called swapping out and swapping in. 

- A process that has been inactive for some time might be swapped by the scheduler. 

- It may also swap a process with frequent page faulting, low priority or more amount of memory etc. 

- This is necessary since this makes the space available for other processes.

Short term Schedulers: 

- These schedulers are more commonly known as the CPU schedulers.

- It decides which one out of all the processes will be executed after the clock interrupt, a system call, an I/O interrupt, hardware interrupt and so on. 

- Thus, we can say that the frequency of the short term schedulers of making decisions is much higher than that of the long term and medium term schedulers since after every time slice these schedulers have to decide.

- There is one more component that is involved in CPU scheduling but is not counted under schedulers. It is called dispatcher. 

Define a process? What are sequential and concurrent processes?

- Each and every task which we order our computer to carry out is accomplished by a set of processes. 

- It is these processes that actually run the program. 

- A process can be defined as an instance of the program that is currently being executed. 

- A program’s current activity and the code being executed are stored in the process itself. 

- However, it depends on the operating system that the process is to constitute of multiple threads for a concurrent execution or just one thread for sequential execution. 

This gives rise to two different types of processes namely:

Sequential processes 

Sequential processes can be executed on the same processor but the concurrent processors however may sometimes require more than one processor.

Concurrent processes

Concurrent processes are executed in parallel to each other and at the same whereas the sequential processes go step by step executing one instruction at a time. 

Concepts of Process

- A computer program can be defined as a set of passive instructions. When these instructions are actually executed, they form a process. 

- The same program may have a number of processes associated with it. 

- Multiple processes can be executed by sharing the processors and the resources. 

- If this is done, it is called multitasking. 

- Each processor takes up a single task. 

- With multitasking, switching between the different tasks becomes possible for the processor and so the processes won’t have to wait for long. 

- However, it depends entirely on the operating system when the switch has to be performed:

1. When the task is performing I/O operations or
2. When the task itself indicates that it can now be switched or
3. On hardware interrupts.

- Time sharing is a common type of multitasking and allows interactive user applications to response quickly. 

- In systems using the time sharing systems, switching is done quite rapidly. 

- This gives an illusion of the simultaneous execution of the multiple processes by the same processor. 

- Such type of execution is termed as concurrency.

- Direct communication that may take place between independent processes is avoided by many of the modern operating systems for the reasons of maintaining reliability and security. 

- The inter-process communication functionality is kept under strict control and mediation. 

- In general, the following resources are said to constitute a process:

Ø  Executable machine code’s image associated with the task.

Ø  Some part of virtual memory that is inclusive of the process specific data, executable code, heap and a call stack. Heap is for holding the immediate data generated during the execution and the call stack is for keeping a track of the subroutines.

Ø OS descriptors belonging to the resources that were allocated to the processes. These descriptors may be data sources, sinks and file descriptors etc.

Ø  Security attributes including the set of permissions for the process and the owner of the process.

Ø  Processor state like physical memory addressing or register contents etc. registers store the state during the execution of the process or otherwise it is stored in memory.

- Most of this information is held in the process control blocks regarding the active processes. 

- The operating system makes it a point to maintain a separation between its resources and allocate them the requested resources so that they won’t interfere with the working of each other and thus won’t cause any system failures such as thrashing or deadlocks. 

- But processes do require communicating with each other. 

- For such cases to make interaction safe, operating system has mechanisms especially for the inter-process communication.

What is Context Switch?

- The context switch refers to the process that involves storing and restoring of the context or the state of the process. 

- This makes it possible to resume the execution of the process from that same saved point in the future. 

- This is very important as it has enabled the various processes for sharing one CPU and therefore it represents one of the essential features of an operating system that is capable of multi – tasking. 

- It is the operating system and the processors which decide what will constitute the context. 

- One of the major characteristic of the context switches is that they are computationally very intensive.

- Most of the designing of the operating systems is concerned with the optimization of the use of these switches. 

- A finite amount of time is required for switching from one process to another one. 

- This time is spent in the administration of the process which includes saving and loading of the memory maps, registers etc. plus the various lists and tables are updated. 

- A context switch may mean either of the following:

Ø  A register context switch

Ø  A task context switch

Ø  A thread context switch

Ø  A process context switch

Potential Triggers for a Context Switch

There are three potential triggers for a context switch. A switch can be triggered in any of the three conditions:

1. Multi-tasking: 

- It is common that one process has to be switched out of the processor so as to execute another process. 

- This is done by the use of some scheduling scheme. 

- Here, if the process makes itself un-executable, then it can trigger this context switch. 

- The process can do this by waiting for synchronization or an I/O operation to finish. 

- On a multitasking system that uses pre-emptive scheduling, the processes that are still executable might be switched out by the scheduler. 

- A timer interrupt is employed by some of the preemptive schedulers to avoid process starving of the CPU time.

- This interrupt gets triggered when the time slice is exceeded by the process. - Furthermore, this interrupt makes sure that the scheduler will be able to gain control for switching.

2. Interrupt handling: 

- Modern architectures are driven by the interrupts. 

- This implies that the CPU can issue the request while continuing with some other execution and without waiting for the current read/ write operation to get over. 

- When the currently executing operation is over, the interrupt fires and presents the result to the CPU. 

- Interrupt handler is used for handling the interrupts. 

- The interrupts are handled by this program directly from the disk. 

- A part of the context is automatically switched by the hardware up on the occurrence of an interrupt. 

- This context is enough for the handling program to go back to the code that raised the interrupt.

- The additional context might be saved by the handler as per the details of both the software and hardware designs. 

- Usually, only a required small context’s part is changed so as to keep the amount of time required for handling as minimum as possible. 

- Kernel does not take part in scheduling a process that would handle the interrupts.

3. User and kernel mode switching: 

- A context switch is not required for making a transition between the kernel mode and the user mode in an operating system.

- A mode transition in itself cannot be considered to be a context switch. 

- But, it depends on the OS whether or not the context switch will take place. 

What are the causes for the failure of traditional planning approach?

The traditional planning approaches does not always lead to very satisfactory results.

Causes for Planning Failure

Cause #1: Planning is done by activity and not feature
- The traditional approaches to planning focus on activity completion rather than on delivery of features.
- Activity based plans generally lead to projects that overrun their schedules.
- Hence, quality is reduced.

Cause #2: Activities do not finish early
Cause #3: Lateness is passed down the schedule
- Traditional approaches being activity based, their main focus is to focus on dependencies between activities.
- Testing will start late if anything goes worse than planned according to traditional approach.
- Testing will start early if everything goes better than planned.

Ways to avoid late start of testing are:
1. User interface coding finishes late.
2. Middle tier coding takes longer than planned and finishes late.
3. Middle tier coding starts late as tables adding to database finishes late.
4. Tester is not available.

Cause #4: Activities are not independent
- Activities are independent if duration of one activity does not influence the duration of another activity.
- For independent activities, late finish on one activity can be offset by an early finish on another.


Cause #5: Delay caused by multitasking
- Multitasking exacts a horrible toll on productivity.
- It becomes an issue once a project starts to have some activities that finish late.
- Dependencies between activities become critical.
- For a traditionally planned project, multitasking becomes a problem for two reasons:
1. Work is assigned in advance and it is impossible to allocate work efficiently in advance.
2. It focuses on achieving high level of utilization of all individuals rather than on maintaining sufficient slack.

Cause #6: Features are not developed by priority
Cause #7: Ignoring Uncertainty
- We fail to acknowledge uncertainty in traditional approach.
- Ignore the uncertainty about product.
- Assuming initial requirement analysis will lead to complete specification of product.
- Ignoring uncertainty about how we will build the product.
- The best way to deal with uncertainty is to iterate.


After looking at the problems with traditional approaches to planning, many projects are disappointing. Planning based on activity diverts us from features and as a result, a variety of problems leads to the likelihood of delivering late against a schedule.