Otevřená informatika - Softwarové inženýrství

Státnicové otázky

Filip Štěpánek

BSY

Topics

Security analysis of operating systems, development of secure software and web applications security. Analysis of cyberattacks and malware. Security of mobile devices. BE4M36BSY (Course web pages)

Questions

Bezpečnostní řízení projektů softwaru

Bezpečnost je klíčovou součástí každého softwarového projektu. Správné řízení projektu s důrazem na bezpečnost může pomoci snížit rizika a minimalizovat náklady na opravy bezpečnostních nedostatků v pozdějších fázích projektu.

Existují různé modely řízení projektů softwaru, ale v této souvislosti se zaměříme na Waterfall a Elipsa model.

Waterfall model

Waterfall model je lineární proces řízení projektů, který se skládá z jednotlivých fází, které se následují:

Výhodou Waterfall modelu je jeho jednoduchost a přehlednost, která usnadňuje řízení projektu. Nevýhodou je však jeho nedostatečná flexibilita, což může být problematické v případě, že se objeví nějaké neočekávané problémy během realizace projektu.

Elipsa model

Elipsa model je iterativní proces řízení projektů, který se skládá z opakujících se fází:

Výhodou Elipsa modelu je jeho flexibilita, což umožňuje rychlé reakce na změny v průběhu projektu. Nevýhodou může být větší náročnost na řízení projektu, jelikož každá iter

Systematic identification of potential vulnerabilities

Systémová identifikace potenciálních zranitelností

STRIDE

STRIDE je zkratka pro sedm nejčastějších hrozeb v kybernetické bezpečnosti:

Použití této metodiky může pomoci při analýze bezpečnostních hrozeb a návrhu ochranných opatření.

Attack modelling (attack trees)

Útokové modelování (stromy útoků) je metoda, která se používá k identifikaci možných zranitelností v systému a kategorizaci útoků, které by mohly být na systém provedeny. Tato metoda umožňuje analyzovat potenciální hrozby a navrhnout zabezpečení systému proti nim.

Attack trees jsou grafické nástroje, které reprezentují útoky na systém pomocí stromové struktury. Kořen stromu představuje cíl útoku, zatímco listy stromu představují konkrétní způsoby, jak útok na cíl dosáhnout. Každý uzel stromu reprezentuje jednu zranitelnost nebo krok v útoku.

Použití attack trees umožňuje identifikovat nejpravděpodobnější útoky a navrhnout opatření pro zvýšení bezpečnosti systému. Tato metoda také umožňuje určit, které zabezpečovací opatření jsou nejúčinnější a které jsou méně účinné.

Attack modelling (attack trees) jsou užitečným nástrojem pro každého, kdo se zabývá kybernetickou bezpečností. Tato metoda umožňuje identifikovat a analyzovat potenciální hrozby a navrhnout opatření pro ochranu systému proti nim.

Ranking of vulnerabilities (ideal, DREAD)

Ideální

Ideální ranking zranitelností se skládá z pěti kritérií:

  1. Vliv (Impact) - jak moc by zranitelnost mohla poškodit organizaci
  2. Pravděpodobnost (Likelihood) - jak pravděpodobné je, že se zranitelnost vyskytne
  3. Využitelnost (Ease of Exploitation) - jak snadné je zranitelnost využít
  4. Zjištění (Discoverability) - jak snadné je zranitelnost najít
  5. Důležitost (Importance) - jak důležitá je pro organizaci ohrožená oblast

DREAD

DREAD ranking zranitelností se skládá z pěti kritérií:

  1. Vliv (Damage) - jak moc by zranitelnost mohla poškodit organizaci
  2. Reprodukovatelnost (Reproducibility) - jak snadné je zranitelnost reprodukovat
  3. Exploitabilita (Exploitability) - jak snadné je zranitelnost využít
  4. Postižení uživatelů (Affected Users) - kolik uživatelů by mohlo být zasaženo zranitelností
  5. Rozšíření (Discoverability) - jak snadné je zranitelnost najít

Timing and storage covert channels

Časování a ukládání skrytých kanálů

Popis

Skryté kanály jsou metody, které umožňují komunikaci mezi útočníkem a obětí bez detekce ze strany bezpečnostních opatření. Časování a ukládání skrytých kanálů jsou dva způsoby, jak mohou být skryté kanály implementovány.

Časování skrytých kanálů: Tento typ skrytého kanálu využívá různých časových prodlev mezi různými akcemi, jako jsou například požadavky na server nebo odesílání dat. Tyto prodlevy jsou použity jako kódování pro přenos informací.

Ukládání skrytých kanálů: Tento typ skrytého kanálu využívá různých možností ukládání dat, jako jsou například metadata souborů nebo skryté sektory na pevném disku. Tyto metody jsou použity k ukládání informací, které jsou později získány útočníkem.

Příklad využití

Útočník může využít časování skrytého kanálu k přenosu informací mezi svým počítačem a obětí. Například může použít prodlevu mezi požadavky na server k přenosu informací v kódované formě.

Další možností je využití ukládání skrytého kanálu k ukládání informací na pevný disk oběti. Útočník může využít skrytých sektorů na disku k ukládání informací, které jsou později získány pomocí speciálního softwaru.

Prevence

Prevence skrytých kanálů zahrnuje monitorování časových prodlev a ukládání dat na počítači. Bezpečnostní opatření by měla být navržena tak, aby minimalizovala možnosti využití skrytých kanálů útočníky. Například by měla být omezena možnost ukládání dat na pevný disk a monitorovány časové prodlevy.

Side channel attacks

Side channel attacks are a type of cyber attack that exploits weaknesses in a system’s physical or electromagnetic characteristics, such as power consumption, electromagnetic radiation, or sound, to extract sensitive information. These attacks are often used to bypass encryption or other security measures and can be difficult to detect.

Types of Side Channel Attacks

  1. Power Analysis Attack: This attack involves analyzing the power consumption of a device to determine the secret key used in encryption.

  2. Electromagnetic Attack: This attack involves analyzing the electromagnetic radiation emitted by a device to determine the secret key used in encryption.

  3. Acoustic Attack: This attack involves analyzing the sound produced by a device to determine the secret key used in encryption.

Prevention of Side Channel Attacks

  1. Implementing Countermeasures: Implementing countermeasures such as noise reduction techniques, shielding, and filtering can help prevent side channel attacks.

  2. Using Advanced Encryption: Using advanced encryption algorithms that are resistant to side channel attacks can also help prevent these attacks.

  3. Regular Security Audits: Regular security audits can help identify and address any vulnerabilities that may be exploited by side channel attacks.

Steganography

Steganografie je technika skrytí dat uvnitř jiných dat, aby se skryla existence samotného zprávy. Tato technika se často používá k ukrývání škodlivého kódu nebo citlivých informací. Steganografie může být detekována pomocí specializovaných nástrojů, které jsou navrženy k odhalení skrytých dat. Je důležité mít vědomosti o této technice, aby se zabránilo útokům, které využívají steganografii.

Discretionary access control(Access control list, Capabilities)

Discretionary access control (DAC) - řízení přístupu na základě diskrece uživatele

Co to je? DAC je typ řízení přístupu, který umožňuje uživatelům kontrolovat přístup k objektům, jako jsou soubory a složky, na základě své diskrece. To znamená, že uživatelé mohou rozhodnout, kteří další uživatelé nebo skupiny mají přístup k jejich objektům.

Jak to funguje? DAC využívá dvou metod řízení přístupu: Access control list (ACL) a Capabilities. ACL umožňuje uživatelům určit, kdo má přístup k jejich objektům a jaký typ přístupu mají. Capabilities na druhé straně umožňují uživatelům určit, ke kterým objektům mají ostatní uživatelé přístup a jaký typ přístupu mají.

Proč je to důležité v kybernetické bezpečnosti? DAC je důležitým nástrojem v kybernetické bezpečnosti, protože umožňuje uživatelům kontrolovat přístup k důležitým datům a informacím. Pokud jsou tyto objekty špatně chráněny, mohou být snadno ohroženy útokem hackerů. DAC umožňuje uživatelům chránit své objekty a informace před neoprávněným přístupem.

Poznámka: V českém jazyce se používá termín řízení přístupu na základě diskrece uživatele pro Discretionary access control.

Mandatory access control

Mandatory Access Control (MAC) je bezpečnostní mechanismus v kybernetické bezpečnosti, který řídí přístup k datům a zdrojům na základě předem definovaných pravidel. Tyto pravidla jsou vytvořeny administrátorem systému a aplikovány na uživatele a procesy.

MAC je účinným způsobem, jak minimalizovat rizika způsobená útoky na systém. Umožňuje správci systému přesně definovat, kdo má přístup k určitým datům a zdrojům a co s nimi může dělat. Tím se snižuje riziko, že neoprávněný uživatel získá přístup k citlivým informacím nebo je poškodí.

MAC je často používán v prostředí s vysokou úrovní bezpečnosti, jako jsou vládní organizace, finanční instituce a průmyslové podniky. Je to důležitý nástroj v boji proti kybernetickým hrozbám a je nezbytný pro ochranu citlivých dat a informací.

Povinná kontrola přístupu (MAC) je bezpečnostní mechanismus, který řídí přístup k datům a zdrojům na základě předem definovaných pravidel. Tento mechanismus minimalizuje riziko útoků na systém a snižuje riziko získání přístupu k citlivým informacím nebo jejich poškození. MAC je často používán v prostředí s vysokou úrovní bezpečnosti, jako jsou vládní organizace, finanční instituce a průmyslové podniky.

Multi-level security

Multi-level security (MLS) je koncept zabezpečení, který se používá v oblasti kybernetické bezpečnosti. Tento koncept zahrnuje použití různých úrovní zabezpečení pro různé části systému. Každá úroveň zabezpečení má své vlastní pravidla a omezení, které pomáhají chránit systém před útoky.

MLS se používá v mnoha různých oblastech, včetně vládních a vojenských systémů, finančních institucí a podobně. Většina systémů MLS používá tři nebo více úrovní zabezpečení, ale některé mohou mít i více než deset úrovní.

Každá úroveň zabezpečení má své vlastní názvy a čísla, například Top Secret (nejvyšší tajné), Secret (tajné), Confidential (důvěrné) a Unclassified (neutajené). Každá úroveň má také své vlastní pravidla pro přístup a zpracování informací.

Použití MLS může pomoci minimalizovat riziko útoku na systém a chránit citlivé informace. Nicméně, implementace MLS může být nákladná a složitá, a může vyžadovat specializované znalosti a technologie.

Biba model

Biba model je bezpečnostní model, který se používá k ochraně informací a dat. Tento model se zaměřuje na zachování integrity dat a předcházení neautorizovanému přístupu k nim.

Model je pojmenován po svém tvůrci, americkém matematikovi Kennethu Bibovi. Biba model se skládá ze tří základních úrovní:

  1. Integrita dat - Tato úroveň se zaměřuje na zachování integrity dat a zabraňuje jakémukoli neoprávněnému zásahu do dat. Zabezpečuje se tak, aby data nebyla poškozena, ztracena nebo změněna.

  2. Dostupnost dat - Tato úroveň se zaměřuje na zajištění dostupnosti dat pro autorizované uživatele. Zabezpečuje se tak, aby data byla k dispozici v době, kdy jsou potřebná.

  3. Důvěrnost dat - Tato úroveň se zaměřuje na zajištění důvěrnosti dat a zabraňuje neoprávněnému přístupu k nim. Zabezpečuje se tak, aby data byla přístupná pouze autorizovaným uživatelům.

Biba model je velmi užitečný pro organizace, které se zabývají citlivými informacemi a daty. Tento model pomáhá chránit informace a data před útoky a zabezpečuje, že jsou k dispozici pouze pro autorizované osoby.

Multi-lateral security

Multi-laterální bezpečnost znamená spolupráci a koordinaci mezi více stranami v oblasti kybernetické bezpečnosti. To zahrnuje vládní organizace, soukromé společnosti, akademické instituce a další subjekty. Cílem multi-laterální bezpečnosti je zlepšit ochranu proti kybernetickým hrozbám a zvýšit schopnost reagovat na ně.

V rámci multi-laterální bezpečnosti se mohou provádět různé aktivity, jako jsou společné cvičení, výměna informací o hrozbách a zranitelnostech, spolupráce na vývoji bezpečnostních technologií a standardů a další. Tato spolupráce může být regionální, mezinárodní nebo dokonce globální.

V České republice se multi-laterální bezpečnost v kybernetické bezpečnosti provádí prostřednictvím různých iniciativ a organizací, jako jsou Národní centrum kybernetické bezpečnosti, Česká asociace pro kybernetickou bezpečnost a další. Tyto organizace spolupracují s různými subjekty, včetně vládních úřadů, soukromých společností a akademických institucí, aby zlepšily kybernetickou bezpečnost v České republice.

Role-based access control

Role-based access control (RBAC) je metoda řízení přístupu k informacím a systémům založená na přidělování oprávnění uživatelům na základě jejich rolí v organizaci. Tento systém umožňuje správci přidělit uživatelům práva k určitým činnostem na základě jejich pracovních funkcí a odpovědností, což snižuje riziko zneužití oprávnění. RBAC je důležitým prvkem kybernetické bezpečnosti, protože pomáhá minimalizovat riziko útoků ze strany interních a externích hrozeb a zajišťuje ochranu citlivých informací.

Privilege escalation

Privilege escalation představuje zvýšení úrovně oprávnění uživatele v systému. To znamená, že uživatel, který nemá původně dostatečné oprávnění, získává vyšší úroveň oprávnění, aby mohl provádět určité akce, ke kterým by jinak neměl přístup.

Tento proces může být zneužitý útočníky, kteří se snaží získat neoprávněný přístup k systému. Pokud útočník dokáže získat omezené oprávnění, může použít různé techniky, aby získal vyšší úroveň oprávnění a získal tak plný přístup k systému.

Existuje několik způsobů, jak útočníci mohou provést privilege escalation, včetně zneužití chyb v softwaru, zneužití chyb v konfiguraci systému a využití slabých hesel.

Proti privilege escalation útokům mohou být použity různé bezpečnostní opatření, jako jsou aktualizace softwaru, konfigurační změny a zlepšení správy hesel.

Security of operating systems

Bezpečnost operačních systémů je klíčovou součástí kybernetické bezpečnosti. Operační systémy jsou základem pro všechny aplikace a procesy běžící na počítači, a proto je důležité zajistit jejich bezpečnost. Některé z důležitých opatření pro zajištění bezpečnosti operačních systémů jsou:

1. Aktualizace

Aktualizace operačního systému jsou důležité, protože obsahují opravy chyb a zranitelností. Je důležité pravidelně aktualizovat operační systém a všechny nainstalované aplikace, aby se minimalizovala rizika útoku.

2. Antivirový software

Antivirový software je důležitým nástrojem pro ochranu operačního systému. Antivirový software dokáže odhalit a zablokovat škodlivý software, který by mohl poškodit operační systém.

3. Firewall

Firewall je dalším důležitým nástrojem pro zajištění bezpečnosti operačního systému. Firewall dokáže blokovat nežádoucí přístup k počítači a chránit ho před útoky z internetu.

4. Silné heslo

Silné heslo je důležité pro ochranu operačního systému. Heslo by mělo být dostatečně dlouhé a obsahovat kombinaci písmen, číslic a speciálních znaků.

Bezpečnost operačních systémů je důležitá pro ochranu počítače a dat před útoky. Pravidelná aktualizace, antivirový software, firewall a silné heslo jsou důležitými nástroji pro zajištění bezpečnosti operačního systému.

Trusted computer base

Trusted computer base je termín používaný v kybernetické bezpečnosti pro označení části systému, která je považována za důvěryhodnou a zabezpečenou. Tato část systému je obvykle oddělena od zbytku systému a obsahuje kritické funkce, jako jsou autentizace uživatelů, řízení přístupu a záznamy o událostech. Cílem trusted computer base je minimalizovat rizika spojená s útoky na systém a zajistit, aby důvěryhodné informace zůstaly v bezpečí.

Reference monitor

Reference Monitor (Referenční monitor) je základním bezpečnostním mechanismem v oblasti kybernetické bezpečnosti. Je to softwarový mechanismus, který řídí přístup k systému a zajišťuje, že pouze oprávněné osoby mají přístup k citlivým datům a aplikacím.

Referenční monitor funguje jako středník mezi uživateli a systémem. Každý požadavek na přístup k systému musí projít referenčním monitorem, který vyhodnotí, zda je uživatel oprávněn přistupovat k daným datům a aplikacím. Pokud je uživatel oprávněn, referenční monitor povolí přístup. Pokud ne, přístup je zamítnut.

Referenční monitor je klíčovým prvkem v rámci bezpečnostní architektury a je používán v mnoha systémech, včetně operačních systémů, firewalů a antivirových programů. Jeho účelem je minimalizovat rizika spojená s neoprávněným přístupem k citlivým datům a aplikacím a chránit tak uživatele a organizace před kybernetickými hrozbami.

Complete mediation, needed mechanism for securing current OS, memory management, rings.

Kompletní mediací je mechanismus, který zajišťuje, že každá interakce mezi subjekty v systému je řízena a kontrolována. Tento mechanismus zahrnuje kontrolu přístupu, autentizaci, autorizaci a auditování.

Mechanismus pro zabezpečení současného operačního systému

Pro zabezpečení současného operačního systému je třeba použít několik mechanismů, jako jsou firewally, antivirové programy, aktualizace operačního systému a aplikací, zabezpečené připojení k internetu a další.

Správa paměti

Správa paměti je proces, který zajišťuje, že každý proces v systému má přístup pouze k paměti, kterou mu byla přidělena. Tento mechanismus zahrnuje virtualizaci paměti, oddělení procesů a kontrolu přístupu k paměti.

Kruhy

Kruhy jsou mechanismem pro oddělení procesů v systému. Existují čtyři kruhy, přičemž každý kruh má svou úroveň oprávnění. Kruh 0 je nejvyšší úroveň a používá se pro jádro operačního systému. Kruhy 1 a 2 jsou určeny pro ovladače a systémové služby. Kruh 3 je určen pro uživatelské procesy. Tento mechanismus zajišťuje, že procesy v nižších kruzích nemohou ovlivnit procesy v kruzích vyšších.

Virtualization

Virtualizace je proces vytváření virtuálních verzí hardwaru, softwaru nebo síťových prostředků. Tento proces umožňuje oddělit jednotlivé části systému od sebe a simulovat jejich chování. To může být užitečné v oblasti kybernetické bezpečnosti, protože umožňuje izolovat potenciálně nebezpečné aplikace nebo procesy od zbytku systému.

