مکینتاش Macintosh

مکینتاش (Macintosh) یا مک (Mac) ساخته شرکت رایانه‌ای اپل است که مکینتاش اولیه در تاریخ ۲۴ ژانویه ۱۹۸۴ تولید شده است و اولین رایانه شخصی برای Graphical user interface (GUI) بود و در عوض استفاده از موشی با Command line interface کار می کند. در حال حاضر میزان تنوع مکینتاش اپل از مک کوچک (Mac mini) هست تا قویترین Server ها مثل Xserve که همگی ساخته شرکت اپل می باشد. مکینتاش اولیه از موتورولا 68k که از خانواده ریزپردازندهها هستند استفاده می کردند که بعدا تغییر کرد به موتورولا و آی‌بی‌ام پاور پیسی (Power PC) . با حروف اختصاری Mac، محدوده‌ای از کامپیوترهای شخصی که توسط شرکت رایانه‌ای اپل در سال ۱۹۸۴ معرفی گردید. مکینتاش بر روی یک رابط گرافیکی کاربر معروف با استفاده آسان تأکید دارد که کامپیوترهای مبتنی بر مجموعه ریزپردازنده‌های ۶۸۰۰۰ موتورولا است.

 تاریخچه

پروژه مکینتاش از اوایل سال ۱۹۷۹ به وسیله جف راسکین (Jef Raskin) یک کارمند اپل آغاز شد. در سبتامبر ۱۹۷۹ راسکین مجاز شد تا روی پروژه کار کند و در آغاز به دنبال یک مهندس کامپیوتر رفت که بتواند یک شکل اولیه داشته باشند و بعد از چند سال راسکین توانست یک تیم برای ساخت اولین مکینتاش درست کنند که از

تیم

• Chris Espinosa
• Joanna Hoffman
• George Crow
• Jerry Manock
• Susan Kare
• Andy Hertzfeld

تشکیل شده بودند.

