home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / mutex.zip / english.read.me next >
Text File  |  1996-07-11  |  7KB  |  119 lines
  1.  
  2.             An particular fast semaphore realization for OS/2.
  3.  
  4. This archive contains the result of my quest in searching for an fast, 
  5. reliable and serialized algorythm for semaphores. Need to say that this
  6. is not an trivial task, as you might think at the first look (at least
  7. I thought so :-) I spent summary about five hours to implement them.
  8. In the last instance I realized that OS/2`s semaphores are not so bad
  9. as you might think - my fully (?) assembler-optimized semaphores are
  10. only three times faster than OS/2`s (and we don`t take into account the
  11. context-switching time which happens each time when we`re calling an
  12. Dos### API function, you know, this is an *very* time-eating operation).
  13.  
  14. For simplest semaphore realization one bit of memory is enough. It is one -
  15. the semaphore is owned; zero - it is not. To grab semaphore you must do two
  16. things in one operation: first, to check if it is not already busy; and
  17. second to set it to 1. This must be done in a single processor-operation
  18. since between any two commands can occur an thread-switch and other 
  19. `aggresive` thread can eventually grab our semaphore. The x8086 processors
  20. have three suitable commands for this: xchg, bts/btr (386+) and cmpxchg (486+).
  21. The first works with at least one byte of memory, second - with one bit and
  22. third - also with one byte. The cmpxchg command was especially designed
  23. for semaphores, although it is a bit obscure (for me, since I lost somewhere
  24. my docs on i486). Let`s try to implement the simplest semaphore algorythm:
  25.  
  26. request: jmp   check
  27. sleep:     call  DosSleep(0)
  28. check:   mov   al,1
  29.          xchg  al,Sem
  30.          test  al,al
  31.          jnz   sleep        ;Semaphore busy, lets check it again
  32.  
  33. For multi-processor systems we also need an LOCK prefix before XCHG command
  34. to prevent two different processors from altering the same variable.
  35.  
  36. This implementation have one major leak: we NEVER can be sure in what 
  37. order the semaphore will be given to some threads that desire it.
  38. And another one is the high degree of posibility that if a thread
  39. owns the semaphore it will own it for a long period of time, even if it
  40. sometimes releases it. This happens when (and because) the time interval
  41. between semaphore releases/requests is VERY short and a task switching
  42. is very likely to not occur. So, thread grabs semaphore again before any
  43. other thread has a chance to get it. As an workaround we can release
  44. thread`s time-slice (DosSleep(0)) right after releasing semaphore, but
  45. what if nobody needs the semaphore?
  46. Another leak in this algorythm is the need for polling semaphore once
  47. in each time-slice until semaphore becomes free - this is an very bad
  48. approach to multi-programming, you know.
  49.  
  50. So, the most optimal algorythm I think is this: on each semaphore request
  51. we first check if semaphore is busy, if not - we`re marking him as owned
  52. and we`re on our way, if it is - we`re adding our thread identifier into
  53. a *queue* associated with this semaphore and we suspend our thread until
  54. current semaphore owner releases it. When semaphore owner releases semaphore,
  55. it checks if there are queued threads waiting for semaphore, if not it
  56. marks semaphore as unowned and that`s it. If there are such threads
  57. it marks semaphore as owned by first thread in queue then releases the
  58. wakes it up. Anyhow, the thread is simply *marked* as released - it does
  59. not receive control immediately, but when OS/2 sheduler passes control to
  60. the thread. And when it will, the thread will already be the owner of
  61. semaphore.
  62. An particular realization of this algorythm is contained in os2SysLib.pas
  63. (this is an subset of my os2SysLib so don`t wonder why the name is so common);
  64. it is specifical for Virtual Pascal; although you can use them with minimal
  65. changes in any other language since it is written fully in assembler;
  66. You only have to replace the Virtual-Pascal specific functions SuspendThread
  67. and ReleaseThread with corresponding functions in your language; if your
  68. language does not have such, use OS/2 API functions DosSuspendThread and
  69. DosReleaseThread; don`t forget that OS/2 API uses C calling sequence so you
  70. have to remove parameters from stack after call.
  71.  
  72. For a comparison of these semaphores and OS/2`s native semaphores I wrote 
  73. three tiny programs: they`re in subdirectory tests/. TestSem.pas shows
  74. how the semaphore works: it launches fifteen threads each writing with
  75. its own color numbers from one to nine and between numbers it yields to
  76. operating system calling DosSleep(0) to give other threads more chances
  77. to run and try to break the fsmRequest() barrier.
  78.  
  79. For an effectivity comparison of these and OS/2 native semaphores I wrote
  80. three tiny programs placed in tests/ subdirectory. First, called TestSem.pas,
  81. runs fifteen identical threads each of which writes to screen using an unical 
  82. color numbers from one to nine; between output of each two numbers thread 
  83. gives up its current time slice yielding DosSleep(0), to give other threads
  84. more chances to run and to break fmsRequest() - fmsRelease() barrier. Second,
  85. TestStdSem does the same, but using standard OS/2 mutex semaphores. The speed
  86. difference between these two programs is unnoticeable since it takes many
  87. more time to draw text on screen (and to sleep) than to request/release
  88. a semaphore. To test the speed difference I wrote third program - it computes
  89. the number of Request/Release pairs per second for OS/2 standard and for
  90. proposed semaphores. Run BenchSem.exe and see what is the difference.
  91. On my 486DX4/100 it is about three times - not too much but I wrote 
  92. these semaphores primarily for an full-screen graphics library where
  93. any speedup is welcome.
  94.  
  95. The source code was written in demonstrational version of Virtual Pascal,
  96. so they will compile without changes in commercial version too. Since license
  97. agreement for demo version prohibits spreading of the executable modules
  98. produced by demo version, I made a few changes and recompiled sources
  99. using early demo version of Virtual Pascal which is (I presume) free.
  100. I done this for those of you who do not use Virtual Pascal, but are
  101. interested in the matter of semaphores.
  102.  
  103. The source code is provided as-is. The author is not responsible for any
  104. damage caused by errors in source code and for spelling/grammatical errors
  105. in this text. The permission is granted to use it for any purpose except
  106. military ones :-)
  107.  
  108. I will be very glad if someone will tell me how I can do them even faster.
  109. This primarily can be achieved (?) by using cmpxchg command instead of
  110. bts/btr & xchg that I used.
  111.  
  112. How to contact me:
  113.    fidoNet: 2:5030/84.5@fidonet
  114.    e-mail:  bit@freya.etu.ru
  115.  
  116. Your sincerely,
  117.    _\ndy Zabolotny
  118.  
  119.