Nevite nekdo, jak by se resily priklady 4 a 5 z te pisemky, ktera je nekde tu na foru nebo i ve studnici (nevim, jestli je z minuleho nebo z predminuleho roku)?
Rušíme záznam v souboru organizovaném v rozšířitelném (Faginově) hašování s adresářem ve dvou stránkách na disku.
· Kolik bufferů (1 buffer = 1 stránka) je třeba alokovat ve vnitřní paměti? 1
· Kolik I/O operací je třeba v nejhorším případě (zkracuje se adresář)?
5. Mějme redundantní B-strom (m = 6) se třemi úrovněmi, jehož část je zachycena na
obrázku.
· Zakreslete, jak bude vypadat odpovídající část uvedeného B-stromu po přidní
prvku 13.
· Jaký je minimální počet bufferů potřebný pro provedení uvedené operace
INSERT za předpokladu, že pro potřeby uvedené operace každou stránku
načítáme nejvýše 1x?
· Kolik stránek musíme mít pro danou operaci nejvíce zamčených, jsou-li operace
na uvedeném B-stromě prováděny paralelně?
· Kolik času bychom potřebovali na provedení dané operace za předpokladu, že
žádnou ze stránek nemáme v paměti (s=8,5ms, r=4,7ms, btt=0,2ms) a že s diskem
nepracuje žádný jiný proces?
Je to za spoustu bodu (zvlast ta 5) a ja vubec nevim jak se pracuje s tema bufferama a jak spocitat ten cas .
Priklady z minulych pisemek
-
- Matfyz(ák|ačka) level I
- Příspěvky: 20
- Registrován: 15. 5. 2006 09:02
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Priklady z minulych pisemek
Computers are useless. They can only give you answers. - Pablo Picasso
Calm down -- it's only ones and zeros.
Bug? That's not a bug, that's a feature. -T. John Wendel
Calm down -- it's only ones and zeros.
Bug? That's not a bug, that's a feature. -T. John Wendel
Re: Priklady z minulych pisemek
1 buffer ti urcite nestaci, pokud by doslo na slevani stranek, potrebujes buffery na obe dotycne stranky. Aby se zbytecne znova nenacitalo z disku, potrebujes buffery 4.aja píše:Rušíme záznam v souboru organizovaném v rozšířitelném (Faginově) hašování s adresářem ve dvou stránkách na disku.
· Kolik bufferů (1 buffer = 1 stránka) je třeba alokovat ve vnitřní paměti? 1
READ 1. stranky adresare do bufferu 1aja píše:· Kolik I/O operací je třeba v nejhorším případě (zkracuje se adresář)?
READ 2. stranky adresare do bufferu 2
READ stranky, ve ktere je vypousteny prvek, do bufferu 3, vypustime ho, spocteme prvky
READ stranky, ktera je s touto sdruzena, tj. jedina, s kterou ji lze slevat, do bufferu 4, spocteme prvky
Nyni mame tri moznosti:
1. Stranky neni nutne slevat => WRITE stranky v bufferu 3, dohromady 4 READ a 1 WRITE
2. Stranky slevame, ale adresar nezkracujeme. Nejhorsi je v tomto pripade, kdyby na obe stranky bylo pouzito mene bitu, nez je v adresari. Pointry ukazujici na jednu stranku je nutne prepsat - adresar je na 2 stranky. Nemohlo by se nam stat, ze bychom prepisovali pointery na obou z nich? Nemohlo, v takovem pripade bychom si vybrali tu druhou, a protoze jsou ostruvky pointeru souvisle, musi uz byt na jedne strance v adresari => WRITE nove stranky (jeji vytvoreni je mozne na miste z bufferu 3 a 4), WRITE adresare (vytvoreni taktez na miste), dohromady 4 READ a 2 WRITE.
3. Stranky slevame, adresar zkracujeme. WRITE nove stranky( jeji vytvoreni je opet mozne na miste), WRITE noveho adresare( jeho vytvoreni je mozne na miste posouvanim pointeru, novy adresar je polovicni, tedy na jednu stranku). Tedy 4 READ a 2 WRITE.
V nejhorsim pripade je to 6 I/O operaci.
Pripomenuti: Strom je trojurovnovy, v koreni je jeste misto, mame zakreslenou jen cestu nejvice vlevo a uzly jsou plne. Doprostred toho nejvice vlevo patri cislo 13, tedy je nutne provest deleni na nejnizsi urovni, i o uroven vys.aja píše:5. Mějme redundantní B-strom (m = 6) se třemi úrovněmi, jehož část je zachycena na
obrázku.
· Zakreslete, jak bude vypadat odpovídající část uvedeného B-stromu po přidní
prvku 13.
· Jaký je minimální počet bufferů potřebný pro provedení uvedené operace
INSERT za předpokladu, že pro potřeby uvedené operace každou stránku
načítáme nejvýše 1x?
· Kolik stránek musíme mít pro danou operaci nejvíce zamčených, jsou-li operace
na uvedeném B-stromě prováděny paralelně?
· Kolik času bychom potřebovali na provedení dané operace za předpokladu, že
žádnou ze stránek nemáme v paměti (s=8,5ms, r=4,7ms, btt=0,2ms) a že s diskem
nepracuje žádný jiný proces?
Oznacme K koren stromu, S stredni uzel, L list, N novy list, R novy rozstepeny stredni uzel.
Prace je takova:
1) READ K do bufferu 1, zamek je nutny, cas s + r + btt (je to na nahodnem miste na disku)
2) READ S do bufferu 2, zamek je nutny, uzel je plny, takze zamky nad nim uvolnit nelze, cas s + r + btt (je to na nahodnem miste na disku).
3) READ L do bufferu 3, zamek je nutny, uzel je plny, takze zamky nad nim uvolnit nelze, cas s + r + btt (je to na nahodnem miste na disku).
4) Rozdelime L do bufferu 3 a 4.
5) Zapiseme L z bufferu 3, zamek uvolnime, cas 2r (je to rewrite, jsme na spravne stope, cekame na data), buffer 3 uvolnime.
6) Rozdelime S do bufferu 2 a 3.
7) Zapiseme S z bufferu 2, zamek uvolnime, cas s + r + btt (je to na nahodnem miste na disku), buffer 2 uvolnime.
Najdeme volne misto (??Lze predpokladat, ze mame dve volne stranky za sebou??), cas s + r
9) Zapiseme N z bufferu 4, cas btt, buffer 4 uvolnime.
10) Zapiseme R z bufferu 3, cas btt, buffer 3 uvolnime.
11) Zapiseme K z bufferu 1, zamek uvolnime, cas s + r + btt (je to na nahodnem miste na disku), buffer 1 uvolnime.
Celkem jsme tedy potrebovali 4 buffery (mezi kroky 4-5 a 6-7), 3 zamky (mezi kroky 3-5) a potrebny cas je 6s + 8r + 7btt = 90 ms.
|- <xs> --> ( <xs> --> <xs> )
-
- Matfyz(ák|ačka) level I
- Příspěvky: 20
- Registrován: 15. 5. 2006 09:02
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Re: Priklady z minulych pisemek
Tyjo, pekny . Dik moc .
Computers are useless. They can only give you answers. - Pablo Picasso
Calm down -- it's only ones and zeros.
Bug? That's not a bug, that's a feature. -T. John Wendel
Calm down -- it's only ones and zeros.
Bug? That's not a bug, that's a feature. -T. John Wendel
Re: Priklady z minulych pisemek
Ahoj a jak by se pocitalo tohle:
3. Mějme indexovaný soubor s blokovacím faktorem primárního souboru b = 6, v něm je
uložených 597 záznamů. Indexy jsou tvořeny B+-stromem (m = 60; primární klíč) a
bitovou mapou (příslušný atribut nabývá šesti hodnot). Předpokládejme, že žádná data
nejsou načtena do paměti.
· Spočtěte, kolik přístupů na disk bude třeba pro vyhledání záznamu podle
primárního klíče? Uveďte postup. 4
· Spočtěte, kolik nejméně přístupů na disk bude třeba na přidání nového záznamu
do uvedeného souboru? Odůvodněte. 4
· Předpokládejme, že uvedený soubor je umístěn na disku s parametry s = 8,5ms,
r = 4,2ms, btt = 0,2ms. Kolik času budeme přinejhorším potřebovat na přidání
záznamu? 5
Dik
3. Mějme indexovaný soubor s blokovacím faktorem primárního souboru b = 6, v něm je
uložených 597 záznamů. Indexy jsou tvořeny B+-stromem (m = 60; primární klíč) a
bitovou mapou (příslušný atribut nabývá šesti hodnot). Předpokládejme, že žádná data
nejsou načtena do paměti.
· Spočtěte, kolik přístupů na disk bude třeba pro vyhledání záznamu podle
primárního klíče? Uveďte postup. 4
· Spočtěte, kolik nejméně přístupů na disk bude třeba na přidání nového záznamu
do uvedeného souboru? Odůvodněte. 4
· Předpokládejme, že uvedený soubor je umístěn na disku s parametry s = 8,5ms,
r = 4,2ms, btt = 0,2ms. Kolik času budeme přinejhorším potřebovat na přidání
záznamu? 5
Dik
- Petr-H
- Matfyz(ák|ačka) level II
- Příspěvky: 81
- Registrován: 30. 1. 2006 14:18
- Typ studia: Informatika Mgr.
- Login do SIS: hosep5am
- Bydliště: VŠK 17. listopadu
- Kontaktovat uživatele:
Re: Priklady z minulych pisemek
Tento příklad je už rozebrán zde http://forum.matfyz.info/viewtopic.php?f=386&t=2380Návštěvník píše:Ahoj a jak by se pocitalo tohle:
3. Mějme indexovaný soubor s blokovacím faktorem primárního souboru b = 6, v něm je
uložených 597 záznamů. Indexy jsou tvořeny B+-stromem (m = 60; primární klíč) a
bitovou mapou (příslušný atribut nabývá šesti hodnot). Předpokládejme, že žádná data
nejsou načtena do paměti.
· Spočtěte, kolik přístupů na disk bude třeba pro vyhledání záznamu podle
primárního klíče? Uveďte postup. 4
· Spočtěte, kolik nejméně přístupů na disk bude třeba na přidání nového záznamu
do uvedeného souboru? Odůvodněte. 4
· Předpokládejme, že uvedený soubor je umístěn na disku s parametry s = 8,5ms,
r = 4,2ms, btt = 0,2ms. Kolik času budeme přinejhorším potřebovat na přidání
záznamu? 5
Dik