وبلاگ میثم پاسداری هریس

۱۰ مطلب با موضوع «علمی» ثبت شده است

  • ۰
  • ۰

استادی داریم که خیلی علاقه مند به مباحث سیستمی هست، حتی به قول یکی از دوستان عطسه هاش هم سیستمیه!
یه مقاله خوبی رو تو حوزه System design معرفی کرده، به نظر جالب میاد، گفتم بذارم، قدیمیه اما پیشنهادم اینه یه نگاه بندازید بهش، دوست داشتید نقدهایی (Critical review) هم که بهش شده رو بخونید


از اینجا دانلود کنید

  • میثم پاسداری
  • ۰
  • ۰

چرخه تولید نرم افزار

why is software so expensive? an explanation to the hardware designer عنوان کامل مقاله ای است که آقای دیجسترا (+لینک) آن را نوشته است و یکی از مقالاتی هست که تمرکزش بر روی بررسی مسائل و شباهت ها و تفاوت های دو حوزه مهندسی نرم افزار و مهندسی سخت افزار است. آقای دیجسترا توی این مقاله صراحتا به سختی های حوزه نرم افزار اشاره می کند و گران بودن آن را به نوعی با سختی هایی که دارد توجیه می کند...


" !The Hardware Designer's Target is the Programmer's Starting Point "


یک خلاصه یک صفحه از این مقاله آماده کردم که همینجا در کنار مقاله اصلی قرار می دهم.

مقاله اصلی (+دانلود)

خلاصه یک صفحه ای از مقاله (+ دانلود)


مقاله شاید از لحاظ سنی از بعضی از ماها بزرگ تر باشد اما ارزش خوندن دارد.

  • میثم پاسداری
  • ۱
  • ۰

تراکنش (Transaction) به فرآیندی که در پایگاه داده بر روی داده ها صورت می گیرد گفته می شود. تراکنش ها در پایگاه داده ها را رفتار خیلی مشابهی همچون فرآیند ها در سیستم های عامل دارد و همچنین مسائل مختلفی همچون همگام سازی و... را نیز خواهند داشت.

در این گذر یک اصلطاح مشهور را که از چندین مفهوم دیگر تشکیل شده است مورد بررسی قرار می دهیم و به تعریف اجزای آن اکتفا می کنیم.

هر گاه حرف از تراکنش هست، ACID اصطلاح معروفی است که به میان می آید. به عبارتی بهتر هر سیستم پایگاه داده برای تامین یک محیط مناسب برای داده ها، باید در اجرای تراکنش ها 4 شرط ذیل را مد نظر قرار دهد.

ACID = Atomicity Consistency Isolation Durability

Atomicity (تجزیه ناپذیری): در صورتی که بخشی از تراکنش نتواند به درستی اجرا شود، اجرای کل تراکنش باید لغو شود و اطمینان حاصل شود که هیچ تغییری در پایگاه داده اتفاق نیفتاده باشد.

Atomicity of a transaction

Consistency (سازگاری): باید این اطمینان حاصل شود که پایگاه داده از یک حالت درست به یک حالت نادرست نرود به این معنی که اگر اتفاق بدی رخ داده باشد و تغییر ناخواسته ای در داده ها اتفاق بیفتد، پایگاه داده باید به حالت درست قبل از آن اتفاق برگردد.

Consistency of a transaction

Isolation (انزوا): اطمینان حاصل کردن از اجرای تراکنش ها به شکل سریالی، در محیطی که اجرای تراکنش ها همروند است.

Isolation of a transaction

Durability (پایایی): تغییراتی که حاصل اجرای یک تراکنش هست باید فارغ از بروز مشکل در سیستم یا از کار افتادن آن، در پایگاه داده تثبیت شود .

Durability of a transaction

  • میثم پاسداری
  • ۰
  • ۰

بررسی آزمون آلن تورینگ

سال 1950 آلن تورینگ (ریاضی دان - متولد 1912 انگلستان) آزمونی را مطرح کرد که پایه و اساسی شد برای هوش مصنوعی و بعد از آن نیز هوش مصنوعی (AI) را به طور رسمی معرفی کرد.

آزمون تورینگ در مورد بررسی هوشمندی ماشین است که برای این کار انسان را معیاری برای مقایسه قرار داده است.

