Đồng bộ hóa chuỗi được triển khai như thế nào, ở cấp độ ngôn ngữ lắp ráp?

Question

Trong khi tôi quen thuộc với các khái niệm lập trình đồng thời như mutexes và semaphores, tôi chưa bao giờ hiểu cách chúng được triển khai ở cấp độ ngôn ngữ assembly.

Tôi tưởng tượng có là một tập hợp các bộ nhớ "cờ" nói:

• khóa A được tổ chức bởi thread 1
• khóa B được tổ chức bởi thread 3
• khóa C không được tổ chức bởi bất kỳ chủ đề
• vv

Nhưng cách truy cập vào các cờ này được đồng bộ hóa giữa các chuỗi? Một cái gì đó giống như ví dụ ngây thơ này sẽ chỉ tạo ra một tình trạng chủng tộc:

mov edx, [myThreadId] 
wait: 
    cmp [lock], 0 
    jne wait 
    mov [lock], edx 
    ; I wanted an exclusive lock but the above 
    ; three instructions are not an atomic operation :(

Answer 1

• Trên thực tế, những xu hướng được thực hiện với CAS và LL/SC. (... và một số kéo sợi trước khi bỏ đoạn thời gian của sợi - thường bằng cách gọi vào một hàm hạt nhân chuyển đổi ngữ cảnh.)
• Nếu bạn chỉ cần một spinlock, wikipedia cung cấp cho bạn một ví dụ giao dịch CAS cho khóa có tiền tố xchg trên x86/x64. Vì vậy, theo nghĩa hẹp, CAS là không cần thiết để tạo ra một spinlock - nhưng vẫn cần một số loại nguyên tử. Trong trường hợp này, nó sử dụng một hoạt động nguyên tử có thể ghi một thanh ghi vào bộ nhớ và trả về các nội dung trước đó của khe nhớ đó trong một bước đơn . (Để làm rõ hơn một chút: tiền tố khóa khẳng định tín hiệu #LOCK để đảm bảo rằng CPU hiện tại có quyền truy cập độc quyền vào bộ nhớ.Đối với các CPU ngày nay, nó không nhất thiết được thực hiện theo cách này, nhưng hiệu quả là như nhau. bằng cách sử dụng xchg, chúng tôi đảm bảo rằng chúng tôi sẽ không được ưu tiên ở đâu đó giữa đọc và viết, vì hướng dẫn sẽ không bị gián đoạn một nửa vì vậy nếu chúng tôi có một khóa tưởng tượng khóa mov reg0, mem/lock mov mem, reg1 (mà chúng tôi không), điều đó sẽ không hoàn toàn giống nhau - nó có thể được ngăn chặn ngay giữa hai lần di chuyển.)
• Trên các kiến ​​trúc hiện tại, như được chỉ ra trong các ý kiến, bạn chủ yếu sử dụng nguyên tử nguyên tử của CPU và các giao thức mạch lạc được cung cấp bởi hệ thống con bộ nhớ.
• Vì lý do này, bạn không chỉ phải sử dụng những nguyên thủy này, mà còn phải tính đến sự kết hợp bộ nhớ cache/bộ nhớ được bảo đảm bởi kiến ​​trúc.
• Có thể có các sắc thái thực hiện. Xem xét ví dụ một spinlock:
  • thay vì triển khai ngây thơ, có lẽ bạn nên sử dụng ví dụ: một TTAS spin-lock with some exponential backoff,
  • trên một CPU Hyper-Threaded, có lẽ bạn nên hành pause hướng dẫn đóng vai trò như gợi ý rằng bạn đang quay - vì vậy mà cốt lõi bạn đang chạy trên có thể làm điều gì đó hữu ích trong thời gian này
  • bạn nên thực sự cung cấp cho lên trên quay và mang lại quyền kiểm soát để đề khác sau một thời gian
  • vv ...
• đây vẫn là chế độ người dùng - nếu bạn đang viết một hạt nhân, bạn có thể có một số công cụ khác mà bạn có thể sử dụng cũng (vì bạn là người lập lịch trình và xử lý/cho phép/vô hiệu hóa ngắt).

Answer 2

Kiến trúc x86, từ lâu đã có hướng dẫn gọi là xchg sẽ trao đổi nội dung của sổ đăng ký với vị trí bộ nhớ. xchg luôn luôn là nguyên tử.

Luôn có tiền tố lock có thể được áp dụng cho bất kỳ một hướng dẫn duy nhất để thực hiện lệnh đó nguyên tử. Trước khi có nhiều hệ thống bộ vi xử lý, tất cả điều này thực sự là ngăn chặn việc gián đoạn được truyền tải ở giữa lệnh bị khóa. (xchg bị khóa hoàn toàn).

Bài viết này có một số mẫu mã sử dụng xchg để thực hiện một spinlock http://en.wikipedia.org/wiki/Spinlock

Khi đa hệ thống cốt lõi sau đa CPU và bắt đầu được xây dựng, hệ thống phức tạp hơn là cần thiết để đảm bảo khóa đó và xchg sẽ đồng bộ hóa tất cả các các hệ thống con bộ nhớ, bao gồm cả cache l1 trên tất cả các bộ vi xử lý. Khoảng thời gian này, nghiên cứu mới về các thuật toán khóa và khóa cho thấy CompareAndSet nguyên tử là một nguyên thủy linh hoạt hơn, vì vậy nhiều CPU hiện đại hơn có một hướng dẫn.

Hợp đồng bổ sung: Trong các ý kiến ​​andras cung cấp danh sách hướng dẫn "cũ bụi" cho phép tiền tố lock. http://pdos.csail.mit.edu/6.828/2007/readings/i386/LOCK.htm

Answer 3

Tôi thích nghĩ về đồng bộ hóa thread như từ dưới lên nơi xử lý và hệ điều hành cung cấp cấu trúc đó là nguyên thủy đến phức tạp hơn

Ở cấp vi xử lý bạn có CAS và LL/SC cho phép bạn thực hiện một kiểm tra và lưu trữ trong một hoạt động nguyên tử duy nhất ... bạn cũng có các cấu trúc bộ xử lý khác cho phép bạn tắt và bật ngắt (tuy nhiên chúng được xem là nguy hiểm ... trong một số trường hợp bạn không có tùy chọn nào khác ngoài sử dụng chúng)

hệ điều hành cung cấp khả năng chuyển đổi ngữ cảnh giữa các tác vụ có thể xảy ra mỗi khi một luồng đã sử dụng lát thời gian của nó ... hoặc nó có thể xảy ra do các lý do otgher (tôi sẽ đến đó)

sau đó có cấu trúc mức cao hơn như mutexes sử dụng các cơ chế nguyên thủy được cung cấp bởi bộ vi xử lý (nghĩ spinex ...) sẽ liên tục chờ điều kiện để trở thành hiện thực và kiểm tra điều kiện nguyên tử

sau đó những mutex quay có thể sử dụng các chức năng được cung cấp bởi hệ điều hành (switch bối cảnh và hệ thống gọi như năng suất mà tuyên bố từ bỏ quyền kiểm soát để thread khác) và cho chúng ta mutexes

các cấu trúc được tiếp tục sử dụng bởi các cấu trúc mức cao hơn như các biến điều kiện (có thể theo dõi số lượng chuỗi đang đợi mutex và đó thread để cho phép đầu tiên khi mutex trở nên có sẵn)

Những cấu trúc hơn có thể được tiếp tục sử dụng để cung cấp đồng bộ phức tạp hơn xây dựng ... Ví dụ: Cột vv