Learning-Assisted Schedulability Analysis: Opportunities and Limitations

Learning-Assisted Schedulability Analysis: Opportunities and Limitations | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Learning-Assisted Schedulability Analysis: Opportunities and Limitations Sanjoy Baruah, Pontus Ekberg, Marion Sudvarg This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-6113316/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 02 Jul, 2025 Read the published version in Real-Time Systems → Version 1 posted 14 You are reading this latest preprint version Abstract We present the first (to our knowledge) Deep-Learning based framework for realtime schedulability-analysis that guarantees to never incorrectly mis-classify an unschedulable system as being schedulable, and is hence suitable for use in safetycritical scenarios. We relate applicability of this framework to well-understood concepts in computational complexity theory: membership in the complexity class NP. We apply the framework upon the widely-studied schedulability analysis problems of determining whether a given constrained-deadline sporadic task system is schedulable on a preemptive uniprocessor under both Deadline-Monotonic and EDF scheduling. As a proof-of-concept, we implement our framework for Deadline-Monotonic scheduling, and demonstrate that it has a predictive accuracy exceeding 70% for systems of as many as 20 tasks without making any unsafe predictions. Furthermore, the implementation has very small (<1 ms on two widely-used embedded platforms; <4 μs on an embedded FPGA) and highly predictable running times. Schedulability analysis Computational complexity: NP-completeness Learning-Enabled Components (LECs) Deep Learning Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 02 Jul, 2025 Read the published version in Real-Time Systems → Version 1 posted Editorial decision: Revision requested 23 Apr, 2025 Reviews received at journal 30 Mar, 2025 Reviews received at journal 28 Mar, 2025 Reviews received at journal 18 Mar, 2025 Reviews received at journal 16 Mar, 2025 Reviewers agreed at journal 02 Mar, 2025 Reviewers agreed at journal 02 Mar, 2025 Reviewers agreed at journal 02 Mar, 2025 Reviewers agreed at journal 28 Feb, 2025 Reviewers agreed at journal 28 Feb, 2025 Reviewers invited by journal 28 Feb, 2025 Editor assigned by journal 27 Feb, 2025 Submission checks completed at journal 27 Feb, 2025 First submitted to journal 26 Feb, 2025 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-6113316","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":423001654,"identity":"dbfd9089-2414-40a5-8089-44cff79ec31b","order_by":0,"name":"Sanjoy Baruah","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAv0lEQVRIiWNgGAWjYBACAxDB2GADpg4wMDATrSWNAaSaJC2HSdBizn72mcTPHecTN5w/f+AAQ4V1YgMhLZY96WaSvWduJ264kQy05Uw6YS0GB9LYJHjbbuduuAF0GGPbYSK0nH/GJvm37VzuhvOHgVr+EaPlRhqbNG/bgdwNB4AOA4YDEX6Z8YzZWrYtuX7mjWSDAwnH0o0JajHnT2O8+bbNzpjv/MGHDz7UWMsS1IIKEkhTPgpGwSgYBaMAFwAAap9FAlaWLRIAAAAASUVORK5CYII=","orcid":"","institution":"Washington University in St. Louis","correspondingAuthor":true,"prefix":"","firstName":"Sanjoy","middleName":"","lastName":"Baruah","suffix":""},{"id":423001656,"identity":"cd6895f2-c55a-4c3d-9e9d-cc67d8fe6815","order_by":1,"name":"Pontus Ekberg","email":"","orcid":"","institution":"Uppsala University","correspondingAuthor":false,"prefix":"","firstName":"Pontus","middleName":"","lastName":"Ekberg","suffix":""},{"id":423001658,"identity":"d49b2a9b-3da7-4c2d-a9a9-cde511ad6633","order_by":2,"name":"Marion Sudvarg","email":"","orcid":"","institution":"Washington University in St. Louis","correspondingAuthor":false,"prefix":"","firstName":"Marion","middleName":"","lastName":"Sudvarg","suffix":""}],"badges":[],"createdAt":"2025-02-26 12:53:11","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-6113316/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-6113316/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1007/s11241-025-09450-y","type":"published","date":"2025-07-02T15:58:14+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":86180296,"identity":"06fecd70-02e7-4042-ab2d-90ab91ee951d","added_by":"auto","created_at":"2025-07-07 16:22:05","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":599025,"visible":true,"origin":"","legend":"","description":"","filename":"Archive.pdf","url":"https://assets-eu.researchsquare.com/files/rs-6113316/v1_covered_1158687f-0296-43fa-9aea-71407ceb9d52.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Learning-Assisted Schedulability Analysis: Opportunities and Limitations","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"real-time-systems","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"time","sideBox":"Learn more about [Real-Time Systems](http://link.springer.com/journal/11241)","snPcode":"11241","submissionUrl":"https://submission.nature.com/new-submission/11241/3","title":"Real-Time Systems","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"Schedulability analysis, Computational complexity: NP-completeness, Learning-Enabled Components (LECs), Deep Learning","lastPublishedDoi":"10.21203/rs.3.rs-6113316/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-6113316/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eWe present the first (to our knowledge) Deep-Learning based framework for realtime schedulability-analysis that guarantees to never incorrectly mis-classify an unschedulable system as being schedulable, and is hence suitable for use in safetycritical scenarios. We relate applicability of this framework to well-understood concepts in computational complexity theory: membership in the complexity class NP. We apply the framework upon the widely-studied schedulability analysis problems of determining whether a given constrained-deadline sporadic task system is schedulable on a preemptive uniprocessor under both Deadline-Monotonic and EDF scheduling. As a proof-of-concept, we implement our framework for Deadline-Monotonic scheduling, and demonstrate that it has a predictive accuracy exceeding 70% for systems of as many as 20 tasks without making any unsafe predictions. Furthermore, the implementation has very small (\u0026lt;1 ms on two widely-used embedded platforms; \u0026lt;4 μs on an embedded FPGA) and highly predictable running times.\u003c/p\u003e","manuscriptTitle":"Learning-Assisted Schedulability Analysis: Opportunities and Limitations","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-03-03 10:25:39","doi":"10.21203/rs.3.rs-6113316/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2025-04-23T13:00:23+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-03-30T15:59:26+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-03-28T16:34:18+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-03-19T00:37:18+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-03-16T15:00:41+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"225903887927694757297138412155101270674","date":"2025-03-02T21:37:20+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"313393326362728447863666118463137856457","date":"2025-03-02T18:46:00+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"185023592146554970842121461386516953623","date":"2025-03-02T18:32:12+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"274918356346403219329050480383382347727","date":"2025-02-28T18:34:20+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"63181456943345916717281622613932515684","date":"2025-02-28T18:30:51+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2025-02-28T18:19:53+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2025-02-27T07:46:29+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2025-02-27T07:44:44+00:00","index":"","fulltext":""},{"type":"submitted","content":"Real-Time Systems","date":"2025-02-26T12:40:19+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"real-time-systems","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"time","sideBox":"Learn more about [Real-Time Systems](http://link.springer.com/journal/11241)","snPcode":"11241","submissionUrl":"https://submission.nature.com/new-submission/11241/3","title":"Real-Time Systems","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"00ced026-3153-453c-ba21-368aa8c75eb5","owner":[],"postedDate":"March 3rd, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2025-07-07T16:16:35+00:00","versionOfRecord":{"articleIdentity":"rs-6113316","link":"https://doi.org/10.1007/s11241-025-09450-y","journal":{"identity":"real-time-systems","isVorOnly":false,"title":"Real-Time Systems"},"publishedOn":"2025-07-02 15:58:14","publishedOnDateReadable":"July 2nd, 2025"},"versionCreatedAt":"2025-03-03 10:25:39","video":"","vorDoi":"10.1007/s11241-025-09450-y","vorDoiUrl":"https://doi.org/10.1007/s11241-025-09450-y","workflowStages":[]},"version":"v1","identity":"rs-6113316","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-6113316","identity":"rs-6113316","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}