Generic ======= * Compile and run the above code. The code will fail, why? Correct the code. It fails because we create a queue for positive integers only, yet try to put on the queue a negative integer. Either change the queue to be integers, or dont put negative values on the queue! Here are changes - note two lines replaced and package name changed! with Queue_Pack_Generic; with Ada.Text_IO; use Ada.Text_IO; procedure Queue_Test_Generic is package Queue_Pack_Integer is -- new Queue_Pack_Generic (Element => Positive); new Queue_Pack_Generic (Element => Integer); use Queue_Pack_Integer; Queue : Queue_Type; -- Item : Positive; Item : Integer; begin Enqueue (Item => 10, Queue => Queue); Enqueue (Item => -1, Queue => Queue); Dequeue (Item, Queue); Dequeue (Item, Queue); exception when Queueunderflow => Put("queue underflow"); when Queueoverflow => Put("queue overflow"); end Queue_Test_Generic; * Modify the code to create a second queue that contains at most 6 elements and is used to store the values "Up", "Down", "Spin" and "Turn" of an enumerated data type (i.e. like what you had in last weeks lab!). As below: with Queue_Pack_Generic; with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure Queue_Test_Generic is type My_Element is (Up, Down, Spin, Turn); package Queue_Pack_Integer is new Queue_Pack_Generic (Element => Integer); use Queue_Pack_Integer; package Queue_Pack_Enumerate is new Queue_Pack_Generic (Element => My_Element); use Queue_Pack_Enumerate; Queue1 : Queue_Pack_Integer.Queue_Type; Queue2 : Queue_Pack_Enumerate.Queue_Type; Item1 : Integer; Item2 : My_Element; begin Enqueue (Queue => Queue1, Item => 10 ); Enqueue (Queue => Queue2, Item => Up ); Enqueue (Item => 20, Queue => Queue1); Enqueue (Item => Spin, Queue => Queue2); Enqueue (Queue => Queue1, Item => 30 ); Enqueue (Queue => Queue2, Item => Down ); Dequeue (Item => Item2, Queue => Queue2); Put(Item2'Img); New_Line; Dequeue (Queue => Queue2, Item => Item2 ); Put(Item2'Img); New_Line; Dequeue (Item => Item2, Queue => Queue2); Put(Item2'Img); New_Line; Dequeue (Item => Item1, Queue => Queue1); Put(Item1); New_Line; Dequeue (Queue => Queue1, Item => Item1 ); Put(Item1); New_Line; Dequeue (Item => Item1, Queue => Queue1); Put(Item1); New_Line; exception when Queue_Pack_Integer.Queueunderflow => Put("Int queue underflow"); when Queue_Pack_Integer.Queueoverflow => Put("Int queue overflow"); when Queue_Pack_enumerate.Queueunderflow => Put("Enu queue underflow"); when Queue_Pack_enumerate.Queueoverflow => Put("Eun queue overflow"); end Queue_Test_Generic; * (Not for the lab - but try and modify your code so that you also give the size of the queue as a generic formal parameter. This is not straightforward because of the modular data type!) One way to do this is below (there may well be others). Note that QueueSize only appears twice: a) In its declaration & definition. b) When defining the modulus of Marker. We can eliminate both of these by passing Marker as a generic formal parameter. In queue_pack_generic.ads, remove QueueSize and Marker from the package spec, and add Marker to the generics section. The notation (<>) means 'Marker can be any discrete type': generic type Element is private; type Marker is (<>); package Queue_Pack_Generic is type Queue_Type is limited private; procedure Enqueue (Item: in Element; Queue: in out Queue_Type); procedure Dequeue (Item: out Element; Queue: in out Queue_Type); Queueoverflow, Queueunderflow : exception; private type List is array (Marker'Range) of Element; type Queue_State is (Empty, Filled); type Queue_Type is record Top, Free : Marker := Marker'First; State : Queue_State := Empty; Elements : List; end record; end Queue_Pack_Generic; queue_pack_generic.adb is unchanged. queue_test_generic.adb is changed to use two queues of different length: with Queue_Pack_Generic; with Ada.Text_IO; use Ada.Text_IO; procedure Queue_Test_Generic is type Flavour is ( Up, Down, Spin, Turn ); type Size_10 is mod 10; type Size_6 is mod 6; package Queue_Pack_Integer is new Queue_Pack_Generic (Element => Integer, Marker => Size_10 ); package Queue_Pack_Flavour is new Queue_Pack_Generic( Element => Flavour, Marker => Size_6 ); use Queue_Pack_Flavour, Queue_Pack_Integer; Queue : Queue_Pack_Integer.Queue_Type; FQueue: Queue_Pack_Flavour.Queue_Type; Item : Integer; begin Enqueue (Item => 10, Queue => Queue); Enqueue (Item => -1, Queue => Queue); Dequeue (Item, Queue); Put_Line("1st Dequeue " & Item'Img); Dequeue (Item, Queue); Put_Line("2nd Dequeue " & Item'Img); Put_Line("========="); for I in 1..6 loop Enqueue( Item => Up, Queue => FQueue ); end loop; Put_Line("Succeeded in placing 6 elements in FQueue."); -- If our size limiting worked, this should throw an overflow exception. Enqueue( Item => Up, Queue => FQueue ); Put_Line("Succeeded in placing 7 elements in FQueue."); exception when Queue_Pack_Flavour.Queueunderflow => Put("Flavour queue underflow"); when Queue_Pack_Flavour.Queueoverflow => Put("Flavour overflow"); when Queue_Pack_Integer.Queueunderflow => Put("Integer queue underflow"); when Queue_Pack_Integer.Queueoverflow => Put("Integer overflow"); end Queue_Test_Generic; Note: The two instantiated packages appear in 'use' declarations. This pulls multiple definitions of Enqueue, Dequeue, Queueunderflow, etc into scope. For Enqueue and Dequeue, the types of their parameters are sufficient for the compiler / runtime to deduce which procedure to call - so there is no need to qualify by package name. In contrast, for the variables and the exceptions, there are no such clues, and hence they need to be manually disambiguated, as in 'Queue_Pack_Flavour.Queueunderflow'. Type Extension ============== * Build the above code and run it. Again you will find that it does not work correctly. Determine what is wrong and fix it!! The problem is that the reader_state is never defined to be filled. So we need to modify the definition of enqueue along the following: with Queue_Pack_Object_Base; use Queue_Pack_Object_Base; package Queue_Pack_Object is type Ext_Queue_Type is new Queue_Type with record Reader : Marker := Marker'First; Reader_State : Queue_State := Empty; end record; procedure Read_Queue(Item: out Element; Queue: in out Ext_Queue_Type); procedure Enqueue (Item: in Element; Queue: in out Ext_Queue_Type); end Queue_Pack_Object; package body Queue_Pack_Object is procedure Read_Queue(Item: out Element; Queue: in out Ext_Queue_Type) is begin if Queue.Reader_State = Empty then raise Queueunderflow; end if; Item := Queue.Elements(Queue.Reader); Queue.Reader := Queue.Reader -1; if Queue.Reader = Queue.Free then Queue.Reader_State := Empty; end if; end Read_Queue; procedure Enqueue(Item: in Element; Queue: in out Ext_Queue_Type) is begin Enqueue (Item, Queue_Type(Queue)); Queue.Reader_State := Filled; end Enqueue; end Queue_Pack_Object; * The above read function works from the head of the queue to the tail. Modify this so that we have two functions that share the same pointer, but one function moves the pointer from the head of the queue to the tail, while the other moves the pointer from the tail to the head. Both functions should return the element that the pointer refers to before incrementing/decrementing it. To do this, we modify Queue_Pack_Object to contain a new function. Queue_Pack_Object.ads gains the line procedure Read_Queue_Backwards(Item: out Element; Queue: in out Ext_Queue_Type); Queue_Pack_Object.adb is augmented as follows: package body Queue_Pack_Object is < as before > procedure Read_Queue_Backwards(Item: out Element; Queue: in out Ext_Queue_Type) is begin if Queue.Reader_State = Empty then raise Queueunderflow; end if; Item := Queue.Elements(Queue.Reader); Queue.Reader := Queue.Reader + 1; if Queue.Reader = Queue.Free then Queue.Reader_State := Empty; end if; end Read_Queue_Backwards; end Queue_Pack_Object; Queue_Test_Object also needs changing to call read_queue_backwards. * (At home or later) Re-write the above using generic units. The first question to decide is: what is going to be the generic aspect? For example, we could write a queue where the direction of reading is a generic parameter. However, following previous exercises, we'll make the type of item stored the generic variable. We start by modifying the base: queue_pack_object_generic_base.ads: ----------------------------------- generic type Element is private; package Queue_Pack_Object_Generic_Base is Capacity : constant Positive := 10; type Marker is mod Capacity; type List is array (Marker'Range) of Element; type Queue_State is (Empty, Filled); type Queue_Type is tagged record Top, Free : Marker := Marker'First; State : Queue_State := Empty; Elements : List; end record; procedure Enqueue (Item: in Element; Queue: in out Queue_Type); procedure Dequeue (Item: out Element; Queue: in out Queue_Type); Queueoverflow, Queueunderflow : exception; end Queue_Pack_Object_Generic_Base; queue_pack_object_generic_base.adb: ----------------------------------- Copy over the old body, changing the package name: cat queue_pack_object_base.adb | sed -r -e's/Queue_Pack_Object_Base/Queue_Pack_Object_Generic_Base/g' > queue_pack_object_generic_base.adb (For those unfamiliar with Bash, this statement says: "grab the contents of queue_pack_object_base.adb, replace all ocurrences of Queue_Pack_Object_Base with Queue_Pack_Object_Generic_Base, and write the result into queue_pack_object_generic_base.adb") queue_pack_object_generic.ads: ----------------------------------- with Queue_Pack_Object_Generic_Base; generic type Element is private; package Queue_Pack_Object_Generic is package Defer is new Queue_Pack_Object_Generic_Base( Element ); use Defer; type Ext_Queue_Type is new Queue_Type with record Reader : Marker := Marker'First; Reader_State : Queue_State := Empty; end record; procedure Read_Queue(Item: out Element; Queue: in out Ext_Queue_Type); procedure Read_Queue_Backwards(Item: out Element; Queue: in out Ext_Queue_Type); procedure Enqueue(Item: in Element; Queue: in out Ext_Queue_Type); end Queue_Pack_Object_Generic; queue_pack_object_generic_base.adb: ----------------------------------- As before, the body is the same, barring the package name: cat queue_pack_object.adb | sed -r -e's/Queue_Pack_Object/Queue_Pack_Object_Generic/g' > queue_pack_object_generic.adb And finally, the test code: queue_test_object_generic.adb: ------------------------------ with Queue_Pack_Object_Generic_Base; with Queue_Pack_Object_Generic; with Ada.Text_Io; use Ada.Text_Io; with Ada.Integer_Text_Io; use Ada.Integer_Text_Io; procedure Queue_Test_Object_Generic is type Element is new Positive range 1..1_000; type Cardinal is (North,South,East,West); package EObject is new Queue_Pack_Object_Generic( Element ); package CObject is new Queue_Pack_Object_Generic( Cardinal ); -- These specialisations are needed to get the relevent exceptions. package EBase is new Queue_Pack_Object_Generic_Base( Element ); package CBase is new Queue_Pack_Object_Generic_Base( Cardinal ); use EObject,CObject; E_Queue : EObject.Ext_Queue_Type; E_Item : Element; C_Queue : CObject.Ext_Queue_Type; C_Item : Cardinal; begin Enqueue (Item => 1, Queue => E_Queue); Enqueue (Item => 3, Queue => E_Queue); Enqueue (Item => 5, Queue => E_Queue); Enqueue (Item => 7, Queue => E_Queue); Put_Line("Forwards:"); Read_Queue( E_Item, E_Queue ); Put( E_Item'Img ); Read_Queue( E_Item, E_Queue ); Put( E_Item'Img ); Read_Queue( E_Item, E_Queue ); Put( E_Item'Img ); New_Line; Put_Line("Backwards:"); Read_Queue_Backwards( E_Item, E_Queue ); Put( E_Item'Img ); Read_Queue_Backwards( E_Item, E_Queue ); Put( E_Item'Img ); Read_Queue_Backwards( E_Item, E_Queue ); Put( E_Item'Img ); Read_Queue_Backwards( E_Item, E_Queue ); Put( E_Item'Img ); Enqueue ( North, C_Queue ); Enqueue (Item => South, Queue => C_Queue); Enqueue (Queue => C_Queue, Item => West); Enqueue (Queue => C_Queue, Item => East); New_Line; Put_Line("Forwards:"); Read_Queue( C_Item, C_Queue ); Put( C_Item'Img & " "); Read_Queue( C_Item, C_Queue ); Put( C_Item'Img & " "); Read_Queue( C_Item, C_Queue ); Put( C_Item'Img & " "); New_Line; Put_Line("Backwards:"); Read_Queue_Backwards( C_Item, C_Queue ); Put( C_Item'Img & " "); Read_Queue_Backwards( C_Item, C_Queue ); Put( C_Item'Img & " "); Read_Queue_Backwards( C_Item, C_Queue ); Put( C_Item'Img & " "); Read_Queue_Backwards( C_Item, C_Queue ); Put( C_Item'Img & " "); exception when CBase.queueunderflow => Put("queue underflow in CQ"); when EBase.queueunderflow => Put("queue underflow in EQ"); when CBase.queueoverflow => Put("queue overflow in CQ"); when EBase.Queueoverflow => Put("queue overrflow in EQ"); end Queue_Test_Object_Generic; Tasks ===== * The values printed are obvious, except for "seconds". What does seconds correspond to? Number of seconds from midnight. The resolution of this value is given by System.Tick. * What does delay do and what are its units? (Try modifying the value and see how the output changes.) There are two forms of delay. The one in the lab is a "relative delay" - it delays for a given time relative to the current time. It expects its argument to be of the (floating point) type Duration, defined in the Standard package. (Standard is available by default, you don't need to 'with' it.) The properties of this type are implementation defined. It can be measured by printing out Duration'Delta, Duration'First and Duration'Last. On my desktop with gnatgcc version 4.1.2, the values are: Duration Delta: 1.00000E-09 Duration First: -9.22337E+09 Duration Last: 9.22337E+09 Note that you can specify a negative relative time - this is interpreted as zero. So 'delay -33.0;' and 'delay 0.0;' do the same thing. From the above values, it may appear that you can order the task to pause for, say, 2.0E-09 seconds. The Ada RM lets implementations specify a lower bound (D) on delays supported. For GNAT-gcc, D is 1E-06 seconds. This, along with other implementation-defined aspects of Ada, is documented here: http://gcc.gnu.org/onlinedocs/gcc-3.3.6/gnat_rm/Implementation-Defined-Characteristics.html * Now return to the two_tasks program and have each task print out the time. Play around with the value of the delay parameter. You should convince yourself that you do have first and second task running concurrently. with Ada.Text_IO; use Ada.Text_IO; with Ada.Calendar; procedure Two_Tasks is task First_one; task Second_one; task body First_one is Seconds : Ada.Calendar.Day_Duration; begin for I in 1..10 loop Seconds = Ada.Calendar.Seconds( Ada.Caldendar.Clock ); Put_Line( " Task1 starts " & Seconds'img ); delay 1.0; Seconds = Ada.Calendar.Seconds( Ada.Caldendar.Clock ); Put_Line( " Task1 ends " & Seconds'img ); end loop; end First_One; task body Second_One is Seconds : Ada.Calendar.Day_Duration; begin for I in 1..10 loop Seconds = Ada.Calendar.Seconds( Ada.Caldendar.Clock ); Put_Line( " Task2 starts " & Seconds'img ); delay 2.0; Put_Line( " Task2 ends " & Seconds'img ); end loop; end Second_One; begin null; end Two_Tasks; You should see both Task1 and Task2 start before either of them ends. * For the two task program set the delay to 0.0. What happens? What happens if you remove the delay entirely (or comment it out). In Ada a delay of 0 has a specific meaning - what is it? (Ask your tutor if you are at all unsure). A delay of 0.0 says "run another task if there is another task ready to be run". If the delay command is removed entirely there is no requirement on the runtime environment to timeslice between the tasks. However, although there is no requirement for this to occur, there is also no prohibition. The Ada environment used in the labs maps Ada tasks 1:1 onto Linux kernel threads. This means they are subject to the same timeslicing as everything else using the threads. To give you a sense of scale: a typical Linux kernel will work with timeslices of 10E-2 seconds. The machines in the labs can potentially chew through ~ 2 x 10E7 (machine) instructions in that time. Of course, a thread which executes a blocking operation will be swapped out regardless of how long it has been running for. * In the two task program, how many tasks are there? The answer is NOT two. Show this to be true. There are of course 3 tasks. The parent task, which jumps to the null statement and then waits for the two children to terminate. Replace the null statement with a print out to demonstrate this. * Predict what you think will happen when you run the above code. Then run it and see if you are right. The final value depends on how the tasks interact. In this context, such interaction comes about through writing the shared variable - i.e: task Counter_1 can interfere with task Counter_2's approach to its goal if and only if Counter_1 gets hold of the CPU. As mentioned above, the Linux kernel will timeslice tasks. However, the tasks only execute for 100 iterations of their inner loop. This loop gets compiled to the following 40 statements of (edited) assembler: 804a893: movl $0x1,0xfffffff4(%ebp) 804a89a: cmpl $0x64,0xfffffff4(%ebp) 804a89e: jg 804a901 804a8a0: mov 0xffffffc0(%ebp),%eax 804a8a3: mov (%eax),%eax 804a8a5: mov %eax,0xffffffc4(%ebp) 804a8a8: mov 0xffffffc4(%ebp),%edx 804a8ab: mov 0xfffffff0(%ebp),%eax 804a8ae: cmp %eax,%edx 804a8b0: jle 804a8c5 804a8b2: mov 0xffffffc0(%ebp),%edx 804a8b5: mov (%edx),%edx 804a8b7: mov %edx,0xffffffc8(%ebp) 804a8ba: mov 0xffffffc8(%ebp),%eax 804a8bd: dec %eax 804a8be: mov 0xffffffc0(%ebp),%edx 804a8c1: mov %eax,(%edx) 804a8c3: jmp 804a8e8 804a8c5: mov 0xffffffc0(%ebp),%eax 804a8c8: mov (%eax),%eax 804a8ca: mov %eax,0xffffffcc(%ebp) 804a8cd: mov 0xffffffcc(%ebp),%edx 804a8d0: mov 0xfffffff0(%ebp),%eax 804a8d3: cmp %eax,%edx 804a8d5: jge 804a8e8 804a8d7: mov 0xffffffc0(%ebp),%edx 804a8da: mov (%edx),%edx 804a8dc: mov %edx,0xffffffd0(%ebp) 804a8df: mov 0xffffffd0(%ebp),%eax 804a8e2: inc %eax 804a8e3: mov 0xffffffc0(%ebp),%edx 804a8e6: mov %eax,(%edx) 804a8e8: movl $0x0,(%esp) 804a8ef: movl $0x0,0x4(%esp) 804a8f7: call 8054010 804a8fc: incl 0xfffffff4(%ebp) 804a8ff: jmp 804a89a Now on any given iteration, less that the full 40 statements will be executed, since only one branch will be taken in the inner if-statement. However, working with upper bounds, we can say that a given task's computation will require < 4 x 10E3 instructions. Thus, it is not likely to be timesliced by the kernel. We assume that the only interactions will be triggered by two sources: 1. delay statements. 2. Blocking IO operations (i.e: Put et al). Given the placement of the delay statements, blocking IO will only occur after both tasks have completed their modifications to Sum. Thus, we will disregard it. The delay statements will result in the two processes alternating. Since counter_1 was declared first, it will execute first, and counter_2 will get to make the last adjustment to Sum. So, the computation will proceed in the following stages: A) Both counter_1 and counter_2 decrement sum until Sum = 10. This will take 40 operations, i.e: 20 iterations per task. B) Counter_1 will execute iteration 21, and decrement Sum to 9. C) Counter_2 will execute iteration 21, and increment Sum to 10. And so on, until there are no more iterations to run. In this case, we'd expect the final values for both tasks to be 10. If the goals of the tasks were switched, then we'd expect the result to be 9, since the final task to execute will be seeking 0. * Run the code several times. Does it always give the same output? (A convenient shell command is repeat - eg try typing "repeat 10 counter_test") No you should not always see the same result. Without the delay statement, there is no forced interleaving, but there is still interleaving, triggered by blocking IO (likely) or kernel timeslicing (unlikely given the timescale). In addition, the choice of which thread to run when a given thread blocks can be considered arbitary. (Note: The choice is not random, but is decided by the kernel in a manner that is not relevent here.) Thus, even if timeslicing doesn't interfere, you could get one of the following sequences: counter_1, counter_2, main : Final sum will be 10. counter_1, main, counter_2: Final sum will be 0. If timeslicing _does_ interfere, you could get a variety of values, depending on how much computation is done between successive calls to the (blocking) Put routine. * Above you might have predicted that at least one of the two tasks would have printed out a value of zero for sum. You probably found this was not the case - indeed this does not have to be the case. Make sure you understand why (this is not so simple). The Intel machines used in the labs are based on a load/store architecture. Thus it is possible for one task (A) to load a value (say 5) from memory into a register, then get swapped out. Next another task (B) gets swapped in, loads the same memory value (5) into a register, adds (say 1) to that register and copies the result (6) back to memory. Then the original task (A) gets swapped back in for execution. Adds (say 2) to the register and writes the result (7) back to memory. As a consequence instead of memory containing 5+1+2=8 it contains 7 (or 6 if the tasks were swapped, or 8 if there was no swapping). The above assembler shows that the simple Ada line Sum := Sum + 1 gets translated into around 7 machine statements - a sequence which may be interrupted at any point. * Modify the above code so that sum is a local variable within each task? (Make sure you understand the difference between a local and shared variable - this is of fundamental importance.) Of course move the definition of Sum into body of the task. At runtime, there will be three separate variables called Sum. with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure Counter_Test is Sum : Natural := 50; task type Counter (Goal : Natural); task body Counter is Sum : Natural := 50; begin for I in 1..100 loop if Sum > Goal then Sum := Sum - 1; elsif Sum < Goal then Sum := Sum + 1; end if; delay 0.0; -- try leaving out this delay statement! end loop; Put( "Final value in Counter (task)"); Put(Sum); New_Line; end Counter; Counter_1 : Counter (0); Counter_2 : Counter (10); begin Put( "Final value in Counter_Test "); Put(Sum); New_Line; end Counter_Test; * (If you have time.) Modify the above so that task 1 adds one to the value of the shared sum variable while task 2 subtracts one. Have the tasks alternate, with task 1 adding one first then task 2 subtracting one, then task 1 adding one etc. At each tasks turn have it print out an identifier (i.e. "I'm task 1"), the value of the variable and the current time. You should achieve the above using only access to shared variables (you may want to consider your lecture notes). This is essentially Ben-Ari's first attempt at mutual exclusion. with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; with Ada.Calendar; procedure Alternate is Sum : Integer := 0; Turn : Boolean := True; task type Stepper ( step : Integer; Req : Boolean ); task body Stepper is Seconds : Ada.Calendar.Day_Duration; begin for I in 1..10 loop -- Begin pre-protocol while Turn /= Req loop delay 0.0; end loop; -- Begin critical section Sum := Sum + Step; Seconds = Ada.Caldendar.Seconds( Ada.Caldendar.Clock ); Put( "Task " & step'img & " Time: " & Seconds'Img & " Value: "); Put(sum); New_Line; -- Begin post protocol Turn := not Req; end loop; end Stepper; add : Stepper( Req => True, Step => 1 ); subtract : Stepper( Step => -1, Req => False ); begin null; end Alternate;