Mac OS که مخفف Macintosh Operating System است، نام تجاری یک سری از سیستم عامل های دارای رابط گرافیکی کاربر است که توسط شرکت Apple برای کامپیوترهای مکینتاش توسعه داده شده اند. سیستم عامل Mac عموماً به خاطر رابط گرافیکی خوب خود مشهور شده است. این سیستم عامل برای نخستین بار در سال 1984 با کامپیوتر Macintosh 128K عرضه شد. نسخه های اولیه Mac OS تنها با کامپیوترهای مکینتاش که بر مبنای Motorola 68000 ساخته شده بودند، سازگار بودند در حالیکه نسخه های جدیدتر با کامپیوترهای PowerPC نیز سازگار شدند. اخیراً نیز سیستم عامل Mac OS X با کامپیوترهای Intel x86 سازگار شده است. نسخه های مختلف Mac OS نخستین سیستم عامل مکینتاش شامل دو بخش نرم افزاری بود که با نام های "System"و "Finder" شناخته می شدند که هرکدام از این دو بخش دارای نسخه مخصوص به خود بودند. System 7.5.1 نخستین نسخه ای بود که در آن آرم Mac OS یک قیافه خندان استفاده شده است؛ و نام Mac OS نیز برای اولین بار با Mac OS 7.6 معرفی شد. سیستم عامل Mac OS را می توان به دو خانواده مختلف سیستم های عامل تقسیم کرد “Classic” Mac OS که شامل سیستم عامل عرضه شده در سال 1984 و نسخه های بعدی آن تا نسخه Mac OS 9 می شود.Mac OS X (که حرف "X" معرف عدد رومی 10 است) از اجزای Open Step (توابع API تعریف شده برای یک سیستم عامل شی گرا که هر سیستم عامل مدرنی آن را به عنوان بخشی از هسته خود دارد استفاده می کند. "Classic” Mac OSبا این وی‍ژگی که در آن از خط فرمان استفاده نمی شود شناخته می شود. این سیستم عاملِ کاملاً گرافیکی بسیار مشابه سیستم عامل Commodore GEOS است. با وجود راحتی استفاده از آن، این سیستم عامل دارای کمبودها و نقایصی نیز بود.

کمبودها و نقایص این سیستم عامل

حالت تک پردازشی (البته در نسخه های اولیه این سیستم عامل) یا چند پردازشی اشتراکی (در نسخه های بعدی)، امکان مدیریت حافظه با مقدار محدود، عدم استفاده از حافظه حفاظت شده، و احتمال تداخل با نسخه های جدیدتر سیستم های عامل دیگری که قابلیت های جدیدی (نظیر استفاده از شبکه) را فراهم می کنند، از جمله کاستی های این سیستم عامل به حساب می آیند. نخستین سیستم فایل استفاده شده در Mac OS سیستم فایل مکینتاش (Macintosh File System (MFS)) بود که تنها امکان استفاده از یک سطح فولدر را فراهم می کرد. این سیستم فایل در نسخه های بعدی، با سیستم فایل Hierarchical File System (HFS) سیستم فایل سلسله مراتبی) که دارای ساختار درختی مدیریت فایل بود، جایگزین شد. در رابطه با سیستم فایل سیستم عامل مکینتاش باید به نکته مهمی اشاره کرد که آن را از سیستم های فایل دیگر سیستم عامل ها متمایز می کند. اکثر سیستم های فایل که توسطDOS ، Unix یا دیگر سیستم عامل ها استفاده می شوند، به سادگی فایل را بصورت یک سری از بایت های پیوسته در نظر می گیرند بطوریکه هر فایل نیاز به برنامه ای دارد که تشخیص دهد آن فایل حاوی چه اطلاعاتی است. برخلاف این قاعده، MFS و HFS فایل را بصورت دو بخش مجزا (بخش داده و بخش منابع) در نظر می گیرند. بخش "داده" (Data) حاوی اطلاعات مشابه با سیستم عامل های دیگر است (مثلاً بخش داده می تواند حاوی متن یک سند یا اطلاعات یک فایل تصویری باشد). بخش "منابع "(Resource) شامل دیگر اطلاعات ساختاری مربوط به فایل (مانند تعاریف منوها، گرافیک، صدا، یا کدهای اجرایی) است. یک فایل ممکن است تنها شامل بخش منابع باشد (در حالی که بخش داده آن خالی است)، یا تنها شامل بخش داده باشد (در حالی که بخش منابع آن خالی است) و یا شامل هر دو بخش داده و منابع باشد. یک فایل متنی می تواند متن را در بخش داده فایل و اطلاعات مربوط به نوع فرمت و قالب بندی متن را در بخش منابع فایل ذخیره کند. این کار به این منظور انجام می شود که مثلاً اگر برنامه ای با فرمت قالب بندی متن آشنا نبود، حداقل قادر به خواندن خود متن باشد. از طرف دیگر، این تقسیم بندی باعث ناهماهنگی و عدم سازگاری با دیگر سیستم های عامل می شود؛ با کپی کردن یک فایل از سیستم فایل Mac به سیستم فایلی غیر از Mac بخش منابع فایل از دست می رود. در Mac OS X از ساختار مدیریت حافظه و چند پردازشی کنترل شده مشابه سیستم عامل Unix استفاده شده است. این سیستم عامل بر مبنای هسته Mach (Mach kernel) یک هسته کوچک سیستم عامل که در دانشگاه Carnegie Mellon در ایالت پنسیلوانیای آمریکا طی یک پرو‍ژه تحقیقاتی درباره محاسبات موازی و توزیع شده ایجاد شده است و نسخه BSD سیستم عامل Unix یک سیستم عامل شیءگرا که توسط Steve Jobs در شرکت NeXT ایجاد و توسعه داده شده است. سیستم مدیریت حافظه جدید اجازه اجرای برنامه های بیشتری را بطور هم‌زمان می دهد و از بسته شدن برنامه های دیگر در حال اجرا به علت crash کردن یک برنامه جلوگیری می کند. همچنین این سیستم عامل دومین سیستم عامل مکینتاش است که در آن خط فرمان نیز گنجانده شده است، هرچند که برای استفاده از این خط فرمان می بایست Terminal Emulator توسط کاربر اجرا شود سیستم عامل Mac OS دارای خط فرمان نبود و نخستین سیستم عامل مکینتاش که دارای خط فرمان بود، سیستم عامل A/UX است که توسعه آن متوقف شده است) .مشکلات مختلفی باعث شده است که Mac OS X نسبت به Mac OS کمتر کاربرپسند باشد و کار با آن مشکل تر باشد. از جمله این عوامل نیاز به سخت افزار قوی تر برای اجرای سیستم عامل، عدم ارائه برخی قابلیت های سیستم عامل که در نسخه های قبلی وجود داشت، و برخی ناسازگاری های جدی با نسخه قبلی (زیرا درایورهای نوشته شده برای Mac OS سازگار با Mac OS X نیستند) است.

