Scheduling (computing): Difference between revisions

Revision as of 14:46, 10 August 2023

Latest revision as of 02:46, 28 August 2025

(44 intermediate revisions by 21 users not shown)

Line 1:

{{Short description|Method by which work is assigned}}

{{About|scheduling inof generalcomputing resources|networks|Network scheduler|other uses|Scheduling (disambiguation)}}

In [[computing]], '''scheduling''' is the action of assigning ''resources'' to perform ''tasks''. The ''resources'' may be [[central processing unit|processors]], [[telecommunications link|network links]] or [[expansion card]]s. The ''tasks'' may be [[thread (computer science)|threads]], [[process (computing)|processes]] or data [[flow (computer networking)|flows]].

In [[computing]], '''scheduling''' is the action of assigning ''[[System resource|resources'']] to perform ''[[task (computing)|tasks'']]. The ''resources'' may be [[central processing unit|processors]], [[telecommunications link|network links]] or [[expansion card]]s. The ''tasks'' may be [[thread (computer science)|threads]], [[process (computing)|processes]] or data [[Traffic flow (computer networking)|flows]].

The scheduling activity is carried out by a process called '''scheduler'''. Schedulers are often designed so as to keep all computer resources busy (as in [[load balancing (computing)|load balancing]]), allow multiple users to share system resources effectively, or to achieve a target [[quality of service|quality-of-service]].

The scheduling activity is carried out by a processmechanism called a '''scheduler'''. Schedulers are often designed so as to keep all computer resources busy (as in [[load balancing (computing)|load balancing]]), allow multiple users to share system resources effectively, or to achieve a target [[quality of service|quality-of-service]].

Scheduling is fundamental to computation itself, and an intrinsic part of the [[execution model]] of a computer system; the concept of scheduling makes it possible to have [[computer multitasking]] with a single [[central processing unit]] (CPU).

Line 26 ⟶ 27:

| quote = We define the response time of a request for a certain task to be the time span between the request and the end of the response to that request.

| doi = 10.1145/321738.321743| s2cid = 207669821

| doi-access = free

}}

