ExerSemaphoresHT11.pdf
Document Details

Uploaded by CleanestTriumph6870
Lund University
2011
Tags
Related
- Advanced Computer Science For The IB Diploma Program PDF
- Computer Operator & Programming Assistant Year 1 JAVA S1.pdf
- B.E-in-Computer-Science-Engineering-updated-on-31.08.2018-5th-CSE-ISE-Open-Elective.pdf
- COMP 1000 Computer Science I Exam 2 Review - PDF
- Computer Science Review PDF
- Java Programming Tutorial PDF
Full Transcript
Exercises and Lab Preparations EDA040 Exercise 1 - Semaphores Basic knowledge of Threads, Semaphores and Java is assumed Exercises 1. Sometimes, multiple threads in a program write to the same file concurrently. One example is a console window such as the Java console in Netscape. A common problem i...
Exercises and Lab Preparations EDA040 Exercise 1 - Semaphores Basic knowledge of Threads, Semaphores and Java is assumed Exercises 1. Sometimes, multiple threads in a program write to the same file concurrently. One example is a console window such as the Java console in Netscape. A common problem is that the interleaving of output from different threads is unpredictable and may result in a hardly readable result. Show, by using a Semaphore, how the output from a sequence of print or println calls of Javas System.out can be ensured to be printed without getting mixed with output from other threads. 2. Even if the printout from one thread only consists of a single println call, certain types of real-time systems do not ensure that a single line is not interrupted by more urgent printouts. We then have a problem similar to the one in Exercise 1, but for individual characters. It is also common that embedded systems (that is, systems with built-in computers) have such textual output on a simple serial port. That port is then a shared resource and we could use a semaphore to protect it just like in Exercise 1. Another solution to the problem in is to introduce an additional thread which is the only one that may use the output port. Review the program below and complete the code in the getLine method. The requirement is that only one thread at a time may write, and additional writers should be blocked by the semaphore. 3. In Exercise 1 the problem of mutual exclusion was solved by requiring the calling threads to use the semaphore in a proper way. In Exercise 2 we handled the semaphores internally in the class/object. Comment on the differences between these two approaches. Which is the easiest and safest way of programming? Why? 4. In the program provided for Exercise 2, there is a semaphore free. Assume you want to provide buffering of up to 8 lines without blocking the callers. How should the program then be changed? Hints: Consider the alternative constructor (taking an argument) of the class CountingSem. A so called ring-buffer is an efficient type of circular buffer that can easily be implemented by an ordinary array. August 2011 http://www.cs.lth.se/EDA040 1 Exercises and Lab Preparations EDA040 5. What will happen if you swap the order of the calls free.take(); mutex.take(); so that you instead do mutex.take(); free.take();? Program RTsemBuffer.java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 import s e. l t h. c s. r e a l t i m e. semaphore. ∗ ; /∗ ∗ ∗ S im p l e p r o d u c e r / consumer example u s i n g semaphores. ∗ The c o m p l e t e example , i n c l u d i n g a l l c l a s s e s , i s p u t i n one o u t e r c l a s s. ∗ That l e t s us k e e p i t a l l i n one f i l e. ( Not good f o r l a r g e r programs. ) ∗/ public c l a s s RTsemBuffer { /∗ ∗ ∗ S t a t i c s t u f f which p e r m i t s t h e c l a s s t o be c a l l e d as a program. ∗/ public s t a t i c void main ( S t r i n g a r g s [ ] ) { // S i n c e t h i s i s a s t a t i c f u n c t i o n , we can o n l y a c c e s s s t a t i c d a t a. // T h e r e f o r e , c r e a t e an i n s t a n c e o f t h i s c l a s s ; run c o n s t r u c t o r : new RTsemBuffer ( ) ; } 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 /∗ ∗ ∗ C o n s t r u c t o r which i n t h i s example a c t s as t h e main program. ∗/ public RTsemBuffer ( ) { B u f f e r b u f f = new B u f f e r ( ) ; Pro duce r p = new Pro duce r ( b u f f ) ; Consumer c = new Consumer ( b u f f ) ; c. start (); p. start (); System. out. p r i n t l n ( ” \n\n”+” RTsemBuffer : Threads a r e r u n n i n g... ” ) ; try { p. join (); // Give comsumer 10 s t o c o m p l e t e i t s work , t h e n s t o p i t. Thread. s l e e p ( 1 0 0 0 0 ) ; c. i n t e r r u p t ( ) ; // T e l l consumer t o s t o p. c. j o i n ( ) ; // Wait u n t i l r e a l l y s t o p p e d. } catch ( I n t e r r u p t e d E x c e p t i o n e ) { /∗ Continue t e r m i n a t i o n... ∗/ } ; System. out. p r i n t l n ( ” \n”+” RTsemBuffer : E x e c u t i o n c o m p l e t e t ! ” ) ; } 37 August 2011 http://www.cs.lth.se/EDA040 2 Exercises and Lab Preparations 38 39 40 41 42 43 44 45 EDA040 /∗ ∗ ∗ The b u f f e r. ∗/ class Buffer { Semaphore mutex ; // For mutual e x c l u s i o n b l o c k i n g. Semaphore f r e e ; // For b u f f e r f u l l b l o c k i n g. Semaphore a v a i l ; // For b l o c k i n g when no d a t a i s a v a i l a b l e. S t r i n g b u f f D a t a ; // The a c t u a l b u f f e r. 46 Buffer () { mutex = new MutexSem ( ) ; f r e e = new CountingSem ( 1 ) ; a v a i l = new CountingSem ( ) ; } 47 48 49 50 51 52 void p u t L i n e ( S t r i n g i n p u t ) { f r e e. t a k e ( ) ; // Wait f o r b u f f e r empty. mutex. t a k e ( ) ; // Wait f o r e x c l u s i v e a c c e s s. b u f f D a t a = new S t r i n g ( i n p u t ) ; // S t o r e copy o f o b j e c t. mutex. g i v e ( ) ; // Allow o t h e r s t o a c c e s s. a v a i l. g i v e ( ) ; // Allow o t h e r s t o g e t l i n e. } 53 54 55 56 57 58 59 60 String getLine () { // Exercise 2... // Here you should add code so that if the buffer is empty, the // calling process is delayed until a line becomes available. // A caller of putLine hanging on buffer full should be released. //... } 61 62 63 64 65 66 67 68 } 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 /∗ ∗ ∗ The p r o d u c e r. ∗/ c l a s s Pro duce r extends Thread { Buffer theBuffer ; Pro duce r ( B u f f e r b ) { super ( ) ; // C o n s t r u c t t h e a c t u a l t h r e a d o b j e c t. theBuffer = b ; } public void run ( ) { S t r i n g producedData = ” ” ; try { while ( true ) { i f ( producedData. l e n g t h () >75) break ; producedData = new S t r i n g ( ” Hi ! ”+producedData ) ; s l e e p ( 1 0 0 0 ) ; // I t t a k e s a s ec o nd t o o b t a i n d a t a. t h e B u f f e r. p u t L i n e ( producedData ) ; } } catch ( E x c e p t i o n e ) { // J u s t l e t t h r e a d t e r m i n a t e ( i. e. , r e t u r n from run ). } } // run } // Producer 94 August 2011 http://www.cs.lth.se/EDA040 3 Exercises and Lab Preparations 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 EDA040 /∗ ∗ ∗ The Consumer. ∗/ c l a s s Consumer extends Thread { Buffer theBuffer ; Consumer ( B u f f e r b ) { super ( ) ; theBuffer = b ; } public void run ( ) { try { s l e e p ( 1 0 0 0 0 ) ; // 10 s u n t i l work s t a r t s. while ( true ) { System. out. p r i n t l n ( t h e B u f f e r. g e t L i n e ( ) ) ; } } catch ( E x c e p t i o n e ) { /∗ Let t h r e a d t e r m i n a t e. ∗/ } ; } // run } // Consumer } // RTsemBuffer August 2011 http://www.cs.lth.se/EDA040 4 Exercises and Lab Preparations EDA040 Exercise 2 - Lab 1 Preparation The programming task - AlarmClock The control program for an alarm clock is to be developed. With the knowledge of threads and semaphores from exercise session 1, the basic design will be made during the exercise session. The software should be fully implemented and tested during the laboratory session. That requires substantial work to be carried out between the exercise and the lab. The testing is done by linking the control software to an applet that emulates the hardware. The physical hardware is under development but possibly not available during the lab. Concerning the interface between the control software and hardware (i.e., the same interface as to the classes emulating the hardware), it mainly consists of three parts: Input: Obtaining input from buttons and time settings as done by the user. Output: Display of current clock time and giving alarm signal. Time: Obtaining the real-time clock, i.e., the time base. There are specific available interfaces, in terms of a Java classes presented below, which model the functionality of the hardware. These classes are available in a package named done. Additionally, in the emulation case, there are some classes in the done package that implement the graphical user interface (GUI). Those GUI classes can, however, not be accessed from the control software. In this way, we ensure that the classes developed by you will actually run on the real hardware (without any changes of the source code). Synchronization and mutual exclusion are to be handled by using semaphores. Your task is to develop the classes in the todo package in such a way that the following specifications are fulfilled. Specifications 1. The displayed clock time should be updated every second. When the user has selected Set alarm or Set time, the hardware/emulator shows the set time and an update of the clock time will have no effect on the clock. However, to better verify that the software keeps track of time, August 2011 http://www.cs.lth.se/EDA040 5 Exercises and Lab Preparations EDA040 and for convenience during testing, the clock time is displayed on an additional information panel below the actual clock panel. Therefore, update the clock time every second regardless of mode. 2. It should be possible to set the clock time and the alarm time. The hardware/emulator internally handles the actual setting/editing of the time value. When the user selects another mode, the set value is written to the ClockInput object and give is called for its semaphore. For example, the user selects Set alarm and edits (using number keys or arrows) the alarm time. Nothing needs to be done by the control software. Then the user selects Time and the time maintained according to previous item is automatically displayed. Also, the alarm time set by the user gets available in the ClockInput and give is called on the semaphore. 3. When the clock time is equal to the alarm time, and the Alarm on is selected, the alarm should beep once a second for 20 seconds1. The sound should be turned off if the user pushes any button while the alarm is sounding. 4. The program should be written in Java, using the Thread class. All synchronization and mutual exclusion shall be achieved by using semaphores. Lab preparation You will design a realtime system for the AlarmClock using threads, semaphores and the provided hardware interfaces. Express your design in class diagrams and in Java code where necessary. Your design need to answer the following questions: 1. Which parallel activities are needed, i.e., which are the thread objects you need? 2. What global data structures (abstract data types which we call passive objects) are needed. What operation should they support? Will these objects be accessed concurrently from different threads, that is, do you need to provide mutual exclusion? 1 The ClockOutput.doAlarm() method only makes one beep. August 2011 http://www.cs.lth.se/EDA040 6 Exercises and Lab Preparations EDA040 3. Are there other situations where semaphores are needed for synchronization? 4. If you in a thread wait for the next second by simply calling sleep(1000), what will the effect on the clock time be? Is this ok for alarm clock time updating? Can it be improved? Handout code You will get a simulator for this assignment that emulates the AlarmClock hardware (display and buttons). The handout code consists of two Java packages called done and todo. The done package contains the simulator (as an applet) as well as hardware interfaces (ClockInput and ClockOutput). The todo package will contain your realtime system. The package right now contains one class, AlarmClock, that contains a sample implementation beeping upon key presses. You will modify and extend todo with classes as you deem necessary for your system. AlarmClock class 1 2 3 4 package todo ; import done. ∗ ; import s e. l t h. c s. r e a l t i m e. semaphore. Semaphore ; import s e. l t h. c s. r e a l t i m e. semaphore. MutexSem ; 5 6 7 8 9 public c l a s s AlarmClock extends private s t a t i c C l o c k I n p u t private s t a t i c ClockOutput private s t a t i c Semaphore Thread { input ; ou tp ut ; sem ; 10 public AlarmClock ( C l o c k I n p u t i , ClockOutput o ) { input = i ; ou tp ut = o ; sem = i n p u t. g e t S e m a p h o r e I n s t a n c e ( ) ; } 11 12 13 14 15 16 // The AlarmClock t h r e a d i s s t a r t e d by t h e s i m u l a t o r. No // need t o s t a r t i t by y o u r s e l f , i f you do you w i l l g e t // an I l l e g a l T h r e a d S t a t e E x c e p t i o n. The i m p l e m e n t a t i o n // b e l o w i s a s i m p l e a l a r m c l o c k t h r e a d t h a t b e e p s upon // each k e y p r e s s. To be m o d i f i e d i n t h e l a b. public void run ( ) { while ( true ) { sem. t a k e ( ) ; ou tp ut. doAlarm ( ) ; } } 17 18 19 20 21 22 23 24 25 26 27 28 } August 2011 http://www.cs.lth.se/EDA040 7 Exercises and Lab Preparations EDA040 Looking inside the simulator for a moment, what is happening at startup is that the simulator creates an instance of your AlarmClock class and starts a new thread on the resulting object. The new thread starts executing in the AlarmClock.run() method. Simulator excerpt: AlarmClock startup code 1 2 3 4 5 6 C l o c k I n p u t b u t t 2 c t r l ; // I n t e r f a c e t o u s e r a c t i o n s v i a hardware / s o f t w a r e. ClockOutput c t r l 2 d i s p ; // I n t e r f a c e t o d i s p l a y hardware / s o f t w a r e. AlarmClock c o n t r o l ; // The a c t u a l alarm−c l o c k s o f t w a r e. //... c o n t r o l = new AlarmClock ( b u t t 2 c t r l , c t r l 2 d i s p ) ; control. start ( ) ; In the same manner, when the applet is stopped (corresponding to hardware reset), there is a call control.terminate(); which you need to override, if you want to fulfil the optional specification item 5. The following classes are the ClockOutput and the ClockInput that describe the interface between the control software and the clock hardware/emulator. Make sure you understand the comment on the ClockInput.getValue method. Excerpt from ClockOutput class 1 package done ; 2 3 public c l a s s ClockOutput { 4 /∗ ∗ ∗ Wake−up c l o c k u s e r. ∗/ public void doAlarm ( ) {... } 5 6 7 8 9 /∗ ∗ ∗ I f t h e d i s p l a y i s c u r r e n t l y used t o d i s p l a y t h e time , u p d a t e i t. ∗ I f u s e r i s u s i n g d i s p l a y f o r s e t t i n g c l o c k or alarm time , do ∗ n o t h i n g when w i t h a c t u a l hardware or show i n f o when s i m u l a t i n g. ∗/ public void showTime ( i n t hhmmss ) {... } 10 11 12 13 14 15 16 } August 2011 http://www.cs.lth.se/EDA040 8 Exercises and Lab Preparations EDA040 Excerpt from ClockInput class 1 2 package done ; import s e. l t h. c s. r e a l t i m e. semaphore. ∗ ; 3 4 public c l a s s C l o c k I n p u t { 5 /∗ ∗ ∗ Semaphore s i g n a l i n g when t h e u s e r have changed any s e t t i n g. ∗ Get−method t o a c c e s s t h e semaphore i n s t a n c e d i r e c t l y. ∗/ public Semaphore g e t S e m a p h o r e I n s t a n c e ( ) {... } 6 7 8 9 10 11 /∗ Package a t t r i b u t e s , boolean alarmOn ; // int c h o i c e ; // int l a s t V a l u e S e t ; // 12 13 14 15 o n l y used by t h e s i m u l a t o r / hardware. ∗/ Alarm a c t i v a t i o n a c c o r d i n g t o c h e c k b o x. The r a d i o −b u t t o n c h o i c e. Value from l a s t c l o c k or alarm s e t op. 16 /∗ ∗ ∗ Get check−box s t a t e. ∗/ public boolean getAlarmFlag ( ) {... } 17 18 19 20 21 /∗ ∗ ∗ Return v a l u e s f o r g e t C h o i c e. ∗/ public s t a t i c f i n a l i n t SHOW TIME public s t a t i c f i n a l i n t SET ALARM public s t a t i c f i n a l i n t SET TIME 22 23 24 25 26 27 = 0; = 1; = 2; 28 /∗ ∗ ∗ Get r a d i o −b u t t o n s c h o i c e. ∗/ public i n t g e t C h o i c e ( ) {... } 29 30 31 32 33 /∗ ∗ ∗ When g e t C h o i c e r e t u r n s a new c h o i c e , and t h e p r e v i o u s c h o i c e ∗ was e i t h e r SET ALARM or SET TIME , t h e s e t −v a l u e o f t h e d i s p l a y ∗ i s r e t u r n e d i n t h e f o r m a t hhmmss where h , m, and s d e n o t e s ∗ hours , minutes , and s e c o n d s d i g i t s r e s p e c t i v e l y. This means , ∗ f o r example , t h a t t h e hour v a l u e i s o b t a i n e d by d i v i d i n g t h e ∗ r e t u r n v a l u e by 1 0 0 0 0. ∗/ public i n t g e t V a l u e ( ) {... } 34 35 36 37 38 39 40 41 42 43 } August 2011 http://www.cs.lth.se/EDA040 9 Exercises and Lab Preparations EDA040 Using the simulator First, you must click somewhere on the image of the clock to give the applet keyboard focus (light blue area). Clicking the check box or another window will steal keyboard focus again. Hold Shift to set clock time (button 1). Hold Ctrl to set alarm time (button 3). Hold Shift+Ctrl to toggle alarm on or off. Use direction keys for buttons 2-6. The tow lines on the LCD display should be fairly obvious. The first line displays the current clock time. The second line displays the alarm time. When the alarm is set the separators in the alarm time turn into colons, otherwise they remain as underscores. When the alarm is beeping the separators will flash with the beeps of the alarm. Below the buttons is a small status field which displays the alarm status with a check box and the current input mode with three radio buttons. The radio buttons may not be manipulated directly, but the check box can be used to modify the alarm status (on/off). When either of the modes Set Time or Set Alarm is active the user may increase the digit under the cursor (indicated by an underscore) by pressing the up button (2), decrease the digit under the cursor with the down button (5), shift cursor left with the left button (4) and shift cursor right with the right button (6). August 2011 http://www.cs.lth.se/EDA040 10