home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / compiler / 1383 < prev    next >
Encoding:
Text File  |  1992-08-15  |  3.2 KB  |  66 lines
  1. Newsgroups: comp.compilers
  2. Path: sparky!uunet!decwrl!world!iecc!compilers-sender
  3. From: eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig)
  4. Subject: Multi-Threading and Garbage Collection
  5. Reply-To: eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig)
  6. Organization: The Johns Hopkins University CS Department
  7. Date: Sat, 15 Aug 1992 21:01:21 GMT
  8. Approved: compilers@iecc.cambridge.ma.us
  9. Message-ID: <92-08-082@comp.compilers>
  10. References: <92-08-015@comp.compilers> <92-08-074@comp.compilers>
  11. Keywords: storage, GC, parallel
  12. Sender: compilers-sender@iecc.cambridge.ma.us
  13. Lines: 51
  14.  
  15. boehm@parc.xerox.com (Hans Boehm) writes:
  16. >eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig) writes:
  17. >>
  18. >>    I just don't see how you're going to allow garbage collection to
  19. >>occur _anywhere_ and handle any sort of tagged heap.  Are you assuming
  20. >>that procedure calls and heap allocations are atomic?  What happens if I
  21. >>have to garbage collect while I'm in the middle of allocating a record,
  22. >>and haven't written the length of the record to the heap yet?
  23. >
  24. >There are two ways of dealing with this.  With high allocation rates, you
  25. >probably need to give each thread its own chunk of memory that it can
  26. >allocate from without synchronization.  With lower allocation rates,
  27. >allocation can acquire a lock to prevent conflicts.  The PCR allocator
  28. >acquires and releases a monitor lock (perhaps with some minor shortcut)
  29. >for each allocation.  This isn't free, but the only cost is during
  30. >allocation.  With Cedar-like (or Modula-3 like or C-like) allocation
  31. >frequencies this probably makes sense.  It's almost never a bottleneck.
  32. >With SML-of-NJ like allocation rates, it's a bad idea.
  33.  
  34.     Of course, even if the allocation rate _per_thread_ is fairly low,
  35. one can still get into trouble if the number of threads is very high.  If
  36. enough threads are executing, it becomes likely that _some_ thread is
  37. suspended in the middle of allocation, making any allocation by any other
  38. thread _very_ expensive.  Generally, though, this isn't much of a problem,
  39. since few programs have a lot of threads.  It is another good argument
  40. against a single, multi-process heap (at the operating system lever),
  41. however.
  42.  
  43.     Strangely enough, I've recently stumbled onto a short
  44. communication by Appel relating an interesting brute-force way around this
  45. problem.  One partitions the heap into several pages, and assign these
  46. pages to threads on a as-needed basis; this allows each thread to allocate
  47. without interfering with the others.  When all the pages have run out, a
  48. single, process-level garbage collector is used to recover the garbage
  49. pages.
  50.  
  51.     The _code_ of each thread is examined to determine if it was in
  52. the process of allocating when it was suspended.  If so, the allocation is
  53. completed by the garbage collector by interpreting the machine
  54. instructions of the thread.  This is of course extremely expensive, but
  55. since garbage collection is such a rare event the amortized cost can be
  56. cheaper than manipulating some sort of monitor or semaphore.
  57.  
  58.     (Appel, Andrew W, "Allocation Without Locking," _Soft._Prac._Exp
  59. 19(7) pp. 703-5)
  60.  
  61. --
  62. Jack Eifrig (eifrig@cs.jhu.edu)       The Johns Hopkins University, C.S. Dept.
  63. -- 
  64. Send compilers articles to compilers@iecc.cambridge.ma.us or
  65. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  66.