1
$\begingroup$

So, I had a quiz last night in my discrete structures class and this question came up:

"There are 3 processors in a computer. The instructions to a computer are labeled 1,2,3,4,5,6,7,8,9,10 each taking 1 second to execute. The relation between a pair of instructions (x,y) is given by R:'x' is executed at the same time or before 'y'. Using the properties of relations, design an execution process including the sequence of execution that takes the minimum time. Relation between the instructions is R={(1,1)(2,2)(3,3)(4,4)(5,5)(6,6)(7,7)(8,8)(9,9)(10,10)(1,7)(5,8)(2,3)(8,10)(5,10)}"

How would I go about solving this? I want to understand how to do it....but I don't know where to start...

2 Answers 2

1

I dont think so. youve got the first instruction called more than once. ive got this:

P1: 1 | 4 | 7 | 10

P2: 2 | 5 | 8

P3: 3 | 6 | 9

Its simple. It only takes four seconds, and all the relationships are satisfied. It is partial order (transitive, reflexive, and antisymmetric) so there is more than one right answer. Also, the 10 could be executed by any of the processors.

  • 0
    I sat in tutoring for 40 minutes trying to figure this one out with our tutor. We had 20 minutes to take the quiz. I'm not sure how anyone could have got this right..2011-03-09
2

The interesting part of $R$ is $ \begin{align*} &1 \leq 7 \\ &2 \leq 3 \\ &5 \leq 8 \leq 10 \end{align*} $ Missing are $4,6,9$.

Does that help?

  • 0
    Yes, that's one solution, although there's no reason to compute $1$ twice. Note also that $4$ seconds is the optimal time since we have more than $9$ jobs.2011-03-09