ארכיון עבור הקטגוריה קוד פתוח
נכתב על ידי עמרי בנושא אבטחה, קוד פתוח
אחת התוכנות הפופולאריות ביותר לניהול רשימות תפוצה היא mailman.
היום קיבלתי תזכורת מאחת מרשימות התפוצה אליהן אני רשום שאני רשום אליה, ובתזכורת היתה הסיסמא איתה נרשמתי.
מי שקרא את הפוסט על התורכים, זוכר מה זה אומר:
מיילמן שומר את הסיסמא כטקסט נקי.
חיפוש קצר בגוגל הוביל לזה: באג במיילמן מ2006 (!) שלאחרונה זכה לקצת התייחסות, הכרה מצד מפתחי מיילמן שזו בעיה שתתוקן בגרסא הבאה.
לא ממש מוסיף כבוד להילת האבטחה המוגברת של מוצרי קוד פתוח, באג טיוויאלי וחשוב כזה זוכה להתעלמות במשך ארבע שנים.
הבאג הוא כל כך ישן שגם שכבר תצא הגרסא הבאה רוב המשתמשים לא יטרחו לשדרג כי הם אפילו לא יזכרו שהם התקינו את מיילמן.
בכל מקרה, המשמעות של זה היא שהסיסמאות שנתתם לרשימות התפוצה בסכנת חשיפה גבוהה. הדבר הזה מדגיש את החשיבות של פתרון כמו LastPass או KeePass שיאפשרו שימוש בסיסמאות אקראיות לכל שרות.
 7 תגובות »
