NetApp Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
I think depends on the number of cores in the machine as each core would add some constant time to perform context switch
This problem has nothing to do with the number of cores. It is a valid question even with a single CPU machine.
Assume a computer with one CPU and X Ram.
Lets say it has a program A running consuming all the RAM and it is at at point X in execution. At this point lot of stuff at point X is in register. the remaining immediate stuff is in CPU cache and all of the heap/stack is mapped to virtual memory and committed.
When a context switch happens... and program B starts running. registers will be replaced with B contents so will cpu cache and RAM.
When the context switches back even if the registers are immediately restore it will be while before cache is and even more before everything that was paged out to disk is mapped backed to physical memory.
that is consequence of context switch not part of context switch..........
context switch will store register values (IP for sure not exactly sure of which other registers), currently executing threads user mode stack/kernel mode stack (so as to start with correct values next time context switches to this thread's context) and if thread switch causes process switch then change CR3 (in intel) register to point to new process page tables. I think all this will surely be more than O(1)
that is consequence of context switch not part of context switch..........
context switch will store register values (IP for sure not exactly sure of which other registers), currently executing threads user mode stack/kernel mode stack (so as to start with correct values next time context switches to this thread's context) and if thread switch causes process switch then change CR3 (in intel) register to point to new process page tables. I think all this will surely be more than O(1)
At context switch, it should pick the next process to schedule. There must be an algorithm to decide which process to schedule next and that will be O(n).
Hence context switch will be O(n)
Rajesh
A context switch involves saving the Process Control Block (PCB) of the current process, and loading the PCB of the next process. Scheduling is a separate mechanism for deciding the next process, before it is submitted for context switch. The size of the PCB does not change much between process to process, even if the memory allocation, number of thread etc. because those things come into play after the context switch. So I believe O(1) would be the answer.
If the scheduling algorithm is run during the context switch then the switch time could vary from switch to switch.
The process which is waiting for its turn (on context switch) is already at the Queue of Runnable process. the mechanism to schedule process execution sequence is implemented while the process goes for waiting or sleep in short leaves the Running queue.
So it atomically depends on the "time takes to switch context of current process and the context of the process at the top of runnable queue.
The "switch function" written in the kernel is implemented mostly using mutex/futexe/spin lock which does not allow any other process to interrupt this method nor any interrupt can break this mutex or atomic function.
indeed the "context switch" is atomic hence O(1) complexity ...even for Thread switching
PCBs((Process Control Block s) ) are arranged in linked list fashion so to load a particular PCB one needs to find that PCB which will be O(n) so I think context switch is going to be of order O(n).
O(1) meaning that it will take constant "time" every-time context switch happens. And the time it takes to context switch will not depend on the number of processes/threads in the system. I think it would be O(1) for a particular kind of hardware. As the hardware changes the number of registers to be stored during context switch will change.
- Gone January 10, 2012