תרגיל כיתה מספר1

קבצים ממוינים

מצגת לחישובים ניתן למצוא כאן

1.

קובץ מכיל 14940 רשומות המאורגנות לפי צילינדרים. הדיסק מורכב מ-14 משטחי מגנוט, בכל משטח ישנן 220 מסילות ובכל מסילה יש 100 בלוקים בנפח KB 0.5, אורך כל רשומה 200 בתים. אין פיצול רשומות בין הבלוקים. הנח שיחידת קריאה/ כתיבה(pages) מ/אל הדיסק הינה של בלוק אחד. הקובץ מתחיל בבלוק הראשון של המסילה 9 משטח 7.

א. באיזה משטח ובאיזה צילינדר נמצאת הרשומה האמצעית(ה-7470) של הקובץ?

ב. באיזה משטח ובאיזה צילינדר נמצאת הרשומה האחרונה של הקובץ?הסבר.

ג. כמה זמן דרוש להעביר רשומה אקראית לזיכרון כאשר ידעה שמהירות סיבוב הדיסק היא 100 סל"ש,זמן גישה (seek time) 20 Ms בממוצע. קריאה מהדיסק לזיכרון היא ביחידת גודל של מסילה שלמה.

2.

קובץ פריטים מכיל 12000 רשומות המאורגנות לפי צילינדרים. הדיסק מורכב מ-300 גלילים ו-10 משטחי מגנוט, מסילה מחולקת ל-60 בלוקים בנפח KB 0.5, אורך כל רשומה 200 בתים. אין פיצול רשומות בין הבלוקים. הנח שיחידת קריאה/ כתיבה(pages) מ/אל הדיסק הינה של בלוק אחד. הקובץ מתחיל בבלוק הראשון של המסילה 17 משטח 5.

א. באיזה משטח ובאיזה צילינדר נמצאת הרשומה האחרונה של הקובץ?הסבר.

3.

קובץ פריטים מכיל 18000 רשומות המאורגנות לפי צילינדרים. הדיסק מורכב מ-8 משטחי מגנוט,בכל משטח יש 250 מסילות, מסילה מחולקת ל-100 בלוקים בנפח KB0.5 אורך כל רשומה 150 בתים. אין פיצול רשומות בין הבלוקים. הנח שיחידת קריאה/ כתיבה(pages) מ/אל הדיסק הינה של בלוק אחד. הקובץ מתחיל בבלוק הראשון של המסילה 30 משטח 4.

קריאה או כתיבת נתון מתבצע בלוק שלם בבת אחת .

נתונים :

חשוב לדעת הנתונים נכתבים צילינדר צילינדר .

בכל מסילה יש 100 בלוקים בכל אחד נכנסים 3 רשומות

אנחנו נמצאים במשתח רביעי מתוך 8 כלומר אפשר להכניס 300*5 רשומות

לצילינדר הנוכחי .

נשארו להו עוד 10500 רשומות לפי חישוב של 8* 300 רשומות לצילינדר יקח לנו עוד 4 צילינדרים + 900 רשומות שימוקמו במסילה הבאה .

כלומר הגענו לצילינדר 45 מסילה 3 בסוף.

א. באיזה משטח ובאיזה צילינדר נמצאת הרשומה 12000 של הקובץ?הסבר.

ב. נתון אותו קובץ נתונים ואותו דיסק,אולם כעת נתון שיחידת ק/כ היא בגודל KB5.מותר לפצל רשומות בין בלוקים אך לא בין יחידת ק/כ.כאמור,הקובץ מתחיל בבלוק הראשון של מסילה 31 במשטח 4.

גודל AU\אורך רשומה = 5*1024B\150 =34.13 = 34 רשומות

1מספר AU לקובץ = 18000\34 =529.41 מעגלים למעלה =530AU .

כמה בלוקים לכל AU 5k\0.5k = 10

ב530 AU יש 5300 בלוקים .

במסילה 31 יש 500 בלוקים כלומר צריך צריך עוד 4800

צריך עוד 4800/800-בצילינדר כלומר עוד 6 צילינדרים .

ג. כמה זמן דרוש להעביר רשומה אקראית לזיכרון כאשר ידוע שהמהירות היא 100 סל"ש

זמן גישה 20ms בממוצע .

קריאה \כתיבה מ\אל הדיסק היא בגודל מסילה שלמה.

Seek time - הזמן שעובר בין רגע הזזת הזרוע עד להגעה לרשומה המבוקשת .

Rotation delay – זמן השהיה סיבובית = מחצית סיבוב שלם

לפי המהירות 100 סל"ש סיבוב אחד 1:100 חצי סיבוב

1/200 שניות נהפוך למילי שניות נכפול ב 1000

Data transfer time