Existují různé typy virtualizace, včetně virtualizace operačního systému, virtualizace aplikace a virtualizace síťových prostředků. Každý typ má své vlastní výhody a nevýhody, a také různé použití v oblasti kybernetické bezpečnosti.

Virtualizace může být použita k izolaci potenciálně nebezpečných aplikací od zbytku systému, což může pomoci chránit systém před útoky malware. Také umožňuje vytvoření testovacího prostředí, ve kterém je možné testovat nové aplikace nebo aktualizace bez rizika poškození systému.

Nicméně, virtualizace také přináší svá vlastní rizika. Pokud není řádně zabezpečena, může být virtuální prostředí cílem útoků. Také může být použita k útoku na jiné systémy, pokud je virtuální prostředí propojeno s jinými sítěmi.

Proto je důležité, aby byla virtualizace správně konfigurována a zabezpečena. To zahrnuje použití silných hesel a šifrování dat v rámci virtuálního prostředí. Také je důležité pravidelně aktualizovat virtuální prostředí a provádět pravidelné kontroly zabezpečení.

Virtual machine monitor

Virtual Machine Monitor (VMM) nebo také hypervisor je softwarová vrstva, která umožňuje běh více virtuálních strojů na jednom fyzickém počítači. VMM zajišťuje izolaci mezi jednotlivými virtuálními stroji a hostitelským operačním systémem, což zvyšuje bezpečnost celého systému. Využití VMM je často doporučováno v oblasti kybernetické bezpečnosti, protože umožňuje izolovat potenciálně nebezpečné aplikace a procesy na jednom virtuálním stroji, což minimalizuje riziko šíření škodlivého kódu na ostatní části systému.

V českém jazyce se Virtual Machine Monitor často označuje jako hypervisor.

Micro-kernels

V oblasti kybernetické bezpečnosti se termín micro-kernels používá pro označení jádra operačního systému, které obsahuje pouze nezbytně nutné funkce a služby. Tento přístup přináší výhody v oblasti bezpečnosti, neboť útočník má méně možností, jak zneužít zranitelnosti v jádře systému.

Kromě toho mohou být funkce operačního systému, které nejsou nezbytné pro běh aplikací, implementovány jako samostatné procesy, které běží mimo jádro. Tím se zvyšuje bezpečnost systému, neboť chyby v těchto procesech nemají vliv na stabilitu jádra.

Celkově lze říci, že použití micro-kernels je jedním z přístupů, jak zvýšit bezpečnost operačního systému a minimalizovat riziko útoků.

General-purpose sandboxing,

Obecné sandboxování je metoda, která slouží k izolaci a omezení přístupu k určitým funkcím a zdrojům aplikace. Tato technologie umožňuje chránit systém před nebezpečným kódem a zabezpečit citlivá data. Sandboxování se používá v různých oblastech, jako je například virtualizace, testování aplikací nebo v oblasti kybernetické bezpečnosti. V oblasti kybernetické bezpečnosti se sandboxování používá k analýze neznámých souborů a programů, které mohou obsahovat malware. Sandboxování umožňuje analyzovat chování programu v izolovaném prostředí, což umožňuje identifikovat nebezpečné chování a přijmout potřebná opatření k ochraně systému.

Kernel namespaces, seccomp, Linux kernel capabilities

Kernelové jmenné prostory

Kernelové jmenné prostory jsou mechanismus, který umožňuje oddělit procesy a zdroje v operačním systému. Tento mechanismus může být využit pro izolaci procesů a snížení rizika útoků v kybernetickém prostředí.

Seccomp

Seccomp je bezpečnostní mechanismus v operačním systému, který umožňuje omezit přístup procesů k systémovým voláním. Tento mechanismus může být využit pro snížení rizika útoků v kybernetickém prostředí.

Linuxové jádrové schopnosti

Linuxové jádrové schopnosti jsou mechanismus, který umožňuje procesům získávat přístup k určitým zdrojům v operačním systému. Tyto schopnosti mohou být využity pro izolaci procesů a snížení rizika útoků v kybernetickém prostředí.

Access control model of web ecosystem

Model přístupové kontroly ekosystému webu se používá k řízení přístupu k informacím a zdrojům na internetu. Tento model zahrnuje různé metody, jako jsou autentizace, autorizace a auditování, které pomáhají chránit citlivé informace a zdroje před neoprávněným přístupem.

Autentizace je proces ověřování identity uživatele. To může zahrnovat použití hesel, biometrických údajů nebo jiných metod pro ověření identity uživatele.

Autorizace je proces řízení přístupu k informacím a zdrojům na základě ověřené identity uživatele. To zahrnuje určování, kteří uživatelé mají přístup k určitým informacím a zdrojům a jakým způsobem mohou tyto zdroje používat.

Auditování je proces sledování a zaznamenávání aktivit uživatelů na internetu. To zahrnuje zaznamenávání přístupu k informacím a zdrojům, změn v datech a dalších aktivit, které mohou mít vliv na bezpečnost informací a zdrojů.

Správné použití modelu přístupové kontroly ekosystému webu může pomoci chránit citlivé informace a zdroje před neoprávněným přístupem a zneužitím. Je důležité, aby organizace měly správné politiky a postupy pro řízení přístupu k informacím a zdrojům na internetu a aby tyto politiky a postupy byly pravidelně aktualizovány a přizpůsobeny aktuálním hrozbám v kybernetické bezpečnosti.

Single-origin policy

Single-origin policy (politika jednoho zdroje) je bezpečnostní mechanismus v prohlížečích webových stránek, který omezuje přístup JavaScriptu a dalším skriptovacím jazykům ke zdrojům z jiných domén. Tento mechanismus zabraňuje útočníkům využívat kódy na jedné stránce a aplikovat je na jinou stránku, což může vést k útokům typu cross-site scripting (XSS) a dalším bezpečnostním hrozbám. Jedná se o důležitý prvek v ochraně webových aplikací a uživatelských dat.

Preservations of integrity of data and code

Jedním z hlavních cílů kybernetické bezpečnosti je zajistit ochranu integrity dat a kódu. Integrity dat znamená, že data zůstanou nedotčena a nezměněna během přenosu nebo ukládání. Integrity kódu znamená, že kód zůstane nedotčen a nezměněn během vývoje, testování a nasazení.

Existuje několik způsobů, jak zajistit ochranu integrity dat a kódu:

Je důležité, aby organizace měly plán na ochranu integrity dat a kódu a aby tento plán pravidelně aktualizovaly a testovaly, aby byly připraveny na případné útoky.

Sandboxing in web

Sandboxing je bezpečnostní opatření v kybernetické bezpečnosti, které umožňuje izolovat procesy a aplikace od ostatních částí systému. Tento koncept se nejčastěji používá v internetových prohlížečích, kde jsou webové stránky spouštěny v izolovaném prostředí, aby se minimalizovala možnost útoku na uživatelský systém. Sandbox umožňuje bezpečné testování nových aplikací a softwaru, aniž by se ohrozila bezpečnost celého systému.

Content security policy.

Content Security Policy (CSP) je bezpečnostní mechanismus, který slouží k omezení rizik spojených s útoky typu Cross-Site Scripting (XSS), Clickjacking a dalšími útoky založenými na vkládání kódu do webových stránek.

CSP umožňuje definovat, jaké zdroje jsou povoleny pro načítání na stránce, jako jsou skripty, obrázky, styly a další. To znamená, že pokud je například na stránce použit skript z externího zdroje, který není definován v CSP, bude blokován a stránka se nezobrazí.

CSP lze definovat pomocí HTTP hlavičky nebo meta tagu v HTML kódu stránky. Správné nastavení CSP může výrazně snížit riziko útoků na webové stránky a zlepšit celkovou bezpečnost aplikace.

Network protocols, TCP, DNS, BGP

Síťové protokoly jsou soubory pravidel a postupů, které umožňují komunikaci mezi počítači v síti. Tyto protokoly se používají pro přenos dat v rámci sítě a zajišťují bezpečnost a spolehlivost přenosu.

TCP

TCP (Transmission Control Protocol) je jedním z nejpoužívanějších protokolů pro přenos dat v počítačových sítích. Tento protokol zajišťuje spolehlivý přenos dat mezi počítači a kontroluje, zda dorazila všechna data bez chyb.

DNS

DNS (Domain Name System) je systém, který překládá doménová jména na IP adresy. Tento systém umožňuje počítačům v síti komunikovat s ostatními počítači pomocí doménových jmen, což je pro uživatele mnohem pohodlnější než používání IP adres.

BGP

BGP (Border Gateway Protocol) je protokol, který se používá pro směrování dat mezi autonomními systémy (AS). Tento protokol zajišťuje, že data jsou směrována správným způsobem a že jsou doručena do cílové sítě.

V kontextu kybernetické bezpečnosti jsou tyto protokoly důležité pro zajištění bezpečnosti a spolehlivosti přenosu dat. Například útoky typu DDoS mohou být zaměřeny na síťové protokoly, jako je BGP, aby způsobily výpadek sítě. Útočníci mohou také využít chyby v TCP protokolu k útoku na počítačový systém. DNS pak může být cílem útoků typu DNS spoofing, kdy útočník změní odpověď DNS serveru tak, aby uživatel byl přesměrován na škodlivou stránku. Je tedy důležité zajistit bezpečnost těchto protokolů a sledovat jejich správnou funkci.

Security of HTTPs

HTTPs je protokol pro zabezpečenou komunikaci mezi webovými servery a prohlížeči. Tento protokol zajišťuje šifrování dat, která jsou přenášena mezi serverem a prohlížečem, a tím chrání uživatele před útoky hackerů.

Jak funguje HTTPs?

Když uživatel navštíví webovou stránku s protokolem HTTPs, jeho prohlížeč zašle požadavek na server, aby zahájil zabezpečenou komunikaci. Server poté odešle certifikát, který obsahuje veřejný klíč, který bude použit k šifrování dat. Prohlížeč ověří platnost certifikátu a poté zašifruje data pomocí veřejného klíče a odešle je zpět na server. Server poté dešifruje data pomocí svého soukromého klíče.

Výhody HTTPs

Závěr

HTTPs je důležitým nástrojem pro zabezpečení webových stránek a ochranu uživatelů před útoky hackerů. Použití HTTPs je dnes již standardem a každý majitel webové stránky by měl zajistit, aby jeho stránka byla chráněna touto technologií.

Mechanism of certificates

Mechanismus certifikátů je klíčovým prvkem kybernetické bezpečnosti. Certifikáty jsou digitální identifikátory, které slouží k ověření totožnosti uživatele, serveru nebo aplikace. Certifikáty se vydávají certifikačními autoritami (CA) a obsahují informace o vlastníkovi, platnosti a veřejném klíči.

Certifikáty umožňují šifrování komunikace mezi uživateli a serverem, což zajišťuje důvěrnost a integritu dat. Pokud uživatel obdrží certifikát od serveru, může se spolehnout na to, že komunikuje s legitimním serverem a že data jsou šifrována tak, aby nebyla čitelná pro neoprávněné osoby.

Pro správnou funkci certifikátů je důležité, aby byly správně vydávány, ověřovány a spravovány. Certifikační autority musí mít dostatečné zabezpečení a důvěryhodnost, aby se zabránilo podvržení certifikátů. Uživatelé musí být schopni ověřit platnost certifikátu a důvěryhodnost vydavatele.

Mechanismus certifikátů je klíčovým prvkem kybernetické bezpečnosti a je důležité, aby byl správně implementován a spravován, aby se minimalizovala rizika kybernetických útoků.

Security of certificate infrastructure.

Certifikační infrastruktura (PKI) je systém, který umožňuje vydávat a ověřovat digitální certifikáty. Tyto certifikáty jsou klíčové pro zajištění bezpečného přenosu dat na internetu. Proto je důležité zajistit bezpečnost celé PKI.

Hrozby pro certifikační infrastrukturu

Existuje několik způsobů, jak mohou být certifikační autority (CA) ohroženy:

Zabezpečení certifikační infrastruktury

Aby byla certifikační infrastruktura bezpečná, je nutné dodržovat několik zásad:

Dodržování těchto zásad je klíčové pro zajištění bezpečnosti certifikační infrastruktury a ochranu před útoky.

Firewalls

Firewally jsou základním prvkem zabezpečení počítačových sítí. Jedná se o software nebo hardware, který slouží k ochraně sítě před neoprávněným přístupem. Firewall může blokovat nebo povolit přístup k určitým síťovým službám na základě definovaných pravidel.

Typy firewalů

Stavový firewall

Stavový firewall sleduje stav síťového spojení a umožňuje povolit přístup pouze k platným spojením. Tento typ firewallu je schopen rozpoznat, zda je spojení iniciováno z vnitřní nebo vnější sítě a podle toho povolit nebo blokovat přístup.

Paketový firewall

Paketový firewall pracuje na úrovni síťového protokolu a umožňuje blokovat nebo povolit přenos jednotlivých paketů na základě definovaných pravidel. Tento typ firewallu je méně sofistikovaný než stavový firewall a může být snadno překonán pokročilejšími útoky.

Aplikační firewall

Aplikační firewall pracuje na úrovni aplikace a umožňuje blokovat nebo povolit přístup k jednotlivým aplikacím nebo službám na základě definovaných pravidel. Tento typ firewallu je nejsofistikovanější a umožňuje detailní kontrolu nad síťovým provozem.

Konfigurace firewallu

Správná konfigurace firewallu je klíčová pro úspěšné zabezpečení sítě. Firewall by měl být konfigurován tak, aby blokoval veškerý nevyžádaný síťový provoz a povoloval pouze provoz, který je nezbytný pro fungování sítě. Důležité je také pravidelně aktualizovat pravidla firewallu a sledovat jeho logy pro odhalení podezřelého síťového provozu.

Network intrusion detection

Síťová detekce proniknutí (NID) je proces monitorování síťového provozu a hledání podezřelých aktivit, které by mohly naznačovat útok na síť. NID může být prováděno pomocí hardwarových zařízení nebo softwarových aplikací, které analyzují síťový provoz a hledají známky útoku.

Existuje několik typů NID, včetně detekce chování, detekce signatur a detekce anomálií. Detekce chování sleduje chování uživatelů a aplikací v síti a hledá podezřelé vzorce, jako jsou opakované pokusy o přihlášení nebo přístup k citlivým datům. Detekce signatur používá databázi známých útoků a hledá shodu mezi síťovým provozem a těmito známými útoky. Detekce anomálií sleduje neobvyklé vzorce v síťovém provozu a upozorňuje na podezřelé aktivity.

NID je důležitou součástí kybernetické bezpečnosti a pomáhá chránit organizace před útoky na síť. Správně nakonfigurovaný a spravovaný NID může identifikovat útoky včas a umožnit rychlou reakci na ně.

Network intrusion prevention

Ochrana proti vniknutí do sítě (Network intrusion prevention) je důležitou součástí kybernetické bezpečnosti. Tato technologie slouží k detekci a prevenci neoprávněného přístupu do sítě.

Jak to funguje?

Systém ochrany proti vniknutí do sítě monitoruje provoz v síti a analyzuje ho na základě předem definovaných pravidel. Pokud je detekována podezřelá aktivita, systém aktivuje bezpečnostní opatření, jako je například blokování přístupu nebo varování správce sítě.

Proč je to důležité?

Bez ochrany proti vniknutí do sítě mohou být počítače a další zařízení v síti ohroženy útoky, jako jsou například útoky typu Denial of Service (DoS) nebo ransomware. Tyto útoky mohou způsobit výpadek sítě, ztrátu dat a další škody.

Závěr

Ochrana proti vniknutí do sítě je zásadní pro zajištění kybernetické bezpečnosti. Je důležité mít tuto technologii správně nakonfigurovanou a pravidelně aktualizovanou, aby byla schopna detekovat nové hrozby a bránit se jim.

Poznámka: V češtině se také často používá termín “prevence vniknutí do sítě”.

Thin client

Tenký klient je počítačový systém, který se používá pro přístup k centrálnímu serveru. Tento typ klienta nemá vlastní pevný disk ani většinu hardwarových komponentů, což znamená, že veškeré zpracování a ukládání dat se provádí na serveru. To znamená, že tenký klient je méně náchylný na útoky a viry, protože všechna data jsou uložena na centrálním serveru a ne na samotném klientovi.

V oblasti kybernetické bezpečnosti se tenký klient používá jako jedna z možností pro zabezpečení sítě. Protože všechna data jsou uložena na serveru, mohou být snadno monitorována a chráněna před neoprávněným přístupem. Tenké klienty také umožňují snadnou aktualizaci softwaru a zabezpečení, protože všechny změny se provádějí pouze na centrálním serveru.

Celkově lze říci, že tenký klient je užitečným nástrojem pro zabezpečení sítě a prevenci kybernetických útoků.

Intrusion deflection

Odklon útoků (anglicky Intrusion deflection) je proces, při kterém se snažíme zabránit útokům na počítačové systémy. Tento proces se skládá z několika kroků:

  1. Detekce útoku: Snažíme se identifikovat útoky, které jsou namířeny na naše systémy. K tomu můžeme použít různé nástroje, jako jsou například firewally, antiviry nebo systémy detekce anomálií.

  2. Odpověď na útok: Jakmile identifikujeme útok, musíme na něj adekvátně reagovat. To může zahrnovat například blokování útočníka, uzavření bezpečnostních děr nebo obnovení dat ze zálohy.

  3. Prevence budoucích útoků: Abychom minimalizovali riziko budoucích útoků, musíme zajistit, že jsou naše systémy dostatečně zabezpečené. To zahrnuje pravidelné aktualizace softwaru, silná hesla a další bezpečnostní opatření.

Odklon útoků je důležitou součástí kybernetické bezpečnosti a pomáhá chránit naše počítačové systémy před různými hrozbami, jako jsou například malware, phishing nebo DDoS útoky.

Denial of service attack

Útok typu Denial of Service (DoS) je útok, kdy útočník záměrně přetíží cílový systém, aby byl nedostupný pro legitimní uživatele. Toho lze dosáhnout různými způsoby, například pomocí floodingu síťového provozu, útoků na protokoly nebo využitím zranitelností v softwaru.

Druhy DoS útoků

Ochrana proti DoS útokům

Reflection attacks

Reflection attacks or reflected amplification attacks are a type of DDoS attack where the attacker sends a request to a server with a spoofed IP address, and the server responds to the victim with a much larger response than the original request. This causes the victim to be overwhelmed with traffic, eventually leading to denial of service.

How does it work?

  1. The attacker sends a request to a server with a spoofed IP address.
  2. The server responds to the request, but with a much larger response than the original request.
  3. The victim receives the amplified response, overwhelming their system and causing denial of service.