اگر بخواهیم خیلی ساده تعریف کنیم، در این آزمون ماشین و انسان درون یک اتاق قرار می گیرند و یک داور در بیرون از اتاق قرار می گیرد و با طرح سوالاتی به شکل غیر مستقیم با این اتاق ارتباط دارد که بعد از گرفتن پاسخ جداگانه از سوی دو موجودیت داخل اتاق دو حالت پیش می آید که بر اساس این موقعیت ها تورینگ اثبات می کند که ماشین هوشمند است و یا خیر:

  • اگر داور تشخیص ندهد که جواب مربوط به ماشین است یا انسان، در این حالت تورینگ اثبات می کند که ماشین هوشمند عمل کرده است و داور نتوانسته تفاوت بین ماشین و انسان را بفهمد!
  • حالت بعدی این است که اگر داور تشخیص دهد که کدام جواب مربوط به ماشین است و کدام یک مال انسان، در این صورت تست تورینگ شکست خورده است و نمی توان گفت ماشین هوشمند است!
همانطور که گفته شد این نظریه تورینگ و آزمون اش پایه و اساسی شد برای معرفی هوش مصنوعی و پیشرفت آن، اما با چالش های جدی از سوی صاحبنظرانی از حوزه های مختلف فلسفه، روانشناسی، ریاضیات، علوم دینی، روانشناسی و... مواجه شد، حتی این انتقاد ها از بطن هوش مصنوعی نیز توسط اشخاصی همچون فرد و هایس متوجه اش گردید. اما گذشته از اینها آزمون تورینگ توانسته باز هم به عنوان یک مبحث داغ باقی بماند.
در این مطلب خواستم اشاره کوچکی در مورد این موضوع بکنم و فایل مستند بررسی مختصری که انجام داده ام را نیز در اینجا قرار می دهم.

لینک : دریافت فایل مستند بررسی آزمون تورینگ
  • میثم پاسداری
  • ۳
  • ۰

در این بخش سوالی از مبحث همگام سازی Synchronization را که با استفاده از ابزار سمافور (Semaphore) به صورت عملی قابل حل است،  آورده ام. 

چند نخی در سیستم عامل

سوال) برنامه ای دارای دو Thread است که 10 عدد را در یک متغیر می نویسند، یکی از Thread ها می نویسد و Thread دیگر عدد نوشته شده را می خواند. چه مشکلی می تواند رخ بدهد و به چه شکلی می توان آن را برطرف کرد؟

پاسخ)  

قبل از حل بهتر است یک سری مفروضات را از روی سوال تشخیص دهیم و جدا کنیم:

تعاریف:

حافظه مشترک (Shared Memory): هر دوی Thread ها با متغیر مشترک در کد سر و کار دارند(همانطور که در شکل مشخص است بخش Data بین Thread ها در محیط Multi Threading مشترک است) به همین دلیل متغیر برنامه، حافظه مشترک در این مسئله است.

ناحیه بحرانی (Critical Section): قسمتی از کد که در آنجا حافظه مشترک مورد دسترسی قرار می گیرد.

مشکل:

 انحصار متقابل (Mutual Exclusion): اگر یکی از Thread ها در ناحیه بحرانی باشد، Thread دیگری نباید وارد ناحیه بحرانی شود در حالیکه در این سوال این مورد می تواند اتفاق بیافتد یعنی هر دو Thread در یک مقطع از زمان در ناحیه بحرانی باشند و حافظه مشترک را بخوانند یا بنویسند!

راه حل:

یکی از راه هایی که می توان مشکل انحصار متقابل را در این مسئله حل کرد، استفاده از سمافور هاست (در اینجا سمافورهایی که POSIX در اختیار ما گذاشته).

نکته: POSIX مخفف عبارت Portable Operating System Interface است و کتابخانه ایست که توسط IEEE معرفی شده و در حال حاضر بر روی لینوکس وجود دارد.

سورس کد زیر به زبان C، راه حل پیشنهادی من برای حل این مسئله به صورت عملی در محیط لینوکس می باشد.


بخش1) فراخوانی Herader Fileها، تعریف متغیر ها، تعریف سمافور ها و ایجاد Thread ها

فراخوانی ها و بدنه برنامه

بخش2) روال مربوط به نوشتن (Writer) که توسط thread_a اجرا می شود.

ٌٌ

(1): در این قسمت که ورود به ناحیه بحرانی (Entry Section) است، سمافور writesem ، منتظر می ماند، و این انتظار تا زمانی که سیگنالی (post ای) از طرف readsem بیاید، طول می کشد؛ یعنی بعد از خوانده شدن حافظه مشترک، نوشتن در حافظه صورت می گیرد. 

