讲解CNP 2001程序、辅导C/C++编程、c++编程辅导
- 首页 >> Python编程 Page 1 of 7 COS
CNP 2001/159.341
AKLI
MASSEY UNIVERSITY
AUCKLAND CAMPUS
EXAMINATION FOR
159.341 PROGRAMMING LANGUAGES, ALGORITHMS AND CONCURRENCY
SEMESTER ONE 2020
_________________________________________________________________________________________________________
Time allowed is THREE (3) Hours.
All students should answer all FIVE (5) questions
MASSEY UNIVERSITY
Non-programmable calculators only are permitted.
Students may NOT remove any part of this exam paper from the exam room.
The exam paper will be made available on the University Library website.
This exam is worth 60 Marks
Page 2 of 7 COS
Question 1 – Programming Languages [15 marks]
a) What is the purpose of a programming language? [1 mark]
b) Name and describe the four layers of a programming language. Give an example [4 marks]
of what would be defined in each layer.
c) Discuss the three main criteria used for language evaluation. Illustrate your [3 marks]
answer with an example of a tradeoff between criteria.
d) Describe the model of computations of both imperative and functional [2 marks]
languages and compare them.
e) Explain the meaning of orthogonality with respect to programming languages. [2 marks]
Give an example of non-orthogonality in a language of your choice (other than C).
f) Numbers in programming languages may take several forms: [3 marks]
314 159.265 3.58979E32 +384 -626
+43.383 -279.502 -8.84E-19 7E-16 -9.E3
Write a regular expression to describe these numbers which are based on floatingpoint.
Explain any assumptions you make about your rules.
Page 3 of 7 COS
Question 2 – Synchronisation [8 marks]
a) Below is a proposed solution to the Critical Section Problem. [4 marks]
(Assume that two threads are launched with the id's 0 and 1)
int lights[2]; // lights are shared
int turn;
void thread_function(int id) { // id is either 0 or 1
int j = 1 - id; // j is id of other thread
while(true) {
lights[id] = 1;
turn = id;
while((lights[j] == 1) && (turn == j)) {} // wait
// --- perform critical section ---
lights[id] = 0;
}
}
Is this solution correct? Either provide a justification of why it is correct or give an example of
how it fails one of the four requirements for the critical section problem.
Note: Do not worry about memory barriers, assume that memory transactions are performed
in order and are immediately visible to the other thread.
b) Briefly describe a solution to the Critical Section Problem using a hardware [2 marks]
solution.
c) What would happen if a semaphore intended to be used for mutual exclusion [2 marks]
was initialised to 2 instead of 1?
Page 4 of 7 COS
Question 3 – Deadlock [10 marks]
a) Briefly describe the four necessary conditions for deadlock to occur [2 marks]
(1-2 sentences each).
b) Three machinists – Anne, Bob and Charles are working on three separate [8 marks]
jobs in their shared workshop. In the shop they have the following equipment:
4 Drill Bits
2 End Mills
2 Face Cutters
3 Gear Cutters
Each piece of equipment can only be used by one machinist at a time.
Anne needs at most: 2 drill bits, 1 end mill, 1 face cutter and 2 gear cutters.
Bob needs at most: 1 drill bit, 2 face cutters and 1 gear cutter.
Charles needs at most: 2 drill bits, 2 end mills, 1 face cutter and 1 gear cutter.
At some point in time the equipment is being used as follows:
Anne has 1 drill bit, 1 end mill and 1 gear cutter.
Bob has 1 drill bit and 1 gear cutter.
Charles has 1 end mill and 1 face cutter.
i. Is this state safe? Use the bankers algorithm to prove your answer and identify a safe
sequence (if one exists).
ii. Charles requests the use of a drill bit, is it safe to grant this request? Justify your answer
by either showing a safe sequence or explaining why one does not exist.
iii. If Charles instead requests the use of a gear cutter, is it safe to grant this request? Again
justify your answer by either showing a safe sequence or explaining why one does not
exist.
Page 5 of 7 COS
Question 4 – Multithreaded Programming [12 marks]
a) Compare and contrast the multi-threading approaches of C++ std threads [4 marks]
and OpenMP (from a language perspective). Give an advantage of each.
b) Consider the following architecture: [4 marks]
The main processing element unit MPU executes like a regular CPU with a
memory cache and access to main memory.
There are also a number of small processing units SPUs that have their own
local memory area LM. The MPU can access the LM of each SPU but an SPU
may only access their own local memory (all SPUs can also access the main
memory area).
Each SPU is assigned units of work by the MPU (may be different tasks).
i) Classify the architecture in terms of Flynn's Taxonomy
ii) Classify the architecture in terms of memory architecture
c) There is a large dataset stored in a binary tree structure and we want to [4 marks]
determine whether a particular value is stored in the tree or not. The data
stored in the tree is not sorted in anyway so a brute-force search is the only
option. The tree is also very unbalanced so different branches have different
heights.
Describe a design for a multi-threaded solution with the primary goal of reducing
the time taken to find a particular value. Your answer should:
• Outline your overall approach
• Describe the paradigm it is based on
• Suggest a language/API to use
• Provide a justification for your decisions
Page 6 of 7 COS
Question 5 – Multithreaded Programming [15 marks]
Dennis has written the following multi-threaded program written in C/C++ to simulate customers
getting their cars washed at a valet.
#define NVALET 4
#define NSPACES 10
#define NCUSTOMERS 20
semaphore sem_customer;
semaphore sem_valet;
semaphore sem_customers[NCUSTOMERS];
int customer_key;
void* valet_thread(void *p) {
long id = (long)p;
while(true) {
wait(&sem_customer); // Wait for customer
signal(&sem_valet); // Wake up customer
int key = customer_key; // Get customer key
freeSpaces += 1; // One more free space
printf("Valet %li cleaning car %li.\n", id, key); // Clean car
sleep(1);
signal(&sem_customers[key]); // Tell customer car is finished
}
}
void* customer_thread(void *p) {
long id = (long)p;
while(true) {
if(freeSpaces > 0) { // Check for free space
freeSpaces -= 1; // Park car in free space
signal(&sem_customer); // Customer has arrived
wait(&sem_valet); // Wait for Valet
customer_key = id; // Set key
wait(&sem_customers[id]); // Wait for Valet to clean car
} else {
sleep(5); // Come back later
}
}
}
int main() {
unsigned long i;
create(&sem_valet, ??);
create(&sem_customer, ??);
for(i = 0; i < NCUSTOMERS; i++) {
create(&sem_customers[i], ??);
create_thread(customer_thread, (void*)i); // Create Customer Thread
}
for(i = 0; i < NVALET; i++) {
create_thread(valet_thread, (void*)i); // Create Valet Thread
}
// Wait for program to complete
Sleep(86400000ULL);
}
(continued over)
Page 7 of 7 COS
Synchronisation is provided by semaphores with the type semaphore and three functions
create, signal and wait that initialise, signal and wait on a semaphore respectively.
A separate thread is created for each of the customers and each of the valets.
Each Customer should use the following algorithm:
if there is a free space to park
park the car in the free space
signal the valets that a customer has arrived
wait for a valet to be available
give them your key
wait for the valet to clean your car
else
wait for a while
repeat
Each Valet uses the following algorithm:
wait for a customer to arrive
signal the customer that a valet is available
get their key
remove the car from the parking space
clean the car
signal the customer that their car is ready
repeat
There are several problems with the existing program.
a) Dennis is unsure what values the semaphores sem_valet, sem_customer [3 marks]
and sem_customers[NCUSTOMERS] should be initialised to. Give the
appropriate values that each semaphore should be initialised to.
b) The program has race conditions, identify them and describe the issues may [4 marks]
arise if they are not fixed.
c) Describe a strategy for preventing each of the race conditions you identified in [4 marks]
part b. Your strategy may make use of new semaphores but should not
fundamentally change the algorithms of the customers or valets.
d) Write new versions of valet_thread() and customer_thread() that [4 Marks]
implement your strategy. You should also make it clear what value any of your
new semaphores should be initialised to.
+ + + + + + + +
CNP 2001/159.341
AKLI
MASSEY UNIVERSITY
AUCKLAND CAMPUS
EXAMINATION FOR
159.341 PROGRAMMING LANGUAGES, ALGORITHMS AND CONCURRENCY
SEMESTER ONE 2020
_________________________________________________________________________________________________________
Time allowed is THREE (3) Hours.
All students should answer all FIVE (5) questions
MASSEY UNIVERSITY
Non-programmable calculators only are permitted.
Students may NOT remove any part of this exam paper from the exam room.
The exam paper will be made available on the University Library website.
This exam is worth 60 Marks
Page 2 of 7 COS
Question 1 – Programming Languages [15 marks]
a) What is the purpose of a programming language? [1 mark]
b) Name and describe the four layers of a programming language. Give an example [4 marks]
of what would be defined in each layer.
c) Discuss the three main criteria used for language evaluation. Illustrate your [3 marks]
answer with an example of a tradeoff between criteria.
d) Describe the model of computations of both imperative and functional [2 marks]
languages and compare them.
e) Explain the meaning of orthogonality with respect to programming languages. [2 marks]
Give an example of non-orthogonality in a language of your choice (other than C).
f) Numbers in programming languages may take several forms: [3 marks]
314 159.265 3.58979E32 +384 -626
+43.383 -279.502 -8.84E-19 7E-16 -9.E3
Write a regular expression to describe these numbers which are based on floatingpoint.
Explain any assumptions you make about your rules.
Page 3 of 7 COS
Question 2 – Synchronisation [8 marks]
a) Below is a proposed solution to the Critical Section Problem. [4 marks]
(Assume that two threads are launched with the id's 0 and 1)
int lights[2]; // lights are shared
int turn;
void thread_function(int id) { // id is either 0 or 1
int j = 1 - id; // j is id of other thread
while(true) {
lights[id] = 1;
turn = id;
while((lights[j] == 1) && (turn == j)) {} // wait
// --- perform critical section ---
lights[id] = 0;
}
}
Is this solution correct? Either provide a justification of why it is correct or give an example of
how it fails one of the four requirements for the critical section problem.
Note: Do not worry about memory barriers, assume that memory transactions are performed
in order and are immediately visible to the other thread.
b) Briefly describe a solution to the Critical Section Problem using a hardware [2 marks]
solution.
c) What would happen if a semaphore intended to be used for mutual exclusion [2 marks]
was initialised to 2 instead of 1?
Page 4 of 7 COS
Question 3 – Deadlock [10 marks]
a) Briefly describe the four necessary conditions for deadlock to occur [2 marks]
(1-2 sentences each).
b) Three machinists – Anne, Bob and Charles are working on three separate [8 marks]
jobs in their shared workshop. In the shop they have the following equipment:
4 Drill Bits
2 End Mills
2 Face Cutters
3 Gear Cutters
Each piece of equipment can only be used by one machinist at a time.
Anne needs at most: 2 drill bits, 1 end mill, 1 face cutter and 2 gear cutters.
Bob needs at most: 1 drill bit, 2 face cutters and 1 gear cutter.
Charles needs at most: 2 drill bits, 2 end mills, 1 face cutter and 1 gear cutter.
At some point in time the equipment is being used as follows:
Anne has 1 drill bit, 1 end mill and 1 gear cutter.
Bob has 1 drill bit and 1 gear cutter.
Charles has 1 end mill and 1 face cutter.
i. Is this state safe? Use the bankers algorithm to prove your answer and identify a safe
sequence (if one exists).
ii. Charles requests the use of a drill bit, is it safe to grant this request? Justify your answer
by either showing a safe sequence or explaining why one does not exist.
iii. If Charles instead requests the use of a gear cutter, is it safe to grant this request? Again
justify your answer by either showing a safe sequence or explaining why one does not
exist.
Page 5 of 7 COS
Question 4 – Multithreaded Programming [12 marks]
a) Compare and contrast the multi-threading approaches of C++ std threads [4 marks]
and OpenMP (from a language perspective). Give an advantage of each.
b) Consider the following architecture: [4 marks]
The main processing element unit MPU executes like a regular CPU with a
memory cache and access to main memory.
There are also a number of small processing units SPUs that have their own
local memory area LM. The MPU can access the LM of each SPU but an SPU
may only access their own local memory (all SPUs can also access the main
memory area).
Each SPU is assigned units of work by the MPU (may be different tasks).
i) Classify the architecture in terms of Flynn's Taxonomy
ii) Classify the architecture in terms of memory architecture
c) There is a large dataset stored in a binary tree structure and we want to [4 marks]
determine whether a particular value is stored in the tree or not. The data
stored in the tree is not sorted in anyway so a brute-force search is the only
option. The tree is also very unbalanced so different branches have different
heights.
Describe a design for a multi-threaded solution with the primary goal of reducing
the time taken to find a particular value. Your answer should:
• Outline your overall approach
• Describe the paradigm it is based on
• Suggest a language/API to use
• Provide a justification for your decisions
Page 6 of 7 COS
Question 5 – Multithreaded Programming [15 marks]
Dennis has written the following multi-threaded program written in C/C++ to simulate customers
getting their cars washed at a valet.
#define NVALET 4
#define NSPACES 10
#define NCUSTOMERS 20
semaphore sem_customer;
semaphore sem_valet;
semaphore sem_customers[NCUSTOMERS];
int customer_key;
void* valet_thread(void *p) {
long id = (long)p;
while(true) {
wait(&sem_customer); // Wait for customer
signal(&sem_valet); // Wake up customer
int key = customer_key; // Get customer key
freeSpaces += 1; // One more free space
printf("Valet %li cleaning car %li.\n", id, key); // Clean car
sleep(1);
signal(&sem_customers[key]); // Tell customer car is finished
}
}
void* customer_thread(void *p) {
long id = (long)p;
while(true) {
if(freeSpaces > 0) { // Check for free space
freeSpaces -= 1; // Park car in free space
signal(&sem_customer); // Customer has arrived
wait(&sem_valet); // Wait for Valet
customer_key = id; // Set key
wait(&sem_customers[id]); // Wait for Valet to clean car
} else {
sleep(5); // Come back later
}
}
}
int main() {
unsigned long i;
create(&sem_valet, ??);
create(&sem_customer, ??);
for(i = 0; i < NCUSTOMERS; i++) {
create(&sem_customers[i], ??);
create_thread(customer_thread, (void*)i); // Create Customer Thread
}
for(i = 0; i < NVALET; i++) {
create_thread(valet_thread, (void*)i); // Create Valet Thread
}
// Wait for program to complete
Sleep(86400000ULL);
}
(continued over)
Page 7 of 7 COS
Synchronisation is provided by semaphores with the type semaphore and three functions
create, signal and wait that initialise, signal and wait on a semaphore respectively.
A separate thread is created for each of the customers and each of the valets.
Each Customer should use the following algorithm:
if there is a free space to park
park the car in the free space
signal the valets that a customer has arrived
wait for a valet to be available
give them your key
wait for the valet to clean your car
else
wait for a while
repeat
Each Valet uses the following algorithm:
wait for a customer to arrive
signal the customer that a valet is available
get their key
remove the car from the parking space
clean the car
signal the customer that their car is ready
repeat
There are several problems with the existing program.
a) Dennis is unsure what values the semaphores sem_valet, sem_customer [3 marks]
and sem_customers[NCUSTOMERS] should be initialised to. Give the
appropriate values that each semaphore should be initialised to.
b) The program has race conditions, identify them and describe the issues may [4 marks]
arise if they are not fixed.
c) Describe a strategy for preventing each of the race conditions you identified in [4 marks]
part b. Your strategy may make use of new semaphores but should not
fundamentally change the algorithms of the customers or valets.
d) Write new versions of valet_thread() and customer_thread() that [4 Marks]
implement your strategy. You should also make it clear what value any of your
new semaphores should be initialised to.
+ + + + + + + +