ساختمان داده - جلسه دوم

الگوریتم

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

---

تعریف

به طور خلاصه مجموعه ای از دستوالعمل ها برای حل یک مسئله را الگوریتم می گویند. کلمه الگوریتم از نام ریاضیدان قرن نهم ابوجعفرمحمد ابن موسی الخوارزمی گرفته شده است.
تعریف دقیق تر الگوریـم به صورت زیر است:

یک الگوریتم مجموعه ای متناهی از دستورات برای حل یک مسئله خاص توسط انسان یا ماشین است، که ترتیب انجام عملیات در آن مشخص شده و عملیات در زمان معینی خاتمه پیدا می کند. هر دستورالعمل در الگوریتم باید مختصر، دقیق، و صریح باشد.

یک الگوریتم پنج خاصیت زیر را باید دارا باشد:

1. متناهی بودن. یک الگوریتم باید همیشه بعد از تعدادی گام به پایان برسد.
2. صراحت. فعلی که در هر قدم الگوریتم انجام می گیرد باید مختصر، صریح و غیر مبهم باشد.
3. ورودی. مقادیری هستند که ابتدا، قبل از شروع، به الگوریتم داده می شوند.
4. خروجی. مقادیری هستند توسط الگوریـم تولید می شود و رابطه مشخصی با ورودی ها دارند.
5. کارائی. دستورات الگوریتم درحد کفایت باید ساده و دقیق باشند تا یک انسان مانند یک روبات بتواند آنها را با استفاده از قلم و کاغذ بدون احتیاج به فکر کردن در زمان معینی انجام بدهد.
 

الگوریتم ها قرن ها برای حل مسائلی که بشر با آنها روبرو بوده استفاده می شده اند. تقریبا کلیه برنامه های کامپیوتر، بجز برنامه های کاربردی هوش مصنوعی، دربرگیرنده الگوریتم هستند. مشهورترین الگوریتم در تاریخ، الگوریتم اقلیدسی، مربوط به زمان یونان باستان است که برای محاسبه بزرگترین مقسوم علیه مشترک دو عدد صحیح به کار می رفته است و هنوز در دنیای ریاضی کاربرد دارد.

خلق الگوریتم های زیبا، ساده و با کمترین مراحل، یکی از چالش های برنامه نویسی است.

---

نحوه بیان الگوریتم

الگوریتم های می توانند با نمادهای مختلفی بیان شوند:

• زبان طبیعی. استفاده از عبارات زبان طبیعی برای بیان الگوریتمی ممکن است باعث طولانی و مبهم شدن آن بشود و برای الگوریـتم های پیچیده و فنی بندرت استفاده می شود.
• زبان های برنامه نویسی. در ابتدا بیان الگوریتم با زبان های برنامه نویسی موجود طرفدار داشت.
• Pseudo Code و فلوچارت. راه های ساختیافته ای برای نمایش الگوریتم، که درحین استقلال از زبان برنامه نویسی خاصی، از ابهام پرهیز می کنند.
 

