Return to Main Page
GeSHi © 2004, Nigel McNie.
  1. /* -----------------------------------------------------------
  2. /* NAME : Thomas Stout User ID: tstout
  3. /* DUE DATE : 12/9/2005
  4. /* PROGRAM ASSIGNMENT : mini-project
  5. /*
  6. /* FILE NAME : README
  7. /* --------------------------------------------------------- */
  8.  
  9. Explain how each thread obtains its stack space.
  10. For both versions, the program first calculates by what value the stack pointer
  11. should be changed to reserve the requested amount of stack space for the thread.
  12. Next, it passes this value on to the function THREAD_INIT(), this function has
  13. different versions depending on what platform the system is running on.
  14. Solaris:
  15. First, the program executes a setjmp() to save the current threads context.
  16. Next, the program moves the value of the stack pointer by the value that is
  17. passed in to the function. Then, the stack pointer is manually moved,
  18. reserving the space that it was moved past as the stack space for the new
  19. thread. Next, a setjmp() is called to save the current context to be used by
  20. the newly created thread. Then a longjmp() is used to cause the original
  21. thread to continue exectution. When the context that was saved for the new
  22. thread is eventually loaded, the thread will call THREAD_WRAP(), which will
  23. cause its function to run.
  24. Linux:
  25. In Linux, the altered value for the stack pointer can be directly written to
  26. the jump_buf context of the new process. Since this can be done directly,
  27. there is no need for the linux version to use assembly instructions to move
  28. the stack pointer and then call setjmp() to save the value to the jump_buf.
  29. The adderss of THREAD_WRAP() is also written directly into the program
  30. counter stored in the jump_buf, so that that function will be run when the
  31. thread is resumed with a call to longjmp().
  32. When a longjmp() is eventually called that points the jump_buf that stores the
  33. context of the new process, the process will be loaded in with the modified
  34. value of the stack pointer, preserving this threads stack space.
  35.  
  36. Why is the call to function THREAD_WRAP() necessary?
  37. The call to THREAD_WRAP() is used to cause the thread to run the appropriate
  38. function the first time that its jump_buf is used to restore the threads
  39. context. The THREAD_WRAP() function is the first function executed when a new
  40. thread is resumed, regardless of the platform that the thread system is running
  41. on.
  42.  
  43. How does this system perform context switching?
  44. This system performs context switching using setjmp() and longjmp(). A jump_buf
  45. is stored for each thread, storing the threads current context. This allows for
  46. the calls to THREAD_SCHEDULER() to perform a SaveEnvironment (setjmp) to save a
  47. threads context, and perform a RestoreEnvironment (longjmp) to restore the
  48. threads context. This system doesn't suffer from the problems of corrupted
  49. stacks, like setjmp() and longjmp() usually would, because the values of the
  50. stack pointers that are stored in the jump_bufs are altered when the thread is
  51. initially created, to make sure that the thread has its own stack space.
  52.  
  53. Why is this system using a non-preemptive scheduling policy? Suggest a way of
  54. using a preemptive scheduling policy.
  55. The system is using a non-preemptive scheduling policy because this ensures that
  56. the portions of code in the semaphores and mutex locks that must be atomic will
  57. not be interupted by a context switch. The system could be converted to a
  58. preemptive system by using a timer. If the timer was set up to cause an
  59. interrupt at regular intervals, the interrupt handler for this timer could make
  60. a call to the THREAD_SCHEDULER() function, which would cause a new process to be
  61. switched in. Before calling THREAD_SCHEDULER(), the interrupt handler would
  62. have to place the currently executing thread back into the ready queue, so that
  63. the thread could be run again at a later time.
  64.  
  65. A detailed description of your implementation of THREAD_JOIN()
  66. For THREAD_JOIN(), first the function makes sure that the thread that they wish
  67. to join with is a valid thread that has not already been terminated. If it is a
  68. running thread, then the function adds the caller to the JoinList queue of the
  69. thread they wish to join, changes the callers status the joining, and runs the
  70. thread scheduler to select a new thread to run.
  71.  
  72. A detailed description of your implementation of THREAD_SUSPEND()
  73. First, the function makes sure that the thread to be suspended is a valid thread
  74. that is not already suspended. Next, it removes the thread to be suspended from
  75. the ready queue. After that, it adds the thread to the suspended queue and
  76. changes the threads status to suspended. Finally, it checks to see if the
  77. thread that was suspended was the currently executing one. If it was, it calls
  78. the thread scheduler to select a new thread to run.
  79.  
  80. A detailed description of your implementation of THREAD_RESUME()
  81. First, the function makes sure thta the thread to be resumed is a valid thread
  82. and that it is suspended. Next, it removes the suspened thread from the suspend
  83. queue. Finally, it adds the thread to the ready queue and changes its status to
  84. ready.
  85.  
  86. A detailed description of your implementation of smokers-sem.c
  87. This program uses semaphores to solve the smokers problem. The following
  88. semaphores a used by the program:
  89. smokers - An 2 dimensional array of semaphores, the first dimension has three
  90. entries, one for each smoker. The second dimension has two entries
  91. one for each ingredient the smoker needs.
  92. table - A 1 dimensional array of semaphores with three entries, one for
  93. each ingredient.
  94. There are three smoker threads created and one agent thread. The smokers all
  95. wait on their own semaphores for the agent to give them the ingredients they
  96. need to make a cigarette. After the agent gives out ingredients, it waits on
  97. the table semaphores for the ingredients that it just gave away to be given back
  98. by the smokers. Once the ingredients are given back, the agent gives away two
  99. ingredients again to another smoker.
  100.  
  101. A detailed description of your implementation of exchange.c
  102. This program uses channels to allow for the sorter threads to communicate with
  103. each other. There is a seperate channel used for each direction for the threads
  104. communication. This is done so that one thread doesn't receive its own message.
  105. The threads all compare the numbers they are holding, and pass the numbers
  106. either left or right based on the sorting algorithm. Upon receiving the new
  107. numbers from their neighbor, each thread updates the numbers they are holding.
  108. The only threads that do not communicate with two neighbors are threads 0 and 4.
  109. Thread zero only talks to thread 1 and thread 4 only talks to thread 3, this
  110. ensures that the sorting algorithm will force the lowest numbers to go down to
  111. thread 0 and force the highest numbers to go up to thread 4.
  112.  
  113. A detailed description of your implementation of ring-leader.c
  114. This program creates N threads with N communication channels that are used for
  115. passing information between the threads. Each thread is given a random UID when
  116. the program starts, and then the leader election algorithm is run, selecting the
  117. thread with the highest UID to be the leader. Threads continuosly pass messages
  118. between each other, representing the highest known UID in the network. Once the
  119. message gets all the back to the original sender, so that a thread is notified
  120. that the highest known UID is their own UID, that thread becomes the leader and
  121. starts circulating the END message, ending the program.
Parsed in 0.012 seconds, using GeSHi 1.0.7.20