Prevention

  1. Implement anti-spoofing measures to prevent attackers from using spoofed IP addresses.
  2. Use traffic filtering to block traffic from known sources of reflection attacks.
  3. Use rate limiting to limit the amount of traffic that can be sent to a server in a given time period.

Syn-cookies

Syn-cookies jsou bezpečnostní opatření používaná v počítačových sítích k ochraně před útoky typu SYN flood. Tyto útoky jsou zaměřeny na přetížení sítě nebo serveru tím, že se zasílají velké množství SYN požadavků, které nejsou dokončeny, což vede ke ztrátě výkonu a výpadkům služeb.

Syn-cookies fungují tím, že místo ukládání SYN požadavků do paměti serveru, jsou informace o těchto požadavcích zakódovány do speciálního čísla, které je připojeno k odpovědi serveru na požadavek. Pokud je následující požadavek na server s tímto číslem, server rozpozná, že se jedná o platný požadavek a dokončí ho.

Tímto způsobem jsou Syn-cookies schopny odolat útokům typu SYN flood a zajistit, že server zůstane v provozu i při velkém množství požadavků.

Detection and protection against DOS.

DOS (Denial of Service) útoky jsou útoky, které mají za cíl zahlcení služby nebo systému, což vede k nedostupnosti pro legitimní uživatele. Pro ochranu proti těmto útokům je důležité mít implementované následující opatření:

Detekce DOS útoků

Ochrana proti DOS útokům

Poznámka: V češtině se používá termín DoS útok (Denial of Service).

DS2

Topics

Big Data concept, basic principles of distributed data processing, types and properties of NoSQL databases. BE4M36DS2 (Course web pages)

Questions

Big Data:

NoSQL databáze:

Škálování:

Síťové klamání (Network Fallacies):

  1. Spolehlivost sítě
  2. Nulová latence
  3. Nekonečná šířka pásma
  4. Bezpečná síť
  5. Homogenita sítě

Cluster (shluk):

Distribuční modely:

Architektury:

CAP věta:

ACID:

BASE:

Konzistence:

Konzistence čtení a zápisu:

Kvóra (Quorum):

Optimalizace výkonu:

MapReduce (architecture, functions, data flow, execution, use cases). Hadoop (MapReduce, HDFS).

MapReduce:

Hadoop:

Hadoop MapReduce:

HDFS - Hadoop Distributed File System:

XPath

XQuery

SPARQL

RiakKV

RiakKV Ring

Redis

Cassandra

MongoDB

Grafové datové struktury

Data locality

Graph partitioning

Neo4j

Cypher

ESW

Topics

Effective algorithms and optimization methods. Data structures, synchronization and multithreaded programs. BE4M36ESW (Course web pages)

Questions

Java Virtual Machine (JVM) a paměťové rozložení:

JVM Memory layout Frame

Zásobníkově orientované stroje (Stack-oriented machine processing):

Běžný ukazatel na objekt (Ordinary Object Pointer):

Komprimovaný ukazatel na objekt (Compressed Ordinary Object Pointer):

JVM Bytecode:

Just-In-Time (JIT) kompilátor:

Tiered Compilation (Stupňovitá kompilace):

On-Stack Replacement (OSR):

Disassembler

Decompiler

Globální a lokální bezpečný bod (Global and Local Safe Point):

Globální bezpečný bod (Global Safe Point):

Lokální bezpečný bod (Local Safe Point):

Čas do bezpečného bodu (Time to Safe Point):

Faktory ovlivňující čas do bezpečného bodu:

Význam času do bezpečného bodu:

Automatické správa paměti (Automatic Memory Management):

Funkce automatické správy paměti: - Alokace paměti: Přidělení paměti pro nové objekty a proměnné - Uvolňování paměti: Systém automaticky detekuje a uvolňuje paměť, která již není potřeba (nepoužívané objekty) - Minimalizace úniku paměti a fragmentace: Garbage collector se snaží minimalizovat úniky paměti a její fragmentaci

Výhody automatické správy paměti: - Zjednodušuje programování, protože se programátor nemusí starat o přidělování a uvolňování paměti - Snížení chyb spojených s paměťovou správou, jako jsou úniky paměti nebo přístup k nealokované paměti - Zvyšuje bezpečnost a stabilitu aplikace, protože garbage collector detekuje a řeší problémy s paměťovou správou

Nevýhody automatické správy paměti: - Vyšší režie a zátěž systému kvůli garbage collectoru a automatickému přidělování/uvolňování paměti - Menší kontrola nad správou paměti, což může vést k suboptimálnímu výkonu aplikace v některých případech - Předvídatelnost a výkon garbage collectoru závisí na implementaci a konfiguraci runtime prostředí

Generační hypotéza (Generational Hypothesis):

Principy generační hypotézy:

  1. Mnoho objektů zemře mladých: Většina objektů má krátkou životnost a je rychle zničena
  2. Málo starých objektů odkazuje na mladé: Méně často dochází k odkazům mezi starými a mladými objekty
  3. Málo objektů přežije dlouhou dobu: Jen malé procento objektů má dlouhou životnost

Aplikace generační hypotézy na garbage collectory:

Výhody použití generační hypotézy:

Nevýhody použití generační hypotézy:

Garbage Collectory:

Některé typy garbage collectorů:

  1. Mark and Sweep (Označit a Zamést):
    • Pracuje ve dvou fázích:
      1. Označení: Prochází živé objekty a označuje je jako dosažitelné
      2. Zametání: Uvolňuje paměť obsazenou objekty, které nebyly označeny jako dosažitelné
    • Nevýhody: Může způsobovat fragmentaci paměti a zpoždění při provádění garbage collection
  2. Copying (Kopírování):
    • Paměť je rozdělena na dvě poloviny: Aktivní a rezervní
    • Živé objekty jsou kopírovány z aktivní do rezervní paměti
    • Jakmile jsou všechny živé objekty kopírovány, celá aktivní paměť je uvolněna
    • Nevýhody: Vyžaduje více paměti, protože je rozdělena na dvě části, a může způsobit zpoždění při provádění garbage collection
  3. Generational (Generační):
    • Paměť je rozdělena na mladou a starou generaci
    • Využívá generační hypotézu pro efektivnější garbage collection
    • Častěji provádí garbage collection v mladé generaci, kde je vyšší pravděpodobnost uvolnění paměti
    • Výhody: Snížení režie a zátěže systému, minimalizace zpoždění způsobených garbage collection
    • Nevýhody: Vyšší složitost implementace
  4. Concurrent (Souběžný):
    • Provádí garbage collection současně s během aplikace, bez nutnosti zastavit všechna vlákna
    • Výhody: Snížení zpoždění a přerušení způsobených garbage collection, lepší výkon aplikace
    • Nevýhody: Vyšší složitost implementace a koordinace s běžícími vlákny
  5. Incremental (Inkrementální):
    • Rozděluje garbage collection do menších částí, které jsou prováděny postupně
    • Výhody: Snížení zpoždění a přerušení způsoben

CPU a paměťový profiling:

CPU profiling: - Zaměřuje se na měření a analýzu výkonu aplikace v souvislosti s využitím procesoru - Identifikuje funkce a části kódu, které vyžadují nejvíce času na zpracování - Pomáhá zjistit, kde lze provést optimalizace kódu pro zlepšení celkového výkonu aplikace

Metody CPU profilingu: 1. Sampling (vzorkování): Pravidelně sbírá informace o zásobníku volání (call stack) během běhu aplikace 2. Instrumentace: Vkládá sledovací kód přímo do aplikace, který zaznamenává informace o výkonu a zátěži CPU

Paměťový profiling: - Zaměřuje se na analýzu využití paměti aplikací - Identifikuje objekty, které způsobují zvýšené využití paměti, úniky paměti nebo fragmentaci paměti - Pomáhá zjistit, jak lze zlepšit paměťovou efektivitu a snížit nároky na paměť aplikace

Metody paměťového profilingu: 1. Heap snapshot (snímek haldy): Zaznamenává stav paměti (haldy) v určitém čase, identifikuje objekty a jejich velikosti 2. Allocation tracking (sledování alokace): Sleduje vytváření a uvolňování objektů v paměti během běhu aplikace 3. Garbage collection profiling: Analyzuje chování garbage collectoru, identifikuje dlouhotrvající operace a možné optimalizace

Nástroje pro CPU a paměťový profiling: - Existuje mnoho nástrojů a knihoven pro různé jazyky a prostředí, například: - VisualVM (pro Java) - Valgrind (pro C/C++) - Py-Spy (pro Python) - Ruby-prof (pro Ruby)

Vzorkování (Sampling) a trasování (Tracing) přístup:

Vzorkování (Sampling):

Trasování (Tracing):

Kdy použít vzorkování nebo trasování:

Fáze rozehřátí (Warm-up phase):

Důvody pro fázi rozehřátí: 1. Just-In-Time (JIT) kompilace: Aplikace založené na bytecode, jako je Java, používají JIT kompilátor pro kompilaci bytecode na strojový kód během runtime. Tato kompilace může trvat určitý čas a zpočátku zpomalit výkon. 2. Profilování a optimalizace: Aplikace nebo systém mohou provádět profilování a optimalizace během fáze rozehřátí, což může způsobit zpoždění v dosažení plného výkonu. 3. Cache a přednačítání: Aplikace mohou mít cache nebo přednačítání dat, které mohou být potřeba pro rychlejší běh. Tyto cache nebo přednačítaná data se mohou postupně naplňovat během fáze rozehřátí.

Jak zohlednit fázi rozehřátí při testování výkonu: - Během testování výkonu je důležité zohlednit fázi rozehřátí, protože může ovlivnit výsledky testů - Testy by měly být prováděny po dosažení optimálního výkonu aplikace nebo systému, aby poskytovaly správné a relevantní výsledky - Mohou být použity různé techniky pro zohlednění fáze rozehřátí, například: - Provedení několika krátkých běhů aplikace nebo testů před spuštěním hlavního testu - Použití statistických metod pro eliminaci nebo minimalizaci vlivu fáze rozehřátí na výsledky testů

Data race (soupeření o data):

Příčiny data race: 1. Neexistující nebo nesprávná synchronizace přístupu k datům 2. Chybějící zámky (locks) nebo bariéry (barriers) pro omezení přístupu k datům 3. Nesprávná implementace atomických operací nebo kritických sekcí

Jak předcházet data race: 1. Použití zámků (locks) pro zajištění vzájemného vyloučení při přístupu k datům 2. Využití atomických operací, které zajišťují, že během provedení operace nedojde k přerušení vlákny 3. Použití bariér (barriers) nebo podmínek (conditions) pro koordinaci a synchronizaci vláken 4. Vhodná dekompozice úloh a dat pro snížení potřeby sdílení dat mezi vlákny 5. Použití vysokoúrovňových abstrakcí a knihoven pro paralelní programování, které řeší synchronizaci za vás (např. OpenMP, TBB, C++11 threads)

Detekce data race: - Existují nástroje a techniky pro automatickou detekci data race, například: - Statická analýza kódu: Nástroje jako Clang Static Analyzer nebo PVS-Studio mohou pomoci identifikovat možné data race v kódu - Dynamická analýza běhu: Nástroje jako Helgrind (součást Valgrind), ThreadSanitizer nebo Intel Inspector mohou sledovat běh aplikace a detekovat data race za běhu

CPU pipelining (potrubí) a superskalární architektura:

CPU pipelining (potrubí):

Superskalární architektura:

Kombinace CPU pipeliningu a superskalární architektury:

  1. Instrukce jsou načítány do potrubí a rozděleny do menších kroků (fází)
  2. Procesor s superskalární architekturou může zpracovávat více instrukcí současně v rámci jednoho cyklu hodinových tiků
  3. Výsledkem je vyšší výkon a rychlejší zpracování instrukcí

Příklady procesorů s pipeliningem a superskalární architekturou:

Paměťová bariéra (Memory barrier):

Účel paměťových bariér:

  1. Zajištění, že zápis nebo čtení určitých dat je dokončeno před pokračováním dalších operací
  2. Zajištění, že změny v paměti provedené jedním vláknem nebo procesorem jsou viditelné pro ostatní vlákna nebo procesory
  3. Zajištění, že operace na sdílených datech jsou prováděny ve správném pořadí

Příklady paměťových bariér:

Použití paměťových bariér:

Volatile proměnná:

Java

C++

Synchronizace - tenké (thin), tlusté (fat) a zaujaté (biased) zámky:

Tenký zámek (Thin lock):

Tlustý zámek (Fat lock):

Zaujatý zámek (Biased locking):

Reentrant zámky:

Vlastnosti reentrant zámků:

  1. Povolují vnořené zamykání (nested locking), což umožňuje vláknu získat zámek vícekrát, aniž by došlo k uváznutí
  2. Zvyšují robustnost kódu tím, že se zabrání uváznutí při opakovaném získání zámku stejným vláknem
  3. Mohou poskytnout pokročilé funkce, jako je podpora přerušitelného zamykání, časově omezené zamykání nebo spravedlivé plánování
  import java.util.concurrent.locks.ReentrantLock;

  ReentrantLock lock = new ReentrantLock();

  // Získání zámku
  lock.lock();
  try {
      // kritická sekce
  } finally {
      // Uvolnění zámku
      lock.unlock();
  }
#include <mutex>

std::recursive_mutex mtx;

// Získání zámku
mtx.lock();
try {
    // kritická sekce
} catch (...) {
    // Uvolnění zámku
    mtx.unlock();
    throw;
}
// Uvolnění zámku
mtx.unlock();

Atomické operace založené na instrukcích porovnat-a-nastavit (compare-and-set):

Princip compare-and-set (CAS) operace:

  1. Porovnej hodnotu sdílené proměnné s očekávanou hodnotou
  2. Pokud se hodnoty shodují, nastav novou hodnotu proměnné
  3. Operace vrátí informaci, zda byla hodnota úspěšně nastavena nebo ne

Výhody compare-and-set operací:

Atomické aktualizátory polí (Atomic Field Updaters):

Výhody atomických aktualizátorů polí:

Použití atomických aktualizátorů polí:

Neblokující algoritmy (Non-blocking algorithms):

Typy neblokujících algoritmů:

  1. Lock-free algoritmy:
    • Zajišťují, že alespoň jedno vlákno dokončí svou operaci v konečném čase
    • Zabraňují uváznutí (deadlocks) a vyhladovění (starvation)
  2. Wait-free algoritmy:
    • Poskytují garanci, že každé vlákno dokončí svou operaci v konečném čase
    • Zabraňují uváznutí, vyhladovění a čekání na dokončení jiných vláken
  3. Obstruction-free algoritmy:
    • Poskytují garanci, že operace bude dokončena v konečném čase pouze v případě, že žádné jiné vlákno nezasahuje do provádění operace
    • Slabší záruky než lock-free a wait-free algoritmy, ale stále zabraňují uváznutí

Výhody neblokujících algoritmů:

Wait-free algoritmy:

Vlastnosti wait-free algoritmů: 1. Konečná konvergence: Každé vlákno dokončí svou operaci v konečném čase, bez ohledu na ostatní vlákna 2. Robustnost: Odpovědnost za dokončení operace leží na provádějícím vlákně, což zabraňuje závislosti na chování jiných vláken 3. Spravedlivost: Žádné vlákno nemůže být trvale blokováno jiným vláknem, což zabraňuje vyhladovění

Výhody wait-free algoritmů: - Vysoká škálovatelnost a výkon v paralelním prostředí - Zlepšení spolehlivosti a robustnosti paralelního kódu díky odstranění závislosti na chování jiných vláken - Poskytují nejlepší záruky konvergence ze všech typů neblokujících algoritmů

Příklady wait-free algoritmů: - Wait-free fronty, zásobníky nebo počítadla, které zajišťují spravedlivý přístup ke sdíleným datovým strukturám - Wait-free implementace atomických proměnných nebo operací, jako jsou compare-and-set nebo fetch-and-add

Použití wait-free algoritmů může být složitější než použití lock-free nebo obstruction-free algoritmů, ale poskytuje nejlepší záruky pro paralelní výpočty.

Neblokující zásobník (LIFO) - Non-blocking Stack:

Základní operace nebokujícího zásobníku (LIFO):

  1. Push: Přidání prvku na vrchol zásobníku
  2. Pop: Odebrání prvku z vrcholu zásobníku

Implementace nebokujícího zásobníku (LIFO):

Výhody nebokujícího zásobníku (LIFO):

Statická a dynamická analýza paměti:

Statická analýza paměti:

Dynamická analýza paměti:

Výhody statické a dynamické analýzy paměti:

Mělká velikost (Shallow size) a zadržená velikost (Retained size):

Mělká velikost (Shallow size): - Velikost paměti, kterou přímo zabírá objekt, bez zahrnutí paměti zabírané objekty, na které odkazuje - Zahrnuje pouze velikost objektu a jeho přímých atributů, nikoli objektů, které jsou dostupné prostřednictvím referencí - Mělká velikost objektu je konstantní pro objekty stejného typu, protože závisí pouze na počtu atributů a jejich typu

Zadržená velikost (Retained size): - Celková velikost paměti, kterou zabírá objekt a všechny objekty, které jsou dostupné pouze prostřednictvím tohoto objektu - Zahrnuje velikost objektu a všechny jeho tranzitivně dostupné objekty prostřednictvím referencí - Pokud by byl tento objekt uvolněn, zadržená velikost ukazuje, kolik paměti by bylo uvolněno

Význam mělké a zadržené velikosti při analýze paměti: - Pomáhají identifikovat úniky paměti (memory leaks) a nadměrné využití paměti v aplikacích - Umožňují vývojářům zjistit, které objekty nebo části kódu nejvíce přispívají k celkovému využití paměti - Poskytují informace, které mohou vést k optimalizaci kódu a efektivnějšímu využití paměti

Únik paměti (Memory leak):

Příčiny úniků paměti: 1. Nesprávné uvolňování paměti: Programátor alokuje paměť, ale zapomene ji uvolnit 2. Cyklické reference: Dva nebo více objektů si navzájem udržují reference, což brání jejich automatickému uvolnění 3. Statické proměnné: Proměnné, které zůstávají v paměti po celou dobu běhu programu, a které mohou neúmyslně udržovat reference na objekty

Detekce a řešení úniků paměti:

Datové struktury

  1. Pole (Array):
    • Statická datová struktura s pevnou velikostí
    • Umožňuje rychlý přístup k prvku na základě indexu
    • Nevýhoda: neměnná velikost, která může vést k neefektivnímu využití paměti
  2. Spojový seznam (Linked list):
    • Dynamická datová struktura, která se skládá z uzlů obsahujících data a odkaz na další uzel v seznamu
    • Umožňuje snadné vkládání a mazání prvků bez nutnosti přesunu ostatních prvků
    • Nevýhoda: pomalejší přístup k prvkům, protože je nutné projít seznam od začátku
  3. Zásobník (Stack):
    • Lineární datová struktura, která pracuje na principu LIFO (Last In, First Out)
    • Umožňuje přidávání a odebírání prvků pouze z vrcholu zásobníku
    • Vhodné pro úlohy, které vyžadují rekurzi nebo zpětné sledování (backtracking)
  4. Fronta (Queue):
    • Lineární datová struktura, která pracuje na principu FIFO (First In, First Out)
    • Umožňuje přidávání prvků na konec fronty a odebírání z jejího začátku
    • Vhodné pro úlohy, které vyžadují sekvenční zpracování dat
  5. Strom (Tree):
    • Hierarchická datová struktura, která se skládá z uzlů propojených hranami
    • Umožňuje efektivní vyhledávání, vkládání a mazání prvků v závislosti na konkrétním typu stromu (binární strom, AVL strom, B-strom, atd.)
    • Vhodné pro úlohy, které vyžadují hierarchickou organizaci dat
  6. Graf (Graph):
    • Datová struktura, která se skládá z uzlů (vrcholů) a hran mezi nimi
    • Umožňuje reprezentovat složité vztahy mezi objekty
    • Vhodné pro

Java primitivní typy a objekty:

Primitivní typy:

Objekty:

Rozdíly mezi primitivními typy a objekty: 1. Ukládání: Primitivní typy jsou ukládány na zásobníku, zatímco objekty na haldě 2. Předávání: Primitivní typy jsou předávány hodnotou, objekty referencí 3. Výchozí hodnoty: Primitivní typy mají výchozí hodnoty (např. 0 pro int, false pro boolean), zatímco objekty mají výchozí hodnotu null 4. Metody: Objekty mohou mít metody a být součástí dědičnosti, primitivní typy nemají metody ani dědičnost 5. Wrapper třídy: Pro každý primitivní typ existuje “wrapper” třída, která umožňuje pracovat s primitivním typem jako s objektem (např. Integer pro int, Double pro double)

Auto-boxing a unboxing:

Auto-boxing:

Unboxing:

Efektivita paměti složitých datových struktur:

Efektivita paměti datových struktur závisí na:

  1. Režii paměti: Každá datová struktura vyžaduje určité množství paměti pro uložení dodatečných informací, jako jsou odkazy, ukazatele nebo metadata.
  2. Pevnosti velikosti: Některé datové struktury mají pevnou velikost, zatímco jiné mohou být dynamicky zvětšovány nebo zmenšovány podle potřeby.
  3. Vnitřní fragmentace: Vnitřní fragmentace nastává, když datová struktura má nevyužité části paměti, které nelze přiřadit jiným objektům.

Příklady efektivity paměti některých složitých datových struktur:

  1. Binární vyhledávací strom (Binary Search Tree):
    • Efektivní v případě, že je strom vyvážený
    • Má režii paměti z důvodu ukládání odkazů na levý a pravý potomek pro každý uzel
    • Může mít neefektivní využití paměti, pokud je strom silně nevyvážený
  2. Hash tabulka (Hash Table):
    • Má režii paměti pro ukládání ukazatelů na prvky a pro správu kolizí
    • Při správně nastavené velikosti tabulky a vhodné hashovací funkci může být efektivní z hlediska paměti
    • Vnitřní fragmentace nastává, když je velikost tabulky příliš velká nebo malá vzhledem k počtu prvků
  3. Grafová reprezentace (Graph Representation):
    • Matice sousednosti: Má režii paměti kvůli ukládání celé matice, i když je graf řídký (má málo hran)
    • Seznam sousednosti: Má menší režii paměti než matice sousednosti, ale vyžaduje ukládání odkazů na seznamy sousedů pro každý vrchol
    • Efektivita paměti závisí na hustotě grafu a způsobu reprezentace

Optimalizace efektivity paměti:

Při návrhu a implementaci složitých datových struktur je důležité najít rovnováhu mezi efektivitou paměti, výkonem a čitelností kódu. Vybraná datová struktura by měla být vhodná pro konkrétní problém, snadno použitelná a rozšiřitelná a současně co nejméně náročná na paměť.

Kolekce pro výkon:

Výběr správné kolekce pro výkon závisí na požadavcích na časovou složitost a paměťovou efektivitu konkrétního problému. Některé běžné kolekce v Javě a jejich výkonnostní charakteristiky:

  1. ArrayList:
    • Rychlý přístup k prvkům pomocí indexu (O(1))
    • Pomalejší přidávání a odebírání prvků uprostřed seznamu (O(n))
    • Dynamicky se zvětšuje, když je kapacita překročena
  2. LinkedList:
    • Rychlé přidávání a odebírání prvků na začátku a konci seznamu (O(1))
    • Pomalejší přístup k prvkům pomocí indexu (O(n))
    • Vyšší režie paměti kvůli ukládání odkazů na předchozí a následující prvky
  3. HashSet:
    • Rychlé přidávání, odebírání a vyhledávání prvků (průměrně O(1))
    • Nepodporuje žádné pořadí prvků
    • Vyšší režie paměti než ArrayList, ale nižší než LinkedList
  4. TreeSet:
    • Rychlé přidávání, odebírání a vyhledávání prvků (O(log n))
    • Udržuje prvky seřazené podle jejich přirozeného řazení nebo podle komparátoru
    • Vyšší režie paměti než HashSet
  5. HashMap:
    • Rychlý přístup, přidávání a odebírání klíč-hodnota párů (průměrně O(1))
    • Nepodporuje žádné pořadí klíčů ani hodnot
    • Vyšší režie paměti než ArrayList, ale nižší než LinkedList
  6. TreeMap:
    • Rychlý přístup, přidávání a odebírání klíč-hodnota párů (O(log n))
    • Udržuje klíče seřazené podle jejich přirozeného řazení nebo podle komparátoru
    • Vyšší režie paměti než HashMap

Při výběru kolekce pro výkon zvažte následující faktory:

  1. Požadovaná časová složitost operací (přístup, přidávání, odebírání, vyhledávání)
  2. Pořadí prvků (potřeba udržovat prvky seřazené nebo ne)
  3. Paměťová efektivita (režie paměti a dynamické zvětšování/zmenšování)
  4. Podpora pro konkurenci a synchronizaci (např. ConcurrentHashMap pro bezpečné použití ve vícevláknovém prostředí)

Typově specifické kolekce:

Typově specifické kolekce jsou kolekce, které jsou navrženy pro ukládání primitivních datových typů nebo konkrétních tříd. Použití těchto kolekcí může zlepšit výkon a snížit režii paměti, protože se eliminuje potřeba autoboxingu a unboxingu.

Některé příklady typově specifických kolekcí:

  1. Trove knihovna (Java):
    • Poskytuje kolekce pro primitivní typy, jako jsou TIntArrayList, TDoubleHashSet, TObjectIntHashMap atd.
    • Nabízí nižší režii paměti a rychlejší operace než standardní Java kolekce
  2. FastUtil knihovna (Java):
    • Poskytuje kolekce pro primitivní typy, jako jsou LongArrayList, Int2ObjectOpenHashMap, DoubleLinkedOpenHashSet atd.
    • Nabízí nízkoúrovňové kolekce pro rychlý přístup a manipulaci s daty
    • Rychlejší než standardní Java kolekce a podporuje vysokou kompresi dat
  3. Apache Commons Primitives (Java):
    • Poskytuje kolekce pro primitivní typy, jako jsou IntList, DoubleStack, ObjectIntMap atd.
    • Snadné použití a integrace se standardními Java kolekcemi
  4. Eclipse Collections (Java):
    • Poskytuje kolekce pro primitivní typy i objekty, jako jsou IntArrayList, LongHashSet, MutableObjectIntMap atd.
    • Bohatá API pro práci s daty a pokročilé funkce, jako jsou paralelní zpracování, lazy evaluace, atd.
  5. C++ Standard Template Library (STL):
    • Poskytuje kolekce pro primitivní typy i třídy, jako jsou vector, list, set, map, atd.
    • Přizpůsobitelné a rozšiřitelné pomocí šablon a vlastních komparátorů nebo alokátorů

Při výběru typově specifických kolekcí zvažte následující faktory:

  1. Výkon: Typově specifické kolekce mohou poskytnout rychlejší operace a nižší režii paměti než obecné kolekce
  2. Integrace: Zkontrolujte, jak snadno lze typově specifickou kolekci integrovat do vaší aplikace a jak dobře spolupracuje se standardními kolekcemi nebo knihovnami
  3. Kompatibilita: Ujistěte se, že typově specifická kolekce je kompatibilní s vaší verzí jazyka a platformy
  4. Podpora a údržba: Zvažte úroveň podpory a údržby pos

Otevřené adresování hashování:

Otevřené adresování hashování je metoda řešení kolizí v hash tabulkách, která nevyžaduje použití externích datových struktur (např. seznamů) pro ukládání prvků s kolizí. Místo toho jsou všechny prvky uloženy přímo v hash tabulce.

Klíčové vlastnosti otevřeného adresování hashování:

  1. Kolize řešeny prostřednictvím sekvenčního hledání volného místa v hash tabulce
  2. Různé metody pro hledání volného místa:
    • Lineární sondování: Při kolizi se postupně prochází následující pozice, dokud není nalezeno volné místo
    • Kvadratické sondování: Při kolizi se skáče na pozice s rostoucími kvadratickými intervaly, dokud není nalezeno volné místo
    • Dvojité hashování: Při kolizi se použije druhá hashovací funkce pro určení intervalu skoků, dokud není nalezeno volné místo
  3. Prostorová efektivita: Otevřené adresování hashování může mít nižší režii paměti než hashování s řetězci, protože nevyžaduje externí datové struktury
  4. Výkon: Otevřené adresování hashování může být rychlejší než hashování s řetězci, pokud je kolizí málo a tabulka má dostatečnou kapacitu
  5. Nutnost udržovat nízký faktor zatížení (počet prvků vůči kapacitě tabulky) pro udržení dobrého výkonu

Při použití otevřeného adresování hashování je důležité zajistit, že hash tabulka má dostatečnou kapacitu a je pravidelně zvětšována nebo zmenšována podle počtu prvků. To pomáhá minimalizovat počet kolizí a udržet dobrou efektivitu vyhledávání, přidávání a odebírání prvků.

Schémata řešení kolizí

Schémata řešení kolizí jsou metody, které se používají k řešení kolizí v hash tabulkách. Kolize nastávají, když dva různé prvky mají stejnou hash hodnotu nebo jsou mapovány na stejnou pozici v tabulce. Zde jsou některá základní schémata řešení kolizí:

  1. Řetězení (Chaining):
    • Každá pozice v hash tabulce obsahuje ukazatel na externí datovou strukturu (např. spojový seznam nebo strom)
    • Při kolizi se nový prvek přidá do datové struktury spojené s danou pozicí
    • Výhody: Jednoduché řešení, které umožňuje vysoký faktor zatížení
    • Nevýhody: Vyžaduje více paměti pro externí datové struktury a může způsobit zpomalení při mnoha kolizích
  2. Otevřené adresování (Open Addressing):
    • Všechny prvky jsou uloženy přímo v hash tabulce
    • Při kolizi se hledá volné místo v tabulce pomocí různých metod (např. lineární sondování, kvadratické sondování, dvojité hashování)
    • Výhody: Nižší režie paměti a může být rychlejší než řetězení, pokud je kolizí málo
    • Nevýhody: Nutnost udržovat nízký faktor zatížení a složitější řešení
  3. Koalescentní hashování (Coalesced Hashing):
    • Kombinuje vlastnosti řetězení a otevřeného adresování
    • Při kolizi se nový prvek přidá na volné místo v tabulce a spojí se s předchozím prvkem v kolizním řetězci
    • Výhody: Lepší využití paměti než řetězení a může být rychlejší než otevřené adresování
    • Nevýhody: Složitější implementace a může být pomalejší než otevřené adresování při nízkém faktoru zatížení
  4. Perfect hashing (Perfektní hashování):
    • Používá dvě úrovně hashovacích funkcí pro zajištění, že nebudou žádné kolize
    • První úroveň rozděluje prvky do skupin, druhá úroveň použije samostatnou hashovací funkci pro každou

Bloom filters, complexity, false positives, Bloom filter extensions

Bloom filtry:

Bloom filtry jsou pravděpodobnostní datové struktury, které umožňují testování přítomnosti prvku v množině. Bloom filtry používají více hashovacích funkcí a bitové pole pro uložení informací o prvcích.

Složitost:

Falešné pozitivy:

Rozšíření Bloom filtrů:

  1. Scalable Bloom Filters (Škálovatelné Bloom filtry):
    • Umožňují dynamicky přizpůsobovat velikost bitového pole a počet hashovacích funkcí podle počtu prvků v množině
    • Zajišťují konstantní pravděpodobnost falešných pozitiv při růstu množiny
  2. Counting Bloom Filters (Počítací Bloom filtry):
    • Rozšiřují klasické Bloom filtry tím, že udržují počet výskytů prvku místo jednoduché přítomnosti
    • Umožňují přidávání i odebírání prvků, avšak za cenu vyšší režie paměti
  3. Cuckoo Filters (Kukaččí filtry):
    • Vylepšení Bloom filtrů, které umožňují efektivnější práci s pamětí a poskytují lepší výkon pro testování přítomnosti prvku v množině
    • Používají kukaččí hashování pro řešení kolizí a udržují pouze část informací o prvku (např. fingerprint)
  4. Invertible Bloom Lookup Tables (Invertibilní Bloom vyhledávací tabulky):
    • Rozšiřují Bloom filtry tím, že umožňují ukládat a získávat páry klíč-hodnota
    • Umožňují pokročilé operace, jako je sjednocení, průnik a rozdíl mezi množinami klíčů a hodnot
    • Využívají lineární sondování a kompresi dat pro efektivní využití paměti a rychlé vyhledávání
  5. Space-saving Bloom Filters (Úsporné Bloom filtry):
    • Optimalizují paměťovou náročnost Bloom filtrů tím, že dynamicky přizpůsobují velikost bitového pole a počet hashovacích funkcí
    • Využívají metody pro odhad pravděpodobnosti falešných pozitiv a minimalizují paměťovou režii při udržení požadované úrovně přesnosti
  6. DLeft Counting Bloom Filters (DLeft Počítací Bloom filtry):
    • Kombinují vlastnosti DLeft hashování a počítacích Bloom filtrů pro efektivní ukládání a vyhledávání páry klíč-hodnota
    • Umožňují přidávání, odebírání a aktualizaci prvků s nízkou pravděpodobností falešných pozitiv a efektivním využitím paměti
  7. Layered Bloom Filters (Vrstvené Bloom filtry):
    • Využívají více vrstev Bloom filtrů s různými parametry pro rychlé vyhledávání a eliminaci falešných pozitiv
    • Umožňují postupně zvyšovat přesnost vyhledávání při zachování rychlosti a efektivnosti paměti

Tyto rozšíření Bloom filtrů řeší různé úkoly a výzvy spojené s testováním přítomnosti prvku v množině, přičemž každé rozšíření se zaměřuje na konkrétní aspekt, jako je škálovatelnost, dynamické přidávání a odebírání prvků, efektivita paměti nebo podpora pro práci s páry klíč-hodnota.

Reference types - weak, soft, phantom

  1. Silné reference (Strong references):
    • Běžné reference, které používáme při práci s objekty
    • Pokud je objekt dosažitelný přes silnou referenci, nebude uvolněn garbage collectorem
  2. Slabé reference (Weak references):
    • Vytváříme je pomocí třídy java.lang.ref.WeakReference
    • Pokud je objekt dosažitelný pouze přes slabé reference, může být kdykoliv uvolněn garbage collectorem
    • Často používány pro implementaci cache, která se automaticky uvolní při nedostatku paměti
  3. Měkké reference (Soft references):
    • Vytváříme je pomocí třídy java.lang.ref.SoftReference
    • Pokud je objekt dosažitelný pouze přes měkké reference, může být uvolněn garbage collectorem, ale pouze pokud je potřeba uvolnit paměť
    • Užitečné pro implementaci cache, která se udržuje v paměti, dokud není potřeba uvolnit prostředky
  4. Fantomové reference (Phantom references):
    • Vytváříme je pomocí třídy java.lang.ref.PhantomReference
    • Neslouží k přístupu k objektu, ale pouze k zaznamenání, že byl objekt uvolněn garbage collectorem
    • Užitečné pro sledování životního cyklu objektů a provádění úklidu po uvolnění objektu

Tyto různé typy referencí nám umožňují pracovat s objekty v Javě různými způsoby a ovlivňovat chování garbage collectoru při uvolňování paměti. Slabé, měkké a fantomové reference nám umožňují vytvářet pokročilé datové struktury a algoritmy, které pracují efektivně s omezenými zdroji a reagují na potřeby aplikace.

Alokace objektů v JVM:

  1. Mladá generace (Young Generation):
    • Většina objektů je alokována v mladé generaci
    • Mladá generace se dělí na tři části:
      • Eden: místo, kde jsou všechny nové objekty alokovány
      • Survivor 1 (S0) a Survivor 2 (S1): slouží k ukládání objektů, které přežily garbage collection v Eden prostoru
  2. Alokace objektu:
    • Objekt je nejprve alokován v Eden prostoru
    • Pokud Eden prostor dosáhne kapacity, spustí se garbage collection (tzv. minor GC) pro mladou generaci
    • Objekty, které přežijí minor GC, jsou přesunuty do jednoho z Survivor prostorů (S0 nebo S1)
  3. Promoci objektu do staré generace:
    • Pokud objekt přežije určitý počet minor GC (záleží na nastavení JVM), je promován do staré generace
    • Stará generace obsahuje objekty, které přežily více garbage collection a jsou pravděpodobněji dlouhodobě používány
  4. Alokace velkých objektů:
    • Velké objekty, které nemohou být alokovány v mladé generace, jsou přímo alokovány v staré generaci
  5. Garbage collection pro starou generaci:
    • Pokud stará generace dosáhne kapacity, spustí se garbage collection (tzv. major GC nebo full GC) pro celou heap
    • Major GC je náročnější na výkon a trvá déle než minor GC

Alokace objektů v JVM je optimalizována pro efektivní správu paměti a rychlé uvolňování krátkodobě žijících objektů. Garbage collector a generace paměti pomáhají minimalizovat dopad na výkon při uvolňování paměti.