מורכב משלושה מרכיבים :

Data transfer size - מסילה שלמה 100 בלוקים = גודל בלוק * כמות בלוקים במסילה = 100 * 0.5 k =50k

Media data rate – קצב העברת הנתונים מהמשתח עד הבקר \אוגר\חוצץ\buffer

מהירות סיבוב הדיסק *גודל מסילה = 100*0.5 * 100

/sec5000k.

TANSFER TIME -- =transfer size/media data

+TRANSFER SIZE/ INTERFACE DATA RATEZBHJ

=50KB/5000KB/SEC +0 =10 MS

COMMAND OVERHEAD

זמן שלוקח למעבד לפענח פקודת ק\כ אם לא מצויין זמן אז זה 0

4.

קובץ ממוין מכיל 4000 רשומות המאורגנות לפי צילינדרים. הדיסק מורכב מ-10 משטחי מגנוט,בכל משטח יש 300 מסילות, מסילה מחולקת ל-30 בלוקים בנפח KB0.5 ,אורך כל רשומה 200 בתים זמן גישה 20 Ms בממוצע.קריאה מהדיסק לזיכרון ביחידת גודל של בלוק אחד.מהירות סיבוב הדיסק 80 סל"ש.

א.מהו נפח הדיסק?

ב.מהו נפח הקובץ בבלוקים?

ג.מהו זמן העברת בלוק נתון אקראי לזיכרון?

ד.יש לקרוא ולעבד 67 רשומות (סדרתית),כאשר הגישה לרשומה היא אקראית(הנח שהיא הראשונה בבלוק) .זמן עיבוד פעולת ק/כ לכל רשומה הוא

0.05 Ms .יחידת ק/כ בגודל בלוק.מהו זמן הקריאה ועיבוד הכולל של 67 רשומות.

קבצים לא ממוינים

1.

נתון קובץ לא ממוין(heap) עם 60000 רשומות בעלי אורך 720 בתים.גודל יחידות ק/כ 8KB.מהו זמן חיפוש ממוצע של רשומה אקראית(במונחי מס' גישות AU) כאשר 20% מהחיפושים לא מוצאים רשומות(יש להתעלם מזמן עיבוד פקודה).

60000 רשומות

אורך רשומות 720B

20% מהחיפושים לא מוצאים

יטש למצוא זמן חיפוש ממוצא

גודל AU 8kB

נוסחא לחיפוש סידר

P(1+b)/2 +(1-P)p

שיעור הצלחה – p

1-p שיעור כישלון

B - מספר AU -מספר גישות

כמות רשומות בAU 8k\270 11.37

11 רשומות בAU אחד

כמות AU לקובץ : 60000\11 5454 .

5455 AU

B=5455

לפי הנוסחא : 3273.4= 0.8(1+5455)/2+0.2*5455

מעגלים כלפי מעלה 3274 זמן חיפוש ממוצע =מספר גישות .

כדי למצוא את הדרוש יש לכפול total time ב מספר הזה .

2.

נתון קובץ לא ממוין(heap) עם 120000 רשומות בעלי אורך 720 בתים.גודל יחידות ק/כ 8KB.

א.מהו זמן חיפוש ממוצע של רשומה אקראית(במונחי מס' גישות AU) כאשר 10% מהחיפושים לא מוצאים רשומות(יש להתעלם מזמן עיבוד פקודה).

כמות רשומות בAU 8k\270 11.37

11 רשומות בAU אחד

120000\11 =10909.1

P(1+b)/2+(1-p)*b=0.9(1+10909)/2+0.1*10909=6000.95

6001 גישות בממוצע עבור רשימה אקראית בקובץ הנתון.

ב.בהנחה שהקובץ ממוין מהו זמן חיפוש ממוצע של רשומה בחיפוש בינארי.

נניח שהקובץ ממוייין .

נוסחא לזמן ממוצע :

X=log2(N-1)

n-number of Au

מסעיף קודם

N= מספר רשומות בAU 10910

X=log2(10910-1)

3.

קובץ לא ממוין עם הרשומות הבאות (משמאל לימין):

14, 25, 8, 12, 13, 9, 5, 11, 18, 10, 17, 20, 21, 7, 16

א.יש למיין קובץ בשיטת Natural order sort

ב.כמה מיזוגים יש לבצע.

איך עושים את זה ?

ממסמנים את הקטעים הממויינים בשתי הטורים

את הקטעים האי זוגיים שמים בראשון את הקטעים הזוגיים שמים בשני .

שלב שני :

לוקחים את הקטע הראשון בשתי הקבצים ממינים שמים בראשון את הקטע השני בשני הקבצים שמים בשני וכך אלה עד שמקבלים שתי קטעים ממויינים.

ואז ממיינים אותם לפי גודל