Thread: Semaphore script

  1. #1
    Registered User
    Join Date
    Dec 2015
    Posts
    10

    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. #2
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    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. #3
    Registered User
    Join Date
    Dec 2015
    Posts
    10
    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. #4
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    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?
    Last edited by Nominal Animal; 12-03-2015 at 07:11 PM.

  5. #5
    Registered User
    Join Date
    Dec 2015
    Posts
    10
    better not say anything what i have done, because i dont know how to write in C language ;(
    Last edited by harvio; 12-04-2015 at 04:20 PM.

  6. #6
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    Quote Originally Posted by harvio View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Noob Script Help ~ Simple Script Error
    By WiredAnomaly in forum C++ Programming
    Replies: 5
    Last Post: 10-05-2013, 05:57 AM
  2. Replies: 15
    Last Post: 06-16-2011, 05:17 AM
  3. Replies: 3
    Last Post: 11-14-2010, 11:14 AM
  4. Replies: 0
    Last Post: 02-05-2009, 06:59 PM
  5. semaphore
    By menzeli in forum Linux Programming
    Replies: 12
    Last Post: 04-15-2007, 09:26 AM