data structures - Process allocation algorithm -

data structures - Process allocation algorithm -

i read material on algorithms, , ran problem.

we have n processes, each predetermined start , end time. want utilize minimum number of processors in order run these processes.

consider next algorithm:

in step i, select maximum number of unallocated processes don't overlap, , allocate them processor i.

this algorithm finishes when no processes remain unallocated. maximum i output of algorithm. minimum value of n such algorithm not produce optimal answer?

short answer: n=5. don't know how reply reached, though. can explain?

what have here greedy algorithm. greedy algorithm best can @ each step, in hope give optimal solution overall. gives fast algorithm, , sometimes, not always, leads optimal solution.

your algorithm illustration of greedy algorithm provides optimal solution , doesn't. has advantage runs fast in giving approximation optimal solution; that's improve slow algorithm gives optimal solution.

there's of import ambiguity in question. on step i should take maximum number of remaining processes can scheduled on processor i. let's suppose maximum number of processes can scheduled @ moment 2. if there lots of ways of choosing 2 non-overlapping processes? how decide 2 processes?

i'm going resolve ambiguity carefully, side-stepping it. let's algorithm non-deterministically take maximal set of processes schedule on current processor. means can turn question 2 different ones:

what's smallest n algorithm might sub-optimal? is, let's suppose algorithm unlucky in selection of maximal set. how can things go wrong? what's smallest n algorithm is guaranteed sub-optimal? is, let's suppose algorithm lucky, , chooses right maximal set if there one. how can things go wrong?

your statement n=4 tells me you're interpreting first question. think sec question has reply of n=7, though i'm not certain. interesting plenty issue think inquire follow-up question thoughts that!

here's how see things can go wrong, if we're unlucky, n=4. let's talk in terms of time units. example, we'll there 4 time units (four hours of day, if like, , each process takes whole number of hours, starting , finishing on hour). let's suppose have 4 processes need run:

[1] (i.e., process takes first time unit) [2,3,4] (i.e., process needs time units 2 4) [1,2,3] (etc.) [4]

now, there's allocation works 2 processors. on first processor run [1] , [2,3,4]; on sec processor run [1,2,3] , [4]. , our greedy algorithm might find solution , give optimal. might schedule [1] , [4] run on first processor, since maximal set (it puts 2 processes onto first processor). if so, it's left [1,2,3] , [2,3,4], can't run together, it'll end using 3 processors.

it can go wrong, then, n=4. can go wrong n=3? don't think so. there 3 possibilities optimal solution might like: needs 1 processor, or 2 processors, or 3 processors. if optimal solution requires 1 processor, means 3 processes can scheduled @ first step, , our greedy algorithm find solution. if takes 3 processors, no 2 processes can scheduled @ same time, greedy algorithm schedule 1 @ time, , 1 time again find optimal (3 processor) solution. if takes 2 processors, must 2 of processes can run together. if that's right, though, greedy algorithm take 2 processes @ first step. whichever 2 chooses, there 1 left, , scheduled @ sec step. greedy algorithm require 2 processors, 1 time again optimal.

as say, think optimistic case more interesting: what's smallest n algorithm guaranteed sub-optimal? inquire follow-up question that, , link one!

here's follow-up question.

algorithm data-structures greedy