(2): در این قسمت به سمافور readsem اطلاع می دهد که داده نوشته شد و می توانی آن را از حافظه مشترک بخوانی.


بخش3) روال مربوط به خواندن (Reader) که توسط thread_b اجرا می شود.

Writer Thread

(3): در این قسمت اگر خواننده دیگری بیاید، منتظر می ماند تا زمانی که خواننده فعلی مقداری را بخواند و بعد از آن سیگنال دهد.

(4): در این قسمت هم بخش خروج از نایحه بحرانی (Exit Section) است، سمافور نویسنده سیگنال می دهد که عمل خواندن انجام شد و می توانی بنویسی.


نکته 1) Mutex سمافوری باینری است که ورود Thread ها به ناحیه بحرانی را اصطلاحا سریالی (Serialized) می کند، در این برنامه، سمافور های مورد استفاده از نوع Mutex می باشند که با تابع sem_init مشخص شده است.

نکته 2) برای کامپایل Source Code در محیط لینوکس، دستور زیر را در Terminal اجرا کنید:

gcc -o sem-compiled sem.c -Wall -Werror -lpthread

نکته 3) مسئله مورد بحث، شبیه مسئله معروف Readers & Writers می باشد.


لینک 1)  دانلود Source Code برنامه در زبان C

لینک 2)  نمونه خروجی برنامه، با استفاده از سمافور ها

