Další metody synchronizace
Na tomto cvičení byste si měli vyzkoušet další metody synchronizace vláken přes podmínkové proměnné (condition variables).
Domácí příprava
Nastudujte si použití podmínkových proměnných a k tomu příslušné funkce v
knihovně pthread
:
pthread_cond_init
pthread_cond_destroy
pthread_cond_signal
pthread_cond_broadcast
pthread_cond_wait
Zadání úlohy
Vytvořte program simulující výrobní závod, který vyrábí 3 druhy výrobků. Každý
výrobek musí projít pevně danou sekvencí operací na různých pracovištích.
Pracoviště obsluhují dělníci, přičemž každý dělník je schopen obsluhovat právě
jeden druh pracoviště. Počet dělníků a jemu příslušejících pracovišť je různý a
v čase proměnlivý – dělníci přicházejí a odcházejí, pracoviště mohou přibývat
nebo být vyřazována. Požadavky na výrobu, příchod a odchod dělníků a
nákup/vyřazení strojů se zadávají přes standardní vstup aplikace následujícími
příkazy (jeden příkaz na řádce ukončené ‘\n
'):
make <výrobek>
– požadavek na výrobu výrobku;<výrobek>
je “A
”, “B
”, nebo “C
”start <jméno> <pracoviště>
– příchod dělníka s uvedením jeho specializaceend <jméno>
– odchod dělníkaadd <pracoviště>
– přidání nového pracovištěremove <pracoviště>
– odebrání pracoviště
Parametry jsou odděleny mezerou. Při zadání neplatného příkazu či parametru (např. neexistující pracoviště), nebo špatného počtu parametrů, ignorujte celý řádek. Doporučujeme informovat o tom uživatele výpisem do standardního chybového výstupu.
Výrobní proces je řízen dělníky. Každý dělník bude reprezentován samostatným vláknem, které bude vytvořeno při příchodu dělníka a ukončeno při jeho odchodu. Dělník potřebuje ke své práci polotovar (meziprodukt) a volné pracoviště pro které je specializován. Pokud nebude mít jedno nebo druhé, čeká. Pro první pracoviště nahrazuje meziprodukt požadavek na výrobu. Pokud má dělník vše potřebné k dispozici, vypíše informaci o své aktivitě a poté počká čas, který je definován pro každý typ operace. Formát výpisu aktivity je
<jméno> <pracoviště> <krok> <výrobek>
tedy např.
Karel vrtacka 2 A
Pokud dělník dokončí poslední operaci v procesu, vypíše
done <výrobek>
kde <výrobek>
je kód výrobku A
, B
, nebo C
.
Výrobní procesy pro výrobky A
–C
jsou následující:
1 | 2 | 3 | 4 | 5 | 6 | |
---|---|---|---|---|---|---|
A | nuzky | vrtacka | ohybacka | svarecka | vrtacka | lakovna |
B | vrtacka | nuzky | freza | vrtacka | lakovna | sroubovak |
C | freza | vrtacka | sroubovak | vrtacka | freza | lakovna |
Časy operací v milisekundách na pracovištích jsou následující:
nuzky
: 100vrtacka
: 200ohybacka
: 150svarecka
: 300lakovna
: 400sroubovak
: 250freza
: 500
Můžete předpokládat, že nepřijdou dva dělníci stejného jména.
Pokud se odebírá pracoviště, odeberte přednostně neobsazené. Pokud není žádné pracoviště daného typu volné, vyřaďte libovolné, ovšem až po dokončení aktuální operace.
Dělník odchází z pracoviště buď při ukončování celé aplikace (viz níže) nebo
jako reakce na příkaz end
. Dělník který má odejít nejdříve dokončí aktuálně
rozdělanou práci. Pokud má dělník odejít na základě příkazu end
, nesmí vzít
novou práci. Při odchodu dělník vypíše na standardní výstup:
<jméno> goes home
a poté ukončí své vlákno.
Pokud může dělník v danou chvíli pracovat na více různých místech, vybírá si
místo s nejvyšším možným krokem tak, aby se prioritně zpracovávaly zakázky
nejblíže dokončení. Je-li takových víc, vybírá mezi nimi výrobek blíže začátku
abecedy, tedy např. výrobek A
před B
.
Uzavření standardního vstupu (tzn. Váš program načte EOF
ze stdin
) je
požadavkem na ukončení celé aplikace. Po tomto požadavku dělník odchází v
okamžiku, kdy na žádném výrobku, na kterém může pracovat jeho profese,
nemůže už nikdo pracovat (kvůli chybějícím pracovníkům, pracovním místům či
meziproduktům). Do té doby čeká a pokud se objeví práce začne ještě pracovat.
Ukončení aplikace nastane po odchodu všech dělníků.
Příklad ukončování aplikace: Nechť jsou při příjmuEOF
rozpracovány pouze výrobkyB
aC
. Okamžitě tedy odchází ohýbači a svářeči (ti mohou pracovat jen naA
), ostatní čekají či pracují. Pokud bude jako první dokončen výrobekB
, nebo naB
už nebude možné dále pracovat, odejdou střihači (nůžky). Všichni ostatní odcházejí až po dokončení prací na výrobkuC
.
Před definitivním koncem aplikace ukončete vlákna všech dělníků a dealokujte
dynamicky alokovanou paměť. Návratový kód aplikace bude 0
.
Pokyny k implementaci
-
Čekání všech vláken musí být efektivní, nesmí být vytěžován procesor (busy waiting).
-
Nevytvářejte jiná vlákna než vlákna pro dělníky (byl by to problém pro evaluátor).
-
Jsou-li dostupné zdroje, dělník musí započít práci okamžitě (co nejrychleji, bez zbytečné prodlevy).
-
Standardní vstup čtěte pouze z hlavního vlákna.
-
Příkazy ze vstupu vykonávejte bez zbytečného odkladu, tj. hlavní vlákno neblokujte, pokud to není nezbytně nutné. Zejména se nesnažte v hlavním vlákně čekat na to, až nějaký dělník něco provede. Cílem je, aby hlavní vlákno nebylo blokováno a mohlo tak rychle reagovat na zaslané příkazy.
-
Nesnažte se optimalizovat až příliš, pokud by to významně zkomplikovalo program. Např. je přípustné dělníka vzbudit, i když dotyčný zjistí, že pro něj není práce a opět se uspí.
-
Standardní chybový výstup můžete použít pro libovolné ladící výpisy.
-
Výpis aktivity musí být proveden tak, aby nemohlo dojít k prohození s výpisem jiné aktivity, která začala později.
-
Binární soubor aplikace se bude jmenovat
factory
a bude vytvořen ve stejném adresáři, kde se nacházíMakefile
. -
Program překládejte s příznaky
-Wall -g -O2
a navíc s příznaky v proměnnéEXTRA_CFLAGS
. Pokud tato proměnná není definována na příkazové řádcemake
, nastavte její hodnotu na “-fsanitize=address -fno-omit-frame-pointer
” (viz např. operátor?=
). Pokud provádíte překlad a linkování odděleně, používejte příznaky vEXTRA_CFLAGS
také při linkování. -
Pro načítání vstupu můžete použít následující vzor: (Případně alternativní šablonu).
#include <stdio.h> #include <stdlib.h> #include <string.h> /* You can use these functions and data structures to transform strings to * numbers and use them in arrays */ enum place { NUZKY, VRTACKA, OHYBACKA, SVARECKA, LAKOVNA, SROUBOVAK, FREZA, _PLACE_COUNT }; const char *place_str[_PLACE_COUNT] = { [NUZKY] = "nuzky", [VRTACKA] = "vrtacka", [OHYBACKA] = "ohybacka", [SVARECKA] = "svarecka", [LAKOVNA] = "lakovna", [SROUBOVAK] = "sroubovak", [FREZA] = "freza", }; enum product { A, B, C, _PRODUCT_COUNT }; const char *product_str[_PRODUCT_COUNT] = { [A] = "A", [B] = "B", [C] = "C", }; int find_string_in_array(const char **array, int length, char *what) { for (int i = 0; i < length; i++) if (strcmp(array[i], what) == 0) return i; return -1; } /* It is not necessary to represent each working place with a dynamically * allocated object. You can store only number of ready places * * int ready_places[_PLACE_COUNT]; */ /* It is not necessary to represent each part as a dynamically allocated * object. you can have only number of parts for each working phase * * #define _PHASE_COUNT 6 * int parts[_PRODUCT_COUNT][_PHASE_COUNT] */ int main(int argc, char **argv) { /* Initialize your internal structures, mutexes and conddition variables. */ char *line = NULL; size_t sz = 0; while (1) { char *cmd, *arg1, *arg2, *arg3, *saveptr; if (getline(&line, &sz, stdin) == -1) break; /* Error or EOF */ cmd = strtok_r(line, " \r\n", &saveptr); arg1 = strtok_r(NULL, " \r\n", &saveptr); arg2 = strtok_r(NULL, " \r\n", &saveptr); arg3 = strtok_r(NULL, " \r\n", &saveptr); if (!cmd) { continue; /* Empty line */ } else if (strcmp(cmd, "start") == 0 && arg1 && arg2 && !arg3) { /* - start new thread for new worker * - copy (e.g. strdup()) worker name from arg1, the * arg1 will be removed at the end of scanf cycle * - workers should have dynamic objects, you don't know * total number of workers */ } else if (strcmp(cmd, "make") == 0 && arg1 && !arg2) { /* int product = find_string_in_array( * product_str, * _PRODUCT_COUNT, * arg1 * ); * * if (product >= 0) {..... * add the part to factory cycle * you need to wakeup worker to start working if possible * ... * } */ } else if (strcmp(cmd, "end") == 0 && arg1 && !arg2) { /* tell the worker to finish * the worker has to finish their work first * you should not wait here for the worker to finish * * if the worker is waiting for work * you need to wakeup the worker */ } else if (strcmp(cmd, "add") == 0 && arg1 && !arg2) { /* add new place * * if worker and part is ready, start working - wakeup worker */ } else if (strcmp(cmd, "remove") == 0 && arg1 && !arg2) { /* if you cannot remove empty place you cannot wait for finish * work */ } else { fprintf(stderr, "Invalid command: %s\n", line); } } free(line); /* Wait for every worker to finish their work. Nobody should be able to * continue. */ }
- Do BRUTE nahrávejte crate pojmenovaný
factory
. Zabalte ho např. příkazem:tar czf factory.tgz Cargo.toml src
- Závislosti uvádějte v
Cargo.toml
podobně, jako v předchozích úlohách. Např.:[dependencies] anyhow = "1.0" lazy_static = "1.4" libc = "0.2" nix = "0.27" strum = "0.25" strum_macros = "0.25"
- Základní kostru programu a načítání vstupu můžete implementovat
podle následujícího vzoru:
#[macro_use] extern crate anyhow; use std::fmt; use std::io; use std::io::BufRead; use std::ops::{Index, IndexMut}; use std::str::FromStr; use strum::EnumCount; use strum_macros::EnumCount; #[derive(Debug, PartialEq, Clone, Copy, EnumCount)] enum Place { Nuzky, Vrtacka, Ohybacka, Svarecka, Lakovna, Sroubovak, Freza, } #[derive(Debug, PartialEq, Clone, Copy)] enum Product { A, B, C, } const PROCESS_STEPS: usize = 6; type ProductLineState = [i32; PROCESS_STEPS]; type Stock = [ProductLineState; Product::COUNT]; impl Index<Product> for Stock { type Output = ProductLineState; fn index(&self, product: Product) -> &Self::Output { &self[product as usize] } } impl IndexMut<Product> for Stock { fn index_mut(&mut self, product: Product) -> &mut Self::Output { &mut self[product as usize] } } impl fmt::Display for Place { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write!(f, "{:?}", self) } } impl FromStr for Place { type Err = anyhow::Error; fn from_str(s: &str) -> Result<Self, Self::Err> { match s { "nuzky" => Ok(Place::Nuzky), "vrtacka" => Ok(Place::Vrtacka), "ohybacka" => Ok(Place::Ohybacka), "svarecka" => Ok(Place::Svarecka), "lakovna" => Ok(Place::Lakovna), "sroubovak" => Ok(Place::Sroubovak), "freza" => Ok(Place::Freza), _ => Err(anyhow!("Invalid place '{}'", s)), } } } impl fmt::Display for Product { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write!(f, "{:?}", self) } } impl FromStr for Product { type Err = anyhow::Error; fn from_str(s: &str) -> Result<Self, Self::Err> { match s { "A" => Ok(Product::A), "B" => Ok(Product::B), "C" => Ok(Product::C), _ => Err(anyhow!("Invalid product '{}'", s)), } } } fn start_worker(&mut self, name: &str, place: &str) -> anyhow::Result<()> { match place.parse::<Place>() { Ok(place) => { // ... } Err(e) => { eprintln!("{}", e.to_string()); // Print (and ignore) parse errors } }; Ok(()) } fn make(product: &str) -> anyhow::Result<()> { // ... Ok(()) } fn end_worker(name: &str) -> anyhow::Result<()> { // ... Ok(()) } fn add_place(place: &str) -> anyhow::Result<()> { // ... Ok(()) } fn remove_place(place: &str) -> anyhow::Result<()> { // ... Ok(()) } fn main() -> anyhow::Result<()> { for line in io::stdin().lock().lines() { let line = line?; let mut words = line.split_whitespace(); match (words.next(), words.next(), words.next(), words.next()) { (Some("start"), Some(name), Some(place), None) => start_worker(name, place)?, (Some("make"), Some(product), None, None) => make(product)?, (Some("end"), Some(name), None, None) => end_worker(name)?, (Some("add"), Some(place), None, None) => add_place(place)?, (Some("remove"), Some(place), None, None) => remove_place(place)?, (None, None, None, None) => (), // ignore empty lines (_, _, _, _) => eprintln!("Unsupported command: {}", line), }; } //... Ok(()) }
Ukázkové vstupy a odpovídající výstupy
Výroba A
Vstup:
add nuzky
add vrtacka
add ohybacka
add svarecka
add lakovna
add sroubovak
add freza
start Nora nuzky
start Vojta vrtacka
start Otakar ohybacka
start Sofie svarecka
start Lucie lakovna
start Stepan sroubovak
start Filip freza
make A
Výstup:
Nora nuzky 1 A
Vojta vrtacka 2 A
Otakar ohybacka 3 A
Sofie svarecka 4 A
Vojta vrtacka 5 A
Lucie lakovna 6 A
done A
Nedokončený výrobek a odchod
$ ./factory <<EOF
start Nora nuzky
add nuzky
make A
EOF
Nora nuzky 1 A
Nora goes home
Rozdílný odchod dělníků
Pozn.: Pořadí sousedních řádek goes home
může být pokaždé jiné.
$ ./factory <<EOF
add nuzky
add vrtacka
add ohybacka
add svarecka
add lakovna
add sroubovak
add freza
start Nora nuzky
start Vojta vrtacka
start Otakar ohybacka
start Sofie svarecka
start Lucie lakovna
start Stepan sroubovak
start Filip freza
make A
make C
EOF
Nora nuzky 1 A
Filip freza 1 C
Vojta vrtacka 2 A
Otakar ohybacka 3 A
Sofie svarecka 4 A
Vojta vrtacka 2 C
Stepan sroubovak 3 C
Vojta vrtacka 5 A
Vojta vrtacka 4 C
Lucie lakovna 6 A
Filip freza 5 C
done A
Otakar goes home
Sofie goes home
Nora goes home
Lucie lakovna 6 C
done C
Lucie goes home
Filip goes home
Vojta goes home
Stepan goes home
Domácí příprava na další cvičení
Na příští týden: žádná – na vypracování této úlohy máte 2 týdny.
Za 2 týdny: Seznamte se se základními instrukcemi architektury x86 a způsobem, jakým vkládat instrukce assembleru přímo do zdrojového kódu v jazyce C/C++.