امروزه الگوریتم ها معمولا با استفاده از Pseudo Code در یک زبان برنامه نویسی که معمولا پیاده سازی نشده بیان می شوند. در طی این درس از کدهای ساختگی که در ادامه شرح داده می شوند برای بیان الگوریتم ها استفاده می شود.

variable := value

اختصاص مقداری به یک متغیر را نشان می دهد.

if (condition) then
   statements1
else
   statements2
end if
 

برای بیان تصمیم گیری، اگر شرط برقرار باشد عبارت 1 انجام می گیرد و اگر برقرار نباشد عبارت 2

while (condition)
   statement
end while
 

برای نمایش حلقه تکرار، اگر شرط برقرار باشد دستورات تکرار می شوند.

repeat until (condition)
   statement
end loop
 

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

for (counter:=value1 to value2 )
   statement
end for
 

برای نمایش تکرار عبارتی به تعداد معینی، شمارنده از مقدار1 شروع شده در هربار تکرار یک واحد به آن اضافه می شود تا به مقدار2 برسد. برای شمارش معکوس به جای to از down to قرار می گیرد.

انتهای الگوریتم توسط کلمه end مشخص می شود.

---

مثال. الگوریتم زیر به متغیر x مقادیر 1 تا 10 بجز عدد 5 را اختصاص می دهد.

x:=0
while (x < 10)
   if x = 4 then
     x := x + 2
   else
     x := x + 1
   end if
end while
end

---

ارزیابی کارائی الگوریتم ها

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

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

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

---

پیچیدگی حافظه

پیچیدگی حاظه ای میزان فضائی از حافظه است که برنامه برای اجرای کامل به آن نیاز دارد. فضای مورد نیاز در هربرنامه مجموع قسمت های زیر است:

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

در تحلیل فضای لازم روی تخمین بخش متغیر تاکید نداریم زیرا برای هرمسئله ابتدا باید مشخصات موردی را تعیین کنیم که کار دشواری است.

---

پیچیدگی زمانی

زمان اجرا مقدار زمانی از کامپیوتر است که برنامه برای اجرای کامل مصرف می کند. برای محاسبه پیچیدگی زمان الگوریتم ابتدا تعداد قدم های الگوریتم به صورت تابعی از اندازه مسئله مشخص می شود، برای انجام این کار تعداد تکرارعملیات اصلی الگوریتم محاسبه می شود و به صورت تابع f(n) (که n تعداد ورودی هاست) بیان می شود. سپس تابع g(n)، که مرتبه بزرگی تابع f(n) را وقتی اندازه ورودی به اندازه کافی بزرگ است نشان می دهد، بدست می آید. در نهایت پیچیدگی الگوریتم برای نشان دادن رفتار الگوریتم با ورودی های مختلف با استفاده از نمادها O ، Θ و Ω بیان می شود.

تعریف Big-O (حدبالا)

تابع f(n) را نظر بگیرید که برای کلیه n≥0 است، می گوئیمf(n) = O(g(n)) اگر ثابت های مثبت n₀ و c وجود داشته باشند به طوریکه از یک n₀ به بعد همیشه f(n)≤ cg(n) برقرار باشد.

این نماد حدبالائی برای تابع f(n) می دهد و وقتی بکار می رود که رفتار الگوریتم بدترین حالت و بیشترین زمان اجرا را برای مقادیر معین ورودی دارد

تعریف Big-Ω (حدپائین)

تابع f(n) را نظر بگیرید که برای کلیه n≥0 است ، می گوئیم f(n) = Ω (g(n)) اگر ثابت های مثبت n₀ و c وجود داشته باشند به طوریکه از یک n₀ به بعد همیشه f(n)≥ cg(n) برقرار باشد.

این نماد حد پائینی برای تابع f(n) می دهد و وقتی بکار می رود که رفتار الگوریتم بهترین حالت و کمترین زمان اجرا را برای مقادیر معین ورودی دارد

تعریف Big-Θ (حدمتوسط)

