Symmetric multi-processor system

• US 8,572,626 B2
• Filed: 08/04/2011
• Issued: 10/29/2013
• Est. Priority Date: 08/25/1999
• Status: Expired due to Fees

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: QNX Software Systems Limited (Canada) (Blackberry Limited)
• Inventors: Van Der Veen, Peter
• Primary Examiner(s): Kawsar, Abdullah Al
• Application Number:
  US13/198,461
• Publication Number:
  US 20110289511A1
• Time in Patent Office: 817 Days
• Field of Search: 718 1-106, 719311-320, 719328-330
• US Class Current: 718/107
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

The present invention relates generally to computer operating systems, and more specifically, to operating system calls in a symmetric multiprocessing (SMP) environment. Existing SMP strategies either use a single lock or multiple locks to limit access to critical areas of the operating system to one thread at a time. These strategies suffer from a number of performance problems including slow execution, large software and execution overheads and deadlocking problems. The invention applies a single lock strategy to a micro kernel operating system design which delegates functionality to external processes. The micro kernel has a single critical area, the micro kernel itself, which executes very quickly, while the external processes are protected by proper thread management. As a result, a single lock may be used, overcoming the performance problems of the existing strategies.

Claims

1. A method of symmetric multiprocessing in which one or more processors are connected with a memory that stores an operating system in a machine executable form, wherein the operating system comprises a critical area and a non-critical area, the method comprising the steps of:

receiving a first operating system call from a first thread, wherein the first operating system call comprises a kernel call portion that requires access to the critical area of the operating system and an external call portion that requires access to the non-critical area of the operating system;

acquiring a global lock associated with the operating system for the first thread before accessing the critical area of the operating system for the kernel call portion of the first operating system call without locking the non-critical area of the operating system, wherein the global lock is associated with the entire critical area of the operating system and prevents any other threads from accessing the critical area while the global lock is applied to the critical area for the first thread;

receiving a second operating system call from a second thread that requires access to the non-critical area of the operating system;

granting the second thread access to the non-critical area of the operating system;

executing the first thread concurrently with the second thread; and

releasing the global lock upon completing the kernel call portion of the first operating system call.

2. The method of claim 1, wherein the step of executing comprises executing the first thread on a first processor of the one or more processors concurrently with execution of the second thread on a second processor of the one or more processors.

3. The method of claim 1, further comprising:

receiving an operating system call from a third thread that requires access to the critical area of the operating system; and

blocking the third thread from accessing the critical area of the operating system while the global lock is reserved for the first thread.

4. The method of claim 1, wherein the second operating system call comprises a kernel call portion that requires access to the critical area of the operating system and an external call portion that requires access to the non-critical area of the operating system, the method further comprising:

managing the global lock of the operating system to prevent overlapping execution of the kernel call portion of the first operating system call and the kernel call portion of the second operating system call.

5. The method of claim 4, further comprising allowing overlapping execution of the kernel call portion of the first operating system call and the external call portion of the second operating system call.

6. The method of claim 4, further comprising allowing overlapping execution of the external call portion of the first operating system call and the kernel call portion of the second operating system call.

7. The method of claim 1, where the operating system has a micro kernel architecture.

8. A computer system comprising:

one or more processors;

a first memory storing an operating system in a machine executable form, wherein the operating system comprises a critical area and a non-critical area;

a second memory storing a lock manager in an machine executable form; and

a communication network interconnecting the one or more processors, the first memory, and the second memory;

wherein the lock manager is configured to;

receive a first operating system call from a first thread, wherein the first operating system call comprises a kernel call portion that requires access to the critical area of the operating system and an external call portion that requires access to the non-critical area of the operating system;

acquire a global lock associated with the operating system for the first thread to access the critical area of the operating system for the kernel call portion of the first operating system call without locking the non-critical area of the operating system, wherein the global lock is associated with the entire critical area of the operating system and prevents any other threads from accessing the critical area while the global lock is applied to the critical area for the first thread;

receive a second operating system call from a second thread that requires access to the non-critical area of the operating system;

grant the second thread access to the non-critical area of the operating system;

allow the one or more processors to execute the first thread concurrently with the second thread; and

release the global lock upon completing the kernel call portion of the first operating system call.

9. The computer system of claim 8, wherein a first processor of the one or more processors is configured to execute the first thread concurrently with execution of the second thread on a second processor of the one or more processors.

10. The computer system of claim 8, wherein the lock manager is further configured to:

receive an operating system call from a third thread that requires access to the critical area of the operating system; and

block the third thread from accessing the critical area of the operating system while the global lock is reserved for the first thread.

11. The computer system of claim 8, wherein the second operating system call comprises a kernel call portion that requires access to the critical area of the operating system and an external call portion that requires access to the non-critical area of the operating system, wherein the lock manager is further configured to:

manage the global lock of the operating system to prevent overlapping execution of the kernel call portion of the first operating system call and the kernel call portion of the second operating system call.

12. The computer system of claim 11, wherein the lock manager is further configured to allow overlapping execution of the kernel call portion of the first operating system call and the external call portion of the second operating system call.

13. The computer system of claim 11, wherein the lock manager is further configured to allow overlapping execution of the external call portion of the first operating system call and the kernel call portion of the second operating system call.

14. The computer system of claim 8, where the operating system has a micro kernel architecture.

15. A non-transitory machine-readable medium with software stored thereon, wherein the software is executable by a processor to cause the processor to perform the steps of:

receiving a first operating system call from a first thread, wherein the first operating system call comprises a kernel call portion that requires access to a critical area of an operating system and an external call portion that requires access to a non-critical area of the operating system;

acquiring a global lock associated with the operating system for the first thread to access the critical area of the operating system for the kernel call portion of the first operating system call without locking the non-critical area of the operating system, wherein the global lock is associated with the entire critical area of the operating system and prevents any other threads from accessing the critical area while the global lock is applied to the critical area for the first thread;

receiving a second operating system call from a second thread that requires access to the non-critical area of the operating system;

granting the second thread access to the non-critical area of the operating system;

executing the first thread concurrently with the second thread; and

releasing the global lock upon completing the kernel call portion of the first operating system call.

16. The non-transitory machine-readable medium of claim 15, wherein the step of executing comprises executing the first thread on a first processor of the one or more processors concurrently with execution of the second thread on a second processor of the one or more processors.

17. The non-transitory machine-readable medium of claim 15, wherein the software is executable by the processor to cause the processor to perform the steps of:

receiving an operating system call from a third thread that requires access to the critical area of the operating system; and

blocking the third thread from accessing the critical area of the operating system while the global lock is reserved for the first thread.

18. The non-transitory machine-readable medium of claim 15, wherein the second operating system call comprises a kernel call portion that requires access to the critical area of the operating system and an external call portion that requires access to the non-critical area of the operating system, wherein the software is executable by the processor to cause the processor to perform the step of:

managing the global lock of the operating system to prevent overlapping execution of the kernel call portion of the first operating system call and the kernel call portion of the second operating system call.

19. The non-transitory machine-readable medium of claim 18, wherein the software is executable by the processor to cause the processor to perform the step of allowing overlapping execution of the kernel call portion of the first operating system call and the external call portion of the second operating system call.

20. The non-transitory machine-readable medium of claim 18, wherein the software is executable by the processor to cause the processor to perform the step of allowing overlapping execution of the external call portion of the first operating system call and the kernel call portion of the second operating system call.

21. The non-transitory machine-readable medium of claim 15, where the operating system has a micro kernel architecture.

22. A method of symmetric multiprocessing in which one or more processors are connected with a first memory storing an operating system in a machine executable form, wherein the operating system comprises a critical area and a non-critical area, the method comprising the steps of:

responding to a first thread requiring a first operating system call to the critical area of the operating system by requesting a global lock of the operating system for the first thread, wherein the global lock is associated with the entire critical area of the operating system and prevents any other threads from accessing the critical area while the global lock is applied to the critical area for the first thread;

responding to the global lock being available by performing the steps of;

acquiring the global lock for the first thread to access the critical area of the operating system without locking the non-critical area of the operating system;

performing the first operating system call to the critical area of the operating system,

receiving a second operating system call from a second thread that requires access to the non-critical area of the operating system;

granting the second thread access to the non-critical area of the operating system;

executing the first thread concurrently with the second thread; and

releasing the global lock.

23. The method of claim 22, wherein the first operating system call comprises a kernel call portion that requires access to the critical area of the operating system and an external call portion that requires access to the non-critical area of the operating system;

wherein the step of acquiring the global lock comprises the step of acquiring the global lock for the first thread to access the critical area of the operating system for the kernel call portion of the first operating system call; and

wherein the step of releasing the global lock comprises the step of releasing the global lock upon completing the kernel call portion of the first operating system call.

24. The method of claim 22, where the operating system has a micro kernel architecture.