מפתח הולנדי חובב פיתח בזמנו הפנוי במהלך סוף שבוע תוכנה דמוית שזאם למציאת מוסיקה שמבוססת על ניתוח תדר של הקול, יצירת חתימה פשוטה של חלונות בזמן וחיפוש של התאמות.
הוא פירסם את זה בבלוג שלו, וזכה לאיומים מרומזים מהחברה שפיתחה את שזאם בטענות שהוא מפר את הפטנט שלהם ובדרישה שלא יפרסם קוד ואפילו – תחזיקו – ימחק את הפוסט כי הוא “זמין למשתמשים בין לאומיים ועלול לשמש להפרת הפטנט”.
ספציפית, אני מניח שהם מתכוונים שהוא זמין לאמריקאים (יש להם פטנט בארצות הברית).
הבנתם?
הבחור פיתח אב טיפוס בסוף שבוע, והבהיל את החברה כל כך עד שהם החליטו להפחיד אותו ולמנוע ממנו לפרסם את הקוד.
דעתכם?
10 תגובות »
נכתב על ידי עמרי בנושא לינוקס, קוד פתוח
קרה לכם פעם שניסית להפעיל תוכנת לינוקס שקומפלה במערכת 32 ביט במערכת 64 ביט?
מעבדים מודרניים מסוגלים להריץ קוד 32 ביט וקוד 64 ביט בלי בעיה, אבל התוכנית דורשת ספריות 32 ביט שפשוט לא זמינות במערכת המארחת. גם אם ניסיתם להתקין את הספריות הרלוונטיות, התוכנה סרבה ‘למצוא’ את הספריות, כי היא מחפשת גרסאת 32 ביט והתקנת גירסאת 64 ביט.
יש טריקים של התקנה של ספריות 32 במערכת 64 ביט, למשל חבילת ia-32, אבל רק חלק קטן מהספריות מגיעות באריזה כזו.
דבר אחד לעשות זה לנסות לקמפל את התוכנה ב64 ביט, אבל לפעמים זה לא אפשרי – בין אם כי הקוד של התוכנה לא זמין או כי מסיבות אלו או אחרות היא לא מתקמפלת ב64 ביט או אולי מתקמפלת אבל לא עובדת).
אז מה אפשר לעשות?
יש בלינוקס פקודה בשם chroot, עם דף man קצר במיוחד.
NAME
chroot – run command or interactive shell with special root directory
SYNOPSIS
chroot NEWROOT [COMMAND [ARG]…]
chroot OPTION הפקודה משתמשת בקריאת המערכת chroot, שמשנה את ספרית השורש של התהליך שקורא לה לספריה חדשה.
אחרי chroot, מערכת הקבצים הרגילה מוסתרת וכל מה שהתהליך רואה זה את הקבצים והספריות שבתוך הספריה שניתנה לפקודה כפרמטר.
אחד השימושים הנפוצים (והמפוקפקים למדי) לchroot הוא להשתמש בה כדי לכלוא משתמש / תהליך בספריה מסויימת כדי למנוע ממנו גישה לשאר המערכת.
לא בשימוש הזה אני רוצה להתמקד.
נחזור לדוגמא של תוכנית 32 במערכת 64 ביט.
אפשר ליצור מערכת 32 ביט בספריה מסויימת, עם כל הספריות הדרושות – כולן ב32 ביט ולהריץ את התוכנית הסוררת – והיא תעבוד בלי בעיה.
יש פקודה נפלאה בדביאן בשם debootstrap, שלמעשה מסוגלת ליצור לנו מערכת דביאן מינימלית בארכיטרקטורה שנרצה (i386 במקרה הזה) ומהגרסא שנרצה – נניח stable.
$ mkdir stable-i386
$ sudo debootstrap –arch i386 stable stable-i386/
I: Retrieving Release
I: Retrieving Packages
I: Validating Packages
…
I: Base system installed successfully.
בסוף התהליך יהיה לכם דביאן קטן ורזה למדי בתוך אותה ספריה (בסדר גודל של 200 מגה-בייט).
כדי שהוא יעבוד באמת כדאי לתת לו גישה לספריות dev וproc, ואת זה נעשה בעזרת פקודת mount עם פרמטר bind:
$ sudo mount –bind /dev stable-i386/dev
$ sudo mount –bind /proc stable-i386/proc
אפשר כמובן להוסיף את הפקודות לfstab כדי שהן יורצו אוטומטית בעליה של המחשב.
/dev /stable-i386/dev none bind 0 2
/proc /stable-i386/proc none bind 0 2
יש מי שעושים bind גם לספרית הבית שלהם, כדי שאותם קבצים יהיו זמינים (זהירות עם זה, אם אתם מוחקים את הstable-i386 אחרי שעשיתם את זה הוא יעיף לכם גם את ספריית הבית).
בכל מקרה, אחרי כל זה אפשר פשוט להריץ chroot כדי להכנס “למערכת” החדשה:
שימו לב שקצת קשה לדעת שאנחנו אכן בפנים, אפשר לבדוק שהקבצים מסביב הם לא מה שאתם רגילים לראות.
בדביאן יש טריק חביב, צרו קובץ debian_chroot בתוך etc, שימו בתוכו את השם של הchroot ומהלוגין הבא השם יופיע במקום בולט ונוח:
omry@falcon:~$ sudo chroot stable-i386/
root@falcon:/#
root@falcon:/# echo “i386 stable” > /etc/debian_chroot
root@falcon:/# bash
(i386 stable)root@falcon:/#
בתוך הchroot אפשר להתפרע ולהריץ מה שרוצים, למשל apt-get כדי להתקין חבילות כאוות נפשכם.
אחד הדברים המעניינים ביותר הוא שכל העניין הזה מאפשר להריץ הפצת לינוקס אחת בתוך הפצת לינוקס אחרת.
לאחרונה נאלצתי לעבוד עם Centos 64bit, שהיא הפצה מבוססת רד-האט ועובדת עם חבילות rpm.
המשימה היתה להריץ תוכנה שנבנתה ונבדקה בדביאן בגרסאת 32 ביט, וההתקנה שלה הכילה כעשרה קבצי deb שיצרתי בעצמי מספריות בגרסאות שונות ומשונות (ולפעמים כוללת שינויים שלי).
במקום ליצור קבצי rpm מקבילים, פשוט התקנתי chroot של דביאן 32 ביט (אם מדברים על שתי ציפורים במכה אחת), ופשוט התקנתי את הdebים בפנים כאילו זה דביאן למהדרין.
נתקלתי בבאג בודד שנבע מכך שהקרנל של אותה גרסאת Centos היה ישן יותר מזה של הדביאן ואחת מקריאות המערכת (mmap) השתנתה בין הגרסאות בצורה שגרמה לקוד שעבד בגרסא החדשה של הקרנל לקרוס בגרסא הישנה, אבל שינוי קטן בתוכנה שלי פתר את הבאג.
אגב:
הפוסט הזה לא יהיה שלם בלי להזכיר את schroot שמאפשר גם למשתמשים שאינם root להשתמש בchroot, ובגדול הוא הרבה יותר נוח מאשר שימוש ישיר בchroot.
9 תגובות »
לפני כשנה ארגנתי לי מכונת אחסון ביתית שמריצה OpenSolaris (להלן Iron, או איירון).
איירון מכיל היום שישה דיסקים בגדלים שונים (בתצורת MIRROR, ככה שאני מקבל חצי מנפח האחסון נטו).
בהתחלה השתמשתי במכונה בתור כונן גדול לאחסון סרטים ומוסיקה (גדול מאוד, נטו 4TB וכאמור כל ביט כתוב על שני דיסקים), אבל עוד מההתחלה היו לי מחשבות על אחסון של ספריית הבית שלי על המכונה הזו כדי להרוויח מהירות שרידות וגיבויים נוחים ויעילים (הכל בחסות ZFS).
מכיוון שהדיסקים החדשים יותר שלי נמצאים באיירון המחשב הראשי שלי זכה לקבל שני דיסקים ישנים למדי, של 200GB ו500GB.
על הדיסק של ה200GB מותקנת חלונות 7 שמשמשת אותי למשחקים, ועל הדיסק של ה500 מותקן דביאן לינוקס (Squeeze) שמשמש לכל השאר.
לאחרונה התחילו לצוץ רמזים שהמצב של הדיסקים האלו די ירוד – bad sectors (מגזרים רעים!), שגיאות קריאה וסריקה (seek) אקראיות, תקיעות אקראיות וכו’.
הצעד הטבעי במצב כזה הוא לקנות דיסקים חלופיים, אבל זה די בזבוז לקנות דיסקים חדשים כשיש כל כך הרבה מקום איכותי מהיר ופנוי על איירון.
אז התחלתי לחשוב על האפשרות של איתחול דרך הרשת לשתי מערכות ההפעלה על המחשב הראשי.
מחשבים מודרניים תומכים באיתחל רשת דרך PXE (פיקסי).
מילה מקדימה:
כמעט את כל הבדיקות והמשחקים להלן ביצעתי תוך שימוש בVirtualBox.
ווירצ’ואל בוקס תומך היטב באיתחול פיקסי. כדי לעשות את זה צריך לשנות את הגדרות המכונה הוירטואלית לאיתחול מהרשת.
בנוסף, אם אתם משתמשים כמוני בשרת DHCP ברשת האמיתית, חשוב לשנות את הגדרות כרטיס הרשת של המכונה הוירטואלית למצב Bridged (ברירת המחדל היא NAT) אחרת זה לא יעבוד.
כדי לאפשר למחשבים לבצע איתחול דרך פיקסי צריך את הרכיבים הבאים:
- שרת DHCP – שמעביר אוטומטית למחשב הגדרות רשת ופרמטרים לפיקסי.
- שרת TFTP – שמכיל קבצים שמשמשים את תהליך האתחול. TFTP זה קיצור פרוטוקול טריויאלי להעברת קבצים, והוא מאוד פרימיטיבי ואיטי – אבל מספיק בשביל להתניע את התהליך.
שרת הDHCP צריך לתמוך בכל מני אופציות מתקדמות, לכן לא סביר שהDHCP שמגיע עם הנתב האלחוטי הביתי שלכם יתאים לצורך העניין.
בגדול, הDHCP צריך להכיל שני פרמטרים:
- TFTPsrvN : שמכיל את השם או כתובת הIP של המחשב שמריץ את שרת הTFTP
- BootFile : שמכיל את השם של קובץ ההפעלה הראשי שמתחיל את תהליך האתחול, ונמצא בתוך ספרית השורש של שרת הTFTP.
התהליך הוא כזה:
המחשב מבצע איתחול ומחפש ברשת שרת DHCP שיספר לו מה שרת הTFTP ואיזה קובץ למשוך ממנו, ברגע שהוא מקבל הוא מתחבר לשרת הTFTP, מושך את קובץ ההפעלה ומפעיל אותו.
הקובץ הזה מכיל טוען בוט מיוחד. יש כמה אפשרויות ולמעשה אני עדיין מתנסה בעניין.
מכיוון שאני מתכוון להשתמש במכונת הOpenSolaris לשמירת הקבצים, זה טבעי שאני אשתמש בה גם בשביל שרתי הDHCP והTFTP.
שרת הDHCP הנפוץ ביותר הוא ISC DHCP ואולי כדאי לבחור בו כי רוב הדוגמאות שתמצאו ברשת לגבי הגדרת PXE יתאימו לשרת הזה.
אני החלטתי להשתמש בשרת הDHCP שמגיע עם OpenSolaris, יש הוראות התקנה וקינפוג בסיסיות כאן.
מה שחסר זה שם זה איך מגדירים את TFTsrvN ואת BootFile:
ככה אני עשיתי את זה:
pfexec dhtadm -M -m `hostname` -e BootFile=pxelinux.0
pfexec dhtadm -M -m `hostname` -e TFTPsrvN=10.0.0.4
אפשר גם להשתמש בכלי הגרפי dhcpmgr שיפתח ממשק משתמש שיאפשר שינוים בהגדרות שרת הDHCP.
טועני בוט
לדעתי הטוען בוט הפופולרי יותר הוא pxelinux שהוא למעשה גרסא מיוחדת של syslinux.
כדי לעבוד עם פיקסילינוקס, צריך לשים את pxelinux.0 בספריית השורש של שרת הtftp (בדרך כלל /tftpboot).
כשפיקסילינוקס עולה, הוא מחפש קבצי הגדרות שמתאימות למחשב לפי סדר הגיוני למדי : קודם קובץ בשם של כתובת הMAC של המחשב, ואז בשם של כתובת הIP, ואז חלק יותר קטן מכתובת הIP וכו’ ולבסוף קובץ השם default שיטען אם לא נמצא קובץ הגדרות יותר ספציפי.
פיקסילינוקס תומך במעין תפריט בוט פשוט, למשל:
LABEL sbm
KERNEL memdisk
APPEND initrd=sbm.bin
LABEL local
LOCALBOOT 0 עם התפריט הבא, פיקסילינוקס יציג לנו propmt שבו נוכל להקליד local כדי להמשיך לבוט מקומי או sbm כדי לטעון את Smart boot manager (אפשר למצוא את sbm.bin פה.
דבר אחד שחסר לפיקסילינוקס הוא תמיכה בboot מכונן iscsi.
iscsi הוא פרוטוקול תקשורת שמאפשר שימוש בדיסק מרוחק כאילו הוא דיסק סקאזי מקומי.
מסתבר שפרוייקט אחר בשם gpxe (הידוע גם כ Etherboot) תומך בבוט מiscsi, ואפילו בבוט מhttp, ftp ועוד.
מסתבר עוד, שיש מעין הכלאה של pxelinux ושל gpxe שמאפשרת את היכולות של pxelinux וגם את היכולות של gpxe, ההכלאה נקראת gpxelinux (איזו הפתעה) והיא כלולה בהורדה של pxelinux.
כדי להשתמש בgpxelinux, צריך לקבוע בשרת הDHCP שקובץ הבוט הוא gpxelinux.0, שאר העבודה בדיוק כמו עם פיקסילינוקס.
על ISCSI
לISCSI יש טרמינולוגיה די מעצבנת:
- Logical unit : המקבילה לדיסק או מחיצה
- LUN : המספר של הלוג’יקל יוניט
- Target : מעין מזהה שמגדיר גישה לאחד או יותר יחידות לוגיות, נראה ככה למשל : iqn.1986-03.com.sun:02:2775db99-0772-6e28-bb0e-bcbe420894ee
- Initiator : הלקוח, קוד ששולח בקשות IO בפרוטוקול iscsi.
אפשר להרים שרת iscsi גם עם לינוקס כמובן, אבל אני משתמש באופן סולאריס בתור מערכת האחסון שלי.
לאופן-סולאריס יש ארכיטקטורה חדשה לiscsi שנקראת Comstar, קומסטר תומך גם בעוד פרוטוקולים כמו ערוץ אופטי (FC) אבל זה לא מעניין אותנו.
יש פה פוסט די טוב שמתאר שימוש בסיסי בקומסטר כדי ליצור iscsi target.
מה שחסר זה שצריך בהתחלה להתקין את stmf ולעשות ריבוט אם זה לא עובד (כן, ריבוט – יש על זה באג פתוח).
pkg install SUNWstmf
שימו לב שבדוגמא שם הוא מתאר איך ליצור מיפוי שבו כל היחידות הלוגיות זמינות דרך כל הtargetים. אם אתם רוצים משהו יותר מורכב מזה תקראו את התיעוד, ספציפית את הדף הזה.
ברגע שהגדרתם target בהצלחה, נשאר לבדוק אותו.
זה די פשוט גם בחלונות 7 או וויסטה וגם בלינוקס. חפשו קצת בגוגל.
לגבי התקנות ואיתחול של של מערכות הפעלה ספציפיות על iscsi, יש תיעוד לרוב בוויקי של Etherboot .
עדיין לא הצלחתי להגיע לבוט מלא של חלונות 7 או דביאן דרך הרשת, אבל אני מקווה להצליח בקרוב.
צפו לפוסט עדכון לגבי איך ומה עושים לגבי כל אחת מהמערכות כדי להגיע לאיתחול מISCSI. (אלא אם אני אכשל ואז צפו לשקט חשוד).
אם הפוסט הזה עשה לכם תיאבון לנסות, קחו בחשבון שתצטרכו ללמוד הרבה דברים, ואולי תיתקעו בדרך.
זה לא פשוט, וזה לוקח די הרבה זמן להבין את הכל.
פוסטים קשורים:
מכונת אחסון ביתית על אופן-סולאריס
אופן סולאריס: תצורה, שיתוף קבצים וגיבויים
שידרוג נפח אכסון ZFS על גבי OpenSolaris
6 תגובות »
זליגת זכרון היא אחד הבאגים החמקמקים ביותר, ממש הרוצח השקט של תוכנות מחשב.
לא משנה באיזה שפה אתם כותבים, לא קשה במיוחד לכתוב קוד שידלוף כמסננת (אם כי זליגות זכרון בשפות מנוהלות כמו ג’אווה ו#C הן בעלות מאפיינים שונים לגמרי מזליגות זכרון בשפות בהן המתכנת אחראי על ניהול הזכרון ואין איסוף זבל אוטומטי).
כל משתמש מנוסה מכיר את התופעה המציקה, שתוכנה עובדת מהר בהתחלה ואחרי פרק זמן לא קבוע היא מתחילה להאט ולהאט עד כדי זחילה.
לפעמים היא מצליחה להאט את כל המחשב על הדרך, אם היא זולגת כמויות זכרון שגורמות למחשב להתחיל להשתמש בצורה מופרזת בקובץ הSWAP.
בניגוד להרבה בעיות תכנות אחרות, המתכנת לא מקבל אזהרה או שגיאה כאשר הוא כותב באג של זליגת זכרון, התוכנה לא קורסת מייד כמו למשל בגישה לזכרון דרך מצביע לNULL בC או בC++, והקומפיילר לא יספר למתכנת על הטעות שהוא עשה.
הסיבה לכך היא לא שמפתחי הקומפיילרים הם עצלים מכדי לכתוב קוד שמוצא את הבעיה – אלא שפשוט לא ניתן לכתוב קוד שיזהה זליגת זכרון בכל המקרים בצורה סטטית (על בסיס הקוד הכתוב בלבד).
הדוגמא הפשוטה ביותר היא תוכנית שמקצה ומשחררת זכרון על פי בקשת המשתמש (לאו דווקא במונחים האלו, המשתמש יכול לבקש לפתוח קובץ ובתגובה התוכנה תקצה זכרון בגודל הקובץ ותטען את הקובץ פנימה). אם התוכנה עובדת ישירות עם הזכרון אז הקומפיילר לא יכול להבטיח שהזכרון שיוקצה בשלב מסויים גם ישוחרר – ולו כי זה יקרה רק אם המשתמש יבקש את זה.
אז מה הבעיה עם זליגת זכרון?
הבעיה הראשונה והטריויאלית ביותר היא שתוכנה שזולגת משתמשת ביותר זכרון ממה שהיא צריכה, והמצב מחמיר בהדרגה ככל שאותו קוד שזולג רץ יותר. תוכנה שצורכת יותר מדי זכרון היא לא בהכרח בעיה חמורה. למעשה – כמעט כל תוכנה ברמת מורכבות בינונית ומעלה שנכתבה בשפת C או C++ זולגת זכרון כאילו אין מחר, ובדרך כלל זה לא גורם בעיות כי המשתמש סוגר את התוכנה לפני שהיא מגיע למצב של חוסר זכרון.
הבעיה הזו היא קצת יותר חמור משנדמה במבט ראשון:
כאשר המתכנת מבקש להקצות זכרון, נניח 1MB, הוא מצפה לקבל 1MB של זכרון רציף, שאפשר לעבור עליו בלולאה אחת מתחילתו ועד סופו.
דמיינו מערכת עם 2 מגה זכרון שעומדים לרשות תוכנה שרצה שם, מספיק לכאורה להקצות 2 בלוקים של 1MB.
עכשיו, אם נקצה סך הכל של 1K זכרון, ניתן להניח שנוכל להקצות עוד 1999K ובוודאי שנוכל להקצות 1MB, נכון?
אז זהו – שלא בדיוק : אם נקצה את ה1K בארבע בלוקים של 250 בתים, ובהפרשים של כ500K, למעשה נמנע מהתוכנה אפשרות לקבל זכרון רציף של יותר מכ500K.
כלומר, למרות שהזכרון הפנוי מספיק – בפועל הזכרון הפנוי שבור לחתיכות קטנות מדי (Fragmented), ואין לנו יכולת להקצות את הזכרון הדרוש.
מכאן אפשר להסיק שגם דליפת זכרון קטנה עלולה במצבים מסויימים לגרום לחוסר זכרון קריטי.
אני מקווה שזה שיכנע אתכם שדליפת זכרון זה דבר רע שראוי לטפל בו.
כל מתכנת מתחיל יודע שלשפות מודרניות יש איסוף זבל אוטומטי שאמור למנוע זליגת זכרון.
יש פה כמה בעיות, קודם כל – למרות שלרוב השפות יש איסוף זבל אוטומטי, ברוב המקרים מדובר בזבל של איסוף זבל, ואם להיות פחות ציורי ויותר ספציפי – מדובר בקוד איטי ודי מוגבל, שלא תופס את כל המקרים.
אבל אם נסתכל בג’אווה וב#C (שאני מניח שיש לה איסוף זבל בקליבר דומה לזה של ג’אווה) – הן בהחלט מסוגלות לאסוף את הזבל במהירות וביעילות.
הבעיה היא שההגדרה של זבל הוא אובייקט שהוקצה ואין אליו התייחסות משום מקום (Reference), ולפעמים המתכנת לא מבחין שבעצם יש אליו התייחסות.
למשל, קוד הג’אווה הטריואלי הבא ירוץ עד שיעוף עקב חוסר זכרון:
import java.util.HashSet;
import java.util.Set;
public class a {
public static void main(String[] args) {
Set<String> s = new HashSet<String>();
int a = 0;
while(true)
s.add(String.valueOf(a++));
}
}
די ברור למה.
זו הכוונה בדליפת זכרון בשפות עם איסוף זבל אוטומטי. הבעיה היא שבדרך כלל הרבה יותר קשה מזה לראות את הבעיה.
בשפות עם ניהול זכרון ישיר יש מגוון רחב בהרבה של שגיאות שקשורות לזכרון, החל מזכרון שמוקצה ולא משוחרר, זכרון שמשוחרר פעמיים, זכרון שמוקצה עם Malloc של C ומשוחרר עם delete של C++, כתיבה או קריאה אל מחוץ לגבולות הזכרון שהוקצה ועוד ועוד.
הנה תוכנית C++ קטנה שמדגימה חלק מהשגיאות האפשריות:
#include <stdlib.h>
char* get1(){
return new char[10];
}
char* get2(){
return (char*)malloc(sizeof(char)*10);
}
char* get3(){
static char c[10];
return c;
}
int main() {
char *s1 = get1();
char *s2 = get2();
char *s3 = get3();
s1[11] = ‘x’; // out of bounds access. mistake
free(s1); // mistake, should be delete[]
delete s2; // mistake should be free
delete s3; // mistake, should not be freed or deleted
char *s4 = new char[10];
delete s4; // mistake, should delete with delete[] and not with delete.
delete s4; // mistake, deleted twice.
char *s5 = new char[10]; // mistake, never deleted
return 0;
}
כמו תמיד, C++ נותנת הרבה יותר חבל למתכנת התמים שרוצה לתלות את אח של אח שלו על עץ.
למעשה רק השגיאה האחרונה היא ממש זליגת זכרון, אבל כל השגיאות נפוצות וקשורות לזכרון.
יש טכניקות ידועות ומקובלות שמקטינות מאוד את הסבירות לטעויות שקשורות להקצאה ושחרור זכרון, ספציפית יש טכניקה שמוזכרת בספר The C++ programming language של סטראוסטרופ שנקראת Resource Acquisition Is Initialization או RAII בקיצור.
RAII הוא נושא שראוי לפוסט שלם בפני עצמו, אבל הנה דוגמת שימוש פשוטה (מדי, יש בה לא מעט חורים):
void direct_test(){
char *buffer = new char[100];
try{
work(buffer);
delete[] buffer;
}
catch(…){
delete[] buffer;
throw;
}
}
הקוד למעלה מקצה זכרון, וקורא לפונקציה שעובדת עליו. לבסוף הוא משחרר את הזכרון וגם דואג שהוא ישוחרר כראוי אם הפונקציה תזרוק אקספשן.
התבנית הזו של טיפול ידני בשגיאות היא מאוד בעייתית ומועדת לטעויות.
אם היינו משתמשים בRAII, יכלנו להגדיר מחלקה בשם Buffer, שתדאג לשחרור ולהקצאה:
class Buffer {
char *buffer;
size_t size;
public:
Buffer(int size){
buffer = new char[size];
}
~Buffer(){
delete[] buffer;
}
char *get() {return buffer;}
};
void raii_test(){
Buffer buffer(100); // 100 bytes allocated in constructor
work(buffer.get());
// automatically freed when buffer destructor is called (will be called even if an exception is thrown).
}
אפשר לראות שהקוד שמשתמש בזכרון הוא הרבה יותר פשוט עכשיו.
מצד שני, יש מספר לא מבוטל של באגים בדוגמא הזו (למשל, כשמעתיקים את buffer הזכרון שהוקצה ישוחרר פעמיים). כדי שזה באמת יעבוד צריך לדאוג לבנאי העתקה, אופרטור הצבה וכו’.
כל מתכנת C++ רציני חייב להכיר את הטכניקה הזו, שתחסוך לו שערות לבנות רבות מאוד.
אבל לפעמים אין ברירה וחייבים להשתמש בזכרון ישירות, בדרך כלל כאשר עובדים עם ספריות שכתובות ככה-ככה, או עם קוד אחר שנכתב על ידי מישהו שעדיין לא ראה את האור.
עוד דבר – בC לא אין אפשרות אמיתית להשתמש בRAII כי השפה לא מספיק עשירה, ולכן מתכנתים שכותבים בC אמיתי (ולא C+) לא יכולים להנות מהטכניקה הזו.
אחד הכלים החזקים ביותר לזיהוי בעיות שקשורות לעבודה עם זכרון הוא valgrind.
ואלגרינד הוא למעשה קבוצה של כלים, כשהידוע בהם הוא memcheck שבמגלה שגיאות בעבודה עם זכרון.
הוא כולל כלים אחרים לניתוח ביצועים (cachegrind, callgrind) ועוד.
ואלגרינד עובד על רוב מערכות ההפעלה ממשפחת היוניקסים (BSD, Linux, MacOS X וכו’), בתאוריה אפשר לבדוק איתו תוכנות חלונות דרך WINE.
ואלגרינד עובד בשורת הפקודה, מה שמרתיע משתמשים רבים. לאחרונה חיפשתי ומצאתי פתרון שמאפשר אינטגרציה של ולגרינד עם CDT:
התמיכה היא כחלק מפרוייקט בשם LinuxTools שמפותח על ידי RedHat (כנראה).
יש פה דמו וידאו של השימוש בפלאגין.
קובץ הוידאו נמצא כאן למי שלא מצליח לראות אותו בבלוג (דורש פיירפוקס 3.5 או דפדפן שתומך בתג וידאו).
כדי למצוא זליגות זכרון בג’אווה, אני משתמש בJProfiler. למרות שהוא מסחרי – הוא מומלץ מאוד למפתחי ג’אווה (אפשר להוריד גרסאת נסיון לשבועיים כמדומני, ובתום השבועיים להוריד אותה שוב..).
JProfiler הוא כלי מאוד עשיר שמאפשר ניתוח ביצועים, זכרון, ביצועי סינכרון ת’רדים ועוד.
שווה להסתכל על סרטוני הוידאו לפני שמשתמשים בו, כדי להפיק ממנו את מירב התועלת.
17 תגובות »
לפני קצת יוצר מחצי שנה קניתי מכונת אכסון, כשהתוכנית היתה להריץ עליה אופן סולאריס כדי להנות מפירות הZFS.
נהנתי מאוד, עד שהתחלתי להרגיש שקצת צפוף לי, אז החלטתי להרחיב את נפח האכסון.
מכיוון שהתצורה של הדיסקים דומה לRAID10 – גם MIRROR וגם STRIP, כל הרחבה צריכה לבוא בזוגות.
קניתי שני דיסקים של של סיגייט, בנפח של 2TB כל אחד, ובפוסט זה אתאר את התהליך של השדרוג.
אחרי הקטע המלכלך של לחבר את הדיסקים, הרצתי את הפקודה הבאה:
root@iron:~# zpool add storage mirror c10d0 c11d0
זהו, השדרוג הסתיים.
הפקודה הזו אומרת, תוסיף לבריכת האיכסון שנקראת storage יחידה וירטואלית חדשה מסוג ראי, שבנויה מהדיסקים c10d0 וc11d0.
הפקודה לקחה שניה, ובתום השניה נוספו לי כ2TB נלנפח האכסון במכונה. לא צריך fdisk ולא צריך לפרמט.
ככה נראה הpool הראשי שלי כרגע, הוא מורכב מארבעה דיסקים מלאים ומשתי מחיצות שתופסות את רוב הנפח של שני הדיסקים הנותרים.
למעשה, אין לי מקום לעוד דיסקים במכונה, מה שאומר שבשדרוג הבא אני אעשה משהו שעדיין לא יצא לי לעשות: להחליף דיסקים קטנים בדיסקים יותר גדולים.
root@iron:~ # zpool status storage
pool: storage
state: ONLINE
scrub: none requested
config:
NAME STATE READ WRITE CKSUM
storage ONLINE 0 0 0
mirror ONLINE 0 0 0
c8d0p2 ONLINE 0 0 0
c9d0p2 ONLINE 0 0 0
mirror ONLINE 0 0 0
c9d1 ONLINE 0 0 0
c8d1 ONLINE 0 0 0
mirror ONLINE 0 0 0
c10d0 ONLINE 0 0 0
c11d0 ONLINE 0 0 0
ZFS זה כיף.
2 תגובות »
לפני כמה פוסטים שאלתי את השאלה הבאה:
נתון מערך בגודל NxN של פיקסלים כאשר כל הפיקסלים שחורים חוץ מאחוז מסויים מהם שאינו שחור ומפוזר באופן אקראי,
בהינתן קואורדינטה (x,y) מסויימת בתמונה, מצא במהירות את כל הנקודות שנמצאות בתוך חלון בגודל K על K (כאשר K קבוע בבעיה) שמרכזו (x,y), משהו כזה:
פעולת המציאה עצמה צריכה להיות מהירה מאוד, אבל מותר לעבד מראש את התמונה פעם אחת (בזמן סביר).
אז הנה הפתרון שלי:
נחלק את התמונה למשבצות בגודל KxK, ונשמור רשימה של כל הנקודות בכל משבצת.
כאשר מבקשים מאיתנו לתת את רשימת הנקודות בחלון מסויים, נסתכל בארבעת החלונות שהחלון הזה חותך ונסנן את כל הנקודות בארבעת החלונות שלא נמצאות בתוך החלון המבוקש.
זה הכל בעצם.
הביצועים של הפתרון הזה מעולים, כדי להכין את הגריד (Grid) נעבור על כל הפיקסלים בתמונה, ולכל נקודה נמצא בזמן קבוע את המשבצת שאליה היא שייכת.
כשממש מחפשים את הנקודות בחלון מסויים, נבדוק במקרה הגרוע 2K*2K פיקסלים (אם כל הנקודות לבנות) אבל במקרה הרגיל נבדוק הרבה פחות (ואם החלון לא מכיל נקודות כלל נדע את זה מהר מאוד).
זה הקוד של העיבוד המקדים:
private static int [][][] buildgrid (byte[][] image, int width, int height, int gridSize )
{
int grid [][][] = new int[width / gridSize ][height / gridSize ][];
// count the number of points in each grid cell
int numpoints [][] = new int[width / gridSize ][height / gridSize ];
for(int x= 0;x<width;x++ )
{
for(int y= 0;y<height;y++ )
{
if (image [x ][y ] > Byte. MIN_VALUE)
{
numpoints [x/gridSize ][y/gridSize ]++;
}
}
}
for(int x= 0;x<width;x++ )
{
for(int y= 0;y<height;y++ )
{
int c = image [x ][y ];
if (c > Byte. MIN_VALUE)
{
int gy = y/gridSize;
int gx = x/gridSize;
int list [] = grid [gx ][gy ];
if (list == null)
{
int np = numpoints [gx ][gy ];
list = new int[np * 2];
grid [gx ][gy ] = list;
numpoints [gx ][gy ] = 0;
}
list [numpoints [gx ][gy ]++ ] = x;
list [numpoints [gx ][gy ]++ ] = y;
}
}
}
return grid;
}
הקוד הבא סופר את המספר הנקודות בתוך החלון שמרכזו (x,y)’ שימו לב שהלולאות עוברות על ארבעה ריבועים בגריד בלבד:
// window boundaries:
int rx1 = x – grid_size/ 2;
int ry1 = y – grid_size/ 2;
int rx2 = rx1 + grid_size;
int ry2 = ry1 + grid_size;
// top left grid cell (out of 2×2 group to be checked)
int gx = rx1 / grid_size;
int gy = ry1 / grid_size;
for(int grid_x=gx;grid_x<gx+2 && grid_x >= 0 && grid_x < gwidth;grid_x++)
{
for(int grid_y=gy;grid_y<gy+2 && grid_y >= 0 && grid_y < gheight;grid_y++)
{
int list[] = grid[grid_x][grid_y];
if (list == null) continue;
for(int i=0;i<list.length/2;i++)
{
int jj = i*2;
int dx = list[jj];
int dy = list[jj+1];
if (dx >= rx1 && dx < rx2 && dy >= ry1 && dy < ry2)
{
c++;
}
}
}
}
יתכן שאפשר לשפר את הביצועים אם נחלק את הגריד לריבועים יותר קטנים ונכלול ריבועים שלמים שנופלים בתוך החלון בלי לבדוק כל נקודה באופן פרטני, אבל לא ניסיתי.
הביצועים של הפתרון הזה די מטורפים. על Q6600 במהירות 2.4GHZ, עם תמונה בגודל 500X500 פיקסלים וחלון של 20X20, בדיקה של כמה זמן לוקח לספור את הפיקסלים בכל 250,000 החלונות האפשריים לקחה כ160 מילישניות, מה שנותן מהירות בדיקה של מעל 1500 חלונות במילישניה (או יותר ממליון וחצי חלונות בשניה), בלי תלות בגודל התמונה שנבדקת (על תמונה של 1000X1000 המהירות היתה דומה).
האפלט הבאה מדגימה את האלגוריתם. אפשר להוריד אותה מפה. הקוד כלול בתוך הJAR (אפשר לפתוח את הJAR עם תוכנה לפתיחת קבצי ZIP).
בנוסף, האפלט יכולה לרוץ כתוכנית רגילה : java -jar fast_window.jar
אפשר ללחוץ בתוך האפלט כדי לסמן את הנקודות בחלון.
16 תגובות »
נכתב על ידי עמרי בנושא Java, לינוקס, קוד פתוח
לפני כמה שנים טובות עבדתי בסטארטאפ קטן בשם Content Objects שנסגר זה מכבר.
בתקופתי שם פיתחתי ספרית ג’אווה בשם JNotify שמאפשרת קבלת ארועים על שינויים במערכת הקבצים בלינוקס ובחלונות (ואולי עוד בהמשך).
דאגתי שהקוד ישוחרר ברשיון קוד פתוח כפרוייקט סורספורג’.
החברה נסגרה (אחרי שעזבתי), אבל הקוד נשאר. לא ממש תחזקתי אותו, אבל נראה שאנשים השתמשו בו בכל זאת – למרות שהיו כמה בעיות די חמורות בגרסאת החלונות.
כדי לתת מה שהספריה נותנת, חייבים להשתמש בקריאה לפונקציות של מערכת ההפעלה.
בלינוקס העניין היה פשוט יחסית: קטע הקוד המקומי (native code) הוא מינימלי ביותר ומסתמך על inotfiy. הAPI שלו מאוד פשוט אבל הוא לא תומך בהאזנה ריקורסיבית ולכן רוב הקוד כתוב בג’אווה ונועד להוסיף יכולת לקבלת ארועים על ספריות באופן ריקורסיבי (צפיה בתת ספריה על כל בניה).
בחלונות העניין הפוך, קריאת המערכת ReadDirectoryChangesW תומכת בהאזנה ריקוסיבית, אבל השימוש בה מורכב ברמות שלא יאמנו והתיעוד של מייקרוסופט מחורבן ביחס ישר למורכבות הAPI. ולכן על חלונות רוב הקוד כתוב בC++ (כי אין דרך פשוטה להתממשק אל הAPI המקומי מג’אווה) אבל קוד הג’אווה הספציפי לחלונות פשוט מאוד.
מכיוון שהרבה יותר קל לכתוב ולדבג קוד ג’אווה מאשר קוד C++, המימוש ללינוקס היה הרבה יותר יציב מזה של חלונות – שנטה להתרסק או להתקע לעיתים נדירות בכל מני סיטואציות שלא הצלחתי לשחזר.
לפני כמספר שבועות פנה אלי משתמש של הספריה, והציע שאני אפתור בתשלום את הבאגים בגרסאת החלונות.
לאחר משא ומתן קצר הסכמנו על $100, וניסיתי את מזלי.
זה היה די קשה, אבל לבסוף הצלחתי לתקן את הבאגים החמקמקים, ובנוסף לשפר את הביצועים של הספריה כך שלא תפספס אירועים גם על מחשבים חלשים.
אחרי שכמות השעות ההשקעתי בעניין עברה את מה שנראה לי מוצדק בעבור $100 הסכמנו גם להגדיל את הסכום ל$250 והיום שחררתי את הגרסא המתוקנת
$250 זה לא סכום שבאמת מכסה את כמות השעות שהשקעתי בתיקון הבאגים (אם הייתי לוקח סכום סביר לשעה), אבל זה בכל זאת פרוייקט קוד פתוח ואני מרוצה שתיקנתי את הבאגים האלו.
נודע לי מאותו משתמש שמישהו ביצע fork לספריה והוסיף לה תמיכה בMac.
פניתי אליו ונראה שהוא יצטרף לפרוייקט וישלב את התוספת שלו בקוד (שנכתב כך שיהיה קל מאוד להוסיף תמיכה במערכות הפעלה חדשות), ואולי גם יעזור עם באגים אחרים.
JNotify התעורר.
13 תגובות »
נכתב על ידי עמרי בנושא Java, קוד פתוח
עם השנים נוספו לג’אווה כלים סטנדרטיים שמאפשרים חיבור למכונה וירטואלית חיה, ובחינה של מה שקורה שם ככלי למציאת בעיות בזמן הריצה של תוכניות.
- jps : מראה תהליכי ג’אווה
- jstack : מציג את רשימת הת’רדים בתהליך ג’אווה, ומה כל אחד מהם עושה.
- jmap: מאפשר שמירה לקובץ של תמונת הזכרון (heap dump) של תהליך ג’אווה. אפשר לבחון את הקובץ עם jhat או עם VisualVM.
- jhat : מאפשר ניתוח קבצי heap dump שנוצרו בעזרת jmap.
- jconsole : ממשק פשוט שמאפשר בחינה של שימוש הזכרון, שימוש בזמן מעבד ועוד.
- visualvm: כלי חזק יותר מjconsole, שהחל מעדכון 18 של JDK 1.6.0 מגיע עם הJDK. ויז’ואל VM מאפשר גם ניתוח ביצועים פשוט (cpu and memory profiling).
כל הכלים האלו תומכים גם בגישה למכונה מרוחקת בצורה זו או אחרת, הבעיה היא שכמעט בלתי אפשרי להתחבר איתם למכונה שמוגנת בפיירוואל כי הם עובדים עם פורטים אקראיים.
אם עם כלי שורת הפקודה עוד אפשר להסתדר על שרת מרוחק (קל יותר להריץ jps ישירות על השרת מאשר לנסות לעשות את זה מרחוק), עם הכלים הגראפיים הסיפור כבר אחר.
VisualVM
אז איך בכל זאת אפשר להתחבר לתהליך ג’אווה מרוחק עם VisualVM?
התהליך קצת מורכב, ולכן אני אתעד אותו כאן:
על המחשב המרוחק:
1. צרו קובץ permissions.txt שיכיל את זה:
grant {
permission java.security.AllPermission;
};
2. הריצו את jstatd (שמאפשר לתהליכים מרוחקים לקבל רשימה של מכונות ג’אווה שרצות על המכונה ולהתחבר אליהן) :
jstatd -J-Djava.security.policy=permissions.txt
3. הריצו את התוכנית שלהם עם הפרמטר הבא:
java -Dcom.sun.management.jmxremote MainClass
על המחשב המקומי:
1. צרו תעלות SSH לשרת כך:
ssh -D9696 -L1101:localhost:1099 your_server
שימו לב שיש פה שתי ‘תעלות’:
- תעלת TCP מ1101 אל 1099 בשרת המרוחק. זו תעלה שמאפשרת להתחבר אל הjstatd ישירות.
- פרוקסי SOCKS5 שמאזין על פורט 9696
2. הפעילו את visualvm עם הפרמטרים הבאים :
visualvm -J-Dnetbeans.system_socks_proxy=localhost:9696 -J-Djava.net.useSystemProxies=true
שאומרים לו להשתמש בפרוקסי SOCKS5 שהקמנו.
3. מתוך VisualVM, הוסיפו לחיבור המקומי חיבור לjstatd בפורט 1101.
זהו. הרבה יותר מסובך ממה שהייתי רוצה, אם מישהו מכיר דרך יותר פשוטה אני אשמח לשמוע.
2 תגובות »
עבר הרבה זמן מאז שהיה פה פוסט רציני, כל פעם שהיה לי על מה לכתוב זה איך שהוא התמסמס ותוייק בתיקיית האחר כך.
אז זה יהיה פוסט מוזר, מוזר מאוד אפילו – שיהיה בעצם ערמת פוסטים מרוכזים.
אולי במהלך הכתיבה של תת פוסט כזה אני אגלה שאני מעדיף שהוא יהיה בעצם פוסט שלם, אבל נראה.
שרת חדש
הגיעה התקופה הזו, שבה אני פחות מרוצה מההוסיטנג שלי ועברתי להוסיטנג חדש.
למעשה הייתי מרוצה מספיק מeSecureData (אליהם עברתי מHCOOP לפני פחות משנה וחצי).
מהירות התקשורת היתה קצת מאכזבת אבל לא היו יותר מדי תקלות.
אז למה עברתי?
במסגרת העבודה שלי בface.com (כן, אני עובד בface.com, לא חושב שיצא לי להזכיר את זה פה עד עכשיו) אני עובד מול חברת אכסון בשם CentralHost בסן דייגו, ומחזיק אצלם מספר לא מבוטל של שרתים. בשנה וחצי בשנה חצי שאני עובד שם, הייתי מאוד מרוצה מהם ומרמת התמיכה שלהם – אם כי המחיר שלהם הוא גבוה משמעותית מזה של eSecureData, לפחות למכונות החזקות שאני מחזיק שם במסגרת העבודה.
בכל אופן, יש לי יחסים מצויינים עם בעל החברה, וכששאלתי אם יש לו הצעה אלטרנטיבית שתאפשר לי להעביר את השרת שלי אליו הוא הסכים לתת לי מחשב באותו מחיר שאני מקבל בeSecureData – שזה $79 לחודש, עם יותר זכרון (4 ג’יגה במקום 2 ג’יגה), ושני הרדיסקים של 500 בתצורת רייד 1 (ראי, אם הרדיסק אחד מת לא קורה כלום ופשוט מחליפים אותו) לעומת הרדיסק אחד בלבד בשרת הישן.
העברתי בעזרתו את השרת למכונה החדשה, ולמעט שינויי הגדרות קטנים בשרת הDNS שאני מריץ, ובהגדרות הDNS ברשת הדומיינים שלי הכל פשוט עובד.
אני בטוח שיהיו עוד חבלי לידה, אבל אם אתם קוראים את זה, אתם עובדים מול השרת החדש.
אז כמו תמיד, יש לי מקום לאורחים. מי שחושב לעבור שרת למשהו יותר רציני מאיכסון משותף בגודדי שיצור קשר. (רק לאנשים שמרגישים בנוח עם SSH).
BoneCP
השתמשתי בProxool בתור Connection pool לבסיס הנתונים במשך די הרבה זמן, ועם הזמן גיליתי בעיות – שאומנם די נדירות אבל מספיק חמורות כדי שאני אחפש פתרון.
חשבתי לפתור אותן בעצמי, וגיליתי שהוא לא מתקמפל על JDK מודרני. שלחתי מייל לרשימת התפוצה שלו לגבי העניין, וחודשים עברו בלי שום תגובה ובלי הודעות נוספות.
היה ריח של פרוייקט מת באוויר, וכשנתקלתי בבעיה נוספת (100% CPU בקוד של פרוקסול לעיתים נדירות), החלטתי לחפש Connection pool אחד.
בסוף הגעתי לBoneCP שאומנם מוגדר כבטא, אבל עובד היטב – וחשוב יותר – המפתח שלו עונה לאימיילים ומתקן באגים.
טיפוסי אישיות
מי שלמד פסיכולוגיה (לא אני) מכיר את העניין הזה לעומק כנראה, אבל אני מניח שרוב הקוראים פה לא למדו פסיכולוגיה אני אכנס לעניין:
במהלך שיטוטי באינטרנט בחיפוש אחרי ספרייה לDecoding של תמונות בC או C++ (יש מילה בעברית לDecoding? פענוח? פרישה?) נתקלתי בCxImage, וראיתי בדף האודות של המפתח שהוא טוען שהאישיות שלו היא מסוג INTJ.
אני די בטוח שנתקלתי בסוג הקטלוג הזה למחלקות אישיות בעבר, אבל הפעם הסתקרנתי, אם הוא INTJ אז מה אני? וכמה הדבר הזה בכלל עובד?
התחלתי לחקור, מסתבר שמדובר במבחן פסיכומטרי שמבוסס על העבודה של קארל יאנג מ1920 ופותח על ידי קתרין קוק בריגס וביתה איזבל בריגס מיירס, והמבחן קרוי על שמן: Myers-Briggs Type Indicator או MTBI.
בגדול, הרעיון הוא שהאישיות של בני אדם נקבעת על ידי ארבעה תכונות, כאשר לכל תכונה יש שני צדדים (מוחצן – מופנם, חושב – מרגיש) וכו’, ואצל כל אחד תכונה אחת מכל זוג היא יותר דומיננטית מהשניה.
הזוגות הם:
- התנהגות – מוחצן או מפונם : האם רוב המחשבה של האדם מופנית החוצה או פנימה
- תפיסה – חש או אינטואיטיבי : איך האדם קולט מידע חדש, האם הוא סומך יותר על תחושות פנימיות או על מידע קונקרטי
- החלטה – חושב או מרגיש : איך האדם מבצע החלטות רציונליות בניתוח של המידע שהוא קיבל באמצעי התפיסה, האם הוא מעדיף חשיבה וניתוח לוגי או החלטה לפי הרגשה והזדהות עם המצב.
- סיגנון חיים – שיפוטי או תפיסתי : האם האדם מעדיף להשתמש בבהחלטה (חושב/מרגיש) או בתפיסה (חש/אינטואיטיבי) כשהוא מתייחס אל העולם החיצוני.
קצת מבלבל, ואולי התרגום שלי לא מאוד מדוייק (יש הרבה מאוד חומר מדוייק על זה באינטרנט).
סך הכל יש ארבע ‘ביטים’ כשלכל ביט יש שתי אפשרויות, מה שיוצר 16 קומבינציות.
מצאתי מבחן עם כ-70 שאלות כן/לא שמוצא את הטיפוס שלכם, וקיבלתי שגם אני INTJ.
קראתי קצת על INTJ, ונראה שלפחות לגבי – המבחן יצא מאוד מדוייק.
בעיית החלוקה
שוב ושוב אני נתקל בבעיה הבאה:
בהנתן קבוצת מספרים, איך מחלקים אותה לשתי קבוצות כך שסכום המספרים בכל קבוצה יהיה קרוב ככל האפשר לסכום המספרים בקבוצה השניה.
במילים אחרות, שאף קבוצה לא תהיה ‘כבדה’ הרבה יותר מהשניה בצורה שניתנת לתיקון על ידי סידור מחדש של האיברים בקבוצות.
הרחבה טבעית של השאלה הזו, היא איך מחלקים את הקבוצה לk קבוצות, לאו דווקא רק לשתיים.
הנה כמה דוגמאות למצבים שבהם אלגוריתם כזה יהיה שימושי:
דמיינו משחק מרובה משתתפים שעובד בסיבובים. בכל סיבוב יש שתי קבוצות שנלחמות אחת בשניה. חלוקה אקראית של השחקנים לשתי קבוצות תגרום למצב שבו כל השחקנים החזקים נופלים בקבוצה אחת ואז המשחק לא יהיה מהנה במיוחד לאף אחת מהקבוצות.
חלוקה אידיאלית תהיה כזו שההפרש בין סכומי היכולת בכל קבוצה יהיה נמוך (קבוצות מאוזנות). נניח שיש לנו מדד ליכולת של שחקן (יחס נצחונות/הפסדים ב20 המשחקים האחרונים, או דרגה או כל דבר אחר) נוכל להשתמש באלגוריתם חלוקה כזה כדי למצוא חלוקה טובה של הקבוצות.
דוגמא נוספת: נניח שיש לכם ערמת עבודות, וכמה מחשבים שיכולים לבצע את העבודות. איך תחלקו את העבודות בין המחשבים כך שעבודות יסתיימו בהקדם? אם אחד המחשבים יקבל את כל העבודות הכבדות אז הוא יסיים הרבה אחרי כולם, אז שוב אנחנו מחפשים חלוקה מאוזנת (הפעם לk מחשבים).
אוקיי, עכשיו שמצאנו למה פתרון לבעיה הזה יהיה שימושי, תחשבו על הבעיה ואם יש לכם פתרון נדבר עליו בתגובות.
אני אדבר על הפתרון שלי בפוסט הבא.
10 תגובות »
|
רסיסים (RSS)