{"id":12798,"date":"2021-11-21T17:03:49","date_gmt":"2021-11-21T22:03:49","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12798"},"modified":"2026-06-02T14:59:25","modified_gmt":"2026-06-02T18:59:25","slug":"tr-95-21-reducing-contention-for-run-queue-in-shared-memory-multiprocessor-systems","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-21-reducing-contention-for-run-queue-in-shared-memory-multiprocessor-systems\/","title":{"rendered":"TR-95-21: Reducing Contention for Run Queue in Shared-Memory Multiprocessor Systems"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-95-21: Reducing Contention for Run Queue in Shared-Memory Multiprocessor Systems\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n<p>Carleton University<br>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/\">Technical Report<\/a> TR-95-21<br>\nOctober 1995<\/p>\n\n\n\n<h2 id=\"reducing-contention-for-run-queue-in-shared-memory-multiprocessor-systems\" class=\"wp-block-heading tr_t1\">Reducing Contention for Run Queue in Shared-Memory Multiprocessor Systems<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">Sivarama P. Dandamudi<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n<div>\n<h3>Abstract<\/h3>\n<\/div>\n\n\n\n<div class=\"tr_abstract\">\n<p>Performance of parallel processing systems is sensitive to various hardware and software overheads and contention for hardware and software resources. Hardware resources such as interconnection network and memory introduce communication contention and memory contention that could seriously impact overall system performance. Software resources include critical data structures maintained by application software as well as by the system software.In process scheduling context, run queue is a critical data structure that could potentially affect the overall system performance. There are two basic run queue organizations: centralized and distributed. Many shared-memory multiprocessor systems use the centralized organization in which a single global run queue is shared by all processors in the system. We will first identify performance problems associated with these two organizations and then discuss some means to alleviate these problems. We then present a hierarchical task queue organization that incorporates the merits of these two queue organizations. Performance of the hierarchical organization is shown to inherit the good characteristics of the centralized and distributed organizations while avoiding the pitfalls associated with them. Thus, the hierarchical organization is useful in building large-scale multiprocessor systems.<\/p>\n<\/div>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-95-21.pdf\">TR-95-21.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-95-21 October 1995 Reducing Contention for Run Queue in Shared-Memory Multiprocessor Systems Sivarama P. Dandamudi Abstract Performance of parallel processing systems is sensitive to various hardware and software overheads and contention for hardware and software resources. Hardware resources such as interconnection network and memory introduce communication contention and memory contention that [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11736,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-12798","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12798","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=12798"}],"version-history":[{"count":3,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12798\/revisions"}],"predecessor-version":[{"id":12804,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12798\/revisions\/12804"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11736"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12798"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12798"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}