تابع f(n) را نظر بگیرید که برای کلیه n≥0 است، می گوئیم f(n) = Θ(g(n)) اگر ثابت های مثبت n₀، c₁ و c₂ وجود داشته باشند به طوریکه از یک n₀ به بعد همیشه c₁g(n) ≤f(n) ≤ c₂g(n) برقرار باشد.

این نماد حدمتوسطی برای تابع f(n) می دهد و زمان اجرای الگوریتم را به صورت میانگینی از تعداد عملیات انجام شده با کلیه نمونه ورودی های مسئله نشان می دهد.

---

قضیه. اگر f(n)=a_mn^m+a_m-1n^m-1+…+a₁n+a₀ در اینصورت f(n)=O(n^m) است.

---

مثال. الگوریتم مرتب سازی حبابی را درنظر بگیرید.

for (i:=1 to n-1)
   for (j:=1 to n-1)
     if a_j>a_j+1 then exchange(a_j,a_j+1)
 

با درنظر گرفتن عمل مقایسه بعنوان عملگر اصلی، دستور If در الگوریتم فوق (n-1)² بار تکرار می شود. بنابراین f(n)= (n-1)²=n²-2n+1 و طبق قضیه g(n)=n² است. بنابراین پیچیدگی الگوریتم فوق برابر با O(n2) می باشد.

---

نکته. اگر زمان الگوریتم وابسته به ورودی نباشد با نماد O(1) نشان داده می شود.

نکته. باید به اندازه کافی الگوریتم را درک کرده باشیم تا بهترین و بدترین رفتار را تولید و محاسبه کنیم. چون برآورد رفتار آماری ورودی ها امری دشوار است، در اکثر موارد به بدترین حالت قناعت می کنیم.

نکته. اگر الگوریتم شامل بخش های مختلفی باشد که هر قسمت پیچیدگی متفاوتی دارد، مرتبه بزرگی هر قسمت را پیدا کرده و بزرگترین مرتبه را بعنوان پیچیدگی کل الگوریتم درنظرمی گیریم.

---

غالبا پیچیدگی g(n) یکی از توابع زیر است: n (پیچیدگی خطی)، log n (لگاریتمی)، n^a (چندجمله ای) و aⁿ که a≥2 (نمائی).

در زیر مربته اجرائی چند تابع به ترتیب صعودی نوشته شده است.

O(1)2) < O( n³) < O(2ⁿ) < O(n!)

---

سیستم عامل مینیکس Minix Operating System

