Semaphore help

[Jeff]

In another thread, a puzzle was mentioned where the goal is to read a list of words out of a file (one word per line, no spaces) and find the longest word which contains another word in the file (so "form" would qualify if "for" also appears).

I'm using this as a means of trying out fork and semaphore. However, I can't seem to get one process to finish. Here is the code:

Code: Select all

(map set '(in out) (pipe))
(setq sid (semaphore))

(define (score-word channel word , n)
  (setq n 0)
  (dolist (w words)
    (if (find w word) (inc 'n)))
  (write-line (string w ": " n) channel)
  (semaphore sid 1)
  (exit))

(define (score-keeper channel)
  (while (read-line channel)
    (semaphore sid -1)
    (println (current-line)))
  (exit))

(setq keeper-pid (fork (score-keeper in)))
(dolist (w words)
  (fork (score-word out w)))

(exit)

'words is a list of the words. Either score-keeper or the main thread are not terminating, and I can't see why. Anyone with semaphores experience?

[Jeff]

An additional problem is that the score-keeper is not running the same number of times as score-word is...

[Jeff]

This is another interesting item. It seems to fail when forking score-word at the same place every time for me, about 412 words in. Here is some testing code for it:

Code: Select all

(define (score-word channel word , n)
  (setq n 0)
  (dolist (w words)
    (if (find w word) (inc 'n)))
  (write-line (string w ": " n) channel)
  (exit))

(define (score-keeper channel)
  (while (read-line channel)
    (println (current-line))))

(setq pids '())
(define (add-thread word channel)
  (let ((pid (fork (score-word channel word))))
    (if pid
        (begin
          (setq last-pid pid)
          (println "Started thread for " word " (" pid ")")
          pid)
        (begin
          (println "Failed for " word ". Retrying...")
          (println " * waiting on " last-pid)
          (println " * length of pids is " (length pids))
          (wait-pid last-pid)
          (add-thread word channel)))))

(map set '(in out) (pipe))

(dolist (w words)
  (push (add-thread w out) pids))

(map wait-pid pids)
(score-keeper in)

(exit)

[Lutz]

you have to use 'wait-pid' on a thread's process id returned from the 'fork' statement to make a thraed go away after returning. Wee the following program from newlisp-9.2.0/examples/prodcons.lsp

Code: Select all

#!/usr/bin/newlisp

# prodcons.lsp -  Producer/consumer
#
# this program only runs on Mac OS X/Linux/UNIX
#
# usage of 'fork', 'wait-pid', 'semaphore' and 'share'

(if (> (& (last (sys-info)) 0xF) 4) 
	(begin
		(println "this will not run on Win32")
		(exit)))


(constant 'wait -1 'signal 1 'release 0)

(define (consumer n)
	(set 'i 0)
	(while (< i n)
		(semaphore cons-sem wait)
		(println (set 'i (share data)) " <-")
		(semaphore prod-sem signal))  
	(exit))
		
(define (producer n)
	(for (i 1 n)
		(semaphore prod-sem wait)
		(println "-> " (share data i))
		(semaphore cons-sem signal))   
	(exit))


(define (run n)
	(set 'data (share))	
	(share data 0)

	(set 'prod-sem (semaphore)) ; get semaphores
	(set 'cons-sem (semaphore))

	(set 'prod-pid (fork (producer n))) ; start threads
	(set 'cons-pid (fork (consumer n)))
	(semaphore prod-sem signal) ; get producer started

	(wait-pid prod-pid) ; wait for threads to finish
	(wait-pid cons-pid) ; 
	(semaphore cons-sem release) ; release semaphores
	(semaphore prod-sem release))


(run 10)

(exit)

The program syncronizes 2 threads and exchanges info via 'share'

Lutz

[Jeff]

In that last post of mine, I map wait-pid to a list of the pids returned from fork. Then I run score-keeper in the main thread. It's like it locks after so many threads.

[Jeff]

Ok, it appears that I am failing due to creating too many forks. When I reduce the number of forks it will continue, although apparently (while (read-line channel)) does not automatically fail with pipes. I had to use a dotimes over the length of the word list.

[Lutz]

its probably running out of resources. On my MacBook (1.25Gig memory) I can do at least 2000 threads, but it starts to do the wait-pid branch after about 1200 threads.

Lutz

ps: I take this for words:

Code: Select all

(set 'words (map string (rand 50 1500)))

[Jeff]

Then something is wrong. I couldn't get up to 500 on a quad core g5 with four gigs of ram.

[newdep]

The amount of forks is OS configurable and is limited per user. (hardcoded)

Probably your Stacksize per thread is too big... (smaler = more threads)

To resize this you need to hack into your kernel...

But if you have a 64Bit machine, 500 is far too low..

[newdep]

Btw..what Shell are you using when executing newlisp?

[Jeff]

bash. I basically have a script set up to run `time newlisp -e /path/to/file.lsp`.

[Jeff]

Also, the size of the forks may be an issue, but even so, it should be greater than 500. With four gigs of ram and four 2.5 GHz cpus, it should be able to handle just about anything that I could possibly conceive to throw at it (except, perhaps, simple addition in Java, which takes several days to compute).

[newdep]

The amount of memory inside a machine is not the counter for the amount
of tasks/forks. That is a hardcoded counter. But the more memory the more
space is reserved per task. (this is what i remember from the old day on linux
kernels..)

My current linux machine handles 512 forks whereas my OS/2 machine only
handles 128.. the older linux kernel on 386 could only handle 128 too.. iirc..

I dont have a clue how this is done on the OSX BSD release but you should
be able to find some topics on it..


Using Bash, you could have a task limit per user (normaly not) but checkout the "ulimit" command perhpas its set...