1. ## Semaphore script

Hello, i have problem with a semaphore script. There must be 3 printers and we have 7 books to print which have 7 chapters each.
Printing times each chapter:
Ch1 => 5 seconds
Ch2 => 6s
Ch3 => 7s
Ch4 => 4s
Ch5 => 5s
Ch6 => 6s
Ch7 => 3s

Any ideas how to write script and solve this problem as fastes we can ?

2. The underlying problem is a bin packing or multiple knapsack problem, and is well researched and known.

In your case, there are three equivalent printers, with seven separate jobs with different durations. I gather that the task is to find the job distribution (to the three printers) that yields the shortest completion time. (The completion time being, obviously, the most time taken by one of the three printers to print its jobs.)

At the core, the problem is to find the printer used for each chapter. This is combinatorics. Because there are seven chapters to print, and each chapter can be printed by one of the three printers, there are 3󫢫󫢫󫢫 = 37 = 2187 possible combinations. (This does include the symmetry cases though; the cases that differ only by how the printers are labeled.)

The total printing duration is a constant, 5+6+7+4+5+6+3 = 36 seconds. If evenly divided between the three printers, the soonest that all jobs can be completed is 36/3 = 12 seconds. This does not mean there is a solution where all three printers complete in 12 seconds; it means that if there is such a solution, it is optimal: the best possible.

(It turns out that there indeed are two such packings, each specified by 6 of the 2187 combinations due to symmetries (in naming the printers). In the first one, one printer will print chapters 1 and 3, another will print chapters 2 and 6, and the third will print the remaining chapters 4, 5, and 7. In the second one, one printer will print chapters 1, 4, and 7, another chapters 2 and 6, and the third will print the remaining chapters 3 and 5. In both cases all printers will complete in 12 seconds, in the optimum time.)

I verified this with this Bash one-liner:
Code:
`C=(5 6 7 4 5 6 3) ; for ((I=0;I<2187;I++)); do P=(); D=(); v=\$I ; for ((i=0;i<7;i++)); do k=\$[v%3]; v=\$[v/3]; P[i]=\$k; D[k]=\$[D[k]+C[i]]; done ; D[0]=\$[D[0]] ; D[1]=\$[D[1]] ; D[2]=\$[D[2]] ; M=\${D[0]}; [ \$M -lt \${D[1]} ] && M=\${D[1]} ; [ \$M -lt \${D[2]} ] && M=\${D[2]} ; echo \$M : \${P[@]} : \${D[@]} : \$I ; done | sort -rg`
The first number in the output is the time the slowest printer completes (thus the total duration of the print jobs), the next seven indicate the printer used for each chapter (0 is first printer, 1 is second printer, and 2 is third printer), the next three numbers indicate the total time taken by each printer, and the last number is the "seed", the value in decimal that in base 3 produced the printer selection. The output is sorted in decreasing total time (first column). Here are the last 25 lines the above outputs:
Code:
```13 : 0 1 2 1 0 2 1 : 10 13 13 : 1263
13 : 0 1 2 1 0 2 0 : 13 10 13 : 534
13 : 0 1 2 0 1 2 0 : 12 11 13 : 588
13 : 0 1 1 2 2 0 2 : 11 13 12 : 1686
13 : 0 1 1 2 0 2 2 : 10 13 13 : 2010
13 : 0 1 1 2 0 2 0 : 13 13 10 : 552
13 : 0 1 1 0 2 2 0 : 12 13 11 : 660
13 : 0 1 0 2 1 2 2 : 12 11 13 : 2082
13 : 0 1 0 1 2 2 1 : 12 13 11 : 1407
13 : 0 0 2 1 2 1 1 : 11 13 12 : 1179
13 : 0 0 2 1 1 2 1 : 11 12 13 : 1341
13 : 0 0 1 2 2 1 2 : 11 13 12 : 1926
13 : 0 0 1 2 1 2 2 : 11 12 13 : 2088
12 : 2 1 2 0 0 1 0 : 12 12 12 : 266
12 : 2 1 0 2 0 1 2 : 12 12 12 : 1760
12 : 2 0 2 1 1 0 1 : 12 12 12 : 857
12 : 2 0 1 2 1 0 2 : 12 12 12 : 1604
12 : 1 2 1 0 0 2 0 : 12 12 12 : 502
12 : 1 2 0 1 0 2 1 : 12 12 12 : 1249
12 : 1 0 2 1 2 0 1 : 12 12 12 : 937
12 : 1 0 1 2 2 0 2 : 12 12 12 : 1684
12 : 0 2 1 0 1 2 0 : 12 12 12 : 582
12 : 0 2 0 1 1 2 1 : 12 12 12 : 1329
12 : 0 1 2 0 2 1 0 : 12 12 12 : 426
12 : 0 1 0 2 2 1 2 : 12 12 12 : 1920```
(We can see from the above output that the seed 266, the 267th combination we tried, produced the first optimal solution.)

What I do not understand here, is
• What is a "semaphore script"?
• What does this have to do with semaphores anyway?
• What do you mean by "as fast as we can"? I'm kind of assuming you want a way to find the best solution (as outlined above).
You could, I guess, also mean that the code should not ponder the possibilities first, because that might take too long, but start printing as soon as possible, sacrificing possibly optimal solutions to get better execution speed. In that case, you typically want a greedy packer, which tend to be a bit more complicated than the slow but sure search for the best possible solution.
(Even a simple online greedy algorithm can find the optimal solution 426 for this particular case.)

3. I have to use:

sem_init
sem_wait
sem_post

I will give you example of how it must work:

Ch1 => 10s
Ch2 => 4s
Ch3 => 6s
Ch4 = > 3s
Ch5 => 7s
CH6 => 3s
Ch7 => 4s

 TIME PRINTERS START 1 2 3 4s Ch1 (10s) Ch2 (4s) Ch3(6s) 6s Ch1 Ch4 (3s) Ch3 7s Ch1 Ch4 Ch5(7s) ... R6(3s)

4. That looks like you're supposed to simulate a printer queue with three printers, and use POSIX semaphores for synchronization and locking. (There being only a single queue, but three printers that can print simultaneously; each printer takes the next job off the shared queue.)

There are a number of approaches, too. For example, you can do the simulation as a state machine using a single process and a single thread, although then you'd need to use sem_trywait() instead of sem_wait(); or you can use multiple POSIX threads (via pthread_create()); or you can use shared memory (either POSIX or memory-mapped) and multiple processes (via fork()). If you can choose, the POSIX threads ones is the practical option, and also the most straightforward.

Then again, with POSIX threads a mutex and a condition variable would make a lot more sense, as it would allow an efficient, robust, but simple dynamic queue...

Can you show the code you have written thus far?

5. better not say anything what i have done, because i dont know how to write in C language ;(

6. Originally Posted by harvio
better not say anything what i have done, because i dont know how to write in C language ;(
Well, I -- and other members here -- are certainly not going to write your code for you.

We're here to help you learn and investigate, and perhaps to become a better developer; not to write your code for you.

As Terry Pratchett said: Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.