لینک 3)  یک نمونه از خروجی برنامه، بدون استفاده از سمافور ها

    • میثم پاسداری
    • ۲
    • ۰

    معمولا قبل از ورود به هر بحث تخصصی، بهتر است واژگان و اصطلاحات آن بحث را هم تعریف کرد و بعضا یک پیش درآمدی بر پیدایش و گزینش این اصطلاح داشت که این کار را Terminology (درلغتنامه: واژگان، اصطلاحات فنی و..)  می نامند. در این بخش قصد دارم چندتا تعریف از چندین اصطلاح رایج در مهندسی کامپیوتر را بیاورم و سعی ام بر اینست که دانسته های خودم رو با توجه به مستندات و منابع موجود بیاورم. همچنین تلاش خواهم کرد که تعاریف را تا جایی که ممکن است به صورت مختصر و مفید و با جملات سیستمی بنویسم، اصطلاحات نیز بر مبنای رایج بودن آن ها آورده شده اند که در زیر لیست شده اند:

    Performance (کارایی)

    به میزان سودمندی یک سیستم در انجام یک کار با توجه به منابع در اخیارش، اطلاق می شود.

    کارایی سیستم

    نعریف بالا یک تعریف مختصر سیستمی بود اما در اصل Performance مجموعه تعاریف زیر در یک کلمه است : 

    • زمان پاسخ (Response Time): فاصله زمانی بین ورود process به سیستم تا زمان خروج آن از سیستم.
    • توان عملیاتی (Throughput) : میزان کار انجام شده توسط سیستم در واحدی از زمان.
    • دسترسی پذیری (Availability) : میزان در دسترس بودن سیستم و پاسخگویی به درخواست ها.
    • استفاده از منابع (Resource Utilization) : میزان استفاده سیستم از منابع در اختیارش.
    • پهنای باند (Bandwidth) : میزان داده انتقالی از خط انتقال در واحدی از زمان.
    • و...

    به عنوان مثال: Performance سیستم عامل در حالتی که با الگوریتم Round Robin، زمانبندی می شود بیشتر از حالتی است که از الگوریتم FCFS استفاده می شود.


    Benchmark (محک)

    استاندارد ایست بر پایه یک معیار مشخص (بهترین نمونه از یک محصول)، که به واسطه آن می توان یک نمونه از محصول را از لحاظ کیفیت محک زد. 

    به عنوان مثال: EBD، عنوان Benchmark ایست که شرکت مایکروسافت برای سنجش Performance پایگاه داده های رابطه ای گسترش یافته و شی گرا معرفی کرده است.(لینک +)


    Trade-off (توازن)

    سبک، سنگین کردن بین دو یا چندین رهیافت (Approach) به منظور بدست آوردن یک سری منفعت ها و در مقابل، از دست دادن آن ها.

    در واقع Trade-off برقراری یک توازن در برخورد با فرصت ها (opportunities) و تهدید ها(threats) است.

    تعاریف فوق را می توان در حالت کلی برای Trade-off در نظر گرفت اما می توان گفت که مهندسی خود نوعی Trade-off یا همان عبارت (gain - overhead) است، یعنی دو دو تا چارتا کردن برای رسیدن به یک نقطه ایده آل  است.

    Tradeoff in computer engineering

    به عنوان مثال : موارد زیر مثال هایی برای رسیدن به یک نقطه Trade-off می باشند

    • انتخاب میزان کوانتوم زمانی (Time Quantum) در الگوریتم RR برای زمانبندی Process ها
    حالت 1 : پایین بودن کوانتوم زمانی موجب افزایش تعداد Context Switch ها می شود، اما در عوض Response Time را کاهش دهد.

    حالت 2 : بالا بودن کوانتوم زمانی گرچه تعداد Context Switch ها را کم می کند و به طبع آن سربار را نیز کاهش می دهد اما Response Time را نیز افزایش می دهد و اگر کوانتوم به سمت بی نهایت میل کند، الگوریتم کلا تبدیل به FCFS می شود.

    نکته 1 : Context Switch (تعویض متن) خود سربار (Overhead) ای برای سیستم عامل می باشد چون طی آن CPU هیچ عمل مفیدی را انجام نمی دهد.

    نکته 2 : پیاده سازی الگویتم RR در عمل، خود می تواند به عنوان یک حالت دیگر بررسی شود.

    • استفاده/عدم استفاده از کلید خارجی(FK) در پایگاه داده 
    حالت 1 : ذخیره سازی داده های تکراری یک رابطه در رابطه دیگر و عدم نیاز به کلید خارجی و در نتیجه عدم نیاز به join کردن رابطه ها و در مقابل آن هزینه کردن فضا.

    حالت 2 : استفاده از کلید خارجی و کاهش دادن میزان افزونگی در جدول های پایگاه داده و هزینه کردن از Performance در مقابل افزونگی داده ها.

    • این مقاله ( + ) را ببینید.


    Overhead (سربار)

    تخصیص منابع اضافی به سیستم اعم از حافظه، پهنای باند، زیر ساخت های سخت افزاری و نرم افزاری و... برای تبدیل ورودی به خروجی.

    overhead

    به عنوان مثال: 

    • پیاده سازی یک ضرب کننده نسبت به پیاده سازی یک جمع کننده، بر روی یک بورد الکترونیکی overhead بالایی دارد.
    • Decode کردن Metadata های یک Packet در طول شبکه و تشخیص آن نوعی overhead است.
    • و...
    نکته مهمی که در مورد overhead می توان گفت اینست که overhead را در یک Benchmark یا یک نقطه مشخصی بررسی می کنند و با توجه به معیارها و شرایط موجود آن Benchmark سربار را می سنجند.


    Bottleneck (تگنا)

    این اصطلاح از دو واژه Bottle(بطری) و neck(گردن) تشکیل شده است. فلسفه این نام گذاری این است که آبی که قرار است از بطری بیرون ریخته شود نهایتا از این neck باید عبور کند که در نتیجه این کار موجودی داخل بطری توسط بخشی از خود بطری (یعنی neck) محدود می شود.

    می توان تعریف را اینطوری نیز گفت که "Bottleneck محدود شدن ظرفیت یا کارایی کل سیستم توسط یکی از اجزای سیستم است".

    Bottleneck

    به عنوان مثال: 

    • در مدل Client-Server از شبکه ها Server ها به عنوان Bottleneck مطرح هستند.
    • Device های I/O یکی از Bottleneck های یک سیستم کامپیوتری هستند چرا که سرعت CPU هر چقدر هم بالا باشد توسط آنها محدود شده و از سیستم خارج می گردد.
    • Data Hazard ها در معماری کامپیوتر یک Bottleneck برای Performance سیستم می باشد.

    Starvation (قحطی زدگی)

    این مورد یک مبحث سیستم عاملی می باشد که در حالت Multitasking اتفاق می افتد و در آن "Process در حالت Block است و هیچ تضمینی هم از بدست آوردن منابع در آینده وجود ندارد".

    به عنوان مثال:

    • در الگوریتم زمانبندی SJF با ورود داعم Process هایی با زمان اجرای کوتاه، Process های با زمان اجرای بلند در صف انتظار قرار می گیرند(Block می شوند) و هیچگاه اجرا نمی شوند.
    امیدوارم مطلب مفید باشد و استفاده برده باشید.
    با سپاس از توجهتان به این نوشته
    • میثم پاسداری
    • ۱
    • ۰

    زمانبندی دیسک(Disk Scheduling)

    در مورد زمانبندی دیسک قبلا یک تصویری گذاشته بودم ( لینک+) این بار یه سوال از سوالات سیستم عامل کنکور ارشد 93 مجموعه مهندسی کامپیوتر حل می کنیم.

    سوال سیستم عامل کنکور ارشد 93

    پاسخ:

    الگوریتم C-Scan همان الگوریتم Scan هست با این تفاوت که به صورت Circular عمل میکنه یعنی وقتی به انتها با ابتدای شیار(Track) های دیسک رسید به بالاترین مقدار پرش می کند و به سمت پایین با بالا (بسته به موقعیت اولیه هد و جهت حرکت اولیه) حرکت کرده و شیار های درخواست شده را سرویس دهی می کند.  

    در این سوال به ترتیب زیر عمل می شود : 

    چون موقعیت فعلی هد 53 است و به سمت 0 حرکت می کنند بنابراین به کلیه درخواست های کوچکتر از 53 سرویس می دهد و وقتی به نقطه 0 رسید هد را به بالاترین موقعیت (183) انتقال می دهد و باز به سمت پایین شروع به حرکت کرده و به درخواست کوچکتر از 183 به ترتیب در خواست شان سرویس می دهد.

    53 -> 37 -> 14 -> 0 -> 183 -> 124 -> 122 -> 98 -> 67 -> 65

     که با توجه به ترتیب بالا گزینه 2 پاسخ صحیح این سوال می باشد.

     - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

    بن بست (Deadlock)

    سوالات بن بست سیستم عامل کنکور ارشد مهندسی کامپیوتر

    پاسخ:

    برای حل یک همچین سوالاتی میشه از رابطه زیر استفاده کرد، که مشخص کننده حداکثر مقدار n برای عدم بروز بن بست می باشد.

    n: تعداد Proccess ها 

    M: تعداد منابع از یک نوع!

    Request: تعداد درخواست ها به ازای هر Process

        بن بست در سیستم عامل

    با توجه به رابطه بالا و مفروضات سوال، جواب گزینه 1 و  به شکل زیر می باشد: 

    2n < n+m  => 2n-n<m => n<m

    • میثم پاسداری
    • ۲
    • ۰

    معماری اندروید

    زیاد به بحث های پایه ای نمی پردازم، اما قصد دارم توضیح کوچکی در مورد Dalvik VM بدم. Dalvik را می توان همان JVM جاوا در نظر گرفت که توان و حافظه مصرفی پایینی دارد  و بر خلاف JVM فایل های Class. را مستقیما اجرا نمی کند و بجای آن فایل های dex. را که در زمان کامپایل از همان فایل class. ساخته می شود اجرا می کند. Dalvik امکان ایجاد چندین نمونه از ماشین مجازی را برای تامین امنیت، افزایش کارایی، مدیریت حافظه و پشتیبانی از چندنخی فراهم می کند.

    بخش مهم بعدی Linux Kernel هست که در یک پست دیگر به بررسی جزئیات پرداخته خواهد شد.

    • میثم پاسداری
    • ۱
    • ۰

    • میثم پاسداری
    • ۰
    • ۰

    سیستم عامل (Opearting System)از درس های شیرین و جالب رشته کامپیوتر می باشد که در مقاطع مختلف گرایش نرم افزار به این مبحث پرداخته می شود، از این رو کتاب های زیادی برای درک مفاهیم این درس وجود دارد که یکی از آنها کتاب "مفاهیم سیستم عامل" نوشته آبراهام سسلبرشاتس است ، گرچه کتاب های معروف دیگری(نظیر کتاب آقای استالینگز، آقای تننباوم، آقای دکتر فهیمی و...) نیز  وجود دارد اما این کتاب به دلیل اینکه مفاهیم را به شکل سلیس و روان توضیح می دهد معمولا به عنوان مرجع درسی آموزشی در دانشگاه های داخل و خارج از کشور معرفی می گردد... امیدوارم که این مطلب مفید بوده باشد.

    بنده تو این درس افتخار شاگردی دکتر حسین محمدی(+) رو دارم...

    • میثم پاسداری