This is what computer science home-works should look like

We have a Spooler S, and a Processor P.

S spools jobs and P processes them.

S can spool 3 jobs per second, while P can process 1 job per second.

We can only have one S but as many Ps as possible.

Since S is three times faster than P, we can assume that for every S start, we need to start 3P. This assumption is WRONG.

If we start S and 3P at the same time, 3P will actually sit idle for a second before they start processing records.

So we need to start 3P after S has spooled the first job. While each of the P is processing the job, S can spool another 3. So every one is happy.

Since we can have as many Ps as we want, we decide to have 9Ps.

We can also assume that we should start 9P after S has completed 3 jobs. WRONG AGAIN

If we go by the above assumption, 9P will process 9 jobs while S fetches 3 jobs.

On the next second, there will be 9P but 3 jobs, so oly 3Ps will be working, 6Ps will be idle, this happens all the time after the first second.

We don’t like idle Ps. So we decided to allow S run 90 times before we start 9P, so that each the Ps have 10 jobs waiting for them before they start.

If you are following me, you know that there will be a point where the Ps will catch up with S.

Questions:

  1. Determine for 20Million jobs if the Ps will ever catch up with S
  2. If the answer above is YES, then determine amount of jobs each P needs to be waiting for them before they start so that they can never catch up with s.
  3. If answer above is NO, then determine how many jobs was needed for the Ps to catch up with S
  4. Write a program that takes the number of Ps and The total amount of jobs needed as input. Your program should output how many jobs S needs to spool before we start the Ps such that they will never catch up with S.

e.g If we have 18 jobs and 6P, then S needs to spool 9 jobs before we start the Ps.

| seconds | jobs | processed | total rema |
| 1 | 3 | 0 | 3 |
| 2 | 3 | 0 | 6 |
| 3 | 3 | 0 | 9 |
| 4 | 3 | 6 | 6 |
| 5 | 3 | 6 | 3 |
| 6 | 3 | 6 | 3 |

Get answer in the comments 😉

Advertisements

1 Comment »

  1. Nice read, technically P stays idle for 1/3 of a second. Unless the assumption is that all Ps must start working at d same time. With this you lose the ability to run the jobs in parallel

RSS feed for comments on this post · TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: