KR20180066387A - Method and system for scalability using paravirtualized opportunistic spinlock algorithm - Google Patents
Method and system for scalability using paravirtualized opportunistic spinlock algorithm Download PDFInfo
- Publication number
- KR20180066387A KR20180066387A KR1020160167003A KR20160167003A KR20180066387A KR 20180066387 A KR20180066387 A KR 20180066387A KR 1020160167003 A KR1020160167003 A KR 1020160167003A KR 20160167003 A KR20160167003 A KR 20160167003A KR 20180066387 A KR20180066387 A KR 20180066387A
- Authority
- KR
- South Korea
- Prior art keywords
- lock
- threshold value
- head
- spin
- algorithm
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Withdrawn
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/52—Program synchronisation; Mutual exclusion, e.g. by means of semaphores
- G06F9/526—Mutual exclusion algorithms
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
- G06F9/5061—Partitioning or combining of resources
- G06F9/5077—Logical partitioning of resources; Management or configuration of virtualized resources
Landscapes
- Engineering & Computer Science (AREA)
- Software Systems (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Hardware Redundancy (AREA)
Abstract
본 발명은 매니코어 클라우드 가상환경의 리눅스 운영체제에서의 락(lock) 알고리즘을 개선한 반가상 기회 스핀락(Paravirtualized Opportunistic Spinlock) 알고리즘을 이용한 확장성 보장 시스템 및 방법에 관한 것이다.
본 발명에 따른 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 방법은 티켓 대기행렬 범위 및 임계치를 설정하되, 현재 락을 소유한 헤드에 가까운 대기자일수록 그 임계치를 상향 설정하는 단계와, 임계치를 감소시켜 락을 획득하는 단계 및 언락 시 헤드를 기준으로 기설정된 개수의 여러 대기자를 함께 동작시키는 단계를 포함하는 것을 특징으로 한다. The present invention relates to a scalability assurance system and method using a Paravirtualized Opportunistic Spinlock algorithm that improves the lock algorithm in the Manny core cloud virtual environment Linux operating system.
A method for ensuring extensibility using a semi-prospective chance spin lock algorithm comprises setting a range and a threshold of a ticket queue, setting a threshold value closer to a queue close to a head owning a current lock, And operating a predetermined number of queues on the basis of the head upon unlocking.
Description
본 발명은 매니코어 클라우드 가상환경의 리눅스 운영체제에서의 락(lock) 알고리즘을 개선한 반가상 기회 스핀락(Paravirtualized Opportunistic Spinlock) 알고리즘을 이용한 확장성 보장 방법 및 시스템에 관한 것이다. The present invention relates to a scalability assurance method and system using a Paravirtualized Opportunistic Spinlock algorithm that improves the lock algorithm in the Manny core cloud virtual environment in the Linux operating system.
클라우드 컴퓨팅 기술이 도입됨에 따라, 사용자들에게 가상 머신(Virtual Machine)으로 자원이 분배된다. With the introduction of cloud computing technology, resources are distributed to users as virtual machines.
가상 머신이란 물리적인 컴퓨터에서 구동되는 운영체제와 응용 프로그램으로 이루어진 소프트웨어 컨테이너를 지칭한다. A virtual machine is a software container that consists of an operating system and applications running on a physical computer.
매니코어 시스템이 제안됨에 따라, 단일 시스템이 수백 개에서 수천 개의 코어를 가지는 시스템으로 발전하고 있고, 클라우드에서 활용할 수 있는 자원이 증가되었다. With the proposed Manicore system, a single system has evolved from a system with hundreds to thousands of cores, and the resources available in the cloud have increased.
클라우드 환경에서 빅데이터 처리나 빠른 인메모리 데이터베이스에 대한 요구가 커짐에 따라, 서비스 제공자들은 많은 수의 가상중앙처리장치(vCPU, virtual CPU)를 제공하려는 데 초점을 맞추고 있다. As the demand for big data processing or fast in-memory databases grows in the cloud environment, service providers are focusing on providing a large number of virtual central processing units (vCPUs, virtual CPUs).
하지만, 종래 기술에 따른 리눅스 운영체제에서는 많은 vCPU의 가상환경에서 응용 프로그램이 많은 코어를 사용할 경우, 이에 비례하는 성능을 보장하지 못하는 문제점이 있다. However, in the Linux operating system according to the related art, there is a problem in that, when a large number of application programs are used in a virtual environment of many vCPUs, performance proportional thereto can not be guaranteed.
특히, 커널 컴파일과 같은 병렬처리를 수행할 경우 성능이 저하됨을 확인할 수 있는데, 이는 기존의 멀티프로세서를 위한 락(lock) 알고리즘인 티켓 스핀락(ticket spinlock) 방식이 가상환경에서 오히려 시스템 성능을 저하시키기 때문이다. In particular, performance degradation can be observed when parallel processing such as kernel compilation is performed. This is because the ticket spinlock method, which is a lock algorithm for existing multiprocessors, I will.
따라서, 매니코어 클라우드 환경에서 코어를 많이 사용할수록 성능이 향상되는 확장성(scalability)을 보장하기 위하여 종래 기술에 따른 락 알고리즘의 개선이 필요한 실정이다. Therefore, it is necessary to improve the lock algorithm according to the prior art in order to ensure scalability in which performance is improved as the core is used more in a manicured cloud environment.
본 발명은 전술한 문제점을 해결하기 위하여 제안된 것으로, 기존 멀티 프로세서를 위한 락 알고리즘을 개선하여 매니코어 시스템 확장성을 개선하는 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 방법 및 시스템을 제공하는 데 목적이 있다. SUMMARY OF THE INVENTION The present invention has been made in order to solve the above-mentioned problems, and it is an object of the present invention to provide a scalability guarantee method and system using a half-life chance spin lock algorithm that improves the scalability of a Manioc system by improving a lock algorithm for existing multiprocessors .
본 발명에 따른 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 방법은 티켓 대기행렬 범위 및 임계치를 설정하되, 현재 락을 소유한 헤드에 가까운 대기자일수록 그 임계치를 상향 설정하는 단계와, 임계치를 감소시키며 락을 획득하는 단계 및 언락 시 헤드를 기준으로 기설정된 개수의 여러 대기자를 함께 동작시키는 단계를 포함하는 것을 특징으로 한다. A method for ensuring extensibility using a semi-prospective chance spin lock algorithm includes setting a range of a ticket queue and a threshold value, setting a threshold value closer to a queue near a head owning a current lock, And operating a predetermined number of queues on the basis of the head upon unlocking.
본 발명에 따른 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 시스템은 현재 락을 소유한 헤드에 가까운 대기자의 임계치를 상향 설정하여 그 대기 시간을 조절하는 임계치 설정부와, 임계치를 감소시키며 획득 순서를 확인하여 락을 획득시키는 락 획득 제어부 및 언락 시 헤드를 기준으로 기설정된 개수의 복수의 대기자를 함께 활성화시키는 언락 제어부를 포함하는 것을 특징으로 한다. The system for guaranteeing scalability using a semi-prospective chance spin lock algorithm according to the present invention includes a threshold value setting unit for setting a threshold value of a waiter close to a head having a current lock and adjusting the wait time thereof, A lock acquisition control unit for acquiring a lock and an unlock control unit for activating a predetermined number of waiters together based on the unlocked head.
본 발명은 매니코어 운영체제 상에서의 가상환경에서 티켓 스핀락으로 인해 발생되는 문제점을 개선하는 기회 스핀락을 제안하여, 락을 대기함에 있어서 헤드(head)로부터 테일(tail)까지 대기자(waiter)의 거리에 기반하여 대기 시간을 조절함으로써 락 소유자 선점(LHP, Lock Holder Preemption) 문제를 해결하고, 언락 시에는 바로 연결된 다음 대기자 뿐 아니라 복수의 대기자를 미리 함께 동작시킴으로써 락 대기자 선점(LWP, Lock Waiter Preemption) 문제를 해결하는 효과가 있다. The present invention proposes an opportunity spin lock to solve the problem caused by ticket spin lock in a virtual environment on a ManiOck operating system and proposes an opportunity spin lock in which the distance of the waiter from the head to the tail Lock waiter preemption (LWP) is solved by adjusting the waiting time based on the waiting time, and when a lock is unlocked, a waiting wait time (LWP) It has the effect of solving the problem.
또한, 본 발명에 따르면 기존 리눅스 운영체제의 티켓 스핀락을 기회 스핀락으로 교체하는 최소한의 변경으로 적용이 가능하므로, 실용성 및 적용성이 뛰어난 효과가 있다. In addition, according to the present invention, it is possible to apply the present invention as a minimal change to replace the ticket spin lock of the existing Linux operating system with the opportunity spin lock, and thus, the practicality and applicability are excellent.
또한, 본 발명에 따르면 많은 수의 vCPU를 사용하는 가상 환경에서 확장성을 보장하는 것이 가능한 효과가 있다. In addition, according to the present invention, scalability can be guaranteed in a virtual environment using a large number of vCPUs.
본 발명의 효과는 이상에서 언급한 것들에 한정되지 않으며, 언급되지 아니한 다른 효과들은 아래의 기재로부터 당업자에게 명확하게 이해될 수 있을 것이다.The effects of the present invention are not limited to those mentioned above, and other effects not mentioned can be clearly understood by those skilled in the art from the following description.
도 1은 종래 기술에 따른 티켓 스핀락의 락 알고리즘을 나타내는 순서도이다.
도 2는 종래 기술에 따른 티켓 스핀락의 언락 알고리즘을 나타내는 순서도이다.
도 3은 본 발명에 따른 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 방법의 락 알고리즘을 나타내는 순서도이다.
도 4는 본 발명에 따른 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 방법의 언락 알고리즘을 나타내는 순서도이다.
도 5는 본 발명에 따른 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 시스템을 나타내는 블록도이다.
도 6은 종래 제안된 락 방식들과 대비하여 볼 때 본 발명에 따른 반가상 기회 스핀락 알고리즘의 성능을 나타내는 그래프이다. 1 is a flowchart showing a lock algorithm of a ticket spin lock according to the prior art.
2 is a flowchart showing an unlocking algorithm of a ticket spin lock according to the prior art.
FIG. 3 is a flowchart illustrating a lock algorithm of a scalability guarantee method using a half-chance spin lock algorithm according to the present invention.
FIG. 4 is a flowchart illustrating an unlocking algorithm of a scalability guarantee method using a half-value chance spinlock algorithm according to the present invention.
FIG. 5 is a block diagram illustrating an extensibility assurance system using a semi-progressive opportunistic spin lock algorithm according to the present invention.
FIG. 6 is a graph illustrating performance of a half-value chance spinlock algorithm according to the present invention in comparison with the conventional locking schemes.
본 발명의 전술한 목적 및 그 이외의 목적과 이점 및 특징, 그리고 그것들을 달성하는 방법은 첨부되는 도면과 함께 상세하게 후술되어 있는 실시예들을 참조하면 명확해질 것이다. BRIEF DESCRIPTION OF THE DRAWINGS The above and other objects, advantages and features of the present invention and methods of achieving them will be apparent from the following detailed description of embodiments thereof taken in conjunction with the accompanying drawings.
그러나 본 발명은 이하에서 개시되는 실시예들에 한정되는 것이 아니라 서로 다른 다양한 형태로 구현될 수 있으며, 단지 이하의 실시예들은 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에게 발명의 목적, 구성 및 효과를 용이하게 알려주기 위해 제공되는 것일 뿐으로서, 본 발명의 권리범위는 청구항의 기재에 의해 정의된다. The present invention may, however, be embodied in many different forms and should not be construed as being limited to the exemplary embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, And advantages of the present invention are defined by the description of the claims.
한편, 본 명세서에서 사용된 용어는 실시예들을 설명하기 위한 것이며 본 발명을 제한하고자 하는 것은 아니다. 본 명세서에서, 단수형은 문구에서 특별히 언급하지 않는 한 복수형도 포함한다. 명세서에서 사용되는 "포함한다(comprises)" 및/또는 "포함하는(comprising)"은 언급된 구성소자, 단계, 동작 및/또는 소자가 하나 이상의 다른 구성소자, 단계, 동작 및/또는 소자의 존재 또는 추가됨을 배제하지 않는다.It is to be understood that the terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the invention. In the present specification, the singular form includes plural forms unless otherwise specified in the specification. &Quot; comprises "and / or" comprising ", as used herein, unless the recited component, step, operation, and / Or added.
본 발명의 바람직한 실시예를 설명하기에 앞서, 이하에서는 당업자의 이해를 돕기 위하여 본 발명이 제안된 배경을 먼저 살펴보기로 한다. Prior to describing the preferred embodiments of the present invention, the background of the present invention will be described below in order to facilitate the understanding of those skilled in the art.
종래 기술에 따른 리눅스 운영체제는 멀티 프로세서 환경을 대상으로 CPU 자원을 적절하게 배분하기 위한 방법으로서, 티켓 스핀락(ticket spinlock) 방식이 사용된다.A conventional Linux operating system is a method for properly allocating CPU resources to a multiprocessor environment, and a ticket spinlock scheme is used.
티켓 스핀락은 헤드(head)와 테일(tail)로 구성되는데, 현재 락 확보자는 헤드이고, 추가적으로 락이 필요한 대기자(waiter)들은 테일에 연속적으로 연결되어, 연결된 순서(FIFO, First In First Out)대로 락을 확보하게 된다.Ticket spin locks consist of a head and a tail. The current locker is the head and the additional waiters are connected to the tail in a sequential order (FIFO, First In First Out) Securing the lock.
종래 기술에 따른 티켓 스핀락의 락 알고리즘 및 언락 알고리즘을 도 1 및 도 2에 도시하였다. The locking and unlocking algorithms of the ticket spin lock according to the prior art are shown in Figs. 1 and 2. Fig.
도 1을 참조하면, 임계치의 초기값(예: 215)이 설정되고, 락을 획득하고자 하는 대상(my_ticket)의 현재 위치를 확인한다(S10). Referring to FIG. 1, an initial value (for example, 2 15 ) of a threshold value is set, and a current position of an object (my_ticket) to acquire a lock is confirmed (S10).
이어 임계치를 점점 줄여(1씩 감소) 현재 헤드를 재확인하고(S20), 자신이 현재 락을 획득할 순서인지를 확인하여(S30), 감소된 임계치가 0으로 확인된 경우(S40) 대기상태(spin)가 되며(S50), 헤드가 락을 놓게 되면 락을 획득하게 된다(S60). (S30). If the decremented threshold value is found to be 0 (S40), the current head is re-checked (S20) spin (S50). When the head releases the lock, the lock is acquired (S60).
또한, 도 2를 참조하면, 종래 기술에 따른 티켓 스핀락은 언락을 수행할 경우 헤드를 다음 대기자(waiter)로 바꾸게 된다(S70). Also, referring to FIG. 2, when performing unlock, the ticket spinlock according to the related art changes the head to a next waiter (S70).
반가상화(Paravirtualzation)는 하드웨어를 완전히 가상화하지 않는 가상화 기법으로, 게스트 OS(guest OS)가 직접 하드웨어를 제어하지 않고, 미들웨어인 하이퍼바이저(hypervisor)를 통해 제어한다. Paravirtualization is a virtualization technique that does not completely virtualize the hardware. The guest OS does not directly control the hardware, but controls it through the hypervisor, which is middleware.
이와 같은 가상환경에서 vCPU도 마찬가지로 적절하게 배분하기 위하여 전술한 티켓 스핀락 방식이 사용되고 있으나, 크게 두 가지 관점에서 확장성이 제한되는 문제점이 있다. In such a virtual environment, the ticket spin lock scheme described above is also used to appropriately distribute the vCPU, but the scalability is limited in two respects.
첫 번째는 락 고유자 선점(LHP, Lock Holder Preemption)으로, vCPU가 락을 확보한 채 스케줄러나 인터럽트에 의하여 비선점되어 슬립(sleep) 모드로 전환되면, 락을 기다리는 다른 대기자(waiter)들이 선점되지 못하게 되는 문제점이다. The first is Lock Holder Preemption (LHP). When the vCPU is unoccupied by a scheduler or an interrupt and is switched to a sleep mode while securing the lock, other waiters waiting for the lock are preempted .
두 번째는 락 대기자 선점(LWP, Lock Waiter Preemption)으로, 락을 확보한 vCPU의 다음 대기자(waiter)가 슬립(sleep) 모드로 전환하게 되면, 락을 확보한 vCPU가 락을 놓더라도 다음 대기자가 스케줄링되어 동작될 때까지 그 뒤의 대기자들은 선점되지 못하는 문제점이다. The second is Lock Waiter Preemption (LWP). When the next waiter of the secured vCPU switches to sleep mode, even if the locked vCPU releases the lock, the next waiter Until scheduling and operation, waiters behind them are not preempted.
본 발명은 전술한 문제점을 해결하기 위하여 제안된 것으로, 티켓 스핀락을 개선한 기회 스핀락(opportunistic spinlock)을 제안하며, 락 홀더가 슬립 모드로 바로 전환하지 않도록 임계치를 설정하여 락 소유자 선점 문제(LHP 문제)를 해결하고, 대기자들에게는 헤드 가까이에 있을 경우 미리 동작시킴으로써 락 대기자 선점 문제(LWP 문제)를 해결하는 것이 가능하다. The present invention proposes an opportunistic spinlock which improves the ticket spin lock. The present invention proposes an opportunistic spinlock which improves the ticket spin lock and sets a threshold value so that the lock holder does not directly switch to the sleep mode, LHP problem), and it is possible to solve the waiting queue preemption problem (LWP problem) by waiting beforehand to waiters when they are near the head.
본 발명에 따르면 가상화 환경에서의 시스템 성능 저하를 극적으로 개선하는 것이 가능하며, 특히 기존 리눅스 운영체제의 티켓 스핀락을 기회 스핀락으로 교체하는 최소한의 변경을 통하여 그 적용이 가능하므로 실용성이 뛰어난 효과가 있다. According to the present invention, it is possible to dramatically improve system performance degradation in a virtualized environment. In particular, it is possible to apply the present invention through a minimal change of replacing a ticket spin lock of an existing Linux operating system with an opportunity spin lock, have.
도 3은 본 발명에 따른 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 방법의 락 알고리즘을 나타내는 순서도이고, 도 4는 본 발명에 따른 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 방법의 언락 알고리즘을 나타내는 순서도이다. FIG. 3 is a flowchart showing a lock algorithm of a scalability guarantee method using a half-life opportunity spin lock algorithm according to the present invention, FIG. 4 is a flowchart showing an unlock algorithm of a scalability guarantee method using a half- to be.
반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 방법은 티켓 대기행렬 범위 및 임계치를 설정하되, 현재 락을 소유한 헤드에 가까운 대기자일수록 그 임계치를 상향 설정하는 단계와, 임계치를 감소시켜 락을 획득하는 단계 및 언락 시 헤드를 기준으로 기설정된 개수의 여러 대기자를 함께 동작시키는 단계를 포함한다. The method for ensuring extensibility using a half-life-chance spin lock algorithm includes setting a range and a threshold of a ticket queue, setting a threshold value closer to a head closer to a head owning the current lock, and decreasing a threshold to acquire a lock And operating a predetermined number of queues based on the unlocked head.
S100 단계는 티켓 대기 행렬(ticket_queue, 예: 18)을 설정하고, 임계치(threshold)를 설정(예: 215)하되, 최대 임계치(max_threshold, 예: 234)를 설정하고 현재 my_ticket의 위치를 확인한다.Step S100 sets the ticket queue (e.g., ticket_queue, e.g., 18), sets a threshold (e.g., 2 15 ), sets a maximum threshold (max_threshold, e.g., 2 34 ) and confirms the location of the current my_ticket do.
이어, 티켓 대기행렬 범위 내에 임계치를 설정할 대기자가 있는지 확인하고(S150), 헤드로부터 테일까지의 거리(dist)를 계산하여, 임계치를 그 거리보다 큰 최대 임계치로 설정하게 된다(S200). Then, it is determined whether there is a waiting queue to set a threshold value within the ticket queue matrix (S150). The distance from the head to the tail is calculated to set the threshold value to a maximum threshold value larger than the distance (S200).
이 때, 임계치는 헤드와 가까울수록 더욱 크도록 설정되어야 하는데, 임계치의 상향 설정 증가 비율은 대상 워크로드 및 하드웨어 스펙에 따라 가변되는 것이 가능하다. At this time, the threshold value should be set to be larger as the head is closer to the head, and the rate of increase of the threshold value may vary depending on the target workload and the hardware specification.
현재 락을 소유한 헤드와 가까운 대기자일수록 락을 확보할 수 있는 가능성이 많기 때문에, 전술한 본 발명의 실시예에 따른 S100 내지 S200 단계를 통해 락을 대기하려고 할 때 헤드로부터 테일까지 대기자의 거리에 기반하여 그 대기시간을 조절함으로써, 조금 더 오래 기다릴 수 있도록 하여 락 소유자 선점 문제(LHP 문제)를 해결하는 것이 가능하다. Since there is a high possibility that the lock can be ensured as the closer to the head owning the current lock, the distance from the head to the tail from the head to the tail when trying to wait for the lock through steps S100 to S200 according to the embodiment of the present invention It is possible to solve the lock owner preemption problem (LHP problem) by adjusting the waiting time based on this, so that it can wait a little longer.
S150 단계에서 임계치를 설정할 대기자가 없는 것으로 확인된 경우, S250 단계는 임계치를 감소시키며, 현재 락을 소유한 헤드를 재확인한다. If it is determined in step S150 that there is no waiting queue to set a threshold value, step S250 reduces the threshold and reaffirms the head that currently owns the lock.
S300 단계는 자신이 현재 락을 획득할 순서인지를 확인하여, 락을 획득할 순서에 해당하는 경우 락을 획득하고(S350), 그렇지 않은 경우 임계치가 0인지 확인하여(S400) 그 임계치가 0에 해당하는 경우 대기상태가 된다(S450). In step S300, it is determined whether the lock is in the order of acquiring the current lock. If the lock is in the order of acquiring the lock, the lock is acquired in step S350. Otherwise, it is checked whether the threshold is 0 in step S400. If so, a standby state is entered (S450).
도 4를 참조하면, 본 발명에 따른 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 방법의 언락 알고리즘은 활성화시킬 가상중앙처리장치의 수(wakeup_ncpu)를 설정(예: 4)하고, 카운트값을 설정(예: 1)한다(S500).Referring to FIG. 4, the unlock algorithm of the scalability assurance method using the half-value chance spinlock algorithm according to the present invention sets up the number of virtual central processing units (wakeup_ncpu) to be activated (for example, 4) For example, 1) (S500).
이후, 활성화시킬 가상중앙처리장치가 남아있는지 여부를 확인하여(S550), 남아 있을 경우 헤드로부터 카운트값을 합산한 순번의 가상중앙처리장치를 활성화하고, 카운트값을 1 증가시킨다(S600). Then, it is checked whether the virtual central processing unit to be activated remains (S550). If the virtual central processing unit is left active, the virtual central processing unit of the order in which the count value is added from the head is activated and the count value is incremented by one (S600).
또한, S550 단계에서 활성화시킬 가상중앙처리장치가 더 이상 남아있지 않은 것으로 확인되면, 헤드를 다음 대기자(waiter)로 변경하게 된다(S650). If it is determined in step S550 that the virtual central processing unit to be activated is no longer left, the head is changed to the next waiter (S650).
본 발명의 실시예에 따르면, 다음 대기자(waiter)들을 활성화 시킬 때 활성화시킬 개수를 정하여 함께 미리 활성화시킴으로써, 가상머신에서 언락된 vCPU를 동작시킴에 있어 하이퍼바이저를 거쳐야 하여 시간이 소요됨으로써 발생되는 지연을 방지하는 것이 가능하다. According to the embodiment of the present invention, when activating the next waiters, the number to be activated is determined and activated in advance, so that the vCPU that has been unlocked in the virtual machine must go through the hypervisor to operate the unlocked vCPU, Can be prevented.
도 5는 본 발명에 따른 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 시스템을 나타내는 블록도이다. FIG. 5 is a block diagram illustrating an extensibility assurance system using a semi-progressive opportunistic spin lock algorithm according to the present invention.
본 발명의 실시예에 따른 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 시스템은 현재 락을 소유한 헤드에 가까운 대기자의 임계치를 상향 설정하여 그 대기 시간을 조절하는 임계치 설정부(100)와, 임계치를 감소시키며 획득 순서를 확인하여 락을 획득시키는 락 획득 제어부(200) 및 언락 시 상기 헤드를 기준으로 기설정된 개수의 복수의 대기자를 함께 활성화시키는 언락 제어부(300)를 포함하여 구성된다. The system for guaranteeing scalability using the half-value opportunistic spin lock algorithm according to an embodiment of the present invention includes a
임계치 설정부(100)는 타겟 대기행렬 범위 및 임계치를 설정하되, 헤드로부터 테일까지 대기자의 거리를 고려하여 임계치를 상향 설정한다. The threshold
이 때, 임계치 설정부(100)는 헤드로부터의 거리가 가까울수록 임계치의 상향 설정 범위를 크게 하되, 대상 워크로드 및 하드웨어 스펙을 고려하여 상향 설정 범위의 비율을 가변시킨다. At this time, the
락 획득 제어부(200)는 임계치를 감소시키며 현재 락을 소유한 헤드를 재확인하고, 현재 락을 획득할 순서인지 여부를 확인하여 락을 획득하도록 제어한다. The lock
즉, 본 발명에 따르면 락을 대기하려고 할 때 헤드로부터 테일까지 대기자의 거리에 기반하여 대기 시간을 조절함으로써, 락 소유자 선점 문제(LHP 문제)를 해결하는 것이 가능하다. That is, according to the present invention, it is possible to solve the lock owner preemption problem (LHP problem) by adjusting the waiting time based on the distance of the waiter from the head to the tail when trying to wait for the lock.
언락 제어부(300)는 언락 시 바로 연결된 다음 대기자 뿐 아니라 여러 대기자들을 함께 활성화시켜 동작시키는 구성으로, 활성화시킬 가상중앙처리장치의 개수를 설정하고, 카운터값을 증가시키며 가상중앙처리장치를 활성화시키고, 증가된 카운터값이 기설정된 개수와 같아져 더 이상 활성화시킬 가상중앙처리장치가 없는 경우 헤드를 다음 대기자로 변경시키게 된다. The
이를 통해, 종래 기술에 따른 락 대기자 선점 문제(LWP 문제)를 해결하는 것이 가능하다. Thus, it is possible to solve the lock waiters preemption problem (LWP problem) according to the prior art.
도 6은 종래 제안된 락 방식들과 대비하여 볼 때 본 발명에 따른 반가상 기회 스핀락 알고리즘의 성능을 나타내는 그래프이다. FIG. 6 is a graph illustrating performance of a half-value chance spinlock algorithm according to the present invention in comparison with the conventional locking schemes.
본 발명은 리눅스 운영체제가 설치된 80코어 서버에서, 고도의 병렬화를 실험할 수 있는 리눅스 커널 컴파일을 실험 대상으로 하여 성능 평가가 수행되었으며, 본 실험은 입출력으로 인한 오측정을 제거하기 위해 메모리 기반 파일 시스템(tmpfs)를 활용하고, 미리 관련 데이터를 가상환경에 로딩(pre-loading)하여 측정하였고, 가상머신 코어(core)의 두배로 커널 컴파일을 수행하였으며, 최고의 성능을 위해 각 vCPU를 하나의 코어에 연결하여 수행되었다. The present invention is based on a Linux kernel compilation which can test a high degree of parallelism on an 80-core server equipped with a Linux operating system. In order to eliminate erroneous measurement due to input / output, (tmpfs), pre-loading the related data in advance, and compiling the kernel twice as much as the virtual machine core. For the best performance, each vCPU is loaded on one core .
본 실험의 결과, 도 6에 도시한 바와 같이 종래의 다른 락 방식들(ticket, Longer spinning, iticket, qspinlock)과의 성능 차이를 확인할 수 있었다.As a result of the experiment, the performance difference between the conventional locking methods (ticket, long spinning, iticket, and qspinlock) as shown in FIG. 6 was confirmed.
종래 기술에 따른 qspinlock은 슬리피 스핀락(sleepy spinlock) 문제로 가상 환경에서 성능이 떨어지는 것을 확인하였으며, 기존의 캐쉬 충돌(cache-contention)에 의한 성능 저하 문제를 해결하기 위하여 제안된 방법들은 엄격한 순차처리(FIFO, First In First Out)를 보장하나 성능이 저하되는 문제점을 내포하고 있다. The qspinlock according to the prior art confirmed that the performance in the virtual environment was deteriorated due to the sleepy spinlock problem. To solve the performance degradation due to the conventional cache-contention, the proposed methods include strict sequential processing (FIFO, First In First Out), but the performance is degraded.
본 발명은 많은 수의 vCPU를 사용하는 가상 환경에서 확장성을 보장하는 것이 가능한 기회 스핀락(oticket, opportunistic ticket spinlock)을 제안하여, 매니코어 운영체제 상에서의 가상환경에서 티켓 스핀락으로 인해 발생하는 LHP 및 LWP로 인한 시스템 성능 저하 및 붕괴를 개선하는 것이 가능하다. The present invention proposes an opportunistic ticket spinlock (oticket) capable of ensuring scalability in a virtual environment using a large number of vCPUs, and provides an LHP And to improve system performance degradation and collapse due to LWP.
또한, 기존 리눅스 운영체제으 티켓 스핀락을 기회 스핀락으로 교체하는 최소한의 변경으로도 그 적용이 가능하며, 많은 수의 vCPU에 확장성을 보장하는 효과가 있다. In addition, it can be applied to the existing Linux operating system with minimal changes to replace the ticket spin lock with the opportunity spin lock, and it has the effect of ensuring the scalability to a large number of vCPUs.
이제까지 본 발명의 실시예들을 중심으로 살펴보았다. 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자는 본 발명이 본 발명의 본질적인 특성에서 벗어나지 않는 범위에서 변형된 형태로 구현될 수 있음을 이해할 수 있을 것이다. 그러므로 개시된 실시예들은 한정적인 관점이 아니라 설명적인 관점에서 고려되어야 한다. 본 발명의 범위는 전술한 설명이 아니라 특허청구범위에 나타나 있으며, 그와 동등한 범위 내에 있는 모든 차이점은 본 발명에 포함된 것으로 해석되어야 할 것이다. The embodiments of the present invention have been described above. It will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims. Therefore, the disclosed embodiments should be considered in an illustrative rather than a restrictive sense. The scope of the present invention is defined by the appended claims rather than by the foregoing description, and all differences within the scope of equivalents thereof should be construed as being included in the present invention.
100: 임계치 설정부
200: 락 획득 제어부
300: 언락 제어부100: threshold setting unit 200: lock acquisition control unit
300: unlock control unit
Claims (11)
(a) 티켓 대기행렬 범위 및 임계치를 설정하되, 현재 락을 소유한 헤드에 가까운 대기자일수록 그 임계치를 상향 설정하는 단계;
(b) 상기 임계치를 감소시켜 락을 획득하는 단계; 및
(c) 언락 시 헤드를 기준으로 기설정된 개수의 여러 대기자를 함께 동작시키는 단계
를 포함하는 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 방법.
In the scalability guarantee method using the half-chance spin lock algorithm in the ManiCoc cloud virtual environment,
(a) setting a range and a threshold of a ticket queue, and setting a threshold value closer to a queue near a head owning the current lock;
(b) decreasing the threshold to obtain a lock; And
(c) operating a predetermined number of queues together with respect to the head at the time of unlocking
A method for guaranteeing scalability using a half - life opportunistic spin lock algorithm.
상기 (a) 단계는 상기 티켓 대기행렬 범위 내에 상기 임계치를 설정할 대기자가 있는지 확인하여, 상기 헤드로부터 테일까지 대기자의 거리를 고려하여 상기 임계치를 상향 설정하여 대기 시간을 조절하는 것
인 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 방법.
The method according to claim 1,
The step (a) may include determining a waiter to set the threshold value within the ticket queue matrix, and adjusting the wait time by setting the threshold value up in consideration of the distance of the queue from the head to the tail
A Scalability Method Using Half - Life Opportunity Spin - Lock Algorithm.
상기 (a) 단계는 상기 거리가 가까울수록 임계치의 상향 설정 범위를 크게 하는 것
인 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 방법.
3. The method of claim 2,
In the step (a), the upward setting range of the threshold value is increased as the distance is closer
A Scalability Method Using Half - Life Opportunity Spin - Lock Algorithm.
상기 (a) 단계는 대상 워크로드 및 하드웨어 스펙에 따라 상기 임계치의 상향 설정 증가 비율을 가변시키는 것
인 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 방법.
The method of claim 3,
The step (a) may vary the rate of increase of the upward setting of the threshold according to the target workload and the hardware specification
A Scalability Method Using Half - Life Opportunity Spin - Lock Algorithm.
상기 (b) 단계는 상기 임계치를 감소시키며 상기 현재 락을 소유한 헤드를 재확인하고, 락 획득 순서를 확인하여 락을 획득하는 것
인 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 방법.
The method according to claim 1,
The step (b) reduces the threshold value, reaffirms the head that owns the current lock, and confirms the lock acquisition order to acquire the lock
A Scalability Method Using Half - Life Opportunity Spin - Lock Algorithm.
상기 (c) 단계는 활성화시킬 가상중앙처리장치의 개수를 설정하고, 상기 가상중앙처리장치를 활성화시키고 이에 따라 카운터값을 증가시키며, 증가된 상기 카운터값에 따라 상기 활성화시킬 가상중앙처리장치가 남아있는지 여부를 확인하고, 상기 헤드를 다음 대기자로 변경시키는 것
인 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 방법.
The method according to claim 1,
In the step (c), the number of the virtual central processing units to be activated is set, the virtual central processing unit is activated, and the counter value is increased accordingly. In accordance with the increased counter value, , And changing the head to the next waiter
A Scalability Method Using Half - Life Opportunity Spin - Lock Algorithm.
상기 임계치를 감소시키며 획득 순서를 확인하여 락을 획득시키는 락 획득 제어부; 및
언락 시 상기 헤드를 기준으로 기설정된 개수의 복수의 대기자를 함께 활성화시키는 언락 제어부
를 포함하는 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 시스템.
A threshold value setting unit for setting a threshold value of a waiter close to the head having the current lock to an upper limit and adjusting the waiting time;
A lock acquisition control unit for decreasing the threshold value and confirming an acquisition order to acquire a lock; And
An unlock control section for activating a predetermined number of queues on the basis of the head upon unlocking;
A scalability guarantee system using a half - life opportunistic spin - lock algorithm.
상기 임계치 설정부는 티겟 대기행렬 범위 및 임계치를 설정하되, 상기 헤드로부터 테일까지 대기자의 거리를 고려하여 상기 임계치를 상향 설정시키는 것
인 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 시스템.
8. The method of claim 7,
Wherein the threshold setting unit sets the range of the target queue and the threshold value, and sets the threshold value in consideration of the distance of the queue from the head to the tail
Extensibility Guarantee System Using Half - Life Opportunity Spin - Lock Algorithm.
상기 임계치 설정부는 상기 거리가 가까울수록 상기 임계치의 상향 설정 범위를 크게 하되, 대상 워크로드 및 하드웨어 스펙을 고려하여 상기 상향 설정 범위의 비율을 가변시키는 것
인 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 시스템.
9. The method of claim 8,
The threshold value setting unit may change the ratio of the uplink setting range in consideration of the target workload and the hardware specification while increasing the upward setting range of the threshold value as the distance is closer
Extensibility Guarantee System Using Half - Life Opportunity Spin - Lock Algorithm.
상기 락 획득 제어부는 상기 임계치를 감소시키며 상기 현재 락을 소유한 헤드를 재확인하고, 현재 락을 획득할 순서인지 여부를 확인하여 상기 락을 획득시키는 것
인 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 시스템.
8. The method of claim 7,
The lock acquisition control unit reduces the threshold value, reaffirms the head that owns the current lock, and confirms whether or not the current lock is acquired in order to acquire the lock
Extensibility Guarantee System Using Half - Life Opportunity Spin - Lock Algorithm.
상기 언락 제어부는 활성화시킬 가상중앙처리장치의 개수를 설정하고, 카운터값을 증가시키며 상기 가상중앙처리장치를 활성화시키고, 상기 헤드를 다음 대기자로 변경시키는 것
인 반가상 기회 스핀락 알고리즘을 이용한 확장성 보장 시스템. 8. The method of claim 7,
The unlock control unit sets the number of virtual central processing units to be activated, increases the counter value, activates the virtual central processing unit, and changes the head to the next standby
Extensibility Guarantee System Using Half - Life Opportunity Spin - Lock Algorithm.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020160167003A KR20180066387A (en) | 2016-12-08 | 2016-12-08 | Method and system for scalability using paravirtualized opportunistic spinlock algorithm |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020160167003A KR20180066387A (en) | 2016-12-08 | 2016-12-08 | Method and system for scalability using paravirtualized opportunistic spinlock algorithm |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| KR20180066387A true KR20180066387A (en) | 2018-06-19 |
Family
ID=62790429
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| KR1020160167003A Withdrawn KR20180066387A (en) | 2016-12-08 | 2016-12-08 | Method and system for scalability using paravirtualized opportunistic spinlock algorithm |
Country Status (1)
| Country | Link |
|---|---|
| KR (1) | KR20180066387A (en) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2022072092A1 (en) * | 2020-10-01 | 2022-04-07 | Oracle International Corporation | Efficient adjustment of spin-locking parameter values |
| CN114816678A (en) * | 2022-05-31 | 2022-07-29 | 苏州浪潮智能科技有限公司 | Method, system, equipment and storage medium for scheduling virtual machine |
| CN116225994A (en) * | 2023-03-06 | 2023-06-06 | 广州创龙电子科技有限公司 | High-speed communication method based on FlexSPI ARM and FPGA |
| US11868261B2 (en) | 2021-07-20 | 2024-01-09 | Oracle International Corporation | Prediction of buffer pool size for transaction processing workloads |
-
2016
- 2016-12-08 KR KR1020160167003A patent/KR20180066387A/en not_active Withdrawn
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2022072092A1 (en) * | 2020-10-01 | 2022-04-07 | Oracle International Corporation | Efficient adjustment of spin-locking parameter values |
| US11379456B2 (en) | 2020-10-01 | 2022-07-05 | Oracle International Corporation | Efficient adjustment of spin-locking parameter values |
| US11868261B2 (en) | 2021-07-20 | 2024-01-09 | Oracle International Corporation | Prediction of buffer pool size for transaction processing workloads |
| CN114816678A (en) * | 2022-05-31 | 2022-07-29 | 苏州浪潮智能科技有限公司 | Method, system, equipment and storage medium for scheduling virtual machine |
| CN114816678B (en) * | 2022-05-31 | 2024-06-11 | 苏州浪潮智能科技有限公司 | A method, system, device and storage medium for virtual machine scheduling |
| CN116225994A (en) * | 2023-03-06 | 2023-06-06 | 广州创龙电子科技有限公司 | High-speed communication method based on FlexSPI ARM and FPGA |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US11797327B2 (en) | Dynamic virtual machine sizing | |
| US10061610B2 (en) | CPU scheduler configured to support latency sensitive virtual machines | |
| US8756601B2 (en) | Memory coherency acceleration via virtual machine migration | |
| US8612659B1 (en) | Hardware interrupt arbitration in virtualized computer systems | |
| US10579413B2 (en) | Efficient task scheduling using a locking mechanism | |
| Kim et al. | Constraint-aware VM placement in heterogeneous computing clusters | |
| US9977690B2 (en) | Hypervisor-visible guest thread management | |
| Cheng et al. | vscale: Automatic and efficient processor scaling for smp virtual machines | |
| US10261847B2 (en) | System and method for coordinating use of multiple coprocessors | |
| US9304945B2 (en) | Synchronizing parallel applications in an asymmetric multi-processing system | |
| KR20180066387A (en) | Method and system for scalability using paravirtualized opportunistic spinlock algorithm | |
| CN106250217A (en) | Synchronous dispatching method between a kind of many virtual processors and dispatching patcher thereof | |
| US9158601B2 (en) | Multithreaded event handling using partitioned event de-multiplexers | |
| Kapitza et al. | Storyboard: Optimistic deterministic multithreading | |
| US20160246644A1 (en) | Method And System For Transition From Direct Interrupt State To Virtual Interrupt State Of Emulated Computing Environments | |
| Shrestha | Performance of Cluster-based High Availability Database in Cloud Containers. | |
| US9547522B2 (en) | Method and system for reconfigurable virtual single processor programming model | |
| US12450084B2 (en) | System and operation method of hybrid virtual machine managers | |
| US11809219B2 (en) | System implementing multi-threaded applications | |
| US10528391B1 (en) | Execution manager for binary objects operating across private address spaces | |
| US10678909B2 (en) | Securely supporting a global view of system memory in a multi-processor system | |
| Silambarasan | Handling of Priority Inversion Problem in RT-Linux using Priority Ceiling Protocol | |
| Guo | Moving MapReduce into the cloud: Elasticity, efficiency and scalability | |
| Samson et al. | Hardware acceleration of deadlock avoidance and detection in real-time operating systems |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PA0109 | Patent application |
Patent event code: PA01091R01D Comment text: Patent Application Patent event date: 20161208 |
|
| PG1501 | Laying open of application | ||
| PC1203 | Withdrawal of no request for examination |