مینیکس یک سیستم عامل کوچک و open source است و شبیه به سیستم عامل unix است که بر اساس معماری microkernels برپا شده است. Andrew.s.tanenbawm(اندرو اس تنن باوم این سیستم عامل را برای مقاصد آموزشی طراحی کرد. Linux نیز به گونه ای از minix الهام گرفته است.اسم minix از لغات minimal unix گرفته شده است.

تاریخچه

همان طور که در کتاب اندرو اس تنن باوم ذکر شده ،او minix را در سال 1987 در دانشگاه vrije در آمستردام هلند طراحی کرده است.12000 خط برنامه که قسمت اعظم آن توسط C نوشته شده است اجزا زیر را تشکیل می دهند:

1-هسته(kernel)

2-مدیریت حافظه(memory management)

3-سیستم فایل(system file)

مینیکس 1 با unix  ویرایش هفتم آن سازگار بود.

تنن باوم minix را به گونه ای طراحی کرد که با سیستم هایIBM و مینی کامپیوتر ها یAT  موجود آن زمان سازگار باشد. Minix 1.5 در سال 1991 عرضه شد که از کامپیوتر های  IBM ps/2 ,comodor amiga,apple macintoshو intle 386 پشتیبانی می کرد.

تقاضای زیاد سبب پیدایش minix 2 شد.  Minix 2   در سال 1997 به بازار عرضه شد.این سیستم عامل از پروسسورهای 386 و بعد از آن که 32 بیتیintel بودند پشتیبانی می کرد. در minix 2 سرویس جدیدی به نام Amoeba  که شامل یک پروتکل شبکه با Tcp/Ip stack   می شد ارائه شد.

ورژن بعد از  minix 2 یا پیشرفته تر آن minix-VMD بود که سازگار با پردازنده های 32 بیتی اینتل بود و در آن برای اولین بار امکان استفاده از حافظه مجازی را برای سیستم عامل فراهم کرده بود.

Minix 3 در اکتبر سال 2005 ارائه شد.در این ورژن خاصیت جدیدی به نام LiveCD به آن اضافه کرده بود .LiveCD به کاربر این امکان را می داد که بدون نصب بر روی سیستم ازسیستم عامل استفاده نمایید.

Minix 3  قابلیت سازگاری با حالت مجازی را با انواع نرم افزارها از قبیل ،virtual pc,boches,vmware و..... را دارا میباشد.

جدیدترین ورژن آن 3.1.2 می باشد که در تاریخ 8 may 2006 عرضه شد. این سیستم عامل شامل نرم افزارهای کاربردی unix  از قبیل X11,emacs,python,per,gcc,ash و... بیش از 400 نرم افزار دیگر unix می باشد.دیگر قابلیت آن این است که کاربر می تواند بدون مشکل و بدون ایجاد نقص ذر Driver دستگاه جانبی آن را جدا نماید و دوباره بدون مشکل آن را مجددا وصل نماید. این سیستم عامل به صورت رایگان در سایت www.minix3.org موجود است.

Minix  و linux :

نحوه طراحی سیستم عامل minix که در آن زمان به شهرت رسیده بود ،در نحوه طراحیlinux توسط  لینوس تروالدزlinus torvalds تاثیر زیادی گذاشت. این مطلب در طراحی هسته linux کاملا مشهود است. البته نا گفته نماند که linux دیگر از micro kernel   در طراحی خود استفاده نمی کند و به جای آن ازحالت monolithic  استفاده می کند اما بحث شباهت این دو سیستم عامل زمانی مشخص می شود که متوجه شوید که سیستم فایل این دو کاملا یکی است. همان طور که آقای کنت براون رئس موسسه تحقیقات در may 2004 اعلام کرده است که قسمتی از کدهای اصلی هسته minix  توسط linux  به سرقت رفته است.

MInix 3  :

Minix 3  چند موضوع مشخص را به عنوان دامنه فعالیت خود قرار داده است:

1-برنامه هایی که برای اجرا نیاز به اطمینان بالا دارند.

2- کامپیوتر های تک پردازنده، با حافظه رم پایین و با مصرف انرژی کم را برای کودکان جهان سومی

3- سیستم های خانگی و سیار مانند dvd recorders,cameras   و تلفن همراه

4 – در زمینه تحصیلی( به عنوان مثال : روره سیستم عامل در دانشگاه ها)

بعضی از امکانات minix 3   :

-         فابلیت شبکه کردن با پروتکل TCP/IP

-   استفاده از زبان های cc.gcc,perl,python,……

-         همراه داشتن بیش از 400 برنامه سیستم عامل  unix

-         پیشرفت بسیار نسبت به ورژن 2

-         کاملا multiuser  و multiprogramming بودن

-         امکان نصب و جداسازی وسایل جانبی

-         موجود بودن منبع آن به طور کامل به زبان C

سخت افزار مورد نیاز:

برای اجرای  minix 3  نیاز به سیستمی با مشخصات زیر است:

-         حداقل،386.486 cpu   و یا پنتیوم است

-         به حداقل 16  mbحافظه رم نیاز است

-         با وجود قابلیت liveCD برای اجرا  نیاز به حجم زیادی ندارد،در ای حالت به  50MB حافظه بر روی hard disk نیاز دارد،ولی در نصب آن به طور کامل بر روی Hard disk  به حداقل  600MB حافظه برای کل منبع آن نیاز است.

لازم به ذکر است که جدیدترین ورژن آن ،ورژن 3 (3.1.2)  است که با امکانات بیشتری نیز عرضه شده است.