os_cp:assignments
Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
|
os_cp:assignments [2023/05/10 01:43] jkonczak utworzono |
os_cp:assignments [2023/05/23 23:25] (current) jkonczak [Assignment 2] |
||
|---|---|---|---|
| Line 48: | Line 48: | ||
| **There is one strict performance requirement: several instances of the program | **There is one strict performance requirement: several instances of the program | ||
| must compute faster than a single-threaded brute-force program doing the same job.** | must compute faster than a single-threaded brute-force program doing the same job.** | ||
| + | |||
| + | ----- | ||
| + | |||
| + | |||
| + | ===== Assignment 2 ===== | ||
| + | |||
| + | |||
| + | **Deadline: June 9th.** | ||
| + | |||
| + | Write a **thread-safe | ||
| + | [[https://en.wikipedia.org/wiki/Associative_array|associative array (key-value map)]]** | ||
| + | that offers the following operations: | ||
| + | * ''insert(k,v)'' - associates a key ''k'' with a value ''v'' | ||
| + | * ''get(k)'' - if ''k'' is present in the array, returns the value associated with it; else indicates that there is no such key | ||
| + | * ''poll(k)'' - if ''k'' is present in the array, returns the value associated with it; \\ else waits until the key ''k'' is added and then returns a value associated with it | ||
| + | * ''count()'' - returns the number of items (key-value pairs) | ||
| + | * ''remove(…)'' - removes an item | ||
| + | * operations that allow iterating over all key-value pairs: ''first()'', ''next(…)'', ''last()'' (or equivalent) \\ The order in which the elements are traversed does not matter. \\ Notice that you need to make the iterating procedure thread-safe! \\ | ||
| + | |||
| + | You may extend the API of the associative array whenever needed. | ||
| + | You may choose any type for key and value (e.g., ''int''). | ||
| + | |||
| + | Moreover, write an application that tests the associative array by running the | ||
| + | following operations in parallel: | ||
| + | * iterating through all key-value pairs | ||
| + | * adding a key-value pair and removing it | ||
| + | * adding a number of key-value pairs and then removing all of them | ||
| + | * getting values of randomly chosen keys | ||
| + | * polling for values of randomly chosen keys | ||
| + | (You can run each of these operations in a loop, one thread per one loop.) | ||
| + | |||
| + | <small>You may use ''valgrind --tool=drd //progname//'' and ''valgrind --tool=helgrind //progname//'' to test your program.</small> | ||
os_cp/assignments.1683675823.txt.gz · Last modified: 2023/05/10 01:43 by jkonczak
Except where otherwise noted, content on this wiki is licensed under the following license: Creative Commons Attribution-ShareAlike 4.0 International License
