• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    The method according to the present invention detects a blocking task during a context switch executed by the basic real-time operating system 406 and prevents the blocking task from operating during the period in which the task is blocked.
    公开号:KR20030015234A
    申请号:KR1020027014833
    申请日:2002-01-30
    公开日:2003-02-20
    发明作者:엠. 오테로페레즈클라라；에프. 엠. 스테펜스엘리사베스；제이. 브릴레인더
    申请人:코닌클리케 필립스 일렉트로닉스 엔.브이.；
    IPC主号:
    专利说明:

    Method of AND system for withdrawing budget from a blocking task}
    [5] Method embodiments of the kind described above are known from US Pat. No. 6,108,683. Here, a user-level process scheduler is disclosed as a real-time class process scheduler space that can be used for multimedia processing. The real time class process scheduler is a fixed priority process scheduler supported by the operating system. The user level process scheduler allocates CPU time to the user process, while at the same time, the user level process scheduler provides a blocking detection process with a lower priority than or equal to the user process. When a user process is blocked due to input / output waiting, the user level process scheduler allocates CPU time to the blocking detection process. The block detection process then detects the occurrence of the block and informs the user level process scheduler of the block occurrence. By notifying this occurrence, the user level process scheduler recognizes that the execution of the user process is stopped or stopped, and the user level process causes another user process to run. In addition, the user level process scheduler is notified by reporting the ready state detected when the state of the user process changes to a ready or executable state indicating that the user process can be executed. When the user level process scheduler receives this notification indicating the detection of a ready state, the user level process scheduler again allocates CPU time to the user process.
    [1] The present invention provides a first step of initiating the first task to operate during a period,
    [2] And a second step of detecting that the first task blocks during the interval.
    [3] In addition, the present invention provides a running means configured to operate the first task during an interval;
    [4] It relates to a system for scheduling a first task comprising detection means (412) configured to detect a blocked state of the first task.
    [13] 1 shows a pipeline or streaming architecture.
    [14] 2 shows a missing deadline of a task.
    [15] 3 shows the main steps of an embodiment of the method according to the invention.
    [16] 4 schematically shows the most important parts of an embodiment according to the invention;
    [17] 5 shows schematically a television set comprising an embodiment of a system according to the invention.
    [18] 6 schematically illustrates a set top box comprising an embodiment of a system according to the invention.
    [6] It is an object of the invention to provide a method as described above, which adjusts the blocking state of a task in an improved manner. To achieve this object, the method according to the invention is characterized in that the method further comprises a third step of preventing the first task from resuming operation during the interval. By preventing the first task from resuming operation during the interval where the first task is detected to block, other tasks are prevented from missing their deadlines. Deadlines represent a time stamp before the task has to execute a significant amount of work within the interval. The deadline may be the same as each section. If the task is not satisfied with its deadline in the interval, the overall performance of the system may be degraded. During the time the task is blocked, other tasks can be prevented from progressing, so that these other tasks also miss their deadlines. In order to prevent the task being blocked from interfering with other tasks, causing other tasks to miss their deadlines, the task being blocked is prevented from resuming during the period in which it is being blocked.
    [7] An embodiment of the method according to the invention is disclosed in claim 2. By using context switch information, either provide an individual blocking detection task that must be scheduled by the real-time operating system, or poll each task in predetermined intervals and that is There is no need to provide a polling mechanism to query whether it is blocked or not. The real-time operating system may make a context switch in which the currently running task is suspended and another task resumes. The real-time operating system may provide interfaces or hooks to link-in software that is a link that may be executed during this context switch. Thereafter, the link-in software can access information about tasks that are held and resumed during the context switch and use the information to detect whether the held task has been blocked.
    [8] An embodiment of the method according to the invention is disclosed in claim 3. By using context switch information, the blocking of a task can be accomplished by using the provided interfaces and using the underlying real-time operating system instead of adding additional interfaces or information to the task itself or by adding a designated blocking detection task to the system. It can be derived from possible information. For example, when Rate Monotonic Scheduling (RAM) is applied to schedule tasks, the priority of the pending task and the priority of the resumed task may be used during the context switch. Within the RMS, tasks with longer intervals have lower priority than tasks with shorter intervals, and scheduling of tasks with higher priority precedes tasks with lower priority. Each task is allocated a budget of resources that allow the task to spend during the interval to meet its deadline for the interval. When a held task has a higher priority than the task being resumed during the interval, the high priority task does not spend the budget allocated for that interval, after which the suspended task is blocked.
    [9] An embodiment according to the invention is disclosed in claim 4. By withdraw the remaining budget from the first blocking task, this first blocking task is prevented from being resumed in the same interval as it was withheld. Therefore, this first blocking task ensures that other tasks do not miss their deadlines. This is derived from the conditions that must be met for the task to resume during the interval. One of these conditions is that the task must have a remaining budget to spend during the interval. When the task does not have a remaining budget to spend during the interval, the underlying real-time operating system does not resume the task to operate during this interval.
    [10] It is a further object of the present invention to provide a system as described above for adjusting the blocking state of a task in an improved manner. In order to achieve this object, a system for scheduling a first task according to the invention is characterized in that it comprises prevention means which are configured to prevent the first task from operating and resuming during the interval.
    [11] Embodiments of the system according to the invention are disclosed in claim 6.
    [12] The invention is illustrated by the embodiments illustrated by the accompanying drawings.
    [19] Today, continuous media processing is being performed by more and more programmable components than designated single function components. One of the features of continuous media processing, as required for audio and video, is the presence of time constrains, also called deadlines. In order to adjust this data properly, the system must observe timing constraints and ensure sufficient system resources for processing. Since real-time resources are finite, sufficient system resources cannot be reserved for a particular processing session. This can cause tasks to miss their deadlines, degrade system performance, and prevent optimal use of available resources.
    [20] In high quality video systems, a task may have many predetermined intervals while being allowed to operate, in addition, all the intervals of the task may be the same length and they may be continuous. The budget of resources allowed for a task to consume during each interval is called the periodic budget. The periodic budgets of the task may be the same for each interval or the periodic budgets may vary for each interval. Tasks may have deadlines that represent timestamps before the task has to perform a significant amount of work within the interval. Here, the deadline is equal to the end of the section. If the task does not meet its deadline within the interval, the overall performance of the system may be degraded.
    [21] An embodiment of the method according to the invention uses a commercially available real-time operating system called pSOS. Other real-time operating systems that support fixed priority scheduling, such as VxWorks, can also be used. The real-time operating system schedules other tasks based on the priority of the task, and a task with a higher priority precedes a task with a lower priority. The task receives a priority based on a fixed priority scheduling technique rate monotonic scheduling (RMS). This means that a task with a longer interval has a lower priority than a task with a shorter interval. When two tasks have the same interval, the task with the smaller budget gets higher priority. The priority calculated in this way is called Rate Monotonic Priority (RM). In order for the task to spend its budgets over the interval, the task's priority goes up to the RM priority. Once the budget is exhausted, the task's priority is set to the background priority. Background priority is the lowest priority. When the priority of a task is set to RM priority, its budget is enabled, and when the task's priority is set to background priority, its budget is disabled.
    [22] The operating system enables budgets and disables them. When the budget is enabled, the task resumes or enters the system. When the budget is disabled, the task is suspended or leaves the system. During the context switch executed by the operating system, the task enters the system while another task leaves the system. The operating system provides interfaces to link in an embodiment of the method according to the invention that can be executed during a context switch. This allows the programmer to extend the functionality of the underlying operating system. Extended functionality can be used to improve the performance of the system.
    [23] 1 shows an example of a pipelined or streaming architecture in which tasks executing continuous media processing are linked to each other by queues. Task 102 receives input data from its input queue 106, processes the input data, and places the obtained output data in output queue 108. The output queue of task 102 serves as the input queue of subsequent task 104. Input queues and output queues are bounded queues, meaning that they have a limited capacity to hold data that can be processed by a task. Within this pipeline or streaming architecture, a task can block when its input queue is empty or its output queue is sufficient. This can happen when the task is very fast or runs ahead. An embodiment of the method according to the present invention as described below prevents blocking tasks such as task 102 from interfering with the processing of non-blocking tasks such as task 104.
    [24] 2 shows an example of a deadline miss of a task. Here, task 202 is a periodic task with priority P 202 , interval T 202 = 5 and periodic budget B 202 = 2, and task 206 is priority P 202 , interval T 206 = 6 and periodic budget B 206 Regular task with = 3. Task 202 is a high priority task because its interval is smaller than the interval of task 206.
    [25] T 202 <T 206 => P 202 > P 206
    [26] Each task is ready to operate at the start of its intervals, and therefore it is started up at the beginning of the interval. The arrow indicates the start of the interval, T ij represents the interval T of task i for interval j, and B ij represents the periodic budget B of task i for interval j.
    [27] 2, the task 202 starts at 210, so it is the start of the first interval T 202,1. At 212, task 202 spends its budget B 202,1 . The real-time operating system pSOS suspends task 202 and initiates task 206 to operate at 2112. Second interval T 202,2 begins at 214. However, from 214 to 216, task 202 is blocked while the task does not spend its regular budget. Second interval T 202, 2 of task 206 begins at 216. Since each task is ready to operate at the start of its interval, task 202 is blocked and task 026 starts operation at 216. However, at 218, task 202 is no longer blocked, and since 202 has a higher priority than 206, task 202 preempts task 206 at 218. However, as can be derived from FIG. 2, at this moment, task 206 spends less spent budget CB 206,2 than its regular budget B 206,2 :
    [28] CB 206,2 = 1 and B 206,2 = 3 => CB 206,2 <B 206,2
    [29] At this time, the remaining budget RB 206,2 of task 206 is RB 206,2 = B 206,2 -B 206,2 = 2.
    [30] Task 202 spends its full budget B 202,2 . Since the next interval T 202,3 of the task 202 is initiated at 220, and this is the start of the third period of the task 202, the priority of the task (202) is higher than the priority of the task 206, a task 202 begins operation at 220. When task 220 spends its full budget B 202,3 , task 202 is suspended and task 206 begins to spend its remaining budget RB 206,2 . At 224, task 206 misses its deadline because the third interval of task 206 begins before task 206 spends the remaining budget RB 206,2 . As a result of resuming the blocking task with the higher priority, the missed deadline of the task with the lower priority is prevented by the main steps of the embodiment of the method according to the invention as shown in FIG.
    [31] 3 shows the main steps of an embodiment of the method according to the invention. Here, the intervals of the task are the same length, the intervals are continuous, and the regular budgets are the same. This method is executed during the context switch executed by the basic operating system pSOS as described above.
    [32] Within step 300, the priority of a task leaving the system is checked for the priority of tasks entering the system. When the priority of the task leaving the system is lower than or equal to the priority of the task entering the system, the task entering the system is allowed to operate, and the method according to the invention back controls the pSOS within step 320. . When the priority of the task leaving the system is higher than the priority of the task entering the system, the budget of the leaving task is checked within step 302. The budget of the leaving task represents the remaining budget not used by the task during the current period of the leaving task. When this remaining budget of the leaving task is equal to zero, the leaving task is not allowed to operate again by the underlying operating system. The task entering the system is allowed to operate, and the method according to the invention controls the pSOS retroactively within step 320. When the remaining budget of the leaving task is greater than zero, the leaving task is blocking. The remaining budget of this leaving and blocking task is then reduced to zero within step 304. By reducing the remaining budget of the leaving task to zero, the underlying operating system does not select the leaving task to operate again during the current period of the leaving task. After reducing the remaining budget, the task entering the system is allowed to operate, and the method according to the invention controls the pSOS retroactively within step 320.
    [33] The order in the foregoing embodiments of the method of the present invention is not mandatory, and one of ordinary skill in the art will appreciate that continuous models, multiprocessor systems or without departing from the concept as intended by the present invention. Multiple processes can be used to change the order of the steps or to execute the steps simultaneously.
    [34] 4 illustrates the most important parts of an embodiment of a system according to the invention in a schematic manner. System 400 includes, for example, a first memory 402 having embedded computer-readable code for executing a first task of decoding an image frame. The second memory 404 has built-in computer readable code to apply an image enhancement of the decoded frame, for example, to execute the second task. Code of a real-time operating system, such as pSOS, is embedded in the third memory 406. Code of the real-time operating system accesses memory 410 that includes priorities, allocated budgets, and intervals of the first and second tasks. Here, as described above, the first task is a regular task having a priority P 1 , an interval T 1 = 5 and a periodic budget B 1 = 2, and the second task is a priority P 2 , an interval T 2 = 6 and Regular task with periodic budget B 2 = 3. The memory 410 also includes the time elapsed from the start of operation of the code embedded in the first memory 402 to execute the first task. The real-time operating system pSOS schedules the task based on rate monotonic scheduling. The interval budgets B 1 , B 2 represent the amount of CPU cycles of the CPU 408, and the task can be used during the interval when its budget is enabled by the real-time operating system pSOS. The real-time operating system pSOS fills the memory 412 with context switch information when it executes a context switch. Within the context switch, the priority of the task for which the budget is disabled and the remaining budget and the priority of the task for which the budget is enabled and the remaining budget are placed in memory 412. Memory 414 has embedded computer readable code for retrieving information from memory 412 and updating the remaining budget of tasks for which the budget is disabled. When the retrieved information as described above indicates that the disabled budget is being blocked, this blocking state is added to the contents of the memory 412. The remaining budget of the task with the disabled budget is then set to zero and its priority is set to the background priority during the current period of the task by the real-time operating system pSOS. The system 400 is implemented in software intended to be operated as an application by a computer capable of operating the software or by any other standard architecture. The system can be used to operate the digital television set 416. The software can also be updated from a storage device 420 that includes a computer program product arranged for carrying out the method according to the invention. The storage device is read by a CD reader 418 connected to the system 400.
    [35] 5 shows in a schematic manner the most important parts of a television set 510 which includes an embodiment of the system according to the invention. Here, the antenna 500 receives a television signal. The antenna may also be, for example, a satellite dish, cable, storage, internet, Ethernet or any other device for receiving a television signal. Receiver 502 receives the signal. The signal can be, for example, digital, analog, RGB or YUV. In addition to the receiver 502, the television set includes a programmable component 504, eg, programmable integrated circuit. This programmable component includes a system 506 in accordance with the present invention. The television screen 508 receives images that are received by the receiver 502 and processed by the programmable component 504, the system according to the present invention, and generally other parts included in the television set but not shown here. Shows.
    [36] 6 shows in a schematic way the most important parts of a set top box comprising an embodiment of the system according to the invention. The antenna may also be satellite dish, cable, storage, internet, Ethernet or any other device for receiving television signals. Set top box 602 receives a signal. The signal may for example be digital, analog, RGB or YUV. In addition to the general parts included in the set top box but not shown here, the set top box includes the system 604 of the present invention. Television set 606 may show an output signal generated from the signal received by set-top box 602 with system 604 in accordance with the present invention. Output signals may also be directed to storage devices such as VCRs, DVD-RWs or hard disks, and they may be directed to an internet link instead of to a television set.
    权利要求:
    Claims (10)
    [1" claim-type="Currently amended] A method of scheduling a first task,
    Initiating the first task to operate during the interval;
    And the second step of detecting that the first task blocks during the interval,
    And a third step of preventing the first task from resuming operation during the interval.
    [2" claim-type="Currently amended] The method of claim 1,
    And wherein said second step is based on context switch information.
    [3" claim-type="Currently amended] The method of claim 2,
    A second step of detecting that the first task blocks during the interval,
    A first sub-step of detecting that the first task is suspended and the second task is allowed to start operation,
    The context switch information,
    The second priority of the second task lower than the first priority of the first task,
    And a remaining budget of the first task that is substantially equal to the budget allocated for the interval minus the budget spent during the interval.
    [4" claim-type="Currently amended] 4. The method of claim 3, wherein the remaining budget is recovered from a first task during the interval.
    [5" claim-type="Currently amended] A system 400 for scheduling a first task,
    Running means 408 configured to operate the first task during an interval;
    In the system comprising detection means 412, configured to detect a blocked state of the first task,
    And preventing means (414) configured to prevent the first task from resuming operation during the interval.
    [6" claim-type="Currently amended] The method of claim 5,
    The detection means 412 also,
    A first priority of the first task that is suspended,
    A second priority of the second task resumed with a lower priority than the first priority of the first task,
    Operating based on the remaining budget of the first task that is substantially equal to the budget allocated during the interval minus the budget consumed during the interval.
    [7" claim-type="Currently amended] A computer program product arranged for carrying out the method according to claim 1.
    [8" claim-type="Currently amended] A storage device (420) comprising a computer program product according to claim 7.
    [9" claim-type="Currently amended] Television set 510 comprising a system according to claim 5 or 6.
    [10" claim-type="Currently amended] Set top box 602 comprising a system according to claim 5 or 6.
    类似技术:
    公开号 | 公开日 | 专利标题
    Yun et al.2012|Memory access control in multiprocessor for real-time systems with mixed criticality
    US9823946B2|2017-11-21|Processor and program execution method capable of efficient program execution
    EP2513746B1|2018-07-04|System and method for controlling central processing unit power with guaranteed transient deadlines
    US8504753B2|2013-08-06|Suspendable interrupts for processor idle management
    CA2456220C|2009-12-22|Controlling processor clock rate based on thread priority
    KR950005217B1|1995-05-22|Clock signal control method and data processing system
    US6430594B1|2002-08-06|Real-time operating system and a task management system therefor
    US7321942B2|2008-01-22|Performance counter for adding variable work increment value that is dependent upon clock frequency
    US8875151B2|2014-10-28|Load balancing method and apparatus in symmetric multi-processor system
    JP4694595B2|2011-06-08|Sleep queue management
    DE60109748T2|2006-02-09|Method and device for execution interruption in a processor
    JP5065566B2|2012-11-07|Resource Manager architecture
    US7979680B2|2011-07-12|Multi-threaded parallel processor methods and apparatus
    JP5605970B2|2014-10-15|Minimizing resource latency between processor application states in portable computing devices by scheduling resource set migration
    CN100380329C|2008-04-09|Processor and information processing method
    US9274832B2|2016-03-01|Method and electronic device for thread scheduling
    EP0806730B1|2004-07-14|Real time dispatcher
    US7454600B2|2008-11-18|Method and apparatus for assigning thread priority in a processor or the like
    US5903752A|1999-05-11|Method and apparatus for embedding a real-time multi-tasking kernel in a non-real-time operating system
    US8856791B2|2014-10-07|Method and system for operating in hard real time
    US8270800B2|2012-09-18|Information processing apparatus and method, recording medium, and program
    JP3573546B2|2004-10-06|Parallel process scheduling method for parallel computer and processing device for parallel computer
    US8954980B2|2015-02-10|Conserving power through work load estimation for a portable computing device using scheduled resource set transitions
    US20120216207A1|2012-08-23|Dynamic techniques for optimizing soft real-time task performance in virtual machine
    JP3952992B2|2007-08-01|Information processing apparatus, process control method, and computer program
    同族专利:
    公开号 | 公开日
    WO2002071218A2|2002-09-12|
    CN1478230A|2004-02-25|
    CN1228714C|2005-11-23|
    EP1377903A2|2004-01-07|
    JP2004528635A|2004-09-16|
    US20020124043A1|2002-09-05|
    WO2002071218A3|2003-10-30|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    法律状态:
    2001-03-05|Priority to EP01200810.8
    2001-03-05|Priority to EP01200810
    2002-01-30|Application filed by 코닌클리케 필립스 일렉트로닉스 엔.브이.
    2003-02-20|Publication of KR20030015234A
    优先权:
    申请号 | 申请日 | 专利标题
    EP01200810.8|2001-03-05|
    EP01200810|2001-03-05|
    [返回顶部]