In synchronization, when one process is in a critical section & another is busy waiting, both are using CPU. But in a uni processor system, in the same clock both cant get the CPU. So there must be a scheduling algorithm for them. Should we consider these while solving synchronization problem or should we think both are doing their work on the same clock while we solve problems in synchronization?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
It is very common to run processes on an operating system with a preemptive scheduler. The scheduler can switch between processes at any time: it is unpredictable when the operating system will switch from one process to another.
Unless otherwise specified, this is the model we use when discussing synchronization problems: there may be a switch between processes at any time. This means that in many cases there is no difference between the uniprocessor case and the multiprocessor case: the same execution sequences are possible in both. The operating system effectively pretends that there's one CPU per process.
The switches can even happen in the middle of a high-level instruction. For example, if you write a simple assignment in a high-level language
x := y;
this could translate to multiple machine instructions such as
copy top half from x to y
[possible switch]
copy bottom half from x to y
or
load x to register r1
[possible switch]
store y from register r1
This is why it's important to know which operations are atomic even in the uniprocessor case.
When you consider synchronization between kernel threads, and you get down to the level of machine instructions, there are things that are not possible in a uniprocessor case, because the kernel decides when a context switch is possible. But to exclude these impossible sequences, you need to know both how the machine instructions work and how the kernel works. If you don't know that then you can't exclude any interleaving of the execution.
answered Aug 25, 2017 at 5:55
Gilles 'SO- stop being evil'Gilles 'SO- stop being evil'
44k8 gold badges118 silver badges184 bronze badges
-
$\begingroup$ "The switches can even happen in the middle of a high-level instruction" Thank you. Point. I am asking about the simple problems with lock variable, interested variable, Peterson's solution etc & problems related to this. Not in practically implemented way but when logically asked to verify mutual exclusion, progress, bounded waiting are satisfied or not. While solving the problems related to this, while analysing the problems should I consider both processes are getting CPU at the same instance? @Giles sir $\endgroup$ Commented Aug 25, 2017 at 6:15
-
1$\begingroup$ @AhwanMishra I think the most useful mental model is that the processes are running on separate CPUs, but they are only progressing one at a time. It's hard to reason about things changing at the same time (but of course sometimes you need to). $\endgroup$ Commented Aug 25, 2017 at 8:56