代做CNP 2001程序、代写C/C++代写编程、c++编程代写

日期：2021-06-16 10:22

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.

+ + + + + + + +