Thread-Local Allocation Buffers (TLAB)

  1. Co je TLAB?
    • TLAB je část paměti Eden prostoru v mladé generaci, která je vyhrazena pro alokaci objektů jednoho konkrétního vlákna
    • Každé vlákno má svůj vlastní TLAB, což umožňuje alokovat objekty rychleji bez nutnosti synchronizace mezi vlákny
  2. Výhody TLAB:
    • Snížení režie spojené s synchronizací vláken při alokaci objektů
    • Rychlejší alokace objektů, protože každé vlákno může alokovat objekty ve svém TLAB bez čekání na ostatní vlákna
    • Zlepšení výkonu aplikací s vysokou mírou paralelismu a vytvářením objektů
  3. Jak TLAB funguje?
    • Při inicializaci JVM se pro každé vlákno vytvoří TLAB v Eden prostoru
    • Každé vlákno alokuje objekty pouze ve svém TLAB
    • Pokud je TLAB jednoho vlákna plný, může být přidělena nová část paměti z Eden prostoru, nebo se může spustit garbage collection
  4. Nastavení a ladění TLAB:
    • Velikost TLAB může být nastavena pomocí JVM parametrů, např. -XX:TLABSize=<velikost>
    • Pro ladění TLAB lze použít JVM parametry, např. -XX:+PrintTLAB pro výpis informací o TLAB do logu

TLAB zvyšuje výkon JVM tím, že minimalizuje režii spojenou s alokací objektů v paralelním prostředí. Tím se zlepšuje celková efektivita paměti a výkon aplikací s vysokou mírou vytváření objektů.

Analýza úniku objektů (Object Escape Analysis):

  1. Co je analýza úniku objektů?
    • Optimalizační technika používaná JVM pro identifikaci objektů, které neuniknou z aktuálního kontextu metody nebo vlákna
    • Pokud objekt neunikne, může JVM optimalizovat jeho alokaci a synchronizaci, což zlepšuje výkon aplikace
  2. Výhody analýzy úniku objektů:
    • Snížení režie spojené s alokací objektů na haldě
    • Odstranění zbytečných synchronizací, které nejsou potřeba pro objekty, které neuniknou z aktuálního kontextu
    • Možnost alokovat objekty na zásobníku místo na haldě, což zlepšuje výkon a zjednodušuje práci garbage collectoru
  3. Jak analýza úniku objektů funguje?
    • JVM analyzuje kód aplikace za běhu nebo při kompilaci a identifikuje objekty, které neuniknou z aktuálního kontextu metody nebo vlákna
    • Pokud objekt neunikne, JVM může provést následující optimalizace:
      • Alokace objektu na zásobníku místo na haldě
      • Odstranění zbytečných synchronizací na objektu
      • Optimalizace práce garbage collectoru
  4. Nastavení a ladění analýzy úniku objektů:
    • Analýza úniku objektů je ve většině JVM aktivována automaticky
    • Pro ladění analýzy úniku objektů lze použít JVM parametry, např. -XX:+DoEscapeAnalysis pro zapnutí analýzy úniku objektů

Analýza úniku objektů je důležitá optimalizační technika, která zlepšuje výkon a efektivitu paměti aplikací. Pomáhá JVM identifikovat objekty, které neuniknou z aktuálního kontextu, a provádět optimalizace, které snižují režii spojenou s alokací objektů a synchronizací.

Lokalita dat (Data Locality):

  1. Co je lokalita dat?
    • Lokalita dat se týká organizace dat v paměti tak, aby byla přístupná rychle a efektivně
    • Zaměřuje se na způsob, jakým jsou data uložena a uspořádána v paměti, aby byla minimalizována doba přístupu a režie
    • Existují dva druhy lokality dat: lokalita v čase a lokalita v prostoru
  2. Lokalita v čase (Temporal Locality):
    • Pokud je prvek použit, je pravděpodobné, že bude opět použit v blízké budoucnosti
    • Optimalizace: ukládání často používaných dat v rychlých cache pamětech
  3. Lokalita v prostoru (Spatial Locality):
    • Pokud je prvek použit, je pravděpodobné, že budou použity i jeho sousední prvky v blízké budoucnosti
    • Optimalizace: načítání bloků dat do cache paměti, které obsahují i sousední prvky
  4. Výhody lokality dat:
    • Zlepšení výkonu aplikace díky rychlejšímu přístupu k datům
    • Efektivnější využití cache paměti a minimalizace cache miss
    • Menší režie spojená s načítáním a ukládáním dat
  5. Aplikace lokality dat v programování:
    • Použití kontiguálních datových struktur (např. pole) místo spojových datových struktur (např. spojový seznam)
    • Uspořádání dat v paměti podle přístupových vzorů (např. skupinování souvisejících dat dohromady)
    • Optimalizace smyček a algoritmů pro využití lokality dat (např. procházení pole po řádcích nebo sloupcích)

Lokalita dat je klíčovým aspektem optimalizace výkonu aplikací. Správné uspořádání a organizace dat v paměti může významně zlepšit výkon aplikace a minimalizovat režii spojenou s načítáním a ukládáním dat.

Nerovnoměrná alokace paměti (Non-Uniform Memory Allocation, NUMA):

  1. Co je nerovnoměrná alokace paměti (NUMA)?
    • NUMA je architektura paměti, která se používá v multiprocesorových systémech, kde je přístup k paměti různě rychlý v závislosti na vzdálenosti mezi procesorem a pamětí
    • Cílem NUMA je zlepšit výkon a škálovatelnost systému tím, že se sníží režie spojená s přístupem k paměti
  2. Jak NUMA funguje?
    • V NUMA architektuře je paměť rozdělena do několika menších paměťových uzlů, které jsou připojeny k procesorům
    • Každý procesor má rychlejší přístup k paměti ve svém vlastním uzlu a pomalejší přístup k paměti v ostatních uzlech
    • Při alokaci paměti se pokouší NUMA alokovat paměť v uzlu, který je nejblíže procesoru, který bude paměť používat
  3. Výhody NUMA:
    • Zlepšení výkonu a škálovatelnosti multiprocesorových systémů díky rychlejšímu přístupu k lokální paměti
    • Menší režie spojená s přístupem k paměti, protože paměťová komunikace probíhá většinou uvnitř uzlů
    • Možnost efektivnějšího využití cache paměti
  4. Nevýhody NUMA:
    • Složitější správa paměti a plánování procesů
    • Potenciální problémy s latencí a propustností při přístupu k vzdálené paměti
    • Vyšší nároky na hardware a softwarovou podporu
  5. Jak optimalizovat aplikace pro NUMA?
    • Správné rozdělení práce mezi procesory a jejich lokálními paměťovými uzly
    • Využití NUMA-optimálních knihoven a funkcí pro správu paměti
    • Monitorování a ladění výkonu aplikace v NUMA systémech

Nerovnoměrná alokace paměti (NUMA) je architektura paměti používaná v multiprocesorových systémech pro zlepšení výkonu a škálovatelnosti. Správné využití NUMA může významně zlepšit výkon aplikace v multiprocesorových prostředích.

OSI model (Open Systems Interconnection):

  1. Co je OSI model?
    • OSI model je konceptuální rámec, který popisuje, jak různé vrstvy komunikačního systému spolupracují při přenosu dat mezi síťovými zařízeními
    • Model se skládá ze 7 vrstev, které definují různé úrovně abstrakce a funkcí komunikačního procesu
  2. Seznam vrstev OSI modelu:
    1. Fyzická vrstva (Physical Layer)
    2. Linková vrstva (Data Link Layer)
    3. Síťová vrstva (Network Layer)
    4. Transportní vrstva (Transport Layer)
    5. Relační vrstva (Session Layer)
    6. Prezentační vrstva (Presentation Layer)
    7. Aplikační vrstva (Application Layer)
  3. Popis vrstev OSI modelu:
    1. Fyzická vrstva:
      • Zajišťuje přenos a přijímání bitů přes fyzické médium (např. kabel, rádiové vlny)
      • Definuje fyzické charakteristiky konektorů, kabelů a signálů
    2. Linková vrstva:
      • Řeší přenos datových rámců mezi sousedními uzly v síti
      • Zajišťuje kontrolu chyb a řízení toku dat
    3. Síťová vrstva:
      • Zajišťuje směrování a přeposílání datových paketů mezi různými sítěmi
      • Spravuje adresování a segmentaci dat
    4. Transportní vrstva:
      • Zajišťuje spolehlivý přenos dat mezi koncovými uzly
      • Řídí tok dat, kontrolu chyb a obnovu ztracených dat
    5. Relační vrstva:
      • Řídí spojení mezi aplikacemi a zajišťuje jejich správnou funkci
      • Udržuje a ukončuje komunikační relace
    6. Prezentační vrstva:
      • Zajišťuje převod dat mezi aplikacemi a síťovým formátem
      • Řídí kódování, kompresi a šifrování dat
    7. Aplikační vrstva:
      • Poskytuje rozhraní mezi aplikacemi a komunikačními službami
      • Zajišťuje přístup k síťovým službám, jako jsou e-mail, webové stránky a databáze

OSI model je důležitým konceptem v oblasti počítačových sítí, který pomáhá porozumět základním principům komunikace mezi síťovými zař

Problém C10K

  1. Co je problém C10K?
    • Problém C10K je výkonový problém spojený se schopností serveru zvládat více než 10 000 současných síťových spojení
    • Tento problém byl poprvé popsán v roce 1999 a odráží výzvy spojené s růstem počtu uživatelů a potřeby serverů zvládat více spojení
  2. Příčiny problému C10K:
    • Omezení výkonu způsobená tradičními síťovými modely (jako je model jeden proces/jeden vlákno na jedno spojení)
    • Vysoká režie spojená s vytvářením a zrušením vláken nebo procesů pro každé spojení
    • Nedostatek operačního systému a hardwarové podpory pro vysoký počet současných spojení
  3. Řešení problému C10K:
    • Použití vícevláknových nebo asynchronních modelů serverů, které mohou zpracovávat více spojení pomocí méně zdrojů
    • Využití funkce epoll (Linux) nebo kqueue (BSD, macOS) pro efektivní sledování stavu více síťových spojení
    • Použití non-blocking I/O operací, které umožňují serveru pokračovat v práci, zatímco čeká na dokončení I/O operace
    • Optimalizace operačního systému a hardwaru pro zvýšení propustnosti a snížení režie spojené s přenosem dat
  4. Význam řešení problému C10K:
    • Zlepšení výkonu serverů a schopnosti zvládat vyšší zátěž
    • Zajištění škálovatelnosti serverů, které mohou růst spolu s počtem uživatelů a potřebami aplikací
    • Umožnění efektivnějšího využití zdrojů serverů, což vede ke snížení nákladů na provoz a správu

Problém C10K odráží výzvy spojené se zvládáním velkého počtu současných síťových spojení na serverech. Řešení tohoto problému zahrnuje použití vícevláknových, asynchronních nebo non-blocking modelů serverů, optimalizaci operačního systému a hardwaru a využití pokročilých technologií pro sledování a správu síťových spojení.

Blocking a non-blocking I/O (vstup/výstup):

  1. Co je blocking I/O?
    • Blocking I/O je metoda vstupu/výstupu, při které se vykonávání programu zastaví, dokud nebude dokončena I/O operace
    • Během čekání na dokončení I/O operace je proces nebo vlákno blokováno a nemůže vykonávat žádné další úkoly
  2. Co je non-blocking I/O?
    • Non-blocking I/O je metoda vstupu/výstupu, při které se vykonávání programu nepozastavuje, dokud nebude dokončena I/O operace
    • Místo čekání na dokončení I/O operace může proces nebo vlákno pokračovat v jiných úkolech a zpět ke zpracování I/O operace se vrátí, až bude hotova
  3. Porovnání blocking a non-blocking I/O:
    • Výkon: Non-blocking I/O může zlepšit výkon aplikací tím, že minimalizuje čas strávený čekáním na dokončení I/O operací
    • Složitost: Blocking I/O je jednodušší na implementaci a pochopení, zatímco non-blocking I/O vyžaduje více pozornosti k správě asynchronních operací
    • Vhodnost: Blocking I/O je vhodný pro aplikace, kde je čekání na I/O operace přijatelné nebo očekávané, zatímco non-blocking I/O je vhodný pro aplikace, které vyžadují vysokou propustnost a odezvu
  4. Příklady použití blocking a non-blocking I/O:
    • Blocking I/O: Jednoduché servery, které obsluhují malý počet klientů nebo aplikace, které nevyžadují vysokou propustnost
    • Non-blocking I/O: Webové servery, databázové servery nebo aplikace, které obsluhují velké množství současných spojení nebo vyžadují rychlou odezvu

Blocking a non-blocking I/O představují dva různé přístupy k vstupu/výstupu v aplikacích. Blocking I/O je jednodušší na implementaci, ale může vést k nižšímu výkonu. Non-blocking I/O poskytuje lepší výkon, ale vyžaduje více pozornosti k správě asynchronních operací.

Vícevláknový server (Threading server):

  1. Co je vícevláknový server?
    • Vícevláknový server je typ serveru, který používá více vláken pro obsluhu více klientů nebo požadavků současně
    • Každé vlákno zpracovává jeden nebo více klientů nezávisle na ostatních vláknech
  2. Výhody vícevláknového serveru:
    • Lepší využití zdrojů: Vícevláknový server může efektivněji využívat zdroje procesoru a paměti, což zlepšuje výkon a propustnost
    • Rychlejší odezva: Vícevláknový server může poskytovat rychlejší odezvu na požadavky klientů, protože jednotlivá vlákna mohou pracovat paralelně a zpracovávat více požadavků současně
    • Škálovatelnost: Vícevláknový server může lépe zvládat zvýšenou zátěž, protože může vytvářet a zrušit vlákna podle potřeby
  3. Nevýhody vícevláknového serveru:
    • Složitost: Vícevláknový server může být složitější na implementaci a správu, protože vyžaduje koordinaci a synchronizaci mezi vlákny
    • Režie: Vytváření a zrušení vláken může způsobit režii, která může snížit výkon serveru
    • Sdílené prostředky: Vlákna musí sdílet prostředky, jako je paměť a procesor, což může vést k problémům s výkonem a synchronizací
  4. Použití vícevláknového serveru:
    • Vícevláknový server je vhodný pro aplikace, které vyžadují vysokou propustnost a rychlou odezvu, jako jsou webové servery, databázové servery nebo aplikace pro zpracování videa

Vícevláknový server představuje přístup k zpracování požadavků klientů, který umožňuje lepší využití zdrojů a rychlejší odezvu. Je vhodný pro aplikace, které vyžadují vysokou propustnost a rychlou odezvu, ale může být složitější na implementaci a správu než jednovláknové servery.

Událostmi řízený server (Event-driven server):

  1. Co je událostmi řízený server?
    • Událostmi řízený server je typ serveru, který zpracovává požadavky klientů na základě událostí, jako jsou příchozí data nebo změny stavu spojení
    • Server reaguje na události pomocí asynchronních I/O operací a zpracovává požadavky klientů bez potřeby vytvářet samostatná vlákna nebo procesy pro každé spojení
  2. Výhody událostmi řízeného serveru:
    • Nižší režie: Událostmi řízený server má nižší režii než vícevláknový server, protože nepotřebuje vytvářet a zrušit vlákna pro každé spojení
    • Škálovatelnost: Událostmi řízený server může zvládat velký počet současných spojení s menšími nároky na systémové zdroje
    • Jednodušší koordinace: Událostmi řízený server může být jednodušší na koordinaci a správu než vícevláknový server, protože většina operací je asynchronní a nemusí být koordinována s ostatními vlákny
  3. Nevýhody událostmi řízeného serveru:
    • Složitost: Událostmi řízený server může být složitější na implementaci, protože vyžaduje správu asynchronních událostí a I/O operací
    • Výkon: Událostmi řízený server může mít nižší výkon než vícevláknový server, pokud je zátěž serveru nevyvážená nebo pokud server musí provádět náročné výpočetní úkoly
  4. Použití událostmi řízeného serveru:
    • Událostmi řízený server je vhodný pro aplikace, které potřebují zvládat velké množství současných spojení s nízkou režií, jako jsou webové servery, proxy servery nebo aplikace pro zpracování zpráv

Událostmi řízený server představuje přístup k zpracování požadavků klientů, který se zaměřuje na asynchronní I/O operace a reaguje na události, jako jsou příchozí data nebo změny stavu spojení. Je vhodný pro aplikace, které potřebují zvládat velké množství současných spo

Event-based input/output approaches

Přístupy k událostmi řízenému vstupu/výstupu (Event-based input/output):

  1. Co je událostmi řízený vstup/výstup (event-based I/O)?

    • Událostmi řízený vstup/výstup je asynchronní způsob zpracování I/O operací, který reaguje na události, jako jsou příchozí data nebo změny stavu spojení
    • Tento přístup umožňuje efektivně zpracovávat velké množství současných spojení s nízkou režií a vysokou propustností

  2. Přístupy k událostmi řízenému vstupu/výstupu:

    1. Reactor pattern (Reaktor vzor):
      • Reaktor vzor je návrhový vzor, který řídí událostmi řízený vstup/výstup pomocí jednoho nebo více demultiplexorů událostí
      • Demultiplexor událostí sleduje události na více I/O zdrojích a spouští příslušné obslužné rutiny, které zpracovávají události
      • Reaktor vzor je vhodný pro aplikace s malým počtem současných spojení, které vyžadují rychlou odezvu na události
    2. Proactor pattern (Proaktor vzor):
      • Proaktor vzor je návrhový vzor, který řídí událostmi řízený vstup/výstup pomocí asynchronních I/O operací a plánovače událostí
      • Plánovač událostí zodpovídá za řízení a spouštění asynchronních I/O operací a obslužných rutin, které zpracovávají události
      • Proaktor vzor je vhodný pro aplikace s velkým počtem současných spojení, které vyžadují vysokou propustnost a efektivní využití systémových zdrojů

  3. Porovnání událostmi řízených přístupů k vstupu/výstupu:

    • Reactor pattern:
      • Výhody: Jednodušší na implementaci, rychlá odezva na události
      • Nevýhody: Nižší propustnost při velkém počtu současných spojení, vyšší režie při demultiplexingu událostí
    • Proactor pattern:
      • Výhody: Vysoká propustnost, efektivní využití systémových zdrojů, snížená režie při zpracování událostí
      • Nevýhody: Složitější na implementaci, může vyžadovat specifickou podporu asynchronních I/O operací ze strany operačního systému

  4. Použití událostmi řízených přístupů k vstupu/výstupu:

    • Událostmi řízené přístupy k vstupu/výstupu se používají v širokém spektru aplikací, které vyžadují efektivní zpracování velkého počtu současných spojení, jako jsou webové servery, proxy servery, aplikace pro zpracování zpráv nebo databázové servery