</ref><ref name="kleinrock1976">{{cite book

| last = Kleinrock

Line 78 ⟶ 80:

The process scheduler is a part of the operating system that decides which process runs at a certain point in time. It usually has the ability to pause a running process, move it to the back of the running queue and start a new process; such a scheduler is known as a ''[[Preemption (computing)|preemptive]] scheduler'', otherwise it is a ''[[Nonpreemptive multitasking|cooperative]] scheduler''.<ref>{{cite web|access-date=2023-06-19|author=Paul Krzyzanowski|date=2014-02-19|title=Process Scheduling: Who gets to run next?|url=https://www.cs.rutgers.edu/~pxk/416/notes/07-scheduling.html|website=cs.rutgers.edu}}</ref>

We distinguish between "''long-term scheduling"'', "''medium-term scheduling"'', and "''short-term scheduling"'' based on how often decisions must be made.<ref>{{cite book |author=Raphael Finkel |author-link=Raphael Finkel |url=https://www.yumpu.com/en/document/read/32199214/an-operating-systems-vade-mecum |title=An Operating Systems Vade Mecum |publisher=Prentice Hall |date=1988 |chapter=Chapter 2: Time Management |page=27}}</ref>

[[Raphael Finkel]].

[https://www.yumpu.com/en/document/read/32199214/an-operating-systems-vade-mecum "An Operating Systems Vade Mecum"].

Prentice Hall.

1988.

"chapter 2: Time Management".

p. 27.

</ref>

===={{Anchor|LONG-TERM}}Long-term scheduling====

The ''long-term scheduler'', or ''admission scheduler'', decides which jobs or processes are to be admitted to the [[ready queue]] (in main memory); that is, when an attempt is made to execute a program, its admission to the set of currently executing processes is either authorized or delayed by the long-term scheduler. Thus, this scheduler dictates what processes are to run on a system, the degree of concurrency to be supported at any one time{{snd}} whether many or few processes are to be executed concurrently, and how the split between I/O-intensive and CPU-intensive processes is to be handled. The long-term scheduler is responsible for controlling the degree of multiprogramming.

In general, most processes can be described as either [[I/O-bound]] or [[CPU-bound]]. An I/O-bound process is one that spends more of its time doing I/O than it spends doing computations. A CPU-bound process, in contrast, generates I/O requests infrequently, using more of its time doing computations. It is important that a long-term scheduler selects a good process mix of I/O-bound and CPU-bound processes. If all processes are I/O-bound, the ready queue will almost always be empty, and the short-term scheduler will have little to do. On the other hand, if all processes are CPU-bound, the I/O waiting queue will almost always be empty, devices will go unused, and again the system will be unbalanced. The system with the best performance will thus have a combination of CPU-bound and I/O-bound processes. In modern operating systems, this is used to make sure that real-time processes get enough CPU time to finish their tasks.<ref name="Galvin">{{cite book

Line 112 ⟶ 107:

===={{Anchor|MEDIUM-TERM}}Medium-term scheduling====

The ''medium-term scheduler'' temporarily removes processes from main memory and places them in secondary memory (such as a [[hard disk drive]]) or vice versa, which is commonly referred to as "''swapping out"'' or "''swapping in"'' (also incorrectly as "''[[paging]] out"'' or "''paging in"''). The medium-term scheduler may decide to swap out a process that has not been active for some time, a process that has a low priority, a process that is [[page fault]]ing frequently, or a process that is taking up a large amount of memory in order to free up main memory for other processes, swapping the process back in later when more memory is available, or when the process has been unblocked and is no longer waiting for a resource.

In many systems today (those that support mapping virtual address space to secondary storage other than the swap file), the medium-term scheduler may actually perform the role of the long-term scheduler, by treating binaries as "''swapped-out processes"'' upon their execution. In this way, when a segment of the binary is required it can be swapped in on demand, or "''lazy loaded"'', also called [[demand paging]].

===={{Anchor|SHORT-TERM}}Short-term scheduling====

The ''short-term scheduler'' (also known as the ''CPU scheduler'') decides which of the ready, in-memory processes is to be executed (allocated a CPU) after a clock [[interrupt]], an I/O interrupt, an operating [[system call]] or another form of [[Signal programming(IPC)|signal]]. Thus the short-term scheduler makes scheduling decisions much more frequently than the long-term or mid-term schedulers{{snd}} A scheduling decision will at a minimum have to be made after every time slice, and these are very short. This scheduler can be [[Preemption (computing)|preemptive]], implying that it is capable of forcibly removing processes from a CPU when it decides to allocate that CPU to another process, or non-preemptive (also known as "''voluntary"'' or "''co-operative"''), in which case the scheduler is unable to "''force"'' processes off the CPU.

A preemptive scheduler relies upon a [[programmable interval timer]] which invokes an [[interrupt handler]] that runs in [[kernel mode]] and implements the scheduling function.

Line 173 ⟶ 168:

* To use this policy we should have at least two processes of different priority

===Fixed -priority pre-emptive scheduling===

{{Main|Fixed -priority pre-emptive scheduling}}

The operating system assigns a fixed -priority rank to every process, and the scheduler arranges the processes in the ready queue in order of their priority. Lower-priority processes get interrupted by incoming higher-priority processes.

* Overhead is not minimal, nor is it significant.

* FPPS has no particular advantage in terms of throughput over FIFO scheduling.

Line 190 ⟶ 185:

* RR scheduling involves extensive overhead, especially with a small time unit.

* Balanced throughput between FCFS/ FIFO and SJF/SRTF, shorter jobs are completed faster than in FIFO and longer processes are completed faster than in SJF.

* Good average response time, waiting time is dependent on number of processes, and not average process length.

* Because of high waiting times, deadlines are rarely met in a pure RR system.

* Starvation can never occur, since no priority is given. Order of time unit allocation is based upon process arrival time, similar to FIFO.

* If Time-Slice is large it becomes FCFS /FIFO or if it is short then it becomes SJF/SRTF.

===Multilevel queue scheduling===

Line 208 ⟶ 203:

===Scheduling optimization problems===

There are several scheduling problems in which the goal is to decide which job goes to which station at what time, such that the total [[makespan]] is minimized:

* [[Job -shop scheduling]]{{snd}} there are {{mvar|n}} jobs and {{mvar|m}} identical stations. Each job should be executed on a single machine. This is usually regarded as an online problem.

* [[Open-shop scheduling]]{{snd}} there are {{mvar|n}} jobs and {{mvar|m}} different stations. Each job should spend some time at each station, in a free order.

* [[Flow -shop scheduling]]{{snd}} there are {{mvar|n}} jobs and {{mvar|m}} different stations. Each job should spend some time at each station, in a pre-determined order.

===Manual scheduling===

Line 222 ⟶ 217:

===Choosing a scheduling algorithm===

When designing an operating system, a programmer must consider which scheduling algorithm will perform best for the use the system is going to see. There is no universal "''best"'' scheduling algorithm, and many operating systems use extended or combinations of the scheduling algorithms above.

For example, [[Windows NT]]/XP/Vista uses a [[multilevel feedback queue]], a combination of fixed-priority preemptive scheduling, round-robin, and first in, first out algorithms. In this system, threads can dynamically increase or decrease in priority depending on if it has been serviced already, or if it has been waiting extensively. Every priority level is represented by its own queue, with [[round-robin scheduling]] among the high-priority threads and [[FIFO (computing and electronics)|FIFO]] among the lower-priority ones. In this sense, response time is short for most threads, and short but critical system threads get completed very quickly. Since threads can only use one time unit of the round-robin in the highest-priority queue, starvation can be a problem for longer high-priority threads.

==Operating system process scheduler implementations==

The algorithm used may be as simple as [[Roundround-robin scheduling|round-robin]] in which each process is given equal time (for instance 1&nbsp;ms, usually between 1&nbsp;ms and 100&nbsp;ms) in a cycling list. So, process A executes for 1&nbsp;ms, then process B, then process C, then back to process A.

More advanced algorithms take into account process priority, or the importance of the process. This allows some processes to use more time than other processes. The kernel always uses whatever resources it needs to ensure proper functioning of the system, and so can be said to have infinite priority. In [[Symmetric multiprocessing|SMP]] systems, [[processor affinity]] is considered to increase overall system performance, even if it may cause a process itself to run more slowly. This generally improves performance by reducing [[cache thrashing]].

===OS/360 and successors===

IBM [[OS/360 and successors|OS/360]] was available with three different schedulers. The differences were such that the variants were often considered three different operating systems:

* The ''Single Sequential Scheduler'' option, also known as the ''Primary Control Program (PCP)'' provided sequential execution of a single stream of jobs.

Line 241 ⟶ 236:

===Windows===

Very early [[MS-DOS]] and Microsoft Windows systems were non-multitasking, and as such did not feature a scheduler. [[Windows 3.1x]] used a non-preemptive scheduler, meaning that it did not interrupt programs. It relied on the program to end or tell the OS that it didn't need the processor so that it could move on to another process. This is usually called cooperative multitasking. Windows 95 introduced a rudimentary preemptive scheduler; however, for legacy support opted to let 16 -bit applications run without preemption.<ref>{{webarchive |url=https://web.archive.org/web/*/www.jgcampbell.com/caos/html/node13.html |date=* |title=Early Windows }}</ref>

[[Windows NT]]-based operating systems use a multilevel feedback queue. 32 priority levels are defined, 0 through to 31, with priorities 0 through 15 being "''normal"'' priorities and priorities 16 through 31 being soft real-time priorities, requiring privileges to assign. 0 is reserved for the Operating System. User interfaces and APIs work with priority classes for the process and the threads in the process, which are then combined by the system into the absolute priority level.

The kernel may change the priority level of a thread depending on its I/O and CPU usage and whether it is interactive (i.e. accepts and responds to input from humans), raising the priority of interactive and I/O bounded processes and lowering that of CPU bound processes, to increase the responsiveness of interactive applications.<ref>{{cite web|title=A Tale of Two Schedulers Windows NT and Windows CE |url=http://sriramk.com/schedulers.html |author=Sriram Krishnan |url-status=dead |archive-url=https://web.archive.org/web/20120722015555/http://sriramk.com/schedulers.html |archive-date=July 22, 2012 }}</ref> The scheduler was modified in [[Windows Vista]] to use the [[Time Stamp Counter|cycle counter register]] of modern processors to keep track of exactly how many CPU cycles a thread has executed, rather than just using an interval-timer interrupt routine.<ref>{{cite web|url=https://technet.microsoft.com/en-us/magazine/cc162494.aspx |title=Windows Administration: Inside the Windows Vista Kernel: Part 1 |website=Technet.microsoft.com |date=2016-11-14 |access-date=2016-12-09}}</ref> Vista also uses a priority scheduler for the I/O queue so that disk defragmenters and other such programs do not interfere with foreground operations.<ref>{{cite web |url=http://blog.gabefrost.com/?p=25 |title=Archived copy |website=blog.gabefrost.com |access-date=15 January 2022 |archive-url=https://web.archive.org/web/20080219174631/http://blog.gabefrost.com/?p=25 |archive-date=19 February 2008 |url-status=dead}}</ref>

===Classic Mac OS and macOS===

Mac OS 9 uses cooperative scheduling for threads, where one process controls multiple cooperative threads, and also provides preemptive scheduling for multiprocessing tasks. The kernel schedules multiprocessing tasks using a preemptive scheduling algorithm. All Process Manager processes run within a special multiprocessing task, called the "''blue task"''. Those processes are scheduled cooperatively, using a [[round-robin scheduling]] algorithm; a process yields control of the processor to another process by explicitly calling a [[blocking function]] such as <code>WaitNextEvent</code>. Each process has its own copy of the [[Thread Manager]] that schedules that process's threads cooperatively; a thread yields control of the processor to another thread by calling <code>YieldToAnyThread</code> or <code>YieldToThread</code>.<ref name=appletn2028>{{cite web|url=https://developer.apple.com/library/archive/technotes/tn/tn2028.html |title= Technical Note TN2028: Threading Architectures |website=developer.apple.com |access-date=2019-01-15}}</ref>

macOS uses a multilevel feedback queue, with four priority bands for threads{{snd}}normal, system high priority, kernel mode only, and real-time.<ref>{{cite web|url=https://developer.apple.com/library/archive/documentation/Darwin/Conceptual/KernelProgramming/scheduler/scheduler.html |title= Mach Scheduling and Thread Interfaces |website=developer.apple.com |access-date=2019-01-15}}</ref> Threads are scheduled preemptively; macOS also supports cooperatively scheduled threads in its implementation of the Thread Manager in [[Carbon (API)|Carbon]].<ref name=appletn2028/>

Line 261 ⟶ 256:

Threads are primarily of interest for applications that currently consist of several asynchronous processes. These applications might impose a lighter load on the system if converted to a multithreaded structure.

AIX 5 implements the following scheduling policies: FIFO, round robin, and a fair round robin. The FIFO policy has three different implementations: FIFO, FIFO2, and FIFO3. The round robin policy is named SCHED_RR in AIX, and the fair round robin is called SCHED_OTHER.<ref>[http://www.ibm.com/developerworks/aix/library/au-aix5_cpu/index.html#N100F6] {{webarchive|url=https://web.archive.org/web/20110811094049/http://www.ibm.com/developerworks/aix/library/au-aix5_cpu/index.html |date=2011-08-11 }}</ref>

===Linux===

{{See also|Linux kernel#Scheduling}}

[[File:Simplified Structure of the Linux Kernel.svg|thumb|upright=1.5|A highly simplified structure of the Linux kernel, which includes process schedulers, I/O schedulers, and [[Linux kernel packet scheduler|packet schedulers]] ]]

==== Linux 1.2 ====

Linux 1.2 used a [[round-robin scheduling]] policy.<ref name=":0">{{Cite web |last=Jones |first=M. |date=2018-09-18 |orig-date=first published on 2009-12-14 |title=Inside the Linux 2.6 Completely Fair Scheduler |url=https://developer.ibm.com/tutorials/l-completely-fair-scheduler/ |access-date=2024-02-07 |website=developer.ibm.com}}</ref>

==== Linux 2.2 ====

Linux 2.2 added scheduling classes and support for [[symmetric multiprocessing]] (SMP).<ref name=":0" />[[File:Simplified Structure of the Linux Kernel.svg|thumb|upright=1.5|A highly simplified structure of the Linux kernel, which includes process schedulers, I/O schedulers, and [[Linux kernel packet scheduler|packet schedulers]] ]]

====Linux 2.4====

In [[Linux]] 2.4,<ref name=":0" /> an [[O(n) scheduler]] with a [[multilevel feedback queue]] with priority levels ranging from 0 to 140 was used; 0&ndash;99 are reserved for real-time tasks and 100&ndash;140 are considered [[nice (Unix)|nice]] task levels. For real-time tasks, the time quantum for switching processes was approximately 200&nbsp;ms, and for nice tasks approximately 10 ms.{{citation needed|date=December 2011}} The scheduler ran through the [[run queue]] of all ready processes, letting the highest priority processes go first and run through their time slices, after which they will be placed in an expired queue. When the active queue is empty the expired queue will become the active queue and vice versa.

However, some enterprise [[Linux distributions]] such as [[SUSE Linux Enterprise Server]] replaced this scheduler with a backport of the [[O(1) scheduler]] (which was maintained by [[Alan Cox (computer programmer)|Alan Cox]] in his Linux 2.4-ac Kernel series) to the Linux 2.4 kernel used by the distribution.

Line 274:

In versions 2.6.0 to 2.6.22, the kernel used an [[O(1) scheduler]] developed by [[Ingo Molnar]] and many other kernel developers during the Linux 2.5 development. For many kernel in time frame, [[Con Kolivas]] developed patch sets which improved interactivity with this scheduler or even replaced it with his own schedulers.

====Since Linux 2.6.23 to Linux 6.5====

Con Kolivas' work, most significantly his implementation of "[[Fairfair-share scheduling|fair scheduling]]" named "[[Rotating Staircase Deadline"]] (RSDL), inspired Ingo Molnár to develop the [[Completely Fair Scheduler]] (CFS) as a replacement for the earlier [[O(1) scheduler]], crediting Kolivas in his announcement.<ref>{{cite mailing list

| last=Molnár

| first=Ingo

Line 284:

| date=2007-04-13}}</ref> CFS is the first implementation of a fair queuing [[process scheduler]] widely used in a general-purpose operating system.<ref name="dwrr">{{cite web|url=http://happyli.org/tongli/papers/dwrr.pdf|title=Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin|author1=Tong Li|author2=Dan Baumberger|author3=Scott Hahn|website=Happyli.org|access-date=2016-12-09}}</ref>

The [[Completely Fair Scheduler]] (CFS) uses a well-studied, classic scheduling algorithm called [[fair queuing]] originally invented for [[packet network]]s. Fair queuing had been previously applied to CPU scheduling under the name [[stride scheduling]]. The fair queuing CFS scheduler has a scheduling complexity of <math>O(\log N)</math>, where {{mvar|N}} is the number of tasks in the [[run queue|runqueue]]. Choosing a task can be done in constant time, but reinserting a task after it has run requires <math>O(\log N)</math> operations, because the [[run queue]] is implemented as a [[red–black tree]].

The [[Brain Fuck Scheduler]], also created by Con Kolivas, is an alternative to the CFS.

==== Linux 6.6 ====

In 2023, Peter Zijlstra proposed replacing CFS with an [[earliest eligible virtual deadline first scheduling]] (EEVDF) process scheduler.<ref>{{Cite web |title=EEVDF Scheduler May Be Ready For Landing With Linux 6.6 |url=https://www.phoronix.com/news/Linux-6.6-EEVDF-Likely |access-date=2023-08-31 |website=[[Phoronix]] |language=en}}</ref><ref>{{Cite web |title=EEVDF Scheduler Merged For Linux 6.6, Intel Hybrid Cluster Scheduling Re-Introduced |url=https://www.phoronix.com/news/Linux-6.6-EEVDF-Merged |access-date=2024-02-07 |website=www.phoronix.com |language=en}}</ref> The aim was to remove the need for CFS ''latency nice'' patches.<ref>{{Cite web |title=An EEVDF CPU scheduler for Linux [LWN.net] |url=https://lwn.net/Articles/925371/ |access-date=2023-08-31 |website=[[LWN.net]]}}</ref>

==== Linux 6.12 ====

Linux 6.12 added support for [[User space and kernel space|userspace]] scheduler extensions, also known as sched_ext.<ref>{{Cite web |title=Sched_ext Merged For Linux 6.12 - Scheduling Policies As BPF Programs |url=https://www.phoronix.com/news/Linux-6.12-Lands-sched-ext |access-date=2025-02-10 |website=www.phoronix.com |language=en}}</ref> These schedulers can be installed and replace the default scheduler.<ref>{{Cite web |title=Pluggable CPU schedulers - openSUSE Wiki |url=https://en.opensuse.org/Pluggable_CPU_schedulers |access-date=2025-02-10 |website=en.opensuse.org}}</ref>

===FreeBSD===

Line 292 ⟶ 298:

===NetBSD===

[[NetBSD]] uses a multilevel feedback queue with priorities ranging from 0–223. 0–63 are reserved for time-shared threads (default, SCHED_OTHER policy), 64–95 for user threads which entered [[kernel space]], 96-12896–128 for kernel threads, 128–191 for user real-time threads (SCHED_FIFO and SCHED_RR policies), and 192–223 for [[Interrupt|software interrupts]].

===Solaris===

[[Solaris (operating system)|Solaris]] uses a multilevel feedback queue with priorities ranging between 0 and 169. Priorities 0&ndash;59 are reserved for time-shared threads, 60&ndash;99 for system threads, 100&ndash;159 for real-time threads, and 160&ndash;169 for low priority interrupts. Unlike Linux,<ref name="opensolaris-queue"/> when a process is done using its time quantum, it is given a new priority and put back in the queue. Solaris&nbsp;9 introduced two new scheduling classes, namely fixed -priority class and fair share class. The threads with fixed priority have the same priority range as that of the time-sharing class, but their priorities are not dynamically adjusted. The fair scheduling class uses CPU ''shares'' to prioritize threads for scheduling decisions. CPU shares indicate the entitlement to CPU resources. They are allocated to a set of processes, which are collectively known as a project.<ref name="Galvin"/>

===Summary===

Line 320 ⟶ 326:

| [[O(1) scheduler]]

|-

| Linux kernel after 2.6.23&ndash;6.6

| {{Yes}}

| [[Completely Fair Scheduler]]

|-

| Linux kernel 6.6 and later

| {{Yes}}

| [[Earliest eligible virtual deadline first scheduling]] (EEVDF)

|-

| [[classic Mac OS]] pre-9

Line 358 ⟶ 368:

==See also==

{{Div col|colwidth=20em}}

* [[Activity selection problem]]

* [[Aging (scheduling)]]

* [[Atropos scheduler]]

* [[Automated planning and scheduling]]

* [[Cyclic executive]]

Line 374 ⟶ 382:

* [[Queuing theory]]

* [[Rate-monotonic scheduling]]

* [[Resource-Task Network]]

* [[Scheduling (production processes)]]

* [[Stochastic scheduling]]

Line 391 ⟶ 398:

==Further reading==

*[httphttps://pages.cs.wisc.edu/~remzi/OSTEP/ Operating Systems: Three Easy Pieces] by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. Arpaci-Dusseau Books, 2014. Relevant chapters: [http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf Scheduling: Introduction] [http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-mlfq.pdf Multi-level Feedback Queue] [http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-lottery.pdf Proportional-share Scheduling] [http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-multi.pdf Multiprocessor Scheduling]

*[http://www.cs.sunysb.edu/~algorith/files/scheduling.shtml Brief discussion of Job Scheduling algorithms]

*[https://web.archive.org/web/20060613130106/http://oreilly.com/catalog/linuxkernel/chapter/ch10.html Understanding the Linux Kernel: Chapter 10 Process Scheduling]

Line 399 ⟶ 406:

*Peter Brucker, Sigrid Knust. Complexity results for scheduling problems [http://www.mathematik.uni-osnabrueck.de/research/OR/class/]

*[http://rtime.felk.cvut.cz/scheduling-toolbox TORSCHE Scheduling Toolbox for Matlab] is a toolbox of scheduling and graph algorithms.

*[httphttps://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6226795 A survey on cellular networks packet scheduling]

*[https://static.googleusercontent.com/media/research.google.com/en/us/pubs/archive/43438.pdf Large-scale cluster management at Google with Borg]