جریان کار، گردش کار و یا Workflow عبارت است از:
مجموعهای از فعالیتها که برای تکمیل یک وظیفه لازم است. به بیانی دیگر، گردش کار به افراد درمستندسازی و مدیریت وظایف در پروژه ها کمک می کند و این امر با پیادهسازی فرایندهای کاری روی مستندات محقق میگردد.
جریان کار در حوزههای بسیاری از جمله محاسبات ابری کاربرد دارد و تعریف آن به صورت تخصصیتر در این حوزه به صورت زیر است:
محاسباتی سازمان یافته با تمرگز بر روی داده که دارای محاسبات منظم و الگوهای دسترسی به داده است
که معمولا آن را به وسیله کرافهای جهتدار بدون دور (DAG) نمایش میدهند و مدلسازی میکنند. جریانهای کار چالشهایی را در مدیریت منابع زیرساختهای گرید و ابر برای محققین به وجود میآورد. در برخی از مسائل با مقیاس بزرگ، هر جریان کار از چندین جریان کار مرتبط که در یک دسته قرار میگیرند، تشکیل میشود که پیچیدگی بیشتری را در مدیریت منابع و زمانبندی به دنبال خواهد داشت. در هر صورت طراحی الگوریتم مقیاسپذیری که بتواند نظم محاسبات جریان کار را در نظر بگیرد بسیار با اهمیت است. همان طور که قبلا هم اشاره شد، جریانهای کار در مسائل مختلفی کاربرد دارند که به عنوان نمونه به برخی از کاربردهای آنها در مسائل علمی اشاره میکنیم:
۱. پروژه سایبرشیک(CyberShake): از دستههای جریان کار استفاده میکند تا تقشههای مخاطره زمینلرزه را تولید کند. هر جریان کار در دسته سایبرشیک برای یک منطقه خاص جغرافیایی، یک منحنی مخاطره تولید میکند و در نهایت از منحنیهای تولید شده برای تشکیل یک نقشه مخاطره یا منحنی کلی استفاده میشود. طی تحقیقاتی در سال ۲۰۱۳ از سایبرشیک جهت تولید یک سری نقشه مخاطره برای حدود ۲۸۶ قسمت استفاده شد که نیاز به دستهای شامل ۲۲۸۸ جریان کار داشت.
۲. پروژه ژنوم(GENOME): طرح نقشه برداری و تعیین توالی کل ژنوم انسان اولین بار در سال ۱۹۸۴ میلادی عنوان شد. تأمین قسمتی از بودجه این پروژه را دپارتمان انرژی آمریکا به عهده گرفت و در سال ۱۹۸۸ کنگره آمریکا به طور رسمی اجرای پروژه ژنوم انسان را از از سال ۱۹۹۱ به مدت ۱۵ سال تصویب کرد. در این سال انستیتو بهداشت ملی آمریکا نیز برای اجرای این طرح اعلام آمادگی کرد و بعد از آن کشورهای انگلیس، فرانسه، آلمان و ژاپن نیز به این پروژه پیوستند. در سال ۱۹۹۸ سازمان ژنوم انسان ایجاد و تا الآن اهدافی نظیر موارد زیر را دنبال میکند:
- تعیین نقشه دقیق ژنتیکی کرومزومها
- تهیه نقشه فیزیکی کروموزومهای اورگانیسمهایی که به عنوان مدل انتخاب شدهاند
- تهیه توالی کل ژنوم انسان
- ایجاد شبکههای ارتباطی و بانکهای اطلاعاتی
۳. پروژه لیگو(LIGO): یک آزمایش بزرگ فیزیکی است که به صورت مشترک توسط مؤسسه فناوری کالیفرنیا و مؤسسه فناوری ماساچوست بنا شده و هدف آن آشکارسازی مستقیم امواج گرانشی است.
جریانهای کار ممکن است در پارامترهای مختلفی مانند اولویت با یکدیگر تفاوت داشته باشند. برای مثال در سایبرشیک بعضی از مناطق جغرافیایی ممکن است جمعیت بیشتری داشته باشند و یا تجهیزات حساسی مانند نیروگاهها در آنها باشد، در حالی که مناطق دیگر اهمیت کمتری دارند. دانشمندان جریانهای کار داخل چنین دستههایی را اولویتبندی میکنند. بنابراین جریانهای کار مهمتر، زودتر به پردازش میشوند. این کار آنها را قادر میسازد که نتایج حساس و بحرانی را زودتر ببینند. همچنین به آنها کمک میکند تا مهمترین جریانهای کار را وقتی زمان و منابع مالی در دسترس برای محاسبات محدود هستند، انتخاب کنند.
مهمترین اصطلاحی که در جریانهای کار با آن روبرو میشویم مسیر بحرانی است که عبارت است از:
طولانیترین مسیر از وظیفه اول تا آخرین وظیفه جریان کار که در بسیاری از محاسبات و تصمیمات مربوط به جریانهای کار(مانند: زمانبندی)، از آن استفاده میشود.
تشخیص زمان مسیر بحرانی، در پروژههایی که در آنها جریانهای کار باید قبل از زمان مشخصی(Deadline) پردازش شوند به کار میرود. در چنین کاربردهایی، زمانی که به اجرای جریان کار اختصاص داده میشود نباید کمتر از زمان اجرای مسیر بحرانی باشد.
البته مسیرهای متفاوت جریان کار را میتوان به صورت موازی نیز پردازش و زمانبندی کرد. برای این کار نیاز داریم تا تخمین نسبتا دقیقی از زمان مورد نیاز برای پردازش کل جریان کار را به کمک تکنیکهایی پیشبینی کنیم. البته در این صورت باز هم زمان اختصاص داده شده برای پردازش کل جریان کار نباید کمتر از زمان اجرای مسیر بحرانی باشد.
چگونگی به دست آوردن طولانیترین مسیر جریان کار به عنوان یک موضوع جالب، مورد توجه بسیاری از محققین نیز بوده است که در قسمت مراجع به برخی از آنها اشاره شده است.
در ادامه برنامهی سادهای را به کمک زبان جاوا توسعه میدهیم که توانایی مشخص کردن مسیرهای بحرانی را داشته باشد.
اولین قدم در تشخیص مسیر بحرانی، ساختن مدلی از پروژه است که موراد زیر را در نظر بگیرد:
- لیستی از وظیفهها که نیاز داریم در پروژه انجام شوند.
- زمانی که هر وظیفه نیاز دارد تا به طور کامل پردازش شود.
- وابستگیهای میان وظیفهها.
برای درک بهتر، شکل زیر را در نظر بگیرید:
نمایی از یک جریان کار نمایش داده شده به صورت گراف جهت دار بدون دور (DAG)
در این شکل نام هر وظیفه با یک حرف بزرگ انگلیسی مشحص شده و عدد داخل هر دایره معرف زمان مورد نیاز وظیفه برای پردازش شدن است. همچنین عددهای نمایش داده شده در بالا سمت چپ و راست به ترتیب زودترین زمان ممکن برای شروع و پایان وظیفه و عددهای نمایش داده شده در پایین سمت چپ و راست به ترتیب زمان شروع شدن و پایان یافتن پردازش هر وظیفه را نمایش میدهند.
دایرههای مشخص شده در پایین تصویر که با فلشهای قرمز رنگ به هم متصل شدهاند، مسیر بحرانی این جریان کار را تشکیل میدهند.
برای مدل کردن وظیفهها از کلاس Activity استفاده میکنیم که خواص هر وظیفه مانند: ID، description، زودترین زمان شروع(est)، دیرترین زمان شروع(lst)، زودترین زمان پایان(eet) و دیرترین زمان پایان(let) را توصیف میکند.
وابستگیهای هر وظیفه نیز در دو آرایه successors و predecessors نگهداری میشود.
قسمتی از پیادهسازی این کلاس در قطعه کد زیر نمایش داده شده است.
قسمتی از پیاده سازی کلاس Activity
public class Activity { private String id; private String description; private int duration; private int est; private int lst; private int eet; private int let; private Activity[] successors; private Activity[] predecessors; ... }
این برنامه از اطلاعات وظیفهها برای محاسبه مسیر بحرانی استفاده میکند و با توجه به زودترین و دیرترین زمانی که یک وظیفه بدون نقض محدودیهای مسئله میتواند پردازش شود مسیر بحرانی را مشخص میکند. همچنین در این فرآیند، وظیفههایی که بحرانی هستند (در مسیر بحرانی حضور دارند) و وظایفی که پردازش آنها بدون نقض محدودیتهای مسئله میتواند با تأخیر انجام شود، مشخص میشوند.
برای این منظور از دو متد WalkListAhead و WalkListAback استفاده میکنیم.
متد WalkListAhead آرایه حاوی وظیفهها را دریافت میکند و به صورت رو به جلو حرکت کرده تا زودترین زمان شروع و پایان برای هر وظیفه را محاسبه کند.
و بعد از آن
متد WalkListAback آرایه حاوی وظیفهها را دریافت میکند و به صورت رو به عقب حرکت کرده تا دیرترین زمان شروع و پایان برای هر وظیفه را محاسبه کند.
پیادهسازی این دو متد در قطعه کد زیر نمایش داده شده است.
پیادهسازی متدهای WalkListAhead و WalkListAback
private static Activity[] WalkListAhead(Activity[] list) { list[0].setEet(list[0].getEst() + list[0].getDuration()); for (int i = 1; i < na; i++) { for (Activity activity : list[i].getPredecessors()) { if (list[i].getEst() < activity.getEet()) { list[i].setEst(activity.getEet()); } } list[i].setEet(list[i].getEst() + list[i].getDuration()); } return list; } private static Activity[] WalkListAback(Activity[] list) { list[na - 1].setLet(list[na - 1].getEet()); list[na - 1].setLst(list[na - 1].getLet() - list[na - 1].getDuration()); for (int i = na - 2; i >= 0; i--) { for (Activity activity : list[i].getSuccessors()) { if (list[i].getLet() == 0) { list[i].setLet(activity.getLst()); } else if (list[i].getLet() > activity.getLst()) { list[i].setLet(activity.getLst()); } } list[i].setLst(list[i].getLet() - list[i].getDuration()); } return list;
برای محاسبه مسیر بحرانی متد CriticalPath صفر بودن اختلاف میان زودترین دیرترین و زودترین زمان پایان هر وظیفه و همچنین زودترین زمان پایان و شروع هر وظیفه را بررسی میگند تا در صورت بحرانی بودن آن، ID آن را ذخیره کند و نمایش دهد. همچنین در پایان، مجموع زمانهای وظایف بحرانی به عنوان زمان مسیر بحرانی، توسط این متد در خروجی نمایش داده خواهد شد.
پیادهسازی این متد در قطعه کد زیر نمایش داده شده است.
پیادهسازی متد CriticalPath
private static void CriticalPath(Activity[] list) { System.out.println("\n Critical Path: "); for (Activity activity : list) { if ((activity.getEet() - activity.getLet() == 0) && (activity.getEst() - activity.getLst() == 0)) { System.out.println(activity.getId()); } } System.out.println("\n\n Total duration: " + list[list.length - 1].getEet() + "\n\n"); }
خروجی این برنامه با ورودی جریان کار نمایش داده شده در شکل این مثال به صورت زیر خواهد بود:
خروجی برنامه
کد منبع این برنامه از طریق صفحه آن در سایت GitLab قابل دسترس است.
مراجع:
- https://bpms.rayvarz.com/content/گردش-کار-workflow
- Introduction to Workflows
- What is Workflow?
- An integrated task computation and data management scheduling strategy for workflow applications in cloud environments
- http://www.nature.com/scitable/topicpage/dna-sequencing-technologies-key-to-the-human-828
- Metrics for heterogeneous scientific workflows: A case study of an earthquake science application
- http://ligo.org/about.php
موفق باشید.