Událostmi řízené přístupy k vstupu/výstupu, jako jsou Reactor a Proactor vzory, umožňují efektivně zpracovávat velké množství současných spojení s nízkou režií a vysokou propustností. Tyto přístupy se používají v širokém spektru aplikací, které vyžadují efektivní zpracování velkého počtu současných spojení, jako jsou webové servery, proxy servery, aplikace pro zpracování zpráv nebo databázové servery.

Nativní buffery v JVM (Java Virtual Machine):

  1. Co jsou nativní buffery?
    • Nativní buffery jsou oblasti paměti mimo Java heap, které slouží k ukládání a manipulaci s daty v rámci JVM
    • Tyto buffery mohou být přímo přístupné pro nativní kód a operační systém, což umožňuje rychlejší a efektivnější zpracování dat než při použití běžných Java objektů
  2. Výhody nativních bufferů v JVM:
    • Rychlost: Nativní buffery umožňují rychlejší zpracování dat, protože nejsou omezeny Java garbage collector a nemusí být kopírovány mezi Java heap a nativní pamětí
    • Efektivita: Nativní buffery umožňují efektivnější využití systémových zdrojů, jako je paměť a I/O, protože mohou být přímo přístupné pro nativní kód a operační systém
    • Kompatibilita: Nativní buffery usnadňují interakci mezi Java kódem a nativními knihovnami nebo operačním systémem, což umožňuje vytvářet výkonnější a škálovatelnější aplikace
  3. Použití nativních bufferů v JVM:
    • Nativní buffery se často používají v JVM pro zlepšení výkonu a efektivity aplikací, které pracují s velkým množstvím dat nebo potřebují přímý přístup k nativním knihovnám a operačnímu systému
    • Typické příklady zahrnují síťové I/O operace, grafické a multimediální aplikace, databázové servery nebo výkonnostně náročné výpočty

Nativní buffery v JVM umožňují rychlejší a efektivnější zpracování dat než při použití běžných Java objektů, protože nejsou omezeny Java garbage collector a mohou být přímo přístupné pro nativní kód a operační systém. Tyto buffery se často používají pro zlepšení výkonu a efektivity aplikací, které pracují s velkým množstvím dat nebo potřebují přímý přístup k nativním knihovnám a operačnímu systému.

Kanály a selektory:

  1. Co jsou kanály a selektory?
    • Kanály (Channels) jsou abstrakce, které umožňují efektivní a asynchronní komunikaci mezi Java kódem a I/O zdroji, jako jsou soubory, síťové sockety nebo datové proudy
    • Selektory (Selectors) jsou komponenty, které sledují a řídí události na více kanálech současně, což umožňuje efektivní zpracování událostí a multiplexing I/O operací
  2. Výhody kanálů a selektorů:
    • Efektivita: Kanály a selektory umožňují efektivní využití systémových zdrojů, jako je paměť a I/O, protože umožňují asynchronní a událostmi řízený přístup k I/O zdrojům
    • Flexibilita: Kanály a selektory poskytují jednotné rozhraní pro různé typy I/O zdrojů, což usnadňuje vývoj a údržbu aplikací, které pracují s různými typy dat a komunikací
    • Škálovatelnost: Kanály a selektory umožňují efektivní zpracování velkého počtu současných spojení, což je užitečné pro aplikace, které vyžadují vysokou propustnost a nízkou latenci
  3. Použití kanálů a selektorů v JVM:
    • Kanály a selektory se používají v širokém spektru aplikací, které vyžadují efektivní zpracování I/O operací a komunikace, jako jsou webové servery, proxy servery, aplikace pro zpracování zpráv nebo databázové servery
    • Kanály a selektory jsou součástí Java NIO (New Input/Output) knihovny, která poskytuje rozšířené a výkonné I/O funkce pro Java aplikace

Kanály a selektory jsou klíčovými komponentami Java NIO knihovny, které umožňují efektivní a asynchronní komunikaci mezi Java kódem a I/O zdroji. Tyto komponenty se používají v širokém spektru aplikací, které vyžadují efektivní zpracování I/O operací a komunikace, jako jsou webové servery, proxy servery, aplikace pro zpracování zpráv nebo databázové servery.

Synchronizace v multithreadových programech (atomické operace, mutex, semafor, rw-lock, spinlock, RCU). Kdy použít který mechanismus? Výkonnostní úzká místa zmíněných mechanismů:

  1. Atomické operace:
    • Použití: Malé, jednoduché a rychlé operace, které mají garantovat konzistenci mezi vlákny
    • Výkonnostní úzká místa: Omezená na jednoduché operace, může způsobit zpoždění v případě častých aktualizací dat
  2. Mutex:
    • Použití: Vzájemné vyloučení přístupu k sdíleným zdrojům, vhodné pro krátké kritické sekce
    • Výkonnostní úzká místa: Může způsobit zpoždění, pokud je přístup k sdíleným zdrojům často blokován
  3. Semafor:
    • Použití: Omezení počtu současně prováděných operací, například při omezení počtu současných spojení
    • Výkonnostní úzká místa: Může způsobit zpoždění v případě velkého počtu vláken čekajících na uvolnění semaforu
  4. Rw-lock:
    • Použití: Oddělení čtecích a zapisovacích operací pro sdílené zdroje, vhodné pro situace s častými čtecími operacemi a méně častými zapisovacími operacemi
    • Výkonnostní úzká místa: Může způsobit zpoždění, pokud zapisovací operace často blokují čtecí operace
  5. Spinlock:
    • Použití: Vzájemné vyloučení přístupu k sdíleným zdrojům, vhodné pro velmi krátké kritické sekce, kde je očekávání na uvolnění zámku krátké
    • Výkonnostní úzká místa: Může způsobit zvýšení vytížení procesoru, pokud vlákna čekají na uvolnění zámku po delší dobu
  6. RCU (Read-Copy-Update):
    • Použití: Synchronizace čtecích a zapisovacích operací pro sdílené zdroje bez použití zámků, vhodné pro situace s častými čtecími operacemi a méně častými zapisovacími operacemi
    • Výkonnostní úzká místa: Může způsobit zpoždění v případě častých zapisovacích operací nebo velkého množství vláken, kvůli nutnosti provádět čištění paměti a koordinaci mezi vlákny

Při výběru synchronizačního mechanismu je důležité zvážit následující faktory:

Výběr vhodného synchronizačního mechanismu může mít významný dopad na výkon a škálovatelnost aplikace. Je důležité provádět testy a analýzu výkonu, aby bylo zajištěno, že zvolený mechanismus splňuje požadavky aplikace a nepředstavuje výkonnostní úzká místa.

Synchronizace v “read-mostly workloads” (práce s převážně čtecími operacemi), výhody a nevýhody různých synchronizačních mechanismů:

  1. Atomické operace:
    • Výhody: Rychlé, jednoduché a bez zámku
    • Nevýhody: Omezené na jednoduché operace, méně vhodné pro složitější sdílené struktury
  2. Mutex:
    • Výhody: Zajišťuje vzájemné vyloučení přístupu k sdíleným zdrojům
    • Nevýhody: Může způsobit zpoždění, pokud je přístup k sdíleným zdrojům často blokován
  3. Read-write lock (rw-lock):
    • Výhody: Umožňuje paralelní čtení, odděluje čtecí a zapisovací operace
    • Nevýhody: Může způsobit zpoždění, pokud zapisovací operace často blokují čtecí operace
  4. RCU (Read-Copy-Update):
    • Výhody: Bez zámku, umožňuje efektivní čtení bez blokování
    • Nevýhody: Může způsobit zpoždění v případě častých zapisovacích operací, kvůli nutnosti provádět čištění paměti a koordinaci mezi vlákny
  5. StampedLock:
    • Výhody: Podpora pro optimalizované čtení bez zámku, oddělení čtecích a zapisovacích operací
    • Nevýhody: Složitější použití, může způsobit zpoždění, pokud zapisovací operace často blokují čtecí operace

Pro read-mostly workloads, kde je většina operací čtecích a zapisovací operace jsou méně časté, jsou vhodné mechanismy, které minimalizují dopad zapisovacích operací na čtecí operace a umožňují efektivní paralelní čtení. Mezi takové mechanismy patří rw-lock, RCU a StampedLock.

Výběr vhodného synchronizačního mechanismu závisí na konkrétních požadavcích aplikace a na potřebě optimalizace výkonu a škálovatelnosti. Je důležité provádět testy a analýzu výkonu, aby bylo zajištěno, že zvolený mechanismus splňuje požadavky aplikace a nepředstavuje výkonnostní úzká místa.

Cache-efektivní datové struktury a algoritmy (např. násobení matic):

Cache-efektivní datové struktury a algoritmy jsou navrženy tak, aby minimalizovaly přístupy k paměti a využily cache CPU co nejlépe. Příklady cache-efektivních datových struktur a algoritmů:

  1. Cache-oblivious algoritmy:
    • Navrženy tak, aby efektivně využily cache bez znalosti velikosti cache nebo cache line
    • Příklad: Cache-oblivious násobení matic, které rozdělí matice na menší bloky a provádí násobení bloků s efektivním využitím cache
  2. Cache-aware algoritmy:
    • Navrženy s vědomím velikosti cache a cache line, což umožňuje maximalizovat využití cache
    • Příklad: Cache-aware násobení matic, které rozdělí matice na bloky velikosti, která odpovídá velikosti cache, a násobí bloky efektivně
  3. B-stromy:
    • Cache-efektivní stromová datová struktura, která má větší větve než binární stromy, což umožňuje efektivnější využití cache
    • Příklad: B-stromy se používají v databázových systémech a souborových systémech pro efektivní vyhledávání a manipulaci s daty
  4. Bloom filtry:
    • Cache-efektivní datová struktura, která umožňuje rychlé a efektivní testování přítomnosti prvku v množině s malou paměťovou náročností
    • Příklad: Bloom filtry se používají pro rychlé vyhledávání v cache nebo pro detekci duplicitních dat
  5. Compact hash tabulky:
    • Cache-efektivní varianta hash tabulek, která minimalizuje paměťovou náročnost a zlepšuje využití cache
    • Příklad: Compact hash tabulky se používají pro rychlé vyhledávání a ukládání dat s malou paměťovou náročností

Pro dosažení cache-efektivity je důležité brát v úvahu vlastnosti paměti cache, jako je velikost cache, cache line, asociativita a politika nahrazování. Cache-efektivní algoritmy a datové struktury mohou výrazně zlepšit výkon aplikace tím, že minimalizují přístupy k pomalejší hlavní paměti a maximalizují využití rychlé cache paměti.

Zásady cache pamětí a různé druhy cache chyb:

Cache paměť je rychlá a menší paměť mezi CPU a hlavní pamětí (RAM), která zlepšuje výkon tím, že udržuje kopie často používaných dat z hlavní paměti. Cache paměť využívá vlastnosti prostorové a časové lokalitě přístupu k datům.

Různé druhy cache chyb (misses):

  1. Compulsory miss (nevyhnutelná chyba):
    • Způsobena prvním přístupem k datům, která nejsou v cache
    • Nelze zcela eliminovat, může být minimalizováno efektivním přednačítáním dat do cache
  2. Capacity miss (kapacitní chyba):
    • Způsobena omezenou kapacitou cache paměti, když je počet potřebných dat větší než velikost cache
    • Může být zlepšeno zvětšením cache nebo využitím cache-efektivních algoritmů a datových struktur
  3. Conflict miss (konfliktní chyba):
    • Způsobena kolizemi v cache záznamech, kdy různá data mapují na stejnou pozici v cache
    • Může být zlepšeno zvýšením asociativity cache, použitím cache-oblivious nebo cache-aware algoritmů
  4. Coherence miss (koherenční chyba):
    • Způsobena nekonzistencí mezi cache pamětí různých procesorů v multiprocesorovém systému
    • Může být zlepšeno použitím koherentních protokolů a správných synchronizačních mechanismů

Pro efektivní využití cache pamětí je důležité minimalizovat počet cache chyb a zohlednit vlastnosti cache, jako je velikost cache, cache line, asociativita a politika nahrazování. Cache-efektivní algoritmy a datové struktury mohou výrazně zlepšit výkon aplikace tím, že minimalizují přístupy k pomalejší hlavní paměti a maximalizují využití rychlé cache paměti.

Self-evicting kód:

Self-evicting kód je kód, který je napsán tak, aby se záměrně vyhýbal využití cache paměti nebo z ní byl rychle vytlačen. Tento typ kódu může být užitečný v některých případech, například:

  1. Pro zabezpečení:
    • Když chcete minimalizovat dobu, po kterou citlivá data zůstávají v cache paměti, a snížit tak riziko útoku, který by zneužil přístup k těmto datům (např. cache side-channel útoky)
  2. Pro účely vyvažování zátěže:
    • Když chcete zajistit, že kritické části kódu nebudou vytlačeny z cache paměti méně důležitými částmi kódu, které by mohly vést k výkonnostním problémům

Pro napsání self-evicting kódu je třeba použít techniky, které záměrně zhoršují vlastnosti prostorové a časové lokalitě přístupu k datům a zabraňují jejich uchování v cache paměti. Některé z těchto technik mohou zahrnovat:

  1. Použití nestandardních přístupových vzorů k datům
  2. Záměrné prokládání přístupu k různým datovým oblastem, aby byla zvýšena pravděpodobnost vytlačení dat z cache
  3. Použití technik, které ztěžují předpovědi větví, což zabraňuje efektivnímu přednačítání dat do cache

Je důležité si uvědomit, že self-evicting kód může mít negativní dopad na výkon aplikace v důsledku zvýšených přístupů k pomalejší hlavní paměti. Použití self-evicting kódu by mělo být pečlivě zváženo a použito pouze tam, kde je to opravdu nezbytné.

False sharing - co to je a jak se s tím vypořádat?

False sharing je situace, kdy více vláken v multiprocesorovém nebo multicore systému nezávisle přistupuje k různým datovým položkám, které jsou umístěny ve stejném bloku cache (cache line). Tento přístup může způsobit nežádoucí invalidaci cache line a zvýšení komunikace mezi procesory nebo jádry, což má za následek výkonnostní problémy.

Jak se vypořádat s false sharingem:

  1. Zarovnání dat:
    • Zarovnejte často používaná data na hranice cache line, aby byla oddělena a nezpůsobovala false sharing. V některých jazycích (např. C/C++) lze použít direktivy pro zarovnání dat, jako je alignas().
  2. Padding (vyplnění):
    • Přidejte padding mezi datovými položkami, které jsou přístupné různými vlákny, aby byly umístěny ve vlastních cache lines. Padding může zahrnovat nevyužité proměnné nebo pole.
  3. Oddělení dat:
    • Oddělte data, která jsou přístupná různými vlákny, do různých datových struktur nebo objektů, aby byla minimalizována pravděpodobnost false sharingu.
  4. Thread-local storage (úložiště pro vlákna):
    • Pokud je to možné, použijte thread-local storage pro data, která jsou specifická pro jednotlivá vlákna. Tím se sníží potřeba sdílet data mezi vlákny a zároveň se minimalizuje false sharing.
  5. Použití optimalizací kompilátoru:
    • Některé kompilátory mohou poskytovat optimalizace pro snížení false sharingu. Prozkoumejte možnosti optimalizace vašeho kompilátoru a zvažte jejich použití.
  6. Profiling a analýza:
    • Použijte nástroje pro profiling a analýzu k identifikaci false sharingu ve vaší aplikaci. Tím získáte informace o kritických oblastech kódu, které mohou být zdrojem false sharingu a mohou být optimalizovány.

Při práci s false sharingem je důležité najít rovnováhu mezi snižováním false sharingu a zachováním paměťové efektivity, protože některé z těchto technik mohou zvýšit paměťovou náročnost aplikace.

Profiling a optimalizace programů v kompilovaných jazycích (např. C/C++):

  1. Profiling:
    • Profiling je proces sběru dat o výkonu a chování programu za účelem identifikace oblastí, které lze optimalizovat. Nástroje pro profiling v C/C++ mohou zahrnovat:
      • gprof: GNU profiler pro měření času stráveného v jednotlivých funkcích
      • perf: Nástroj pro profiling na úrovni jádra Linuxu
      • Valgrind: Nástroj pro analýzu paměti a profiling výkonu
  2. Optimalizace kompilátoru:
    • Kompilátory jako GCC nebo Clang poskytují různé úrovně optimalizace, které lze nastavit pomocí přepínačů:
      • -O0: Žádná optimalizace (výchozí)
      • -O1: Optimalizace pro rychlost a velikost kódu
      • -O2: Optimalizace pro rychlost (bez zvýšení velikosti kódu)
      • -O3: Agresivní optimalizace pro rychlost (může zvýšit velikost kódu)
      • -Os: Optimalizace pro velikost kódu
      • -Ofast: Optimalizace pro nejvyšší rychlost (ignoruje striktní standardy)
  3. Optimalizace kódu:
    • Ruční optimalizace kódu může zahrnovat následující techniky:
      • Smyčkové optimalizace: unrolling, fusion, či blocking
      • Minimalizace režie volání funkcí: inlining, tail call optimalizace
      • Optimalizace paměťového přístupu: zarovnání dat, cache-friendly algoritmy
      • Využití paralelismu: SIMD instrukce, vícevláknové programování
      • Snížení režie synchronizace: atomické operace, lock-free algoritmy
  4. Analýza a ladění:
    • Analyzujte a laděte svůj kód za účelem identifikace a řešení výkonnostních problémů, např. pomocí následujících nástrojů:
      • gdb: GNU Debugger pro ladění programů
      • strace: Nástroj pro sledování systémových volání a signálů
      • ltrace: Nástroj pro sledování volání knihoven
      • vtune: Profiler a ladící nástroj od Intelu

Při provádění optimalizací je důležité najít rovnováhu mezi výkonem, čitelností kódu a přenositelností.

Hardwarové čítače výkonu:

Hardwarové čítače výkonu (Hardware Performance Counters, HPC) jsou speciální registry, které integrované do procesoru, umožňují sledovat různé aspekty výkonu a chování procesoru. Tyto čítače mohou poskytovat informace o:

  1. Počet provedených instrukcí
  2. Počet provedených cyklů
  3. Počet cache hitů a missů
  4. Počet branch (větvení) instrukcí a predikcí
  5. Počet zápisů a čtení z paměti
  6. Počet závislostí mezi instrukcemi
  7. Počet událostí souvisejících s pipeliningem

