Show a trace that demonstrates the problem

Assignment Help Data Structure & Algorithms
Reference no: EM132472237

Problem 1

A bakery shop has to provide a stream of muffins for customers. The muffins are made by a baker in the kitchen and placed on a conveyor belt. The conveyor belt carries the muffins to where the customers are waiting to buy them.

This scenario has been simulated using two processes: the baker and customer, and a shared conveyor belt implemented as a circular array called conveyor, where each space in the array can hold one muffin. There are two shared general semaphores, empty and full, and a mutex buffer_mutex. In this scenario, there is only multiple bakers and a single customer.

The pseudo-code for the baker is as follows. The baker makes use of an integer variable in for noting the next available space on the conveyor belt.
1. while(true){
2. muffin = makeMuffin(); // Create a muffin
3. wait(empty);
4. wait(buffer_mutex);
5. conveyor[in] = muffin; // Put the muffin on the conveyor belt
6. in = (in + 1) mod n;
7. signal(buffer_mutex);
8. signal(full);
9. }
The pseudo-code for the customer is as follows. The customer makes use of an integer variable out for noting the next location on the conveyor belt that contains a muffin.
1. while(true){
2. wait(full);
3. muffin = conveyor[out]; // Get a muffin from the conveyor belt
4. conveyor[out] = null;
5. out = (out + 1) mod n;
6. signal(empty);
7. eat(muffin); // Eat the muffin
8. }
This code should be familiar to you as it is similar to the example of the Producer-Consumer problem. Only a few sentences are required for each of the Problems below.
(20 marks) Explain, in words, the purpose of the mod n statement. Explain what is the purpose of mutex buffer_mutex. What problems solves? You may wish to include simple examples.
(20 marks) Explain what will happen if the order of semaphores in the customer changes. So, we have in line 2 signal(empty) and in line 6 wait(full). Now assume that there is a single baker and a single customer, with an infinite buffer. Explain, in words, what changes should be made and why.
Problem 2 (60 marks)
Some researchers are working in a lab. Due to safety regulations, only five people are allowed in the lab at the same time. The code for each researcher is given below. It uses a semaphore lab, to represent whether there is space left in the lab for more people. S1, S2 and S3 are labels identifying the line code.
Researcher code:
S1: wait(lab);
S2: work();
S3: signal(lab);

(a) There are eight researchers, A, B, C, D, E, F, G and H, working in the lab. Each researcher operates according to the above code. Your task is to give an execution trace that contains both of the following:
The trace should show what happens when there are less than five researches in the lab and one or more of them leave.
The trace should show what happens when there are five researchers in the lab and another researcher or several researchers want to enter.

The trace must start with an empty lab and show all the steps of each of the researchers as they enter/leave.
You must show the value of lab after each wait or signal step. Ensure that you state the initial value of lab.
If a wait operation executes, indicate whether the process succeeds or is placed in the queue. If a signal operation executes, indicate whether the value is changed or a sleeping process is woken up.
Each line of your trace should have the following format:
Statement executed including which Researcher process (e.g., M.S1 means that the researcher named M executed statement S1); the value of the lab semaphore (e.g., lab=2); whether the wait succeeded or was placed in the queue/ whether the signal changed the semaphore value or a sleeping process woke up.
For example: M.S1; lab=2; wait succeeded.

(b) The code has now been modified. Each time a researcher enters the lab, an integer totalEntered is incremented. The variable is initially 0. The new code is given below:
Researcher code:
S1: wait(lab);
S2: totalEntered = totalEntered + 1;
S3: work();
S4: signal(lab);

The code given has a problem. The researchers have found that sometimes the totalEntered value does not reflect the actual number of researchers who have entered the lab.

Explain, in words, how this situation could occur.

Show a trace that demonstrates the problem occurring. Note that you are not being asked to solve the problem.

Reference no: EM132472237

Questions Cloud

Determine whats the present value of discounted back : Determine What's the present value of $5,000 discounted back 5 years if the appropriate interest rate is 4.5%, compounded semiannually?
Compute the sharpe ratios of the fund and gold : Compute the Sharpe ratios of the fund and gold. Based only on these ratios, how desirable does investment in the fund by itself compare to investment
Prepare schedule of cost of goods manufactured in good form : Prepare schedule of cost of goods manufactured in good form. cost of goods sold section of Mason Company's income statement for the year.
What rate of return is built into the annuity : Receiving $3,500,000 today or a 20-year annuity of $250,000, with the first payment coming one year from today. What rate of return is built into the annuity
Show a trace that demonstrates the problem : Show a trace that demonstrates the problem occurring. Note that you are not being asked to solve the problem and The trace should show what happens when there a
How much could withdraw at the end of each of the next : Suppose you earned a $505,000 bonus this year and invested it at 8.25% per year. How much could you withdraw at the end of each of the next 20 years?
Describe the type of financial statement : Describe the type of financial statement information about these companies (separate or consolidated) that you would request.
What changes should be made and why : Assume that there is a single baker and a single customer, with an infinite buffer. Explain, in words, what changes should be made and why
What is the present value of the minimum lease payments : Rental of $210 per month (at end of each month). (The present value at 1% per month is $8,232.) What is the present value of the minimum lease payments

Reviews

Write a Review

 

Data Structure & Algorithms Questions & Answers

  Implement an open hash table

In this programming assignment you will implement an open hash table and compare the performance of four hash functions using various prime table sizes.

  Use a search tree to find the solution

Explain how will use a search tree to find the solution.

  How to access virtualised applications through unicore

How to access virtualised applications through UNICORE

  Recursive tree algorithms

Write a recursive function to determine if a binary tree is a binary search tree.

  Determine the mean salary as well as the number of salaries

Determine the mean salary as well as the number of salaries.

  Currency conversion development

Currency Conversion Development

  Cloud computing assignment

WSDL service that receives a request for a stock market quote and returns the quote

  Design a gui and implement tic tac toe game in java

Design a GUI and implement Tic Tac Toe game in java

  Recursive implementation of euclids algorithm

Write a recursive implementation of Euclid's algorithm for finding the greatest common divisor (GCD) of two integers

  Data structures for a single algorithm

Data structures for a single algorithm

  Write the selection sort algorithm

Write the selection sort algorithm

  Design of sample and hold amplifiers for 100 msps by using n

The report is divided into four main parts. The introduction about sample, hold amplifier and design, bootstrap switch design followed by simulation results.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd