2022级硕士新生每周作业提交.zip

共313个文件

cpp：105个

h：103个

go：36个

项目

需积分: 1 18 浏览量 2024-10-06 20:14:24 上传评论收藏 8.58MB ZIP 举报

资源推荐

资源详情

资源评论

收起资源包目录

2022级硕士新生每周作业提交.zip2022级硕士新生每周作业提交.zip （313个子文件）

buffer pool 4KB

xxhash.c 2KB

consistent_hashing.cc 7KB

test.cc 1KB

b_plus_tree.cpp 34KB

extendible_hash_table.cpp 18KB

extendible_hash_table.cpp 16KB

extendible_hash_table.cpp 12KB

b_plus_tree_internal_page.cpp 12KB

lock_manager.cpp 11KB

buffer_pool_manager_instance.cpp 11KB

hash_table_bucket_page.cpp 9KB

b_plus_tree_leaf_page.cpp 9KB

buffer_pool_manager_instance.cpp 9KB

buffer_pool_manager_instance.cpp 8KB

hash_table_bucket_page.cpp 8KB

ConsistentHash.cpp 7KB

hash_table_directory_page.cpp 7KB

lock_manager.cpp 6KB

hash_table_bucket_page.cpp 6KB

lock_manager.cpp 6KB

hash_table_directory_page.cpp 6KB

buffer_pool_manager.cpp 6KB

hash_table_bucket_page.cpp 6KB

hash_table_directory_page.cpp 5KB

executor_factory.cpp 5KB

lock_manager.cpp 5KB

ConsistentHash.cpp 4KB

hash_table_header_page.cpp 4KB

parallel_buffer_pool_manager.cpp 4KB

buffer_pool_manager_instance.cpp 4KB

executor_factory.cpp 4KB

parallel_buffer_pool_manager.cpp 4KB

transaction_manager.cpp 4KB

parallel_buffer_pool_manager.cpp 4KB

transaction_manager.cpp 4KB

update_executor.cpp 4KB

nested_loop_join_executor.cpp 4KB

parallel_buffer_pool_manager.cpp 4KB

insert_executor.cpp 3KB

update_executor.cpp 3KB

consistent_hash_map.cpp 3KB

update_executor.cpp 3KB

nested_loop_join_executor.cpp 3KB

delete_executor.cpp 3KB

seq_scan_executor.cpp 3KB

insert_executor.cpp 3KB

hash_join_executor.cpp 3KB

seq_scan_executor.cpp 2KB

update_executor.cpp 2KB

insert_executor.cpp 2KB

nested_index_join_executor.cpp 2KB

update_executor.cpp 2KB

nested_loop_join_executor.cpp 2KB

delete_executor.cpp 2KB

index_iterator.cpp 2KB

b_plus_tree_index.cpp 2KB

seq_scan_executor.cpp 2KB

insert_executor.cpp 2KB

nested_loop_join_executor.cpp 2KB

aggregation_executor.cpp 2KB

hash_join_executor.cpp 2KB

aggregation_executor.cpp 2KB

lru_replacer.cpp 2KB

hash_join_executor.cpp 2KB

aggregation_executor.cpp 2KB

lru_replacer.cpp 2KB

update_executor.cpp 2KB

seq_scan_executor.cpp 2KB

b_plus_tree_page.cpp 2KB

lru_replacer.cpp 2KB

insert_executor.cpp 2KB

delete_executor.cpp 2KB

index_scan_executor.cpp 2KB

lru_replacer.cpp 2KB

delete_executor.cpp 2KB

seq_scan_executor.cpp 2KB

delete_executor.cpp 2KB

distinct_executor.cpp 1KB

lru_replacer.cpp 1KB

共 313 条

CARNEGIE MELLON UNIVERSITY

COMPUTER SCIENCE DEPARTMENT

15-445/645 – DATABA S E SYSTEMS (FALL 2021)

PRO F.LIN MAANDANDREW CROT TY

Homework #4 (by Sophie Qiu)

Due: Wednesday Nov 10, 2021 @ 11:59pm

IMPORTANT:

• Upload this PDF with your answers to Gradescope by 11:59pm on Wednesday Nov 10,

2021.

• Plagiarism: Homework may be discussed with other students, but all homework is to be

completed individually.

• You have to use this PDF for all of your answers.

For your information:

• Graded out of 100 points; 4 questions total

• Rough time estimate: ⇡ 1 - 2 hours (0.5 - 1 hours for each question)

Revisio n : 2021/11/09 01:21

Question Points Score

Serializability and 2PL 18

Deadlock Detection and Prevention 42

Hierarchical Locking 20

Optimistic Concurrency Control 20

Total: 100

15-445/645 (Fall 2021) Homework #4 Page 2 of 12

Question 1: Serializability and 2PL. . . . . . . . . . . . . . . . . . . . . . . . . . . .[18 points]

(a) Yes/No questions:

i. [2 points] A conﬂict serializable schedule need not always be view serializable.

2 Yes 2 No

ii. [2 points] There could be schedules under 2PL (not rigorous) that are not serializ-

able.

2 Yes 2 No

iii. [2 points] A view serializable schedule may contain a cycle in its precedence graph.

2 Yes 2 No

iv . [2 points] It is not possible to have a deadlock in rigorous 2PL.

2 Yes 2 No

v. [2 points] You will never have unrepeatable reads in rigorous 2PL.

2 Yes 2 No

(b) Serializability:

Consider the schedule given below in Table 1. R(·) and W(·) stand for ‘Read’ and ‘Write’,

respectively.

time t

R(A) R(C) R(B) W(C)

R(C) W(D) W(E)

W(A) R(D)

R(E) W(B)

Table 1: A schedule with 4 transactions

i. [1 point] Is this schedule serial?

2 Yes 2 No

ii. [2 points] Choose the correct dependency graph of the schedule given above. Each

edge in the dependency graph looks like this: ‘T

! T

with Z on the arrow indicat-

ing that there is a conﬂict on Z where T

read/wrote on Z before T

’.

2 A) 2 B)

Question 1 continues. . .

事务

ˇˇ

有

环

15-445/645 (Fall 2021) Homework #4 Page 3 of 12

2 C) 2 D)

iii. [1 point] Is this schedule conﬂict serializable?

2 Yes 2 No

iv . [3 points] Mark all the transactions that can be removed from the schedule that can

make it serializable.

2 T1 2 T2 2 T3 2 T4 2 Original schedule is also

serializable

v. [1 point] Is this schedule possible under 2PL?

2 Yes 2 No

Homework #4 continues. . .

ˇǒ

15-445/645 (Fall 2021) Homework #4 Page 4 of 12

Question 2: Deadlock Detection and Prevention . . . . . . . . . . . . . . . . [42 points]

(a) Deadlock Detection:

Consider the following two transactions and note that

• S(·) and X(·) stand for ‘shared lock’ and ‘exclusive lock’, respectively.

• T

and T

represent two transactions.

• LM stands for ‘lock manager’.

• Transactions will never release a granted lock.

: (a) read(A); (b) read(B); (c) write(B);

: (d) write(A); (e) read(B); (f) read(A);

i. For each position, what lock should be requested:

↵) [1 point] At (a): 2 S(A) 2 S(B) 2 X(A) 2 X(B) 2 No lock

needs to be requested

) [1 point] At (b): 2 S(A) 2 S(B) 2 X(A) 2 X(B) 2 No lock

needs to be requested

) [1 point] At (c): 2 S(A) 2 S(B) 2 X(A) 2 X(B) 2 No lock

needs to be requested

) [1 point] At (d): 2 S(A) 2 S(B) 2 X(A) 2 X(B) 2 No lock

needs to be requested

✏) [1 point] At (e): 2 S(A) 2 S(B) 2 X(A) 2 X(B) 2 No lock

needs to be requested

⇣) [1 point] At (f): 2 S(A) 2 S(B) 2 X(A) 2 X(B) 2 No lock

needs to be requested

ii. [4 points] Which of the following schedule can cause a deadlock?

(b) Consider the following lock requests in Table 2. And note that

• S(·) and X(·) stand for ‘shared lock’ and ‘exclusive lock’, respectively.

• T

, T

, and T

represent three transactions.

Question 2 continues. . .

事务

结束

时

才

会

放

锁

⼝

15-445/645 (Fall 2021) Homework #4 Page 5 of 12

• LM stands for ‘lock manager’.

• Transactions will never release a granted lock.

time t

S(C) S(B) X(B) S(A)

S(B) X(C)

X(A)

LM g

Table 2: Lock requests of three transactions

i. For the lock requests in Table 2, determine which lock will be granted or blocked

by the lock manager. Please write ‘g’ in the LM row to indicate the lock is granted

and ‘b’ to indicate the lock is blocked or the transaction has already been blocked by

a former lock request. For example, in the table, the ﬁrst lock (S(A) at time t

) is

marked as granted.

↵) [1 point] At t

: 2 g 2 b

) [1 point] At t

: 2 g 2 b

) [1 point] At t

: 2 g 2 b

) [1 point] At t

: 2 g 2 b

✏) [1 point] At t

: 2 g 2 b

⇣) [1 point] At t

: 2 g 2 b

ii. [2 points] Mark the correct wait-for graph for the lock requests in Table 2. Each

edge in the wait-for graph looks like this: T

! T

because of Z. Z is denoted in

the arrow in the ﬁgure. (i.e., T

is waiting for T

to release its lock on resource Z).

2 (A)

2 (B)

Question 2 continues. . .

评论收藏

内容反馈

嵌入式大圣

粉丝: 4800
资源: 792

2022级硕士新生每周作业提交.zip

作业本.zip作业本.zip作业本.zip作业本.zip

Python爬虫作业代码.zip

2021-2022数学建模项目试题及介绍.zip

数据结构课程大作业收集.zip数据结构课程大作业收集.zip

系统Java项目大作业源码.zip

网页设计作业网页设计大作业合集.zip

哈尔滨工程大学本科、硕士、博士论文模板.zip

基本遗传算法MATLAB程序源码(作业).zip

数据挖掘课程作业.zip数据挖掘课程作业.zip

基于python的hellokitty原码(课程作业).zip

作业，就R语言的作业.zip作业，就R语言的作业.zip

基于Python PyQt5实现的音频播放器源码（期末大作业）.zip

基于zeek的网络入侵检测项目源码(课程作业).zip

网页设计期末大作业.zip

仿小红书前端设计的网页源码(网页设计作业).zip

基于吴恩达深度学习的图像分类识别作业源码.zip

基于vue前端+springboot后端的考勤系统大作业（研究生java大作业）.zip

Java的作业拼图游戏.zip

产品经理相关文档、作业.zip产品经理相关文档、作业.zip

基于SpringBoot的活动管理平台源码(课程期末大作业).zip

大学计算机类程序设计作业.zip

基于亚博K210的人脸识别项目源码（高分期末大作业）.zip

网页设计期末 大作业.zip

操作系统课程设计：基于C++&QT可视化模拟操作系统作业调度.zip

高级计算机网络第二次作业实验室.zip

基于Vue的机票预定信息管理系统（课程作业）.zip

安卓开发大作业-代码.zip

学校web程序设计的平时作业和大作业.zip

最新资源

网页设计期末大作业.zip