Tyto informace lze použít k analýze výkonu programu a identifikaci úzkých míst nebo problémů, které lze optimalizovat. Některé nástroje pro práci s hardwarovými čítači výkonu zahrnují:

Při použití hardwarových čítačů výkonu je důležité mít na paměti, že jejich podpora a dostupnost se může lišit mezi různými procesory a architekturami.

Optimalizace řízená profilem (Profile-Guided Optimization, PGO):

Optimalizace řízená profilem (PGO) je technika optimalizace kompilátoru, která používá data získaná z profilingu běhu programu za účelem informování kompilátoru o tom, jak nejlépe optimalizovat kód. PGO zahrnuje následující kroky:

  1. Kompilace programu s přepínačem pro generování profilovacích informací (např. -fprofile-generate v GCC nebo Clang).
  2. Spuštění programu na reprezentativní sadě vstupů, které zahrnují typické scénáře použití, aby byly vygenerovány profilovací data.
  3. Opětovná kompilace programu s přepínačem pro využití profilovacích informací (např. -fprofile-use v GCC nebo Clang).

PGO může přinést následující výhody:

Je důležité provést profiling na reprezentativní sadě vstupů, aby PGO mohla efektivně zlepšit výkon programu. PGO může mít významný dopad na výkon, ale jeho výsledky se mohou lišit v závislosti na konkrétním programu a jeho použití.

Základy kompilátorů C/C++ - AST, intermediální reprezentace:

  1. Abstract Syntax Tree (AST):
    • AST je stromová struktura, která reprezentuje zdrojový kód programu ve formě, která je snadno zpracovatelná pro další analýzy a transformace.
    • AST je vytvořen během syntaktické analýzy zdrojového kódu a zachycuje informace o struktuře kódu, např. deklarace, přiřazení, cykly a podmínky.
    • AST slouží jako vstup pro další fáze kompilace, jako je sémantická analýza, optimalizace a generování kódu.
  2. Intermediální reprezentace (Intermediate Representation, IR):
    • IR je zjednodušená reprezentace programu, která slouží jako mezikrok mezi AST a výsledným strojovým kódem.
    • IR je navržen tak, aby byl snadno analyzovatelný a modifikovatelný pro optimalizace a transformace kódu.
    • Existují různé formy IR, například:
      • Three-Address Code (TAC): Lineární sekvence instrukcí, kde každá instrukce má nejvýše tři operandy.
      • Static Single Assignment (SSA): IR, ve kterém je každá proměnná přiřazena pouze jednou.

Kompilátory C/C++ jako GCC nebo Clang provádějí několik transformací a optimalizací na úrovni AST a IR před generováním výsledného strojového kódu. Tyto transformace a optimalizace mohou zahrnovat zjednodušení výrazů, inlining funkcí, eliminaci mrtvého kódu, propagaci konstant a mnoho dalších.

Optimalizační průchody na vysoké a nízké úrovni:

  1. Optimalizace na vysoké úrovni (High-Level Optimization):
    • Tyto optimalizace se provádějí na úrovni zdrojového kódu nebo abstraktního syntaktického stromu (AST).
    • Cílem je zlepšit výkon programu pomocí transformací, které využívají znalosti o struktuře a sémantice zdrojového kódu.
    • Příklady optimalizací na vysoké úrovni:
      • Zjednodušení výrazů
      • Eliminace mrtvého kódu
      • Zabalení (wrapping) a rozbalení (unwrapping) cyklů
      • Rozdělení proměnných
      • Odstraňování společných podvýrazů
  2. Optimalizace na nízké úrovni (Low-Level Optimization):
    • Tyto optimalizace se provádějí na úrovni intermediální reprezentace (IR) nebo strojového kódu.
    • Cílem je zlepšit výkon programu pomocí transformací, které využívají znalosti o architektuře procesoru a paměti.
    • Příklady optimalizací na nízké úrovni:
      • Alokační optimalizace registrů
      • Inlining funkcí
      • Sdílení registrů mezi proměnnými
      • Optimalizace pipeliningu
      • Optimalizace větvení

Kompilátory C/C++ jako GCC nebo Clang provádějí řadu optimalizačních průchodů na vysoké i nízké úrovni před generováním výsledného strojového kódu. Tyto průchody mohou být řízeny pomocí přepínačů kompilátoru, které umožňují nastavit různé úrovně optimalizace, například -O1, -O2, -O3 a -Os.

KO

Topics

Combinatorial optimization problems - formulation, complexity analysis, algorithms and example applications. BE4M35KO (Course web pages)

Questions

Integer Linear Programming. Shortest paths problem and traveling salesman problem ILP formulations. Branch and Bound algorithm. Problem formulations using ILP. Special ILP problems solvable in polynomial time.

Shortest paths problem. Dijkstra, Bellman-Ford, and Floyd–Warshall algorithms. Shortest paths in directed acyclic graphs. Problem formulations using shortest paths.

Network flows. Maximum flow and minimum cut problems. Ford-Fulkerson algorithm. Feasible flow with balances. Minimum cost flow and cycle-canceling algorithm. Problem formulations using network flows. Maximum cardinality matching.

Knapsack problem. Approximation algorithm, dynamic programming approach, approximation scheme.

Traveling salesman problem. Double-tree algorithm and Christofides algorithm for the metric problem. Local search k-OPT.

Scheduling - problem description and notation. One resource - Bratley algorithm, Horn algorithm. Parallel identical resources - list scheduling, dynamic programming. Project scheduling with temporal constraints - relative order and time-indexed ILP formulations.

Constraint Satisfaction Problem.

AC3 algorithm.

PAG

Topics

Properties of parallel and distributed algorithms. Communication operations for parallel algorithms. Parallel algorithms for linear algebra. BE4M35PAG (Course web pages)

Questions

Describe basic communication operations used in parallel algorithms. Show cost analysis of one-to-all broadcast, all-to-all-broadcast, scatter, and all-to-all personalized communication on a ring, mesh, and hypercube. Describe All-Reduce and Prefix-Sum operations and outline their usage.

Describe performance metrics and scalability for parallel systems. How efficiency of a parallel algorithm depends on the problem size and the number of processors? Derive isoefficiency functions of a parallel algorithm for adding numbers (including communication between processors) and explain how it characterizes the algorithm.

Explain and compare two parallel algorithms for matrix-vector multiplication. Describe a parallel algorithm for matrix-matrix multiplication and explain the idea of Cannon’s algorithm. Discuss the principle and properties of the DNS algorithm used for matrix-matrix multiplication.

Outline the principle of sorting networks and describe parallel bitonic sort, including its scalability. Explain parallel enumeration sort algorithm on PRAM model, including its scalability.

Explain all steps of a parallel algorithm for finding connected components in a graph given by the adjacency matrix. Using an example, illustrate a parallel algorithm for finding a maximal independent set in a sparse graph.

PAL

Topics

Polynomial algorithms for standard graph problems. Combinatorial and number-theoretical algorithms, isomorphism, prime numbers. Search trees and their use. Text search based on finite automata.

Questions

Asymptotická složitost algoritmů

O Notace (Big O)

Ω Notace (Big Omega)

Θ Notace (Big Theta)

o Notace (Little O)

ω Notace (Little Omega)

Základní notace problémů s grafy

Reprezentace grafů

Matice sousednosti (Adjacency Matrix)

Matice vzdáleností (Distance Matrix)

Laplaceova matice (Laplacian Matrix)

Matice incidence

Seznam sousednosti (Adjacency List)

Algoritmy pro minimální kostru grafu

Minimální kostra grafu je podgraf, který spojuje všechny vrcholy, je strom a minimizuje celkovou váhu hran.

Algoritmus Prim-Jarník

Kruskalův algoritmus

Borůvkův algoritmus

Silně propojené komponenty

Kosaraju-Sharirův algoritmus

Tarjanův algoritmus

Eulerova stezka

Union-Find

Naivní implementace

Algoritmus pro nalezení Eulerovy stezky

Fleuryho algoritmus

Isomorfismus grafů

Isomorfismus stromů

Algoritmus certifikátů

Složitost

Generování a enumerace kombinatorických objektů

Podmnožiny

k-prvkové podmnožiny

Permutace

Kombinace

Pořadí

Grayovy kódy

Generování Grayových kódů

Prvočísla

Síto Eratosthena

Naivní algoritmus pro generování prvočísel

Zlepšený naivní algoritmus

Pseudonáhodná čísla

Lineární kongruentní generátor (LCG)

Hull-Dobell Theorem

Search trees - data structures, operations, and their complexities. Binary tree, AVL tree, red-black tree (RB-tree), B-tree and B+ tree, splay tree, k-d tree. Nearest neighbor searching in k-d trees. Skip list.

Binární strom (Binary tree)

AVL strom

Červeno-černý strom (Red-Black tree)

B-strom

B+ strom

Splay strom

k-d strom

Nearest Neighbor Searching v k-d stromech

Nejbližší soused hledání (Nearest Neighbor Searching, NNS) je algoritmus používaný v k-d stromech k nalezení bodu, který je nejbližší k danému dotazu. Je to důležitá operace pro řadu aplikací v oblasti počítačového vidění, strojového učení a datové analýzy.

Algoritmus

  1. Začněte na kořeni a procházejte stromem tak, jak byste to udělali při vyhledávání dotazovaného bodu, až narazíte na list.
  2. Nastavte tento list jako “aktuální nejbližší bod”.
  3. Vraťte se zpět na rodičovský uzel.
  4. Zkontrolujte, zda by rodičovský uzel mohl obsahovat bod bližší k dotazovanému bodu než aktuální nejbližší bod. Pokud ano, zkontrolujte, zda je to tak, a případně aktualizujte “aktuální nejbližší bod”.
  5. Zkontrolujte, zda by jiná větev, než kterou jsme prošli, mohla obsahovat bod bližší k dotazovanému bodu. Pokud ano, projeďte touto větví (začněte od kroku 1) a případně aktualizujte “aktuální nejbližší bod”.
  6. Pokračujte, dokud nezkontrolujete celý strom.

Složitost

Porovnání

Typ stromu Složitost vyhledání Složitost vložení Složitost mazání Výhody Nevýhody
Binární strom O(n) O(n) O(n) Přirozené uspořádání dat Nevyvážené stromy mohou mít vysoké výšky, což vede k neefektivním operacím
AVL strom O(log n) O(log n) O(log n) Dobře vyvážený Operace vložení a mazání mohou být pomalé kvůli potřebě vyvažování
Červeno-černý strom O(log n) O(log n) O(log n) Dobře vyvážený Operace vložení a mazání mohou být pomalé kvůli potřebě udržování vlastností stromu
B-strom O(log n) O(log n) O(log n) Dobré pro velké soubory dat Složitější implementace, může být pomalý pro operace v paměti
B+ strom O(log n) O(log n) O(log n) Rychlé sekvenční přístupy Interní uzly neukládají data, což může být neefektivní pro některé typy dotazů
Splay strom O(log n) průměrně O(log n) průměrně O(log n) průměrně Často přistupované prvky jsou rychle dostupné Nevyvážený, může vést k O(n) operacím v nejhorším případě
k-d strom O(log n) průměrně O(log n) průměrně O(log n) průměrně Dobré pro hledání v mnoha dimenzích Neefektivní pro vysoké dimenze, operace vkládání a mazání mohou být pomalé v některých případech

Skip-list

Struktura

Fungování

Složitost

Výhody

Nevýhody

Konečné automaty, regulární výrazy a operace nad regulárními jazyky

Konečné automaty (Finite Automata)

Regulární výrazy (Regular Expressions)

Operace nad regulárními jazyky

Všechny tyto operace vytvářejí regulární jazyky z regulárních jazyků, což je důležitá vlastnost regulárních jazyků.

Bitová reprezentace nedeterministických konečných automatů (NFA)

Nemůžu najít

Algoritmy pro vyhledávání textu

Přesné vyhledávání vzorců

Aproximativní vyhledávání vzorců

Automaty pro vyhledávání ve slovníku

SWA

Topics

Software architectures, their parameters and qualitative metrics. Architectural patterns, styles and standards. BE4M36SWA (Course web pages)

Questions

Popis Krutchenova 4+1 View Modelu softwarové architektury:

Jak 4+1 View Model zachycuje chování softwaru z různých perspektiv:

Souvislost mezi 4+1 View Model a UML modely:

UML diagramy pro 4+1 View Model:

  1. Logický pohled (Logical View):
    • Třídní diagram (Class Diagram)
    • Objektový diagram (Object Diagram)
    • Kompoziční struktura (Composite Structure Diagram)
    • Balíčkový diagram (Package Diagram)
  2. Procesní pohled (Process View):
    • Diagram činností (Activity Diagram)
    • Sekvenční diagram (Sequence Diagram)
    • Diagram spolupráce (Collaboration Diagram)
    • Stavový diagram (State Diagram)
  3. Fyzický pohled (Physical View):
    • Diagram nasazení (Deployment Diagram)
    • Diagram komponent (Component Diagram)
    • Komunikační diagram (Communication Diagram)
  4. Vývojový pohled (Development View):
    • Balíčkový diagram (Package Diagram)
    • Diagram komponent (Component Diagram)

Integrace UML s 4+1 View Model:

- UML diagramy poskytují vizuální reprezentaci pro každý pohled v 4+1 View Modelu
- Umožňují efektivní komunikaci mezi architekty, vývojáři, testery a dalšími členy týmu
- Podporují analýzu, návrh, implementaci a údržbu systému
- Usnadňují kontrolu a řízení kvality architektury

Co je softwarová architektura?

Důležitost softwarové architektury při vývoji systému:

  1. Zajištění kvality:
    • Architektura zajišťuje, že systém splňuje funkční a nefunkční požadavky.
  2. Usnadnění komunikace:
    • Architektura slouží jako společný jazyk pro vývojáře, zákazníky a další zúčastněné strany.
  3. Podpora znovupoužitelnosti:
    • Správně navržená architektura umožňuje znovupoužití kódu a komponent.
  4. Zjednodušení rozhodování:
    • Architektura poskytuje rámcové rozhodnutí pro vývojáře, které usnadňuje vývoj a údržbu.
  5. Řízení rizik:
    • Architektura pomáhá identifikovat a řešit rizika spojená s vývojem systému.
  6. Zlepšení výkonnosti:
    • Architektura optimalizuje výkonnost, škálovatelnost a stabilitu systému.

Směrnice pro návrh softwarové architektury:

  1. Rozdělit a vládnout:
    • Systém rozdělit na menší, snadno řiditelné komponenty.
  2. Abstrakce:
    • Použít abstrakce pro zjednodušení složitých problémů.
  3. Modularita:
    • Navrhnout nezávislé a snadno zaměnitelné moduly.
  4. Zachování informací:
    • Minimalizovat závislosti mezi komponentami.
  5. Škálovatelnost:
    • Umožnit snadné rozšíření systému.
  6. Znovupoužitelnost:
    • Navrhovat komponenty tak, aby byly znovupoužitelné.
  7. Flexibilita:
    • Umožnit snadnou údržbu a přizpůsobení změnám požadavků.

Architektonické styly:

Příklad architektonického stylu: MVC (Model-View-Controller)

  1. Model:
    • Reprezentuje data a byznysovou logiku aplikace.
    • Nezávislý na prezentační vrstvě a uživatelském rozhraní.
  2. View (Zobrazení):
    • Zodpovědný za prezentaci a zobrazení dat z modelu.
    • Aktualizuje se automaticky, když se změní data v modelu.
  3. Controller (Ovladač):
    • Zodpovědný za řízení interakce mezi modelem a zobrazením.
    • Zpracovává uživatelské vstupy a aktualizuje model nebo zobrazení.

Detaily architektonického stylu MVC:

Co je návrhový vzor (design pattern)?

Jaký problém řeší návrhové vzory?

Typy návrhových vzorů:

  1. Vzory pro tvorbu objektů (Creational Patterns):
    • Řeší problémy spojené s procesem vytváření objektů.
    • Příklady: Singleton, Factory Method, Abstract Factory, Builder, Prototype.
  2. Strukturální vzory (Structural Patterns):
    • Řeší problémy týkající se kompozice tříd a objektů.
    • Příklady: Adapter, Bridge, Composite, Decorator, Facade, Flyweight, Proxy.
  3. Vzory chování (Behavioral Patterns):
    • Řeší problémy interakce mezi objekty a způsoby, jakými spolupracují.
    • Příklady: Chain of Responsibility, Command, Interpreter, Iterator, Mediator, Memento, Observer, State, Strategy, Template Method, Visitor.

Důležitost znalosti návrhových vzorů:

  1. Zlepšení kvality kódu:
    • Návrhové vzory poskytují osvědčené řešení, která zvyšují kvalitu kódu.
  2. Zvýšení efektivity vývoje:
    • Použitím návrhových vzorů lze urychlit vývoj a snížit chybovost.
  3. Usnadnění komunikace mezi vývojáři:
    • Návrhové vzory slouží jako společný jazyk, který usnadňuje komunikaci a porozumění mezi vývojáři.
  4. Zjednodušení údržby:
    • Návrhové vzory usnadňují údržbu a rozšiřování kódu díky jejich známé struktuře a principům.
  5. Podpora znovupoužitelnosti:
    • Návrhové vzory podporují znovupoužitelnost kódu tím, že umožňují snadnější integraci a adaptaci kódu.

Existují návrhové antivzory (design antipatterns)?

Co je mikroservisní architektura?

Výhody a nevýhody mikroservisní architektury oproti monolitické architektuře:

Výhody:

  1. Lehká škálovatelnost:
    • Mikroservisy lze škálovat nezávisle na ostatních službách.
  2. Snadnější údržba:
    • Menší a jednodušší kódová základna usnadňuje údržbu a rozšiřování.
  3. Rychlejší nasazení:
    • Mikroservisy lze nasazovat nezávisle, což urychluje vývojový cyklus.
  4. Technologická agilita:
    • Každá služba může používat jiné technologie, což umožňuje snadnější inovace.
  5. Odolnost vůči chybám:
    • Selhání jedné služby má menší dopad na celý systém.

Nevýhody:

  1. Složitost:
    • Větší počet komponent a interakcí mezi nimi zvyšuje složitost systému.
  2. Výkon:
    • Komunikace mezi službami může být pomalejší než u monolitické architektury.
  3. Správa a monitorování:
    • Správa a sledování mnoha nezávislých služeb může být náročné.
  4. Distribuované transakce:
    • Řešení distribuovaných transakcí může být komplikovanější než v monolitických aplikacích.

