مرتب سازی پشته با الگوریتم بازگشتی — به زبان ساده

در این مطلب، روش مرتب سازی پشته با الگوریتم بازگشتی مورد بررسی قرار گرفته و سپس، قطعه کدهای مربوط به آن در زبان‌های برنامه‌نویسی گوناگون شامل C، «جاوا» (Java) و «سی‌شارپ» (#C) ارائه شده است. فرض می‌شود که یک پشته (Stack) به عنوان ورودی داده شده و هدف مرتب کردن آن با استفاده از روش بازگشتی است. فرض می شود در صورت سوال نیز گفته شده که امکان استفاده از هر ساختار حلقه‌ای، مانند for ،while و دیگر موارد وجود ندارد. تنها می‌توان از توابع «نوع داده انتزاعی» (Abstract Data Type | ADT)، شامل مواردی که در ادامه آمده است، روی پشته استفاده کرد.

is_empty(S) : Tests whether stack is empty or not.
push(S) : Adds new element to the stack.
pop(S) : Removes top element from the stack.
top(S) : Returns value of the top element. Note that this
function does not remove element from the stack.

مثال:

Input:  -3  <--- Top
        14 
        18 
        -5 
        30 

Output: 30  <--- Top
        18 
        14 
        -3 
        -5

این مساله، نوعی از مسائل معکوس کردن پشته است. ایده اصلی برای حل این مساله، آن است که همه مقادیر تا هنگامی که پشته خالی شود، در «پشته فراخوانی تابع» (Function Call Stack) نگه داشته شوند. هنگامی که پشته خالی شد، همه عناصر نگه داشته شده باید یکی یکی به صورت مرتب شده قرار بگیرند. در اینجا، مرتب بودن حائز اهمیت است.

مرتب سازی پشته با الگوریتم بازگشتی

می‌توان از الگوریتم زیر برای مرتب‌سازی عناصر پشته استفاده کرد.

1 2 3 4 5

sortStack(stack S)     if stack is not empty:         temp = pop(S);           sortStack(S);         sortedInsert(S, temp);

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

1 2 3 4 5 6 7

sortedInsert(Stack S, element)     if stack is empty OR element > top element         push(S, elem)     else         temp = pop(S)         sortedInsert(S, element)         push(S, temp)

نمایش بصری:

1 2 3 4 5 6

Let given stack be -3    <-- top of the stack 14 18 -5 30

در ادامه، مرتب‌سازی پشته با استفاده از داده‌های مثال ارائه شده در بالا، انجام خواهد شد. ابتدا، باید همه عناصر را از پشته حذف و عناصر حذف شده را در متغیر temp ذخیره کرد. پس از حذف کردن همه عناصر، فریم پشته تابع به صورت زیر خواهد بود:

temp = -3 --> stack frame #1
temp = 14 --> stack frame #2
temp = 18 --> stack frame #3
temp = -5 --> stack frame #4
temp = 30 --> stack frame #5

اکنون، پشته خالی است و تابع «()insert_in_sorted_order» فراخوانی می‌شود و ۳۰ را در پایین پشته (از فریم پشته 5#) درج می‌کند. اکنون، پشته به صورت زیر است.

30 <-- top of the stack

اکنون، عنصر بعدی یعنی ۵- (از فریم پشته 4#) انتخاب می‌شود. از آنجا که ۳۰ > ۵- است، ۵- در پایین پشته درج می‌شود. اکنون، پشته به صورت زیر خواهد بود:

30 <-- top of the stack
-5

در ادامه، ۱۸ (از فریم پشته 3#) انتخاب می‌شود. به دلیل آنکه ۳۰ > ۱۸ است، ۱۸ قبل از ۳۰ قرار می‌گیرد. اکنون پشته به صورت زیر خواهد بود.

1 2 3

30    <-- top of the stack 18     -5

سپس، ۱۴ (از فریم پشته 2#) انتخاب می‌شود. با توجه به آنکه ۳۰ > ۱۴ و ۱۸ > ۱۴، زیر ۱۸ درج می‌شود. اکنون پشته به صورت زیر خواهد بود.

1 2 3 4

30    <-- top of the stack 18 14     -5

اکنون، ۳- (از فریم پشته 1#) انتخاب می‌شود. به دلیل آنکه ۳۰ > ۳ و ۱۸ > ۳-، زیر ۱۴ قرار می‌گیرد. اکنون، پشته به صورت زیر خواهد بود.

1 2 3 4 5

30    <-- top of the stack 18 14 -3     -5

در ادامه، پیاده‌سازی الگوریتم بالا در چند زبان برنامه‌نویسی ارائه شده است.

الگوریتم بازگشتی برای مرتب سازی پشته در زبان C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131

// C program to sort a stack using recursion #include <stdio.h> #include <stdlib.h>    // Stack is represented using linked list struct stack {     int data;     struct stack *next; };    // Utility function to initialize stack void initStack(struct stack **s) {     *s = NULL; }    // Utility function to chcek if stack is empty int isEmpty(struct stack *s) {     if (s == NULL)         return 1;     return 0; }    // Utility function to push an item to stack void push(struct stack **s, int x) {     struct stack *p = (struct stack *)malloc(sizeof(*p));        if (p == NULL)     {         fprintf(stderr, "Memory allocation failed.\n");         return;     }        p->data = x;     p->next = *s;     *s = p; }    // Utility function to remove an item from stack int pop(struct stack **s) {     int x;     struct stack *temp;        x = (*s)->data;     temp = *s;     (*s) = (*s)->next;     free(temp);        return x; }    // Function to find top item int top(struct stack *s) {     return (s->data); }    // Recursive function to insert an item x in sorted way void sortedInsert(struct stack **s, int x) {     // Base case: Either stack is empty or newly inserted     // item is greater than top (more than all existing)     if (isEmpty(*s) || x > top(*s))     {         push(s, x);         return;     }        // If top is greater, remove the top item and recur     int temp = pop(s);     sortedInsert(s, x);        // Put back the top item removed earlier     push(s, temp); }    // Function to sort stack void sortStack(struct stack **s) {     // If stack is not empty     if (!isEmpty(*s))     {         // Remove the top item         int x = pop(s);            // Sort remaining stack         sortStack(s);            // Push the top item back in sorted stack         sortedInsert(s, x);     } }    // Utility function to print contents of stack void printStack(struct stack *s) {     while (s)     {         printf("%d ", s->data);         s = s->next;     }     printf("\n"); }    // Driver Program int main(void) {     struct stack *top;        initStack(&top);     push(&top, 30);     push(&top, -5);     push(&top, 18);     push(&top, 14);     push(&top, -3);        printf("Stack elements before sorting:\n");     printStack(top);        sortStack(&top);     printf("\n\n");        printf("Stack elements after sorting:\n");     printStack(top);        return 0; }

الگوریتم بازگشتی برای مرتب سازی پشته در زبان جاوا

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

// Java program to sort a Stack using recursion // Note that here predefined Stack class is used // for stack operation    import java.util.ListIterator; import java.util.Stack;    class Test {     // Recursive Method to insert an item x in sorted way     static void sortedInsert(Stack<Integer> s, int x)     {         // Base case: Either stack is empty or newly inserted         // item is greater than top (more than all existing)         if (s.isEmpty() || x > s.peek())         {             s.push(x);             return;         }                // If top is greater, remove the top item and recur         int temp = s.pop();         sortedInsert(s, x);                // Put back the top item removed earlier         s.push(temp);     }            // Method to sort stack     static void sortStack(Stack<Integer> s)     {         // If stack is not empty         if (!s.isEmpty())         {             // Remove the top item             int x = s.pop();                    // Sort remaining stack             sortStack(s);                    // Push the top item back in sorted stack             sortedInsert(s, x);         }     }            // Utility Method to print contents of stack     static void printStack(Stack<Integer> s)     {        ListIterator<Integer> lt = s.listIterator();                 // forwarding        while(lt.hasNext())            lt.next();                 // printing from top to bottom        while(lt.hasPrevious())            System.out.print(lt.previous()+" ");     }          // Driver method       public static void main(String[] args)       {         Stack<Integer> s = new Stack<>();         s.push(30);         s.push(-5);         s.push(18);         s.push(14);         s.push(-3);                System.out.println("Stack elements before sorting: ");         printStack(s);                sortStack(s);                System.out.println(" \n\nStack elements after sorting:");         printStack(s);            } }

الگوریتم بازگشتی برای مرتب سازی پشته در زبان #C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

// C# program to sort a Stack using recursion   // Note that here predefined Stack class is used   // for stack operation   using System; using System.Collections;    public class GFG   {       // Recursive Method to insert an item x in sorted way       static void sortedInsert(Stack s, int x)       {           // Base case: Either stack is empty or           // newly inserted item is greater than top           // (more than all existing)           if (s.Count == 0 || x > (int)s.Peek())           {               s.Push(x);               return;           }                  // If top is greater, remove           // the top item and recur           int temp = (int) s.Peek();         s.Pop();         sortedInsert(s, x);                  // Put back the top item removed earlier           s.Push(temp);       }              // Method to sort stack       static void sortStack(Stack s)       {           // If stack is not empty           if (s.Count > 0)           {               // Remove the top item               int x = (int)s.Peek();             s.Pop();                      // Sort remaining stack               sortStack(s);                      // Push the top item back in sorted stack               sortedInsert(s, x);           }       }              // Utility Method to print contents of stack       static void printStack(Stack s)       {           foreach (int c in s)           {             Console.Write(c + " ");         }       }              // Driver method       public static void Main(String[] args)       {           Stack s = new Stack();           s.Push(30);           s.Push(-5);           s.Push(18);           s.Push(14);           s.Push(-3);                  Console.WriteLine("Stack elements before sorting: ");           printStack(s);                  sortStack(s);                  Console.WriteLine(" \n\nStack elements after sorting:");           printStack(s);              }   }    // This code is Contibuted by Arnab Kundu

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

1 2 3 4 5

Stack elements before sorting: -3 14 18 -5 30   Stack elements after sorting: 30 18 14 -3 -5

می‌توان با انجام دادن تغییرات کوچکی در قطعه کدهای بالا، کاری کرد که پشته به صورت نزولی مرتب شود.

ا

منبع: فرادرس

الگوریتم های زمان بندی (Scheduling Algorithms) در سیستم عامل — راهنمای جامع

ابزار زمان‌بندی پردازش به منظور زمان‌بندی پردازش‌های مختلف که بر مبنای الگوریتم‌های زمان‌بندی خاصی به CPU تحویل داده می‌شوند، مورد استفاده قرار می‌گیرد. شش الگوریتم زمان‌بندی پردازش وجود دارند که در این نوشته به بررسی آن‌ها می‌پردازیم:

• زمان‌بندی «اجرا به ترتیب ورود» (First-Come, First-Served) یا به اختصار (FCFS)
• زمان‌بندی «کوتاه‌ترین کار بعدی» (Shortest-Job-Next) یا به اختصار (SJN)
• زمان‌بندی اولویت (Priority)
• زمان‌بندی کوتاه‌ترین زمان باقیمانده (Shortest Remaining Time)
• زمان‌بندی نوبت گردشی یا راند رابین (Round Robin) یا به اختصار (RR)

منبع: فرادرس

• زمان‌بندی صف‌های چند سطحی (Multiple-Level Queues)

اجرا به ترتیب ورود (FCFS)

این روش زمان‌بندی کارها، خصوصیات زیر را دارد:

• وظایف به ترتیب ورود اجرا می‌شوند.
• یک الگوریتم زمان‌بندی غیر preemptive و pre-emptive است.
• درک و پیاده‌سازی آسانی دارد.
• پیاده‌سازی آن مبتنی بر صف FIFO است.
• عملکرد آن پایین است، زیرا میانگین زمان انتظار بالا است.

زمان انتظار هر پردازش به صورت زیر است:

پردازش	زمان انتظار: زمان سرویس – زمان رسیدن
P0	0 – 0 = 0
P1	5 – 1 = 4
P2	8 – 2 = 6
P3	16 – 3 = 13

زمان انتظار میانگین:

(0+4+6+13) / 4 = 5.75

کوتاه‌ترین کار بعدی (SJN)

این الگوریتم خصوصیات زیر را دارد:

• این روش به نام «ابتدا، کوتاه‌ترین کار» یا SJF نیز نامیده می‌شود.
• یک الگوریتم زمان‌بندی غیر preemptive و pre-emptive است.
• رویکرد ساده‌ای برای کاهش زمان انتظار محسوب می‌شود.
• در سیستم‌های دسته‌ای که زمان مورد نیاز CPU از پیش مشخص نیست به سادگی پیاده‌سازی می‌شود.
• پیاده‌سازی آن در سیستم‌های تعاملی که زمان مورد نیاز CPU مشخص نیست ناممکن است.
• پردازنده باید از قبل بداند که پردازش چه مدت طول خواهد کشید.

زمان انتظار هر پردازش به صورت زیر است:

پردازش	زمان انتظار: زمان سرویس – زمان رسیدن
P0	3 – 0 = 0
P1	0 – 0 = 0
P2	16 – 2 = 14
P3	8 – 3 = 5

میانگین زمان انتظار:

(3+0+14+5) / 4 = 5.50

زمان‌بندی مبتنی بر اولویت

این روش خصوصیات زیر را دارد:

• زمان‌بندی اولویت یک الگویتم غیر preemptive است و یکی از رایج‌ترین الگوریتم‌های زمان‌بندی در سیستم‌های دسته‌ای محسوب می‌شود.
• هر پردازش یک اولویت دارد. پردازش دارای بالاتری اولویت ابتدا اجرا می‌شود و همین طور تا آخرین پردازش.
• پردازش‌های دارای اولویت یکسان به روش «اجرا به ترتیب ورود» اجرا می‌شوند.
• اولویت می‌تواند بر مبنای الزامات حافظه، الزامات زمانی یا هر الزام دیگر برای منابع تعیین شود.

زمان انتظار هر پردازش به صورت زیر است:

پردازش	زمان انتظار: زمان سرویس – زمان رسیدن
P0	9 – 0 = 0
P1	6 – 1 = 5
P2	14 – 2 = 12
P3	0 – 0 = 0

میانگین زمان انتظار به صورت زیر است:

(9+5+12+0) / 4 = 6.5

کوتاه‌ترین زمان باقی‌مانده

این روش خصوصیات زیر را دارد:

• کوتاه‌ترین زمان باقی‌مانده (SRT) نسخه preemptive از الگوریتم SNJ محسوب می‌شود.
• زمان پردازنده به وظیفه‌ای که خاتمه یافتن آن به کمترین زمان نیاز دارد تخصیص می‌یابد؛ اما می‌تواند به وظیفه جدیدتری که زمان اجرای کوتاه‌تری دارد نیز اختصاص یابد.
• پیاده‌سازی سیستم‌های تعاملی که در آن زمان مورد نیاز CPU مشخص نباشد در این روش ممکن نیست.
• این روش غالباً در محیط‌های دسته‌ای که کوتاه‌ترین کار باید بالاترین اولویت را داشته باشد مورد استفاده قرار می‌گیرد.

زمان‌بندی راند رابین یا نوبت گردشی

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

زمان انتظار هر پردازش به صورت زیر است:

پردازش	زمان انتظار: زمان سرویس – زمان رسیدن
P0	(0 – 0) + (12 – 3) = 9
P1	(3 – 1) = 2
P2	(6 – 2) + (14 – 9) + (20 – 17) = 12
P3	(9 – 3) + (17 – 12) = 11

میانگین زمان انتظار:

(9+2+12+11) / 4 = 8.5

زمان‌بندی صف چند سطحی

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

• صف‌های چندگانه‌ای برای پردازش‌های دارای خصوصیات مشترک نگهداری می‌شوند.
• هر صف می‌تواند الگوریتم زمان‌بندی خاص خود را داشته باشد.
• اولویت‌هایی برای هر صف تعیین می‌شود.

برای مثال کارهای مرتبط با CPU را می‌توان در یک صف زمان‌بندی کرد و همه کارهای مرتبط با I/O را نیز می‌توان در صف دیگری جمع‌بندی نمود. سپس زمان‌بندی پردازش به نوبت وظایف کارها را از هر صف انتخاب می‌کند و آن‌ها را بر اساس الگویتم تعیین شده برای هر صف به CPU تخصیص می‌دهد.

نصب گیت (Git) روی اوبونتو — به زبان ساده

استفاده از سیستم‌های کنترل نسخه در توسعه نرم‌افزارهای مدرن امری ضروری محسوب می‌شود چون نسخه بندی امکان ردگیری نرم‌افزار در سطح منبع را فراهم می‌سازد. بدین ترتیب می‌توانید تغییرها را پیگیری کنید، به مراحل قبلی بازگردید، و انشعاب (branch) ایجاد کنید تا نسخه‌های متفاوتی از فایل‌ها و دایرکتوری‌ها را داشته باشید. یکی از محبوب‌ترین سیستم‌های کنترل نسخه در حال حاضر Git است. فایل‌های بسیاری از پروژه‌ها در مخزن یا ریپازیتوری گیت نگه‌داری می‌شوند و سایت‌هایی مانند گیت‌هاب (GitHub)، گیت‌لب (GitLab) و بیت‌باکت (Bitbucket) به تسهیل اشتراک‌گذاری و کار جمعی روی پروژه‌های توسعه نرم‌افزار کمک می‌کنند.

در این راهنما شیوه نصب و پیکربندی گیت روی یک سرور اوبونتو 18.04 را آموزش خواهیم داد. در این نوشته به توضیح دو روش متفاوت برای نصب نرم‌افزار می‌پردازیم که هر یک از آن‌ها بسته به نیازهای خاص مزیت‌های خاص خودشان را دارند.

پیش‌نیازها

برای مطالعه این راهنما باید یک حساب کاربری غیر root با دسترسی‌های sudo روی یک سرور اوبونتو 18.04 داشته باشید. برای یادگیری روش دستیابی به این موارد می‌توانید از راهنمای «راه‌اندازی اولیه سرورهای اوبونتو ۱۸.۰4» استفاده کنید. زمانی که این موارد را آماده کردید، می‌توانید به ادامه مطالعه این راهنما بپردازید.

نصب گیت با بسته‌های مختلف

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

در ابتدا از ابزارهای مدیریت بسته apt برای به‌روزرسانی اندیس بسته محلی استفاده کنید. زمانی که به‌روزرسانی کامل شد، می‌توانید گیت را دانلود و نصب کنید:

sudo apt update
sudo apt install git

با اجرای دستور زیر می‌توان مطمئن شد که گیت به درستی دانلود و نصب شده است:

git –version

خروجی

git version 2.17.1

زمانی که گیت با موفقیت نصب شد، می‌توانید به بخش راه‌اندازی گیت این راهنما مراجعه کنید.

نصب گیت از فایل‌های منبع

روشی که برای نصب گیت، انعطاف‌پذیری بیشتری ارائه می‌کند، کامپایل کردن فایل‌های منبع این نرم‌افزار است. این روش زمان بیشتری طول می‌کشد و بسته‌ای که به این ترتیب کامپایل می‌شود از سوی نرم‌افزار مدیریت بسته سیستم نگهداری نخواهد شد؛ اما با استفاده از این روش می‌توان آخرین نسخه از نرم‌افزار گیت را دانلود و نصب نمود و همچنین در صورتی که بخواهید یک نصب سفارشی داشته باشید، در این روش کنترل بیشتری روی مراحل نصب خواهید داشت.

پیش از آغاز این روش باید نرم‌افزارهایی که گیت به آن‌ها وابسته است را نصب کنید. همه این نرم‌افزارها در مخزن‌های پیش‌فرض اوبونتو وجود دارند و از این رو با به‌روزرسانی اندیس بسته محلی و سپس اقدام به نصب می‌توان آن‌ها را به صورت یک جا نصب کرد:

sudo apt update
sudo apt install make libssl-dev libghc-zlib-dev libcurl4-gnutls-dev libexpat1-dev gettext unzip

پس از این که وابستگی‌های ضروری را نصب کردید، می‌توانید به کار خود ادامه داده و نسخه گیت را که می‌خواهید از mirror گیت روی وب‌سایت گیت‌هاب در لینک زیر دانلود کنید:

https://github.com/git/git

در این صفحه، ابتدا باید مطمئن شوید که در شاخه master حضور دارید. سپس روی لینک Tags کلیک کرده و نسخه مطلوب گیت خود را انتخاب کنید. به طور معمول بهتر است از دانلود نسخه‌های release candidate که با حرف rc نمایش می‌یابند خودداری کنید، زیرا نسخه‌های پایداری محسوب نمی‌شوند؛ مگر این که برای این کار دلیل موجهی داشته باشید.

سپس در سمت راست صفحه روی دکمه Clone or download کلیک کنید و زیر آن روی دکمه Download ZIP راست کلیک کنید تا آدرس لینک که به zip. ختم می‌شود را کپی کنید.

اینک به سرور اوبونتو 18.04 خود بازگردید و به دایرکتوری tmp بروید تا فایل‌های موقتی که لینکشان را برداشته‌ایم را دانلود کنید.

cd /tmp

در این دایرکتوری می‌توانید با دستور wget لینک فایل zip کپی شده را دانلود کنید. ما برای فایل نام جدیدی به صورت git.zip تعیین می‌کنیم:

wget https://github.com/git/git/archive/v2.18.0.zip -O git.zip

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

unzip git.zip
cd git-*

اینک می‌توانید با وارد کردن دو دستور زیر بسته‌ها را ایجاد (make) کرده و آن‌ها را نصب کنید:

make prefix=/usr/local all
sudo make prefix=/usr/local install

برای اطمینان از این که نصب موفقیت‌آمیز بوده است، می‌توانید دستور git –version را وارد کنید و بدین ترتیب خروجی مرتبطی را دریافت می‌کنید که نسخه Git نصب شده کنونی را مشخص می‌سازد.

اینک که گیت نصب شده است، اگر بخواهید نرم‌افزار گیت خود را به نسخه بالاتری ارتقا بدهید می‌توانید ریپازیتوری را کلون کنید و سپس نسخه جدید را ساخته و نصب نمایید. برای یافتن URL جهت عملیات کلون کردن باید به شاخه یا تگی که می‌خواهید دانلود کنید روی صفحه گیت‌هاب پروژه بروید و سپس URL کلون را در سمت راست انتخاب کنید:

در زمان نگارش این مقاله URL مربوطه به صورت زیر بوده است:

https://github.com/git/git.git

سپس به دایرکتوری اصلی رفته و با استفاده از دستور git clone روی URL کپی شده اقدام به کلون کردن نرم‌افزار بکنید:

cd ~
git clone https://github.com/git/git.git

بدین ترتیب یک دایرکتوری جدید درون دایرکتوری کنونی ایجاد می‌شود که می‌تواند بسته را مجدداً ساخته و به صورت مجدد همانند روش قبل، آن را به عنوان نسخه جدیدتر نصب کنید. بدین ترتیب نسخه قدیمی با نسخه جدیدتر بازنویسی می‌شود:

cd git
make prefix=/usr/local all
sudo make prefix=/usr/local install

در پایان این مراحل می‌تواند مطمئن باشید که نسخه گیت شما به‌روز است.

راه‌اندازی گیت

اینک که گیت را نصب کردید، باید آن را پیکربندی کنید به طوری که پیام‌های کامیت (commit) ایجاد شده شامل اطلاعات صحیحی از شما باشد.

این کار از طریق استفاده از دستور git config صورت می‌گیرد. به طور خاص باید نام و ایمیل خود را ارائه کنیم چون گیت این اطلاعات را در هر کامیت که انجام می‌دهید قرار می‌دهد. می‌توانیم این اطلاعات را با استفاده از دستورهای زیر وارد می‌کنیم:

git config --global user.name "Your Name"
git config --global user.email [e-mail]

می‌توانید همه آیتم‌های پیکربندی تنظیم شده را با وارد کردن دستور زیر مشاهده کنید:

git config –list

خروجی

user.name=Your Name
user.email=[e-mail]
...

اطلاعاتی که اینک وارد کردید در فایل پیکربندی Git ذخیره می‌شوند و می‌توانید آن را در صورت نیاز به طریق دستی با استفاده از یک ویرایشگر متنی به روش زیر ویرایش کنید:

nano ~/.gitconfig

خروجی

~/.gitconfig contents
[user]
name = Your Name
email = [e-mail]

گزینه‌های زیاد دیگری وجود دارند که می‌توان تنظیم کرد؛ اما این دو مورد ضروری هستند. اگر این مرحله را انجام ندهید در زمان انجام کامیت به گیت با هشدارهایی مواجه می‌شوید. بدین ترتیب کار بیشتری برای شما ایجاد می‌شود، زیرا باید کامیت های خود را بازنگری کنید و اطلاعات صحیحی را در آن‌ها وارد نمایید.

منبع: فرادرس

چند نخی (Multi-Threading) در سیستم عامل — راهنمای جامع

منظور از نخ (thread) یک گردش اجرایی از طریق کد پردازشی است که شمارنده برنامه خاص خود را برای ردگیری دستورالعمل‌های اجرایی بعدی دارد. هر نخ شامل ثبات‌های سیستم که متغیرهای کاری کنونی را نگه‌داری می‌کنند و پشته‌ای که شامل تاریخچه اجرایی است نیز می‌شود. در این نوشته به معرفی مفهوم محاسبات چند نخی در سیستم‌های عامل می‌پردازیم.

هر نخ اطلاعاتی شامل قطعه کد، قطعه داده و فایل‌های باز را با نخ‌های همتایش به اشتراک می‌گذارد. زمانی که یک نخ آیتم حافظه قطعه‌ای از کد را تغییر می‌دهد، همه نخ‌های دیگر می‌توانند آن را ببینند.

یک نخ به نام پردازش سبک (lightweight process) نیز نامیده می‌شود. نخ‌ها روشی برای بهبود عملکرد برنامه از طریق موازی‌سازی ارائه می‌کنند. نخ‌ها نشان‌دهنده یک رویکرد نرم‌افزاری برای بهبود عملکرد سیستم عامل از طریق کاهش نخ بالاسری هستند. نخ بالاسری (overhead thread) معادل یک پردازش کلاسیک است.

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

تفاوت‌های بین پردازش و نخ

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

مزیت‌های نخ

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

انواع نخ

نخ‌ها به دو روش زیر پیاده‌سازی می‌شوند:

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

نخ‌های در سطح کاربر

در این حالت کرنل مدیریت نخ از وجود نخ‌ها اطلاعی ندارد. کتابخانه نخ شامل کد لازم برای ایجاد و تخریب نخ، ارسال پیام و داده بین نخ‌ها، زمان‌بندی اجرای نخ و ذخیره‌سازی و بازیابی زمینه‌های نخ است. اپلیکیشن با یک نخ منفرد آغاز می‌شود.

مزیت‌ها

• سوئیچ کردن بین نخ‌ها نیازمند دسترسی به کرنل نیست.
• نخ‌های در سطح کاربر روی هر سیستم عاملی اجرا می‌شوند.
• زمان‌بندی نخ‌های در سطح کاربر می‌توان خاص یک اپلیکیشن باشد.
• نخ‌های سطح کاربر به طور سریعی ایجاد و مدیریت می‌شوند.

معایب

• در یک سیستم عامل معمولی اغلب فراخوانی‌های سیستم مسدود می‌شوند.
• اپلیکیشن چند نخی نمی‌تواند از مزیت چند پردازشی بهره‌مند شود.

نخ‌های سطح کرنل

در این حالت مدیرت نخ از سوی کرنل اجرا می‌شود و هیچ کدِ مدیریت نخی در سطح اپلیکیشن وجود ندارد. نخ‌های کرنل مستقیماً از سوی سیستم عامل پشتیبانی می‌شوند. هر اپلیکیشن می‌تواند طوری برنامه‌نویسی شود که چند نخی باشد. همه نخ‌های درون یک اپلیکیشن در یک پردازش منفرد پشتیبانی می‌شوند.

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

مزیت‌ها

• کرنل می‌تواند به طور همزمان چند نخ از یک پردازش را روی چند پردازش زمان‌بندی کند.
• اگر یک نخ در پردازش مسدود شود، کرنل می‌تواند نخ دیگری را روی همان پردازش زمان‌بندی کند.
• روال‌های کرنل خودشان چند نخی هستند.

معایب

• نخ‌های کرنل عموماً فرایند ایجاد و مدیریت کندتری نسبت به نخ‌های کاربر دارند.
• انتقال کنترل از یک نخ به نخ دیگر درون یک پردازش نیازمند مد سوئیچ روی کرنل است.

مدل‌های چند نخی

برخی از سیستم‌های عامل ترکیبی از نخ‌های سطح کاربر و کرنل ارائه می‌کنند. سولاریس نمونه مناسبی از این رویکرد ترکیبی است. در یک سیستم ترکیبی چندین نخ درون اپلیکیشن یکسان می‌توانند به طور موازی روی چندپردازنده اجرا شوند و بدین ترتیب انسداد سیستم الزامی برای مسدود شدن کل پردازش ندارد. مدل‌های چند نخی سه نوع هستند:

• رابطه چند به جند
• رابطه چند به یک
• رابطه یک به یک

مدل چند به چند

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

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

مدل چند به یک

مدل چند به یک نخ‌های سطح کاربر را به یک نخ در سطح کرنل نگاشت می‌کند. مدیریت نخ در فضای کاربر به وسیله کتابخانه نخ انجام می‌پذیرد. زمانی که یک نخ موجب انسداد سیستم می‌شود، کل پردازش مسدود خواهد شد. در این حالت، هر زمان تنها یک نخ می‌تواند به کرنل دسترسی داشته باشد و از این رو چندین نخ نمی‌توانند به طور موازی در محیط چندپردازنده‌ای اجرا شوند.

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

مدل یک به یک

در مدل رابطه یک به یک برای هر نخ در سطح کاربر یک نخ در سطح کرنل وجود دارد. در این مدل همزمانی بیشتری نسبت به مدل چند به یک وجود دارد. این مدل امکان اجرای نخ دیگر در هنگام انسداد سیستمی یک نخ را فراهم می‌سازد. این مدل از اجرای چنین نخ به طور موازی روی محیط‌های چندپردازنده‌ای پشتیبانی می‌کند.

عیب این مدل آن است که ایجاد نخ‌های در سطح کاربر، نیازمند نخ‌های متناظری در سطح کرنل است. OS/2، ویندوز NT و ویندوز 2000 از مدل رابطه یک به یک استفاده می‌کنند.

تفاوت‌های بین نخ‌های سطح کاربر و سطح کرنل

ردیف	نخ‌های سطح کاربر	نخ‌های سطح کرنل
1	نخ‌های سطح کاربر ایجاد و مدیریت سریع‌تری دارند.	نخ‌های سطح کرنل ایجاد و مدیریت کندتری دارند.
2	نخ‌های سطح کاربر توسط کتابخانه نخ در سطح کاربر پیاده‌سازی می‌شوند.	سیستم عامل از ایجاد نخ‌های سطح کرنل پشتیبانی می‌کند.
3	نخ‌های سطح کاربر یکسان هستند و می‌توانند روی هر سیستم عاملی اجرا شوند.	نخ‌های سطح کرنل خاص هر سیستم عامل هستند.
4	اپلیکیشن‌های چند نخی نمی‌توانند از مزیت چندپردازنده‌ای بودن بهره‌مند شوند.	رویه‌های کرنل خودشان چند نخی هستند. منبع: فرادرس

چگونه از گیت (Git) به طرز موثرتری استفاده کنیم؟ — به زبان ساده

گیت نرم‌افزار بسیار مفیدی است که به منظور کمک به فرایند توسعه پروژه‌های برنامه‌نویسی استفاده می‌شود. گیت هیچ الزام خاصی برای زبان برنامه‌نویسی یا ساختار فایل ندارد و همه چیز بر عهده برنامه‌نویس گذارده شده است تا گردش کاری خود را سازماندهی کند.

در این نوشته فرض شده که شما گیت را روی سیستم خود نصب کرده‌اید و تنظیمات پیکربندی عمومی (مانند نام کاربری و ایمیل) را نیز به طرز صحیحی تنظیم کرده‌اید. اگر چنین نیست، می‌توانید از مقاله «نصب گیت (Git) روی اوبونتو» کمک بگیرید.

پیش از استفاده از گیت برای توسعه کد، بهتر است گردش کار خود را طرح‌ریزی کنید. تصمیم‌گیری در مورد گردش کار معمولاً مبتنی بر اندازه و مقیاس پروژه صورت می‌گیرد. برای این که درکی اولیه از گیت داشته باشید، طراحی یک گردش کاری ساده و تک انشعابی (single branch) کافی خواهد بود. به طور پیش‌فرض نخستین شاخه از هر پروژه گیت به نام «مستر» (master) نامیده می‌شود. در این راهنما با روش ساخت شاخه‌های دیگر نیز آشنا می‌شویم.

در ادامه نخستین پروژه خود را به نام «testing» می‌سازیم. اگر از قبل پروژه‌ای دارید که می‌خواهید به گیت ایمپورت کنید، می‌توانید به بخش «تبدیل پروژه به محیط فضای کار» مراجعه کنید.

ایجاد فضای کار (workspace)

همان طور که هر کس دوست دارد محیط کاری تمیز و مناسبی داشته باشد، این مسئله در مورد محل کدنویسی نیز به خصوص در حالتی که همزمان روی چند پروژه کار شود، صدق می‌کند. پیشنهاد خوب در این زمینه آن است که پوشه‌ای به نام git روی دایرکتوری home سیستم خود داشته باشید که زیرپوشه‌های آن هر یک به یک پروژه مستقل اختصاص داشته باشند.

نخستین کاری که باید برای ایجاد محیط کاری خود انجام دهید، به صورت زیر است:

user@host ~ $ mkdir -p ~/git/testing; cd ~/git/testing

دستور فوق دو کار انجام می‌دهد:

1. یک دایرکتوری به نام git در دایرکتوری home ایجاد می‌کند و سپس یک زیردایرکتوری به نام testing داخل آن ایجاد می‌کند. در واقع پروژه ما درون این زیردایرکتوری ذخیره خواهد شد.
2. ما را به این زیردایرکتوری می‌برد.

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

ما با استفاده از دستور زیر یک فایل تست ایجاد می‌کنیم که در ریپازیتوری که ایجاد می‌کنیم، استفاده خواهد شد:

user@host ~/git/testing $ touch file

زمانی که فایل‌های پروژه در فضای کاری آماده شدند، باید شروع به ردگیری فایل‌ها با گیت بکنیم. در مرحله بعدی این فرایند توصیف خواهد شد.

تبدیل یک پروژه موجود به محیط فضای کاری

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

user@host ~/git/testing $ git init
Initialized empty Git repository in /home/user/git/testing/.git/

زمانی که ریپازیتوری خالی اولیه خود را راه‌اندازی کردیم، می‌توانیم فایل‌ها را به آن اضافه کنیم. در ادامه همه فایل‌ها و دایرکتوری‌ها را به ریپازیتوری جدیداً ایجاد شده اضافه می‌کنیم:

user@host ~/git/testing $ git add.

در این حالت بنا به مصداق ضرب‌المثل «بی‌خبری، خوش‌خبری است»، اگر هیچ خروجی دیده نشود، یعنی همه چیز به درستی پیش رفته است. متأسفانه گیت در همه موارد در صورت بروز اشکال، اطلاع‌رسانی نمی‌کند.

هر زمان که مواردی را به فایل‌ها اضافه کنید یا تغییری ایجاد کنید، باید یک پیام کامیت (commit) بنویسید. در بخش بعدی توضیح می‌دهیم که پیام کامیت چیست و چگونه می‌توان آن را نوشت.

ایجاد یک پیام کامیت

پیام کامیت، پیام کوتاهی است که تغییراتی که صورت گرفته است را توضیح می‌دهد. این پیام برای ارسال تغییرات کد به ریپازیتوری که پوش (push) نامیده می‌شود ضروری است و روش مناسبی برای ارتباط با همکاران توسعه‌دهنده محسوب می‌شود که می‌خواهند تغییرات را مشاهده کنند. در این بخش روش ایجاد کامیت را توضیح می‌دهیم.

پیام‌های کامیت به طور کلی کوتاه هستند و در یک یا دو جمله تغییراتی که ایجاد شده‌اند را توضیح می‌دهند. توضیح همه تغییراتی که صورت گرفته است، پیش از ارسال هر پوش رویه مناسبی است. شما می‌توانید به هر تعداد که دوست دارید پوش کنید. تنها الزام برای هر کامیت این است که باید دست کم یک فایل وجود داشته باشند و همچنین پیامی برای آن تنظیم شود. هر Push باید دست کم یک کامیت داشته باشد.

اگر مثال خود را پیگیری کنیم می‌توانیم پیام نخستین کامیت خود را به صورت زیر تنظیم کنیم:

user@host ~/git/testing $ git commit -m "Initial Commit" -a
[master (root-commit) 1b830f8] initial commit
0 files changed
create mode 100644 file

دو پارامتر مهم در دستور فوق وجود دارد. نخست پارامتر m- است که مشخص می‌سازد پیام کامیت ما در ادامه آمده است. پارامتر دوم a- است که تعیین می‌کنید می‌خواهیم پیام کامیت ما در مورد همه فایل‌های اضافه شده یا تغییر یافته اعمال شود. این وضعیت برای نخستین کامیت مشکلی ندارد؛ اما به طور کلی باید فایل‌ها یا دایرکتوری‌های منفردی که می‌خواهیم کامیت کنیم را تعیین نماییم. همچنین می‌توانیم دستور زیر را برای تعیین فایل خاصی که کامیت می‌کنیم، به کار بگیریم:

user@host ~/git/testing $ git commit -m "Initial Commit" file

برای افزودن فایل‌ها یا دایرکتوری‌های دیگر باید یک فهرست جداشده با کاراکتر اسپیس به انتهای دستور فوق اضافه کنید.

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

ما تا این مرحله از این راهنما، همه کارهای خود را روی سرور محلی انجام داده‌ایم. با این که استفاده محلی از گیت، مواردی که می‌خواهید روش آسانی برای کنترل نسخه فایل‌هایتان داشته باشید، گزینه ایده‌آلی محسوب می‌شود؛ اما اگر می‌خواهید با تیمی از توسعه‌دهندگان کار کنید باید تغییرات را به یک سرور ریموت پوش کنید. در ادامه روش این کار را توضیح می‌دهیم.

در مرحله نخست باید بتوانیم کد خود را از طریق یک URL که مربوط به ریپازیتوری است به آن پوش کنیم و یک نام نیز برای آن تعیین کنیم. برای پیکربندی ریپازیتوری ریموت جهت استفاده و دیدن همه سرورهای ریموت (شما می‌توانید چند سرور ریموت داشته باشید) باید دستور زیر را وارد کنید:

user@host ~/git/testing $ git remote add origin ssh://[e-mail]/repository.git

user@host ~/git/testing $ git remote -v

origin ssh://[e-mail]/repository.git (fetch)

origin ssh://[e-mail]/repository.git (push)

دستور نخست یک سرور ریموت به نام «origin» اضافه می‌کند و URL را به صورت ssh://[e-mail]/repository.git تنظیم می‌کند.

شما می‌توانید نام ریموت را هر چیزی که دوست دارید بگذارید؛ اما URL باید به یک ریپازیتوری ریموت واقعی اشاره کند. برای نمونه اگر بخواهید کد خود را به گیت‌هاب پوش کنید، باید از ریپازیتوری دارای URL ارائه شده از سوی گیت‌هاب استفاده کنید. زمانی که ریموت پیکربندی شد می‌توانید کد خود را پوش کنید.

با دستور زیر می‌توان کد را به سرور ریموت پوش کرد:

user@host ~/git/testing $ git push origin master
Counting objects: 4, done.
Delta compression using up to 2 threads.
Compressing objects: 100% (2/2), done.
Writing objects: 100% (3/3), 266 bytes, done.
Total 3 (delta 1), reused 1 (delta 0)
To ssh://[e-mail]/repository.git
0e78fdf..e6a8ddc master -> master

دستور git push به گیت می‌گوید که می‌خواهید تغییرات را پوش کنید. در دستور فوق «origin» نام سرور ریموت اخیراً پیکربندی‌شده ما است و «master» نیز نام نخستین شاخه یا branch ما محسوب می‌شود. در آینده هر کامیتی را که بخواهید به سرور پوش کنید، می‌توانید به سادگی از دستور git push استفاده کنید.

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

منبع: فرادرس