الگوریتم‌های چندریسمانی
موقعیت‌های چالش‌آمیز

یک الگوریتم چند ریسمانی، قطعی (به انگلیسی: Deterministic) است اگر همیشه برای یک ورودی خاص، خروجی یکسان تولید کند(مستقل از اینکه دستورالعمل‌ها چگونه روی پردازنده‌ها برنامه‌ریزی می‌شوند) و غیرقطعی (به انگلیسی: Nondeterministic) است اگر رفتار آن‌ها در اجراهای مختلف با هم تفاوت داشته باشد. خیلی مواقع یک الگوریتم چند ریسمانی که باید قطعی باشد نمی‌تواند به این هدف دست یابد، چون حاوی یک چالش قطعیت است. موقعیت‌های چالش‌آمیز، مخرب همزمان سازی هستند. چند خطای معروف ناشی از این موقعیت‌ها عبارتند از دستگاه تابشی therac-25 که باعث مرگ سه نفر و مجروح شدن چندین نفر دیگر شد و قطع برق امریکای شمالی در سال ۲۰۰۳ که بیش از ۵۰ میلیون نفر از آن رنج بردند. یافتن این اشکالات مهلک بسیار دشوار است. ممکن است روزهای متوالی در آزمایشگاه برنامه خود را بدون هیچ مشکلی تست کنید، ولی در نهایت هنگام عمل به خطاهای عجیب و نادر بر بخورید.. یک چالش قطعیت زمانی رخ می‌دهد که دو دستورالعمل منقطا موازی به یک خانه از حافظه دسترسی داشته باشند و حداقل یکی از آن‌ها در آن خانه حافظه بازنویسی انجام دهد. رویه زیر حالت چالش‌آمیز را نشان می‌دهد:
RACE()
X = ۰
Parallel for i = 1 to 2
X = x + 1
Print x
پس از مقدار دهی اولیه x  با ۰ در خط ۱، رویه RACE دو ریسمان موازی می‌سازد که هر دوی آن‌ها x را در خط ۳ افزایش می‌دهند. با این که به نظر می‌رسد RACE همیشه باشد مقدار ۲ را چاپ کند (نسخه سریال آن قطعاً همین کار را می‌کند) ممکن است مقدار ۱ را چاپ کند. اما این ناسازگاری چه گونه به وجود می‌آید؟
وقتی یک پردازنده مقدار x را افزایش می‌دهد این عملیات غیرقابل تقسیم است و لی خود از چند دستورالعمل تشکیل می‌شود:
1. خواندن x از حافظه و نوشتن آن روی یکی از ثباتهای پردازنده
۲. افزایش مقدار ثبات
3. نوشتن مقدار ثبات در حافظه مربوط به x
شکل زیر یک Dag محاسباتی است که اجرای رویه RACE را نشان می‌دهد که در آن ریسمان‌ها به دستورالعمل‌های تکی شکسته می‌شوند.
در جدول زیر نیز مقادیر را برای اجرایی نشان می‌دهد که در آن ناهنجاری بروز کرده‌است.
| r2 | r3 | x | steps |
| --- | --- | --- | --- |
| - | - | ۰ | ۱ |
| - | ۰ | ۰ | ۲ |
| - | ۱ | ۰ | ۳ |
| ۰ | ۱ | ۰ | ۴ |
| ۱ | ۱ | ۰ | ۵ |
| ۱ | ۱ | ۱ | ۶ |
| ۱ | ۱ | ۱ | ۷ |
مقدار x در حافظه ذخیره شده‌است و r1, r2 ثباتهای(به انگلیسی: Register) پردازنده هستند. در مرحله ۱ یکی از پردازنده‌ها x  را برابر ۰ قرار می‌دهد. در مراحل ۲ و ۳ پردازنده ۱ مقدار x را از حافظه خوانده و در ثبات r1 قرار می‌دهد. در این مرحله پردازنده ۲ وارد عمل می‌شود ودستورالعمل‌های ۶ تا ۴ را انجام می‌دهد. پردازنده ۲ مقدار x را از حافظه خوانده و در ثبات r2 می‌ریزد و آن را افزایش می‌دهد که مقدار ۱ را برای r1 تولید می‌کند و سپس مقدار حاصل را در x می‌ریزد. اکنون پردازنده ۱ با مرحله ۷ بازمی‌گردد که ذخیره مقدار ۱ مربوط به r1 در x است که در واقع x  را تغییر نمی‌دهد. بنابراین در مرحله ۸ مقدار ۱ در خروجی چاپ می‌شود برعکس حالت سریال که در آن مقدار ۲ را در خروجی خواهیم داشت.
در واقع بسیاری از اجراها باعث این رخداد نمی‌شوند. مثلاً اگر ترتیب اجرا به صورت <۱,۲,۳,۴,۵,۶,۷,۸> باشد به نتیجه صحیح دست پیدا می‌کنیم. این مشکل چالش‌های قطعیت است. معمولاً اکثر ترتیب‌ها نتیجه درستی را تولید می‌کنند. در نتیجه انجام تست برای تشخیص این چالش‌ها دشوار است. ممکن است روزها برنامه خود را تست کرده و هیچ خطایی نیابید ولی در عمل زمانی که خروجی برنامه حیاتی است، با توقف ناگهانی روبرو شوید.
با اینکه می‌توان از طرق مختلف مثلاً انحصار متقابل (به انگلیسی: Mutual Exclusion) این چالش را برطرف کرد ولی در اینجا به سادگی اطمینان حاصل می‌کنیم که ریسمانهایی که به‌طور موازی کار می‌کنند مستقل هستند. یعنی هیچ چالشی نسبت به یکدیگر ندارند. بنابراین در یک ساختار parallel forتمام تکرارها باید مستقل از یکدیگر باشند. بین spawn ,sync متناظر کر فرزند تشکیل شده باید مستقل از کد پدر باشد که شامل کر فرزندان تکثیر یا فراخوانی شده اضافی هم می‌شود.