Jak se vývoj mikroservisů liší od vývoje monolitické aplikace?

  1. Rozdělení aplikace:
    • Aplikace je rozdělena na menší, nezávislé služby.
  2. Komunikace mezi službami:
    • Mikroservisy komunikují pomocí API a lehkých protokolů.
  3. Databáze a konfigurace:
    • Každá služba má vlastní databázi a konfiguraci.
  4. Nezávislé nasazení:
    • Mikroservisy mohou být nasazeny a škálovány nezávisle.
  5. Technologická diverzita:
    • Každá služba může používat jiné technologie, což umožňuje snadnější inovace.
  6. Správa a monitorování:
    • Vyžaduje nástroje a postupy pro správu a sledování mnoha nezávislých služeb.
  7. Distribuované transakce:
    • Řešení distribuovaných transakcí může být komplikovanější než v monolitických aplikacích.

Metodiky, směrnice a osvědčené postupy pro vývoj mikroservisů:

  1. Rozdělit a vládnout:
    • Aplikaci rozdělit na menší, nezávislé a snadno řiditelné služby.
  2. Definice rozhraní (API):
    • Navrhnout jasná a stabilní API pro komunikaci mezi službami.
  3. Oddělení zájmů:
    • Každá služba by měla mít jednu zodpovědnost a řešit jeden aspekt byznysu.
  4. Decentralizace správy dat:
    • Každá služba by měla mít svou vlastní databázi a spravovat svá data nezávisle.
  5. Stavová nezávislost:
    • Preferovat bezestavové služby, které neuchovávají stav mezi požadavky.
  6. Automatizace nasazení a škálování:
    • Používat nástroje a postupy pro automatické nasazení a škálování služeb.
  7. Monitorování a sledování:
    • Implementovat monitorování, sledování a protokolování pro snadnou detekci a řešení problémů.
  8. Resilience a tolerování selhání:
    • Navrhnout služby tak, aby byly schopny zotavit se z chyb a pokračovat v provozu.
  9. Bezpečnost:
    • Zabezpečit komunikaci mezi službami a chránit citlivá data.
  10. Kontejnerizace a orchestrace:
    • Používat kontejnery (např. Docker) a orchestrátory (např. Kubernetes) pro snadnou správu a škálování.

Antivzory, kterým by se mělo vyhnout při vývoji mikroservisů:

  1. Nedostatečné rozdělení služeb:
    • Příliš velké nebo příliš malé služby mohou vést k problémům se škálovatelností a údržbou.
  2. Nadbytečná komunikace mezi službami:
    • Příliš mnoho vzájemné komunikace mezi službami může vést k problémům s výkonem a složitosti.
  3. Centrální správa dat:
    • Spoléhání na jednu centrální databázi pro všechny služby může vést k problémům se škálovatelností a nezávislostí služeb.
  4. Synchronní komunikace:
    • Nadměrné použití synchronní komunikace může způsobit výkonnostní problémy a závislost mezi službami.
  5. Nedostatečné monitorování a sledování:
    • Absence monitorování a sledování může ztížit detekci a řešení problémů.
  6. Nedostatečná bezpečnost:
    • Nedostatek zabezpečení mezi službami nebo nedbalost při ochraně dat může vést k zranitelnostem.
  7. Vývoj monolitu v mikroservisách:
    • Přístup k vývoji mikroservisů, který zachovává špatné návyky z monolitického vývoje, může způsobit výkonnostní a údržbové problémy.
  8. Nedostatečná automatizace nasazení a škálování:
    • Ruční nasazení a škálování služeb může vést k chybám a zpomalit vývoj.
  9. Zanedbávání kontejnerizace a orchestrace:
    • Neužívání kontejnerů a orchestrátorů může ztížit správu a škálování mikroservisů.
  10. Nedostatečná dokumentace a komunikace:
    • Špatně zdokumentované nebo nekomunikované změny mohou vést k nedorozuměním a chybám mezi týmy.

Výběr softwarové architektury

Při výběru softwarové architektury je těžké říci, že jedna architektura je obecně lepší než druhá, protože jejich vhodnost závisí na konkrétních požadavcích a omezeních projektu. Při výběru architektury je důležité zvážit následující faktory:

  1. Požadavky na výkon:
    • Některé architektury mohou lépe podporovat vysoký výkon než jiné, například distribuované systémy pro škálování.
  2. Škálovatelnost:
    • Zvolená architektura by měla umožňovat snadné škálování a rozšiřování aplikace, aby bylo možné lépe řešit růst zátěže.
  3. Flexibilita a rozšiřitelnost:
    • Architektura by měla umožňovat snadné přidávání nových funkcí a integraci s dalšími systémy.
  4. Bezpečnost:
    • Důležité je zvážit, jak dobře architektura řeší bezpečnostní hrozby a zabezpečuje citlivá data.
  5. Údržba a evoluce:
    • Architektura by měla usnadňovat údržbu a umožňovat snadnou adaptaci na změny v požadavcích nebo technologiích.
  6. Náklady a zdroje:
    • Je třeba zohlednit dostupné zdroje, jako je čas, rozpočet a lidské zdroje, a zvážit náklady na vývoj, provoz a údržbu.
  7. Kompatibilita s technologiemi:
    • Zvolená architektura by měla být kompatibilní s technologiemi, které tým již používá, nebo které plánuje použít.
  8. Týmová zkušenost a dovednosti:
    • Je důležité zvážit zkušenosti a dovednosti týmu a jak dobře se dokážou vyrovnat s nároky zvolené architektury.

Při výběru architektury je důležité zvážit všechny tyto faktory a zvolit takovou, která nejlépe vyhovuje konkrétním potřebám a omezením projektu. Není žádná univerzálně “špatná” nebo “lepší” architektura; místo toho je třeba posoudit, jaká architektura je nejvhodnější pro daný projekt.

Měření kvality architektury:

Kvalitu softwarové architektury lze měřit pomocí několika metrik a z různých perspektiv. Některé z těchto perspektiv zahrnují:

  1. Výkon:
    • Měření, jak rychle a efektivně architektura zvládá požadavky, např. doba odezvy, průchodnost a latence.
  2. Škálovatelnost:
    • Hodnocení, jak snadno může architektura růst, aby vyhověla rostoucím požadavkům, a jak dobře se přizpůsobuje změnám v zátěži.
  3. Flexibilita a rozšiřitelnost:
    • Určení, jak snadno může být architektura rozšířena nebo upravena pro nové funkce nebo integraci s dalšími systémy.
  4. Bezpečnost:
    • Hodnocení, jak dobře architektura zabezpečuje citlivá data a chrání před bezpečnostními hrozbami.
  5. Spolehlivost a odolnost:
    • Měření, jak dobře architektura zvládá selhání a chyby, a jak rychle se dokáže zotavit.
  6. Údržba a evoluce:
    • Hodnocení, jak snadno může být architektura udržována a aktualizována, aby vyhovovala změnám v požadavcích a technologiích.
  7. Modularita a oddělení zájmů:
    • Určení, jak dobře je architektura rozdělena do samostatných, snadno spravovatelných a znovupoužitelných komponent.
  8. Testovatelnost:
    • Hodnocení, jak snadno lze architekturu testovat a validovat pro zajištění kvality a spolehlivosti.

Každá z těchto perspektiv nabízí odlišné metriky a hodnocení kvality architektury. Pro měření kvality architektury je třeba zvážit všechny tyto aspekty a určit, jaké metriky jsou nejrelevantnější pro konkrétní projekt a jeho požadavky.

TAL

Topics

Problem/language complexity classes with respect to the time complexity of their solution and memory complexity including undecidable problems/languages. BE4M01TAL (Course web pages)

Questions

Asymptotic growth of functions, time and space complexity of algorithms. Correctness of algorithms - variant and invariant.

Deterministic Turing machines, multitape Turing machines, and Nondeterministic Turing machines.

Decision problems and languages. Complexity classes P, NP, co-NP. Reduction and polynomial reduction, class NPC. Cook theorem. Heuristics and approximate algorithms for solving NP complete problems.

Classes based on space complexity: PSPACE and NPSPACE. Savitch Theorem.

Randomized algorithms. Randomized Turing machines. Classes based on randomization: RP, ZPP, co-RP.

Decidability and undecidability. Recursive and recursively enumerable languages. Diagonal language. Universal language and Universal Turing machine.

ZKS

Topics

The methodology of software testing. Methods for test creation from the application model. Automated testing. BE4M36ZKS (Course web pages)

Questions

V-model:

W-model:

Srovnání V-modelu a W-modelu:

Statické testování a jeho role ve W-modelu:

Statické testování:

Role ve W-modelu:

Individuální metody statického testování:

  1. Průzkum kódu (Code review):
    • Manuální kontrola zdrojového kódu
    • Hledání chyb, nedostatků, či nesouladu se standardy
    • Mohou být prováděny kolegy, týmem nebo i autorem kódu (sebereview)
  2. Statická analýza kódu (Static code analysis):
    • Automatická kontrola zdrojového kódu pomocí nástrojů a algoritmů
    • Identifikace potenciálních chyb, problémů a nesouladů se standardy
    • Příklady nástrojů: FindBugs, PMD, SonarQube, JSHint
  3. Kontrola dokumentace (Documentation review):
    • Manuální kontrola dokumentace projektu
    • Ověření správnosti, úplnosti a srozumitelnosti informací
    • Zahrnuje kontrolu technické dokumentace, návody, specifikace apod.
  4. Průzkum návrhu (Design review):
    • Manuální kontrola návrhu systému nebo komponenty
    • Ověření, zda návrh splňuje požadavky a je vhodný pro implementaci
    • Posouzení technických a architektonických rozhodnutí
  5. Kontrola požadavků (Requirements review):
    • Manuální kontrola specifikace požadavků na systém
    • Ověření správnosti, úplnosti a srozumitelnosti požadavků
    • Hledání možných konfliktů, nejasností nebo nekonzistencí

Manuální testování:

Model Based Testing (MBT):

Výhody MBT oproti manuálnímu testování:

Nevýhody MBT oproti manuálnímu testování:

Příklady modelů použitelných v Model Based Testing (MBT):

  1. Konečný automat (Finite State Machine, FSM):
    • Model založený na stavech a přechodech mezi nimi
    • Popisuje chování systému nebo komponenty
    • Vhodný pro testování systémů s omezeným počtem stavů a přechodů
  2. Petriho síť (Petri Net):
    • Matematický model pro popis distribuovaných systémů
    • Zahrnuje místa, přechody a tokeny pro popis chování
    • Použitelný pro testování paralelních nebo konkurenčních systémů
  3. Markovův řetězec (Markov Chain):
    • Model náhodných procesů s konečným počtem stavů
    • Přechody mezi stavy závisejí pouze na aktuálním stavu
    • Užitečný pro testování systémů s pravděpodobnostními přechody
  4. Scénářové modely (Scenario Models):
    • Modely popisující konkrétní případy užití nebo interakce s aplikací
    • Vhodné pro testování funkcionality systému z pohledu uživatele
  5. Datové modely (Data Models):
    • Modely zaměřené na strukturu a vztahy mezi daty v systému
    • Použitelné pro testování datových operací, jako je ukládání, načítání a zpracování dat

Vztah MBT k automatickému testování:

Principy automatizace testování:

Ekonomika automatizace testování:

Úrovně automatizace testů:

  1. Jednotkové testy (Unit tests):
    • Automatické testování jednotlivých funkcí nebo tříd
    • Zajišťují, že jednotlivé komponenty fungují správně
  2. Integrační testy (Integration tests):
    • Automatické testování interakce mezi komponentami nebo systémy
    • Ověřují, že celý systém funguje správně jako celek
  3. Systémové testy (System tests):
    • Automatické testování celého systému nebo aplikace
    • Kontrolují, zda systém splňuje požadavky a očekávání uživatelů
  4. Uživatelské akceptační testy (User Acceptance tests, UAT):
    • Částečně automatizované testování z pohledu uživatele a jeho zkušeností
    • Ověřují, že aplikace je připravena k nasazení a použití
  5. Regresní testy (Regression tests):
    • Automatické testování zaměřené na odhalení chyb po změnách v kódu
    • Kontrolují, že nové změny nezpůsobily problémy v již otestovaných částech

Příklady hlavních přístupů a technologií používaných v automatizaci testování softwaru:

  1. Nástroje pro jednotkové testování (Unit testing tools):
    • JUnit (pro Java)
    • NUnit (pro .NET)
    • Mocha (pro JavaScript)
    • Pytest (pro Python)
    • Pomáhají vytvářet a provádět jednotkové testy pro jednotlivé komponenty
  2. Nástroje pro integrační a systémové testování (Integration and system testing tools):
    • Selenium (pro webové aplikace)
    • Appium (pro mobilní aplikace)
    • JMeter (pro testování výkonnosti)
    • SoapUI (pro testování webových služeb)
    • Umožňují automatizaci testů na úrovni celého systému nebo aplikace
  3. Rámce pro Behavior-Driven Development (BDD):
    • Cucumber (pro Ruby, Java, .NET)
    • SpecFlow (pro .NET)
    • Behave (pro Python)
    • Pomáhají vytvářet testy založené na chování systému a propojení s požadavky
  4. Nástroje pro kontinuální integraci (Continuous Integration, CI) a kontinuální nasazení (Continuous Deployment, CD):
    • Jenkins
    • GitLab CI/CD
    • Bamboo
    • CircleCI
    • Travis CI
    • Umožňují automatizovat provádění testů a nasazení aplikace v průběhu vývoje
  5. Testovací nástroje pro vizuální porovnávání (Visual testing tools):
    • Applitools
    • Percy
    • Galen Framework
    • Porovnávají vizuální vzhled aplikace napříč různými prohlížeči, platformami a obrazovkami
  6. Nástroje pro nahrávání a přehrávání testů (Record and playback tools):
    • Selenium IDE
    • Katalon Studio
    • Umožňují nahrát testovací scénáře při manuálním provádění testu a poté je automaticky přehrát

Ekvivalentní třída (Equivalence Class):

Hraniční hodnoty (Boundary Values):

Kombinatorické interakční testování (Combinatorial Interaction Testing):

Kombinatorický výbuch (Combinatorial Explosion):

Jak efektivně snížit kombinace vstupních dat:

  1. Pairwise testing (dvojice testů):
    • Testování všech možných dvojic proměnných místo všech kombinací
    • Značně snižuje počet testovacích případů, aniž by se značně snížila účinnost testování
  2. Orthogonal Arrays (ortogonální pole):
    • Testování s omezeným počtem kombinací, které zahrnují všechny možné interakce mezi proměnnými
    • Pomáhá snížit počet testovacích případů, zatímco zachovává dobré pokrytí interakcí
  3. Testování založené na prioritách:
    • Prioritizace testovacích případů na základě rizik a pravděpodobnosti chyb
    • Provedení testů s vyšší prioritou a omezení testů s nižší prioritou
  4. Ekvivalentní třídy (Equivalence Classes) a hraniční hodnoty (Boundary Values):
    • Rozdělení vstupních hodnot do ekvivalentních tříd a testování na základě reprezentativního vzorku
    • Testování hraničních hodnot, které se zaměřuje na hodnoty na hranicích tříd
  5. Model-Based Testing (MBT):
    • Vytvoření matematického nebo formálního modelu systému a generování testovacích případů z tohoto modelu
    • Pomáhá snížit počet testovacích případů a současně zvyšuje účinnost testování

Pairwise (2-way) testing:

N-way testing:

Princip testování založeného na cestách (Path-based testing):

Formální definice modelu systému a kritéria pokrytí testů:

  1. Node (uzel) coverage:
    • Požadavek, aby každý uzel v grafu byl navštíven alespoň jednou během testování
    • Zaměřuje se na procházení všech možných stavů systému
    • Méně náročné než ostatní kritéria pokrytí, ale méně účinné v odhalování chyb
  2. Edge (hrana) coverage:
    • Požadavek, aby každá hrana v grafu byla projita alespoň jednou během testování
    • Zaměřuje se na testování všech možných přechodů mezi uzly
    • Přináší lepší pokrytí než node coverage, ale vyšší nároky na testovací případy
  3. Edge-pair coverage:
    • Požadavek, aby každá dvojice sousedních hran v grafu byla projita alespoň jednou během testování
    • Zaměřuje se na testování všech možných sekvencí dvou přechodů mezi uzly
    • Poskytuje ještě lepší pokrytí než edge coverage, ale s vyššími nároky na testovací případy
  4. Prime-path coverage:
    • Požadavek, aby každá jedinečná, nezkrácená cesta v grafu byla projita alespoň jednou během testování
    • Zaměřuje se na testování všech možných sledů uzlů a hran bez opakování
    • Poskytuje nejlepší pokrytí v porovnání s ostatními kritérii, ale s nejvyššími nároky na testovací případy

Prioritizace procesů/workflow aktivit při generování testovacích případů:

  1. Analýza rizik:
    • Identifikace oblastí s nejvyšším rizikem chyb nebo dopadů na systém
    • Prioritizace testování těchto oblastí s vyšším rizikem
    • Pomáhá alokovat zdroje na nejvíce kritické části systému
  2. Důležitost funkcí:
    • Určení důležitosti jednotlivých funkcí nebo workflow aktivit pro uživatele nebo systém
    • Testování nejdůležitějších funkcí má vyšší prioritu
    • Zajišťuje, že klíčové části systému jsou pečlivě testovány
  3. Frekvence použití:
    • Identifikace často používaných funkcí nebo workflow aktivit
    • Prioritizace testování těchto často používaných částí
    • Alokace zdrojů na oblasti, které mají největší dopad na uživatele
  4. Historie chyb:
    • Analýza předchozích chyb a identifikace oblastí, které jsou náchylnější k chybám
    • Prioritizace testování těchto částí systému
    • Zaměření na odhalení a opravu chyb v problémových oblastech
  5. Závislosti mezi komponentami:
    • Identifikace komponent nebo workflow aktivit, které mají významné závislosti na ostatních částech systému
    • Prioritizace testování těchto závislých částí
    • Odhalení chyb v závislých komponentách, které by mohly ovlivnit celý systém
  6. Testovací techniky a kritéria pokrytí:
    • Použití různých testovacích technik, jako jsou ekvivalentní třídy, hraniční hodnoty, kombinatorické testování nebo testování založené na cestách
    • Určení kritérií pokrytí pro testování, jako je node coverage, edge coverage, edge-pair coverage nebo prime-path coverage
    • Prioritizace testovacích případů na základě zvolených technik a kritérií pokrytí

Při generování testovacích případů se prioritizace provádí na základě různých faktorů, jako je riziko, důležitost funkcí, frekvence použití, historie chyb, závislosti mezi komponentami a zvolené testovací techniky a kritéria pokrytí. Prioritizace pomáhá alokovat zdroje na nejdůležitější části systému a maximalizovat účinnost testování.