当前位置:天才代写 > 作业代写 > Lab1代写 source code代写 lab report代写 two-way linked list代写

Lab1代写 source code代写 lab report代写 two-way linked list代写

2020-12-23 14:49 星期三 所属: 作业代写 浏览:65

Lab1代写

Lab #3: Synchronization

Lab1代写 Lab 3 is due Monday, Nov. 11. Your lab report and source code must be submitted by 1:25PM before class. The late policy applies

Lab 3 is due Monday, Nov. 11. Your lab report and source code must be submitted by 1:25PM before class. The late policy applies to this lab project.

When you measure the performance of the programs you write for this lab, make sure the measurement is stable and consistent. A simple way to do that is to repeat the execution multiple times and use the average.

Problem 1: Synchronization Lab1代写

Assume we have a two-way linked list with the following data structure declaration. Every node has an integer key “v”. We want to use this data structure to implement a FIFO queue, i.e., new elements will always be added to the tail and existing elements will be only removed from the head.

struct p { struct p * head = nullptr;
int v; struct p * tail = nullptr;
struct p * pre; Lab1代写 void add (int v);
struct p * next; int remove();
} int size();

a.Implement three methods based on the linked list. The three methods are (1) “add”, that addsa key to tail of the list, and update “tail” or potentially “head”  Remember the list might be empty. (2) “remove”, will remove and return the key pointed by “head” from the list, and update “head” and “tail” properly. If the list is empty, wait until a new element become available. And (3) “size” return the size of the list.

 

Also when a new node is needed, just

Lab1代写
Lab1代写

malloc the memory for that node.Lab1代写

b.Implement the following workload. Spawn 8 threads, each of which executes the workload. The goal of this task is to minimize the overall execution time of the 8

(1)First make sure your implementation of the methods in a. is thread-safe, i.e., multiplethreadscan call them  The simplest way is to use one lock to protect the whole list. Assume this is the baseline version for this task. Measure the execution time of the 8 threads based on this baseline version.

For(i=0; i<1K; i++){

Add(i*thread_id);

}

For(i=0; i<100K; i++){

Add(i);Lab1代写

remove();

}

Print size().

(2)Design and implement a better synchronization schemes at method level (i.e, not protecting the whole loop)., in pthread, for the “add” and “remove” methods, specifically for the example workload. Very importantly, the scheme should provide the best tradeoff betweenmaximum concurrency and lock  The maximum concurrency means that as long as the invocations of the methods from multiple threads change different locationsof the list, the multiple invocation should run concurrently, i.e., not waiting for each other. For example, if one thread is adding a key to a list of 100 elements, and another thread is removing a key, then the two threads should not block each other. The lock overhead is incurred when a lot of locks are used in a synchronization scheme.Lab1代写

Measure the execution time of the 8 threads based on the new synchronization scheme. Very importantly, you should verify that your implementation is correct at the end of the program: the list is properly formed, and list size = 8K. Explain why you think your scheme works better.

What to submit:Lab1代写

The package you submit for this lab should include your source code, performance results and analysis, and brief description that you think might help the instructor understand your code, e.g., about any design choices you make in your program. The instructor will compile, run and measure the performance of your code. Therefore, you should also describe how to compile and run your code in your submitted documentation.

How to Submit:

Copy your lab report, which is a .pdf, a .doc, or a .html file, and all your source code into an empty directory. Assuming the directory is “submission”, make a tar ball of the directory using the following command:Lab1代写

tar czvf [your_first_name]_[your_last_name]_lab3.tar.gz submission.

Replace [your_first_name] and [your_last_name] with your first name and your last name. Submit the tar ball. The submission time will be used as the time-stamp of your submission.

Lab1代写
Lab1代写

其他代写:考试助攻 计算机代写 java代写 algorithm代写 代写CS  function代写paper代写 r代写 金融经济统计代写  web代写 数学代写 essay代写 编程代写 report代写 algorithm代写 Data Analysis代写

合作平台:天才代写 幽灵代写 写手招聘 Essay代写

 

天才代写-代写联系方式