NetApp Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
2
of 2 vote

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree its O(1)

- y so serious? January 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think depends on the number of cores in the machine as each core would add some constant time to perform context switch

- Anonymous September 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think depends on the number of cores in the machine as each core would add some constant time to perform context switch

- Anonymous September 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous September 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

A cache isn't restored on a context switch. It's simply flushed and will "rebuild" as the process executes. The rebuilding is not considered a part of the context switch. Likewise, the paging in/out within the RAM isn't part of the context switch.

- Thomas Edison May 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

But context switch might initiate reading memory pages from swap file, isn't it?

- i.a.borisova September 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Anonymous October 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Anonymous October 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous October 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- tiputiger December 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If the scheduling algorithm is run during the context switch then the switch time could vary from switch to switch.

- Thomas Edison May 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- rnavale1 April 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

My 2 cents
In case of windows os, scheduling is done based on threads and not processes
The scheduling algo looks at thread priority array to find out which highest prio thread can be scheduled to run next
Hence the algo will be < O(n) probably O(priority levels) ~ O(constant)

- Anonymous October 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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).

- Anonymous May 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The size of the ready queue is a constant factor for any processor. So, picking out a process for execution by the scheduler is a constant factor. Hence, O(1) process.

- Aashish July 04, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More