Concurrent Filtering using Semaphores In this assignment you will need to devise a concurrent program to filter a list of seven distinct numerals and letters. They should be filtered (separated) in such a way that the numerals are moved to the right side of the array and the letters to the left. Consider the following list of numerals and letters. 5, A, 9, M, W, 6, Z [After filtering the resulting list should have the letters occupying the first few positions while the remaining positions should be occupied by numerals. An example of such a resulting list is: A, M, W,Z, 5, 9,6] The program must be constructed in the following manner. Each of the seven elements in the input list is to be stored in an element of a shared array B with seven elements (B[1] ... B[7]) located in a shared memory segment that is shared by a set of concurrent processes. Your program must include three concurrent processes P; (i = 1..3). The list of numerals and letters will be filtered by these processes in the following manner. Every process P; is to be associated with three array elements. P, is associated with B[1], B[2], and B[3]. P2 is associated with B[3] and B[4], and B[5]. Pz is associated with B[5], B[6] and B[7] (see Figure). Every process P repeatedly checks its three elements until the entire list of is filtered. Whenever a process P; (i=1..3) finds a letter in one of its three elements B[k] it swaps it with the element in B[k-1], if B[k-1] is a numeral. P1 P3 P2 Ra B[1] B [2] B[3] B[4] B[5] B[6] B[7] Note that executing for only one cycle may not be enough for a process. This is because an order established by one process P can be disturbed by the reorganization done by another process Pj. Consider for example the unfiltered list of numerals and letters presented earlier. Thus, initially: B[1]= 5;B[2] = A;B[3] =9; B[4]=M;B[5]=W, B[6] = 6, B[7] = Z The processes are independent and can execute is any sequence. Let us consider an example sequence of process execution in which P, executes first. In its first cycle, P, swaps the contents of B[1] and B[2] resulting in B[1]=A, B[2] = 5 and B[3] =9. Assume that the CPU gets switched and P2 executes next and swaps the content of B[4] (M) with that of B[3] (9) so that B[3] = M and so on. If P2 continues the cycle (without a CPU switch taking place) then at the end of its first cycle we will have: B[3] =M, B[4] =W and B[5] =9. The new content of B[3] is a letter and needs to be propagated to the left by P, in its next cycle. Thus, every process Pi (i= 1.3) needs to repeat its cycles until the filtering of the entire list is complete. Once the list is filtered we will get a list with all the letters appearing before the numerals. Note that an array element may be accessed simultaneously by two processes and your design should ensure mutual exclusion. You will need to ensure mutual exclusion by using Linux semaphores. Your program should ensure good concurrency in execution. That is why putting the entire array in one critical section and controlling access to this critical section by a single semaphore is not a good solution. Remember that the processes must continue until all the elements are in order; disorder in any place in the array may propagate further left or right in the array. Once the filtering is over the contents of the array data[i] should be printed. Input: One of the processes in the program should prompt the user for seven distinct elements comprising both letters and numerals. These should then be stored in the elements of the shared array. Output: At the end the program has to print out the filtered list of letters and numerals. Debug Mode: Your program should be able to printout additional information when run in a "debug" mode. When run in this mode, in each iteration of process P; it should print out "Process Pi: performed swapping or Process Pi: No swapping depending on whether or not it swapped any of the array elements (in the current iteration) it is dealing with. Upon start when your program starts executing it should ask the user if the debug mode is to be used. If the answer is yes, the program should generate the additional printouts. No additional printouts are to be generated if the user did not want to use the debug mode. You Job: Devise a semaphore and shared memory based solution to the problem written in C running under Linux. Concurrent Filtering using Semaphores In this assignment you will need to devise a concurrent program to filter a list of seven distinct numerals and letters. They should be filtered (separated) in such a way that the numerals are moved to the right side of the array and the letters to the left. Consider the following list of numerals and letters. 5, A, 9, M, W, 6, Z [After filtering the resulting list should have the letters occupying the first few positions while the remaining positions should be occupied by numerals. An example of such a resulting list is: A, M, W,Z, 5, 9,6] The program must be constructed in the following manner. Each of the seven elements in the input list is to be stored in an element of a shared array B with seven elements (B[1] ... B[7]) located in a shared memory segment that is shared by a set of concurrent processes. Your program must include three concurrent processes P; (i = 1..3). The list of numerals and letters will be filtered by these processes in the following manner. Every process P; is to be associated with three array elements. P, is associated with B[1], B[2], and B[3]. P2 is associated with B[3] and B[4], and B[5]. Pz is associated with B[5], B[6] and B[7] (see Figure). Every process P repeatedly checks its three elements until the entire list of is filtered. Whenever a process P; (i=1..3) finds a letter in one of its three elements B[k] it swaps it with the element in B[k-1], if B[k-1] is a numeral. P1 P3 P2 Ra B[1] B [2] B[3] B[4] B[5] B[6] B[7] Note that executing for only one cycle may not be enough for a process. This is because an order established by one process P can be disturbed by the reorganization done by another process Pj. Consider for example the unfiltered list of numerals and letters presented earlier. Thus, initially: B[1]= 5;B[2] = A;B[3] =9; B[4]=M;B[5]=W, B[6] = 6, B[7] = Z The processes are independent and can execute is any sequence. Let us consider an example sequence of process execution in which P, executes first. In its first cycle, P, swaps the contents of B[1] and B[2] resulting in B[1]=A, B[2] = 5 and B[3] =9. Assume that the CPU gets switched and P2 executes next and swaps the content of B[4] (M) with that of B[3] (9) so that B[3] = M and so on. If P2 continues the cycle (without a CPU switch taking place) then at the end of its first cycle we will have: B[3] =M, B[4] =W and B[5] =9. The new content of B[3] is a letter and needs to be propagated to the left by P, in its next cycle. Thus, every process Pi (i= 1.3) needs to repeat its cycles until the filtering of the entire list is complete. Once the list is filtered we will get a list with all the letters appearing before the numerals. Note that an array element may be accessed simultaneously by two processes and your design should ensure mutual exclusion. You will need to ensure mutual exclusion by using Linux semaphores. Your program should ensure good concurrency in execution. That is why putting the entire array in one critical section and controlling access to this critical section by a single semaphore is not a good solution. Remember that the processes must continue until all the elements are in order; disorder in any place in the array may propagate further left or right in the array. Once the filtering is over the contents of the array data[i] should be printed. Input: One of the processes in the program should prompt the user for seven distinct elements comprising both letters and numerals. These should then be stored in the elements of the shared array. Output: At the end the program has to print out the filtered list of letters and numerals. Debug Mode: Your program should be able to printout additional information when run in a "debug" mode. When run in this mode, in each iteration of process P; it should print out "Process Pi: performed swapping or Process Pi: No swapping depending on whether or not it swapped any of the array elements (in the current iteration) it is dealing with. Upon start when your program starts executing it should ask the user if the debug mode is to be used. If the answer is yes, the program should generate the additional printouts. No additional printouts are to be generated if the user did not want to use the debug mode. You Job: Devise a semaphore and shared memory based solution to the problem written in C running under Linux