In parallel programming the iteration scheduling is defined as the determination of the logical execution time for each loop iteration, while in operating systems, the processor scheduling (FCFS etc) is defined as the ordering in which the processes get the CPU to execute. Since the execution of a loop is a process itself, i wonder if these terms describe the same thing even though a process is more general than a simple loop that perform pure calculations since, for example, it generally requires additional resources, such as hard disk access. Generally speaking, is there any connection between these terms, or they can used independently of each other? Thanks.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
They are different problems in practice. Task scheduling is about fulfilling constraints, computation scheduling is about minimizing work.
In computing, we know the entire problem in advance and we want to find the optimal schedule (order of operations, split between multiple machines) and then execute it. If we have a product of four matrices ABCD we can solve this as ((AB)C)D or (AB)(CD) or (A(BC))D or A((BC)D) or A(B(CD)). Depending on the shape of the matrices, some of these calculations produce much larger intermediate results than others and consequently run slower. For database queries, we can chose which filter to apply first and this will have a massive performance impact. How to split work between multiple machines for parallel computing (to minimize communication overhead and exploit locality) also falls into this category of scheduling.
Scheduling tasks in an operating system is different. Less science, more practical engineering. The scheduler doesn't know in advance what resources will be requested in the future, so it cannot make optimal decisions. Often a notion of optimality doesn't exist at all, the scheduler just needs to be 'good enough' i.e. not violate any deadlines on the critical tasks.
Strictly speaking, scheduling tasks is also 'scheduling the order of operations' as in my matrix example above, but in practice it's a very different problem: 'find a solution that fulfills all constraints' versus 'unconstrained optimization for least amount of floating point operations.' The goal is different, the constraints are different and the information you have is different.
