Линеаризуемость

Линеаризу́емость (англ. linearizability) — свойство программной системы, при котором результат любого параллельного выполнения (операций) эквивалентен некоторому последовательному выполнению. Для любого другого потока выполнение линеаризуемой операции является мгновенным: операция либо не начата, либо завершена. Применяется как в многопоточном программировании, так и в распределённых системах.

Как было показано[1], линеаризуемость является локальным и неблокируемым свойством. Локальность означает, что если доказана линеаризуемость операций для нескольких программ в отдельности (или для операций работающих с разными объектами одной программы), то программы вместе (операции вместе) также будут линеаризуемы. В линеаризуемой программе запущенные операции не требуют для своего завершения запуска других операций. Это свойство неблокируемости. Кроме того, линеаризуемость упрощает доказательство свойств программ, которые используют линеаризуемые операции, так как поведение линеаризуемой программы сводится к последовательным выполнениям.

Свойство линеаризуемости во многом сходно с такими свойствами как сериализуемость (англ. serializability), атомарность, последовательная согласованность (англ. sequential consistency). В отличие от них, линеаризуемость предполагает наличие спецификации, тогда как эти свойства накладывают ограничения только на саму программу. В некоторых источниках термин атомарность используется как синоним линеаризуемости, в других же означает самолинеаризуемость.

Часто под неформальным понятием потоковой безопасности (англ. thread-safety) понимают именно линеаризуемость.

Понятие линеаризуемости впервые появилось в статье Херлихи и Винг[англ.] 1987 года[2] как модель согласованности для систем с объектной организацией общей памяти. В отличие от всех остальных систем, здесь программы не могут напрямую использовать общие переменные, а только через специальные функции-методы (операции). Для этих систем линеаризуемость совпадает со строгой согласованностью.

Задача проверки линеаризуемости — это частный случай задачи функционального тестирования, в которой проверяется, удовлетворяет ли программа функциональным требованиям к ней, заданным в виде спецификации. Но в отличие от общего случая, здесь спецификация требуется только для последовательных выполнений.

Примечания

  1. ↑ Linearizability: a correctness condition for concurrent objects
  2. ↑ Axioms for concurrent objects. Дата обращения: 2 августа 2022. Архивировано 9 ноября 2022 года.

Ссылки

  • M. Herlihy и J. Wing, «Axioms for Concurrent Objects», Труды 14-го ACM SIGACT-SIGPLAN симпозиума по Принципам языков программирования (Январь 1987), стр. 13-26 [1].
  • M. Herlihy, «A methodology for implementing highly concurrent data structures», Труды ACM SIGPLAN симпозиума по Принципам и практике параллельного программирования, 1990, стр. 197—206 [2].
  • M. Herlihy и J. Wing «Linearizability: a correctness condition for concurrent objects», Труды ACM по Языкам программирования и системам, 1990, стр. 463—492 [3].

Read other articles:

Manouel I Komnenos

Manouel I Komnenos Untuk anak tertua dari Andronikos I Komnenos dan ayah dari Alexios I of Trebizond, lihat Manuel Komnenos (lahir 1145). Manouel I Komnenos, atau Comnenus, Manouēl I Komnēnos, 28 November 1118 – 24 September 1180) adalah kaisar dari kekaisaran Bizantium pada abad ke-12 yang memerintah atas sebuah poin balik yang penting dalam sejarah Bizantium. Untuk mengembalikan kekaisaran Bizantium kedalam kejayaannya dulu, Manuel membuat kebijakan luar negeri yang ambisius. Untuk itu,...

 

Carnival Games

2007 video game For the games at a carnival, see Carnival game. 2007 video gameCarnival GamesNorth American Wii box artDeveloper(s)Cat Daddy GamesPublisher(s)Global Star Software (Wii)2K (DS, iPhone)Platform(s)Wii, Nintendo DS, iOS (iPhone)ReleaseWiiNA: August 27, 2007AU: October 19, 2007EU: October 26, 2007DSNA: July 8, 2008EU: August 22, 2008AU: September 4, 2008iPhoneAugust 5, 2010Genre(s)PartyMode(s)Single-player, multiplayer Carnival Games (known in Europe and Australia as Carnival Funfa...

 

منطقة لاندسهوت

منطقة لاندسهوت  علم شعار الاسم الرسمي (بالألمانية: Landkreis Landshut)‏(بالألمانية: Bezirksamt Landshut)‏    الإحداثيات 48°34′N 12°12′E / 48.56°N 12.2°E / 48.56; 12.2   [1] تاريخ التأسيس 1 يوليو 1862  تقسيم إداري  البلد ألمانيا[2]  التقسيم الأعلى بافاريا السفلى  العاص...

Синелобый амазон

Синелобый амазон Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:ЗавропсидыКласс:Пт�...

 

Kumkum – Ek Pyara Sa Bandhan

Indian drama television series Kumkum – Ek Pyara Sa BandhanGenreSoap operaWritten byMayah BasleJayesh Patil Harsha JagdishRadheshyam RaiShobhit JaiswalBinita DesaiMahesh PandeyS FarhanBarry DhillonR M JoshiMitesh ShahKapil Bavad Virendra ShahaneyFaizal AkhtarAnshuman SinhaGayatri GillVed Raj Koel Chaudhuri Ranu UniyalDirected byAashish PatilAnil V. KumarArvind BabbalManchan VikalParesh Patil Swapnil ShahaneySanjay Upadhyay[1]StarringJuhi ParmarHussain KuwajerwalaAniket BhandariOpeni...

 

Kan (tribe)

Indo-Aryan Muslim communityKanকানখলিফাRegions with significant populations Bangladesh (Faridpur District) West Bengal (Malda division, Presidency division)LanguagesSouth Bangali or Rarhi (native)Standard Bengali (mostly spoken as an L2)ReligionSunni IslamRelated ethnic groupsBengalis, Domba Islam in Bangladesh History Muslim conquest Islamic rule Bengal Sultanate Bengal Subah Anjuman-i-Ulama-i-Bangala Culture Architecture Bangladeshi Bengali Indo-Islamic Indo-Saracenic Mu...

大字 (数字)

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています（詳細）。 数字の大字（だいじ）は、漢数字の一種。通常用いる単純な字形の漢数字（小字）の代わりに同じ音の別の漢字を用いるものである。 概要 壱万円日本銀行券（「壱」が大字） 弐千円日本銀行券（「弐」が大字） 漢数字には「一」「二」「三」と続く小字と、「壱」「�...

 

Новотитаровское сельское поселение

Сельское поселение России (МО 2-го уровня)Новотитаровское сельское поселение Флаг[d] Герб 45°14′09″ с. ш. 38°58′16″ в. д.HGЯO Страна  Россия Субъект РФ Краснодарский край Район Динской Включает 4 населённых пункта Адм. центр Новотитаровская Глава сельского пос�...

 

Port of Aarhus

Port in DenmarkPort of AarhusContainer Terminal, Port of AarhusClick on the map for a fullscreen viewLocationCountryDenmarkLocationAarhusCoordinates56°55′48″N 10°08′04″E / 56.930°N 10.1344°E / 56.930; 10.1344DetailsOpened1845Operated byAarhus MunicipalityOwned byPublicType of harbourDeep-water seaportStatisticsAnnual cargo tonnage8.4 million (2017)Websitehttps://www.aarhushavn.dk/ The Port of Aarhus (Danish: Aarhus Havn) is a deep-sea port located in the ci...

Gugark

Pour l’article homonyme, voir Gougark. Gugark (hy) Գուգարք L'entrée de Gugark Administration Pays Arménie Région Lorri Maire Mandat Ashot Ashughyan (HHK)[1],[2] 2012-2016 Démographie Population 6 562 hab. (2008) Densité 304 hab./km2 Géographie Coordonnées 40° 48′ 26″ nord, 44° 32′ 17″ est Superficie 2 158 ha = 21,58 km2 Fuseau horaire UTC+4 Localisation Géolocalisation sur la carte : Arméni...

 

2010 Arab League summit

Arab League 22nd summitArab League Summit EmblemHost countryLibyaDates27 March 2010 (2010-03-27)CitiesSirteFollows2009 Arab League summitPrecedes2011 Arab League summit The Arab League 22nd Summit was held in Sirte, Libya on 27 March 2010. Then-Italian prime minister Silvio Berlusconi spoke at the summit, stressing that Israel should return the Golan Heights to Syria.[1] Palestinian president Mahmoud Abbas rejected pressure from Syria and Libya to quit the peace process...

 

ميت السودان (الدقهلية)

ميت السودان  -  قرية مصرية -  تقسيم إداري البلد  مصر المحافظة محافظة الدقهلية المركز دكرنس المسؤولون السكان التعداد السكاني 4578 نسمة (إحصاء 2006) معلومات أخرى التوقيت ت ع م+02:00  تعديل مصدري - تعديل   قرية ميت السودان هي إحدى القرى التابعة لمركز دكرنس في محافظة ا�...

Alex Smith (golfer)

Scottish-American golfer For other people named Alex Smith, see Alex Smith (disambiguation). Alex SmithSmith, c. 1913Personal informationFull nameAlexander SmithBorn(1874-01-28)28 January 1874Dundee, Angus, ScotlandDied21 April 1930(1930-04-21) (aged 56)Baltimore, MarylandSporting nationality Scotland United StatesSpouseJessie MaidenChildren2CareerStatusProfessionalProfessional wins8Best results in major championships(wins: 2)Masters TournamentNYFPGA ChampionshipT9: 1916U.S. Op...

 

Sally of the Sawdust

Sally of the SawdustPosterSutradaraD. W. GriffithProduserD. W. GriffithDitulis olehForrest HalseyBerdasarkanPoppy olehDorothy DonnellyPemeranCarol DempsterW.C. FieldsAlfred LuntErville AldersonMarie ShotwellGlenn AndersSinematograferHarry Fischbeck Hal SintzenichPenyuntingRussell G. ShieldsPerusahaanproduksiParamount Pictures[1]DistributorUnited ArtistsTanggal rilis 02 Agustus 1925 (1925-08-02) Durasi104 menit[2]NegaraAmerika SerikatBahasaBisu (intertitel Inggris) Fi...

 

إنوسنت الرابع

إنوسنت الرابع (باللاتينية: Innocentius PP. IV)‏    معلومات شخصية الميلاد جنوة  الوفاة 7 ديسمبر 1254 [1]  نابولي  مواطنة جمهورية جنوة  مناصب كاهن كردينالي   في المنصب18 سبتمبر 1227  – 25 يونيو 1243  بابا الفاتيكان[2] (180 )   في المنصب25 يونيو 1243  – 7 ديسمبر 1254&#...

Fidelis Leite Magalhães

Fidelis Leite MagalhãesMagalhães pada 2019 Presiden Dewan MenteriPetahanaMulai menjabat 29 Mei 2020 (2020-05-29)Perdana MenteriTaur Matan RuakPendahuluJabatan dibentukPenggantiPetahanaMenteri Reformasi Legislatif dan Urusan ParlementerMasa jabatan22 Juni 2018 (2018-06-22) – 29 Mei 2020 (2020-5-29)Perdana MenteriTaur Matan RuakPenggantiJabatan ditiadakanAnggota Parlemen NasionalMasa jabatan2017–2018Kepala Staf untuk PresidenMasa jabatan20 Mei 2012 (2012-0...

 

沙莱 (米纳斯吉拉斯州)

沙莱Chalé市镇沙莱在巴西的位置坐标：20°02′38″S 41°41′16″W / 20.0439°S 41.6878°W / -20.0439; -41.6878国家巴西州米纳斯吉拉斯州面积 • 总计212.513 平方公里（82.052 平方英里）人口 • 總計5,465人 • 密度25.7人/平方公里（66.6人/平方英里） 沙莱（葡萄牙语：Chalé）是巴西米纳斯吉拉斯州的一个市镇。总面积212.513平方公里，总人口5465...

 

Hamza bin Laden

Hamzah bin Usamah bin Muhammad bin Awad bin LadinPenilaian Ancaman Terorisme 2018Lahir1989Jeddah, Arab SaudiMeninggal2019 (umur 29–30)[1]Orang tuaUsamah bin Ladin (bapak)Karier militerPengabdianAl-QaedaJama'at Ansar al-Furqan di Bilad asy-Syam (Dikabarkan sejak 2017) [2]Lama dinas2010–2019Perang/pertempuranPerang Melawan Teror: Perang di Afganistan Perang di Pakistan Barat Daya Perang Saudara Suriah Hamzah bin Usamah bin Muhammad bin Awad bin Ladin (bahasa Arab: ...

Mariano Rumor

Mariano Rumor Presidente del Consiglio dei ministri della Repubblica ItalianaDurata mandato13 dicembre 1968 –6 agosto 1970 Capo di StatoGiuseppe Saragat Vice presidenteFrancesco De MartinoPaolo Emilio Taviani PredecessoreGiovanni Leone SuccessoreEmilio Colombo Durata mandato8 luglio 1973 –23 novembre 1974 Capo di StatoGiovanni Leone PredecessoreGiulio Andreotti SuccessoreAldo Moro Ministro degli affari esteriDurata mandato23 novembre 1974 –...

 

Order of Friars Minor Capuchin

Religious order of Franciscan friars Order of Friars Minor CapuchinOrdo Fratrum Minorum Capuccinorum[1] (Latin)Common Capuchin logoFormationFounded: 1209 by St. Francis of Assisi and until the reformation aimed at regaining the original spirit of St. Francis and the Original Habit of St. Francis remained as the part of main branches. Capuchin Reformation started in 1525.[1]FounderSt. Francis of Assisi Reformed as Capuchins by Matteo SerafiniTypeMendicant Order of Pontifical Ri...